JavaScript löst das magische Quadrat dritter Ordnung (Neunquadratgitter)_Javascript-Fähigkeiten

Rätsel: Magisches Quadrat dritter Ordnung Versuchen Sie, die 9 verschiedenen ganzen Zahlen von 1 bis 9 in eine 3×3-Tabelle einzutragen, sodass die Summe der Zahlen in jeder Zeile, Spalte und Diagonale gleich ist.

Strategie: Umfassende Suche. Listen Sie alle Integer-Padding-Szenarien auf und filtern Sie dann.

Das Highlight ist das Design der rekursiven Funktion getPermutation. Am Ende des Artikels werden mehrere nicht-rekursive Algorithmen vorgestellt

// 递归算法，很巧妙，但太费资源
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 &#63; 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]);

/*
Vollständiger Permutationsalgorithmus (nicht rekursive Reihenfolge)
1. Erstellen Sie ein Positionsarray, dh ordnen Sie die Positionen an. Nachdem die Anordnung erfolgreich war, wird sie in eine Anordnung von Elementen umgewandelt 2. Finden Sie die vollständige Anordnung nach folgendem Algorithmus:
Angenommen, P ist eine vollständige Anordnung von 1 bis n (Positionsnummern): p = p1,p2...pn = p1,p2...pj-1,pj,pj 1...pk-1,pk,pk 1 ...pn
(1) Suchen Sie vom Ende der Anordnung aus den ersten Index j, der kleiner als die rechte Positionsnummer ist (j wird von Anfang an berechnet), d. h. j = max{i | pi 1}
(2) Finden Sie unter den Positionsnummern rechts von pj den Index k der kleinsten Positionsnummer größer als pj, d. h. k = max{i | > Die Positionsnummern rechts von pj nehmen von rechts nach links zu, sodass k der größte Index unter allen Positionsnummern größer als pj
ist (3) Tauschen Sie pj und pk aus
(4) Drehen Sie dann pj 1...pk-1,pk,pk 1...pn um, um die Anordnung p' = p1,p2...pj-1,pj,pn...pk 1,pk, zu erhalten. pk -1...pj 1
(5) p' ist die nächste Permutation der Permutation p

Zum Beispiel:

24310 ist eine Permutation der Positionsnummern 0 bis 4. Die Schritte zum Finden der nächsten Permutation sind wie folgt:

(1) Finden Sie die erste Zahl 2 in der Anordnung, die von rechts nach links kleiner ist als die Zahl rechts; (2) Finden Sie unter den Zahlen nach der Zahl die kleinste Zahl 3, die größer als 2 ist (3) Tausche 2 und 3, um 34210 zu erhalten; (4) Drehen Sie alle Zahlen nach der ursprünglichen 2 (derzeit 3) um, d. h. 4210, um 30124 zu erhalten (5) Finden Sie die nächste Permutation von 24310 als 30124.
*/




Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, er gefällt Ihnen allen.