javascript 해 3 단계 환 방 (구 궁 격)

수수께끼: 3 단계 환 방, 1 ~ 9 개의 서로 다른 정 수 를 3 개 에 채 워 보 세 요.×3. 표 는 줄, 열, 그리고 각 대각선 의 숫자 를 똑 같이 합 니 다.
정책: 검색 을 빈 거 합 니 다.모든 정수 충전 방안 을 열거 한 다음 여과 합 니 다.
하 이 라 이 트 는 재 귀 함수 getPermutation 의 디자인 이 고 글 은 마지막 으로 몇 가지 비 재 귀 알고리즘 을 제시 했다.

//     ，   ，     
function getPermutation(arr) {
  if (arr.length == 1) {
    return [arr];
  }
  var permutation = [];
  for (var i = 0; i < arr.length; i++) {
    var firstEle = arr[i];         //      
    var arrClone = arr.slice(0);      //    
    arrClone.splice(i, 1);         //       ，      
    var childPermutation = getPermutation(arrClone);//  
    for (var j = 0; j < childPermutation.length; j++) {
      childPermutation[j].unshift(firstEle);   //         
    }
    permutation = permutation.concat(childPermutation);
  }
  return permutation;
}

function validateCandidate(candidate) {
  var sum = candidate[0] + candidate[1] + candidate[2];
  for (var i = 0; i < 3; i++) {
    if (!(sumOfLine(candidate, i) == sum && sumOfColumn(candidate, i) == sum)) {
      return false;
    }
  }
  if (sumOfDiagonal(candidate, true) == sum && sumOfDiagonal(candidate, false) == sum) {
    return true;
  }
  return false;
}
function sumOfLine(candidate, line) {
  return candidate[line * 3] + candidate[line * 3 + 1] + candidate[line * 3 + 2];
}
function sumOfColumn(candidate, col) {
  return candidate[col] + candidate[col + 3] + candidate[col + 6];
}
function sumOfDiagonal(candidate, isForwardSlash) {
  return isForwardSlash ? candidate[2] + candidate[4] + candidate[6] : candidate[0] + candidate[4] + candidate[8];
}

var permutation = getPermutation([1, 2, 3, 4, 5, 6, 7, 8, 9]);
var candidate;
for (var i = 0; i < permutation.length; i++) {
  candidate = permutation[i];
  if (validateCandidate(candidate)) {
    break;
  } else {
    candidate = null;
  }
}
if (candidate) {
  console.log(candidate);
} else {
  console.log('No valid result found');
}

//  （   ）     

/*
       ：
* 4   ["a", "b", "c", "d"]    ,    4!=24 ，    >=0   index    ，    1，     index+23   ；
*  index=13（ 13+24，13+224，13+3*24…），   4   ，   4 ，             ：
* 1   ，13/1， =13，  =0，  1      0   （    0）， ["a"]；
* 2   ，13/2,  =6，  =1，  2      1   （    1）， ["a", "b"]；
* 3   ，6/3,  =2，  =0，  3      0   （    0）， ["c", "a", "b"]；
* 4   ，2/4， =0，  =2,   4      2   （    2）， ["c", "a", "d", "b"]；
*/

function perm(arr) {
  var result = new Array(arr.length);
  var fac = 1;
  for (var i = 2; i <= arr.length; i++)  //             
    fac *= i;
  for (var index = 0; index < fac; index++) { //   index      
    var t = index;
    for (i = 1; i <= arr.length; i++) {   //        
      var w = t % i;
      for (var j = i - 1; j > w; j--)   //  ， result[w]    
        result[j] = result[j - 1];
      result[w] = arr[i - 1];
      t = Math.floor(t / i);
    }
    if (validateCandidate(result)) {
      console.log(result);
      break;
    }
  }
}
perm([1, 2, 3, 4, 5, 6, 7, 8, 9]);
//        ，        

