javascript third order magic cube
- 2020-06-01 08:16:35
- OfStack
Puzzle: magic cube 3, try to fill a 3 by 3 table with 9 different integers, 1 to 9, so that the sum of the Numbers in each row, column, and diagonal is the same.
Strategy: exhaustive search. List all integer fill schemes and filter them.
The highlight is the design of the recursive function getPermutation. At last, several non-recursive algorithms are given
// Recursive algorithm, very clever, but too expensive resources
function getPermutation(arr) {
if (arr.length == 1) {
return [arr];
}
var permutation = [];
for (var i = 0; i < arr.length; i++) {
var firstEle = arr[i]; // Take the first 1 An element
var arrClone = arr.slice(0); // Copy the array
arrClone.splice(i, 1); // Delete the first 1 Element, reduce the array size
var childPermutation = getPermutation(arrClone);// recursive
for (var j = 0; j < childPermutation.length; j++) {
childPermutation[j].unshift(firstEle); // Insert the fetched element back in
}
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');
}
// Modular (non recursive) full - permutation algorithm
/*
A concrete example of the algorithm:
* o 4 An element ["a", "b", "c", "d"] The whole arrangement , Total cycle 4!=24 Times can be arbitrary from >=0 The integer index Start the cycle and add each time 1 Until the cycle is over index+23 After the end;
* Assuming that index=13 (or 13+24 . 13+224 . 13+3*24 ...). Because, 4 , so iteration 4 Second, you get this 1 The permutation process is as follows:
* The first 1 Iterations, 13/1 , =13 The remainder =0 , so the first 1 Insert the first element 0 (that is, the subscript is 0 ), ["a"] ;
* The first 2 Iterations, 13/2, shang =6 The remainder =1 , so the first 2 Insert the first element 1 (that is, the subscript is 1 ), ["a", "b"] ;
* The first 3 Iterations, 6/3, shang =2 The remainder =0 , so the first 3 Insert the first element 0 (that is, the subscript is 0 ), ["c", "a", "b"] ;
* The first 4 Iterations, 2/4 , =0 The remainder =2, Therefore, the first 4 Insert the first element 2 (that is, the subscript is 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++) // Calculate the number of permutations according to the length of the array
fac *= i;
for (var index = 0; index < fac; index++) { // every 1 a index The corresponding 1 A permutation
var t = index;
for (i = 1; i <= arr.length; i++) { // Determine the position of each number
var w = t % i;
for (var j = i - 1; j > w; j--) // Shift, result[w] space
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]);
// Very clever backtracking algorithm, non-recursive solution to all permutations
function seek(index, n) {
var flag = false, m = n; //flag To find the placement of the signs, m Save which location you are searching for, index[n] Encoding elements (position)
do {
index[n]++; // Sets the current location element
if (index[n] == index.length) // No space available
index[n--] = -1; // Reset the current position and back up 1 A position
else if (!(function () {
for (var i = 0; i < n; i++) // Determines if the current location setting conflicts with the previous location
if (index[i] == index[n]) return true;// Conflict, go back to the front of the loop and reset the element value
return false; // No conflict, see if the current location is the end of the queue, yes, find 1 An arrangement; No, the current position moves back
})()) // The location was not selected
if (m == n) // The current location search is complete
flag = true;
else
n++; // The current and previous position elements have been arranged and moved back
} 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); // Initialized to 1,2,3,...,-1 And the last 1 An element of -1 ; Note that from small to large, if the element is not a number, can be understood as its position subscript
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]);
/*
Full permutation (non - recursive order) algorithm
1. Set up a position array, that is, arrange the positions, and convert it into the arrangement of elements after the successful arrangement;
2. Complete the arrangement according to the following algorithm:
Let P be a full permutation of 1 ~ n(position number) : p = p1,p2... pn = p1 p2... pj, pj pj - 1, + 1... pk, pk pk - 1, + 1... pn
(1) starting from the tail of the array, find the first index j (j is calculated from the head) which is less numbered than the position on the right, that is, j = max{i | pi
<
pi+1}
(2) in the position number to the right of pj, find the index k of the smallest position number of all position Numbers larger than pj, that is, k = max{i | pi
>
pj}
The position number to the right of pj increases from right to left, so k is the largest index of all position Numbers greater than pj
(3) exchange pj and pk
(4) then pj + 1... pk, pk pk - 1, + 1... p' = p1,p2... pj - 1, pj pn... pk + 1, pk pk - 1... pj + 1
(5)p' is the next permutation of p
Such as:
24310 is a permutation of position no. 0 ~ 4, and the next permutation is as follows:
(1) find the number 2 which is smaller than the number on the right from right to left;
(2) find the smallest 3 in the number after the number greater than 2;
(3) exchange 2 with 3 to get 34210;
(4) flip all the Numbers after the original 2 (current 3), i.e., flip 4210 to get 30124;
(5) the next order of 24310 is 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--)
; // This loop starts at the end of the position array and finds the first 1 Where the left hand side is less than the right hand side j
if (j < 0) return false; // All permutations have been completed
for (var k = index.length - 1; index[k] < index[j]; k--)
; // This loop starts at the end of the position array and finds the ratio j The smallest of the large positions, that is k
swap(index, j, k);
for (j = j + 1, k = index.length - 1; j < k; j++, k--)
swap(index, j, k); // Loop reversal j+1 All the way to the end
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]);
That's all for this article, I hope you enjoy it.