여덟 여왕 문제에 대한 JavaScript 솔루션과 관련하여 항상 알고리즘을 배워야한다고 생각합니다. 언젠가 그것을 사용하는지 알아내는 것은 당황 스러울 것입니다.
배경
여덟 퀸즈 질문은 체스를 기반으로 한 질문입니다. 여왕이 다른 여왕을 직접 먹을 수 없도록 8 × 8 체스 보드에 8 여왕을 어떻게 배치 할 수 있습니까? 이를 달성하기 위해 여왕도 같은 수평, 수직 또는 대각선에있을 수 없습니다.
여덟 여왕 문제는 퀸 배치의보다 일반적인 문제로 일반화 될 수 있습니다. 현재 체스 판의 크기는 n × n이되고 퀸의 수는 n이됩니다. n = 1 또는 n ≥ 4 인 경우에만 문제에 대한 해결책이 있습니다.
블라인드 열거 알고리즘
n-fold 루프를 통해 제약 조건을 충족하는 솔루션 (8 배 루프 코드가 많이 있고 4 배 루프가 수행됩니다), 4 개의 퀸즈의 가능한 모든 위치를 찾은 다음 전체 보드 에서이 네 여왕이 서로 직접 먹을 지 여부를 판단하는 솔루션을 열거합니다. 프로그램 아이디어는 비교적 간단합니다.
함수 check1 (arr, n) {for (var i = 0; i <n; i ++) {for (var j = i+1; }}} return true;} function Queen1 () {var arr = []; for (arr [0] = 1; arr [0] <4; arr [0] ++) {for (arr [1] = 1; arr [1] <= 4; arr [1] ++) {for (arr [2] = 1; arr [2] <= 4; arr [2] ++) {for [3] = 1; arr [3] <= 4; 계속하다; } else {console.log (ARR); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}. }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}. }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}. }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}결과와 관련하여 4*4 체스 보드에서 4 개의 여왕은 연속 할 수 없습니다. ARR [0]에서 ARR [3]는 각각 4 개의 여왕에 해당합니다. 배열 및 첨자 첨자에 해당하는 값은 보드에서 여왕의 위치입니다.
역 추적 방법
"갈 수 없다면 돌아 서십시오." 해당 노드에서 일치하는지 여부를 결정하십시오. 일치하지 않으면 더 이상이 지점을 탐색하지 않습니다.
함수 check2 (arr, n) {for (var i = 0; i <= n -1; i ++) {if ((math.abs (arr [i] - arr [n]) == n -i) || (arr [i] == arr [n]) {return false; }} return true;} function Queen2 () {var arr = []; for (arr [0] = 1; arr [0] <= 4; arr [0] ++) {for (arr [1] = 1; arr [1] <= 4; arr [1] ++) {if (! check2 (arr, 1)) 계속; // (ARR [2] = 1; ARR [2] <= 4; ARR [2] ++) {if (! check2 (arr, 2)) 계속; // (ARR [3] = 1; ARR [3] <= 4; ARR [3] ++) {if (! check2 (arr, 3)) {계속; } else {console.log (ARR); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}. }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}. }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}. }}}}}}}}}}}}}}}비수체적인 역 추적
알고리즘 프레임 워크 :
(k> 0 0 목표에 도달하지 못하는 방법이 있습니다』』』) {// k> 0 {(k> n) {// 잎 노드 검색 // 솔루션 검색, 출력} else {// [k]는 검색 공간에있다 "). 검색 공간 ") {// 점유 된 자원을 표시하십시오 // k = k + 1; } else {// 점유 상태 공간을 정리 // k = k -1; }}}특정 코드는 다음과 같습니다. 가장 바깥 쪽 층은 두 부분을 포함합니다. 하나는 현재 여왕의 가능한 값의 횡단이고 다른 하나는 다음 레이어를 입력할지 또는 이전 레이어를 역 추적할지 결정하는 것입니다.
함수 백 데이트 (n) {var arr = []; var k = 1; // nth Queen Arr [0] = 1; while (k> 0) {arr [k-1] = arr [k-1] + 1; while ((arr [k-1] <= n) && (! check2 (arr, k-1))) {arr [k-1] = arr [k-1] + 1; } //이 여왕은 제약 조건을 충족시키고 다음 판단을한다. } else {k = k + 1; // 다음 퀸 arr [k-1] = 0; }} else {k = k -1; // BackTrack, Last Queen}}} BackDate (4); // [2, 4, 1, 3] // [3, 1, 4, 2]재귀 역 추적 방법
재귀 호출은 코드의 양을 크게 줄이고 프로그램의 가독성을 증가시킵니다.
var arr = [], n = 4; 함수 백 트랙 (k) {if (k> n) {console.log (arr); } else {for (var i = 1; i <= n; i ++) {arr [k-1] = i; if (check2 (arr, k-1)) {backtrack (k + 1); }}}}} backtrack (1); // [2, 4, 1, 3] // [3, 1, 4, 2]화려한 암석
AMB는 무엇입니까? 제약 조건의 성공 상황을 충족하는 방법을 반환 할 수있는 데이터 목록을 제공하십시오. 성공하지 않으면 실패 할 것입니다. 물론 모든 성공 상황을 반환 할 수 있습니다. 저자는이 AMB 알고리즘을 여기에서 추천하기 위해 위의 많은 포인트를 작성했습니다. 간단한 역 추적 시나리오를 처리하는 데 적합합니다. 매우 흥미 롭습니다. 그것이 어떻게 작동하는지 봅시다.
먼저 작은 문제를 다루고 인접한 문자열을 찾아 봅시다 : 여러 개의 문자열 배열 세트를 얻으면 각 배열이 문자열을 꺼냅니다. 이전 문자열의 마지막 문자는 다음 문자열의 첫 번째 문자와 동일합니다. 조건이 충족되면 새로 검색된 문자열이 출력됩니다.
ambrun (function (AMB, FAIL) {// 제약 메서드 함수 링크 (S1, S2) {return S1.Slice (-1) == S2.Slice (0, 1);} // 데이터 목록 var w1 = Amb ( "That", "A"]; Var W2 = [ "Frog" " "tread", "성장"); 느리게"});매우 간단한 것 같습니다! 그러나 사용의 전제는 성능에 관심이 없다는 것입니다. 실제로 시간 낭비입니다!
아래는 JavaScript 구현입니다. 관심이 있으시면 역 추적을 추출하는 방법을 연구 할 수 있습니다.
함수 ambrun (func) {var 선택 = []; var index; 함수 AMB (값) {if (values.length == 0) {실패 (); } if (index == choices.length) {choices.push ({i : 0, count : values.length}); } var 선택 = 선택 [index ++]; 반환 값 [선택 .i]; } function fail () {Throw FAIL; } while (true) {try {index = 0; 반환 func (AMB, FAIL); } catch (e) {if (e! = 실패) {Throw e; } var 선택; while ((choice = choices.pop ()) && ++ choice.i == choice.count) {} if (choice == undefined) {return undefined; } 선택 .push (선택); }}}AMB를 사용하여 구현 된 여덟 여왕 문제의 특정 코드
ambrun (function (Amb, fail) {var n = 4; var arr = []; var turn = []; for (var n = 0; n <n; n ++) {turn [turn.length] = n +1;} while (n-) {arr.length] = Amb (turn); var a = ar [j];여덟 여왕 문제에 대한 자바 스크립트 솔루션
이것은 여덟 여왕 문제에 대한 JavaScript 솔루션입니다. 전체 프로그램은 루프에 사용되지 않으며 재귀를 통해 구현됩니다. 배열 객체의 맵, 축소, 필터, 연결, 슬라이스 방법을 완전히 사용합니다.
'strict'; var Queens = function (bodersize) {// 재귀를 사용하여 시작부터 끝까지 배열 var 간격을 생성합니다 = function (start, end) {if (start> end) {return []; } 반환 간격 (시작, 끝 -1) .concat (끝); }; // 조합이 유효한 var isvalid = function (queencol)인지 확인 {// 두 위치 사이에 충돌이 있는지 확인하십시오. if ((0 === 경사) || (1 === 경사) || (-1 === 경사)) {return false; } true를 반환합니다. }; var len = queencol.length; var pointtocompare = {row : queencol [len -1], col : len}; // 먼저 마지막 열을 제외한 배열을 자른 다음 각 열의 포인트와 테스트 할 지점 사이에 충돌이 있는지 테스트하고 테스트 결과를 병합합니다. return queencol .slice (0, len -1) .map (function (row, index) {return issafe ({row : row, col : index + 1}, pointTocompare);}) .reduce (function (a, b) {return a && b;}); }; // 규칙에 따른 조합을 재귀 적으로 생성합니다. } // 먼저 규칙을 준수하는 모든 이전 열의 세트를 확장 한 다음 치수 감소 감소를 사용하고 마지막으로 IsValid를 사용하여 규칙을 준수하는 조합을 필터링하여 Queencol (size -1). .reduce (function (a, b) {return a.concat (b);}) .filter (isvalid); }; // Queens 기능 입력 return Queencols (Bodersize);}; console.log (Queens (8)); // 출력 결과 : // [[1, 5, 8, 6, 3, 7, 2, 4], // [1, 6, 8, 3, 7, 7, 4, 2, 5], // 6, 2, 7, 5]]추신 : 확장 n 퀸 문제
체스 플레이어 Max Bezzel이 1848 년에 8 명의 퀸즈 퍼즐을 물었을 때, 아마도 100 년이 지난 후에이 문제는 프로그래밍 학습에서 가장 중요한 강제 과정 중 하나가되었을 것입니다. 여덟 여왕 문제는 매우 간단하게 들립니다. 8 여왕이 8 여왕이 서로를 공격하지 않도록 체스 보드에 8 여왕을 넣습니다 (체스 보드는 8 × 8 제곱 어레이이며 여왕은 8 개의 방향으로 수평 및 수직으로 여러 단계를 밟을 수 있습니다). 이 문제에 대한 92 개의 솔루션이 있지만 맨손으로 하나의 솔루션을 찾는 것은 쉽지 않습니다. 다음 수치는 솔루션 중 하나입니다.
여덟 여왕 문제에는 많은 변형이 있지만, 아무리 어려운지에 관계없이 다음 변형보다 더 잘 생기지 않을 것입니다. 모든 줄에 여왕을 배치 할 계획을 설계하십시오. 구체적으로,이 보드의 왼쪽 하단 모서리가 원점에 있다고 가정하고, 왼쪽에서 오른쪽에서 오른쪽에서 오른쪽으로 무한 행이있는 무한 행 A1, A2, A3,… 두 번째 여왕을 두 번째 여왕을 배치하면 두 개의 퀸이 서로 공격하지 않도록해야합니다.
다음은 매우 간단하고 영리한 구조입니다. 먼저, 우리는 5 개의 퀸즈 문제에 대한 답변을 제공합니다. 그리고 매우 중요한 것은 여왕 중 하나가 왼쪽 하단의 그리드를 차지합니다.
다음으로, 우리는 5 개의 여왕의 솔루션을 25 여왕으로 확장하고 5 개의 여왕 자체의 레이아웃을 기반으로합니다.
결과적으로, 같은 그룹의 5 명의 여왕은 분명히 서로를 공격하지 않을 것이며, 다른 그룹의 여왕은 분명히 서로를 공격하지 않을 것입니다. 이것은 요구 사항을 충족하는 25 여왕 솔루션입니다. 확장 후 이전에 채워진 섹션은 변경되지 않았습니다.
다음에 무엇을해야합니까? 맞습니다. 우리는 25 여왕의 차단을 5 개 조각으로 복사하여 5 개의 여왕의 레이아웃에 따라 다시 배열하여 125 여왕으로 확장했습니다!
이와 같은 가득 찬 부품을 기반으로 바깥쪽으로 지속적으로 확장하면 무한한 여왕 문제에 대한 솔루션을 생성 할 수 있습니다.