function seek(index, n) {
  var flag = false, m = n; //flag          ，m          ，index[n]   （    ）
  do {
    index[n]++;    //        
    if (index[n] == index.length) //      
      index[n--] = -1; //      ，        
    else if (!(function () {
        for (var i = 0; i < n; i++)  //                  
          if (index[i] == index[n]) return true;//  ，               
        return false;  //   ，           ， ，      ； ，      
      })()) //       
      if (m == n) //        
        flag = true;
      else
        n++;  //              ，    
  } while (!flag && n >= 0)
  return flag;
}
function perm(arr) {
  var index = new Array(arr.length);
  for (var i = 0; i < index.length; i++)
    index[i] = -1;
  for (i = 0; i < index.length - 1; i++)
    seek(index, i);  //    1,2,3,...,-1 ，       -1；        ，       ，          
  while (seek(index, index.length - 1)) {
    var temp = [];
    for (i = 0; i < index.length; i++)
      temp.push(arr[index[i]]);
    if (validateCandidate(temp)) {
      console.log(temp);
      break;
    }
  }
}
perm([1, 2, 3, 4, 5, 6, 7, 8, 9]);

/ * 전체 배열 (비 재 귀적 순서) 알고리즘 1. 위치 배열 을 만 듭 니 다. 즉, 위 치 를 배열 하고 배열 에 성공 한 후에 요소 의 배열 로 전환 합 니 다.2. 다음 알고리즘 에 따라 전체 배열 을 구 합 니 다. 설정 P 는 1 ~ n (위치 번호) 의 전체 배열 입 니 다. p = p1, p2. pn = p1, p2... pj - 1, pj, pj + 1... pk - 1, pk, pk + 1. pn (1) 은 배열 의 끝부분 부터 오른쪽 위치 번호 보다 작은 색인 j (j 는 첫 번 째 부터 계산), 즉 j = max {i | pi < pi + 1} (2) 를 찾 아 pj 의 오른쪽 위치 번호 에서pj 보다 큰 위치 번호 중 가장 작은 위치 번 호 를 찾 는 색인 k, 즉 k = max {i | pi > pj} pj 오른쪽 위치 번 호 는 오른쪽 에서 왼쪽 으로 점점 증가 하기 때문에 k 는 pj 보다 큰 위치 번호 중 색인 이 가장 큰 (3) pj 와 pk (4) 를 교환 하고 pj + 1... pk - 1, pk, pk + 1. pn 을 뒤 집어 배열 p '= p1, p2... pj - 1, pj, pn.. pk + 1, pk - 1. pj + 1 (5)p '는 바로 p 의 다음 배열 이다.
예 를 들 어 24310 은 위치 번호 0 ～ 4 의 배열 로 다음 배열 의 절 차 는 다음 과 같다. (1) 오른쪽 에서 왼쪽 까지 배열 에서 오른쪽 숫자 보다 작은 숫자 2 를 찾 아 라.(2) 이 숫자 뒤의 숫자 에서 2 보다 큰 숫자 중 가장 작은 3 을 찾아낸다.(3) 2 와 3 을 교환 하여 34210 얻 기;(4) 원래 2 (현재 3) 뒤의 모든 숫자 를 뒤 집 습 니 다. 즉, 4210 을 뒤 집 으 면 30124 가 됩 니 다.(5) 24310 을 구 한 다음 배열 은 30124 이다. * /

function swap(arr, i, j) {
  var t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;

}
function sort(index) {
  for (var j = index.length - 2; j >= 0 && index[j] > index[j + 1]; j--)
    ; //             ，              ， j
  if (j < 0) return false; //       
  for (var k = index.length - 1; index[k] < index[j]; k--)
    ; //             ，   j          ， k
  swap(index, j, k);
  for (j = j + 1, k = index.length - 1; j < k; j++, k--)
    swap(index, j, k); //     j+1        
  return true;
}
function perm(arr) {
  var index = new Array(arr.length);
  for (var i = 0; i < index.length; i++)
    index[i] = i;
  do {
    var temp = [];
    for (i = 0; i < index.length; i++)
      temp.push(arr[index[i]]);
    if (validateCandidate(temp)) {
      console.log(temp);
      break;
    }
  } while (sort(index));
}
perm([1, 2, 3, 4, 5, 6, 7, 8, 9]);

이상 에서 말 한 것 이 바로 본문의 전체 내용 이 니 여러분 들 이 좋아 하 시 기 를 바 랍 니 다.