javascript解三次ファントム(九宮格)

パズル:三次ファントム、1~9の9つの異なる整数を一つの3つに書き入れてみます.×3の表は、行ごと、列ごと、および対角線ごとの数値の合計が同じになるようにします.
ストラテジスト:検索する.すべての整数塗りつぶしスキームを一覧表示し、フィルタリングします.
ハイライトは再帰関数get Permutationの設計であり、記事は最後にいくつかの非再帰的アルゴリズムを与えた.

//     ，   ，     
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=p 1,p 2…pn=p 1,p 2…p j-1,pj,pj＋1…pk,pk＋1…pn(1)は、配列の末尾から、最初の右の位置番号より小さいインデックスj(jは、ヘッダから計算する)である.pjより大きい位置番号の中で最小の位置番号のインデックスk、すなわちk=max｛i pi＞pj｝pj右の位置番号は右から左にインクリメントされているので、kはpjより大きい位置番号の中でインデックスが一番大きい(3)交換pjとpk(4)でpj＋1…pk-1、pk＋1、pk＋1、pk＋1、pk＋1p'はpの次の配列です.
例えば、24310は位置番号0〜4の一つの配列であり、その次の配列を求めるステップは以下の通りである.(2)この数字の後の数字の中から、2より大きい数の中で一番小さいのを見つけます.(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]);

以上述べましたが、本文の内容は全部です.お好きになってください.