JavaScript implementation of N Queens problem algorithm puzzle solution_javascript skills

Puzzle

N Queen problem. Place N queens on an NxN chess board where no two queens are in the same row, column or diagonal so that they cannot attack each other.

Strategy

Backtracking method.

JavaScript Solution

Take the 8 Queens problem as an example:

Copy code The code is as follows:

/**
 * Created by cshao on 12/28/14.
 */

function getNQueens(order) {
if (order < 4) {
console.log('N Queens problem apply for order bigger than 3');
Return;
}

var nQueens = [];
var backTracking = false;
rowLoop:
for (var row=0; row If (nQueens[row] === undefined) {
nQueens[row] = [];
}

for (var col=0; col If (nQueens[row][col] === 0) {
Continue;
} else if (backTracking && nQueens[row][col] == 1) {
If (col === order-1) {
              resetRow(nQueens, order, row);
             row = row - 2;
                 continue rowLoop;
}
nQueens[row][col] = 0;
         backTracking = false;
Continue;
}
       
nQueens[row][col] = 1;
If (isQueenValid(nQueens, row, col)) {
Continue rowLoop;
} else if (col == order-1) {
backTracking = true;
          resetRow(nQueens, order, row);
           row = row - 2;
Continue rowLoop;
} else {
nQueens[row][col] = 0;
Continue;
};
}
}

return nQueens;
}

function resetRow(nQueens, order, row) {
for (var col=0; col nQueens[row][col] = undefined;
}
}

function isQueenValid(nQueens, row, col) {
for (var i=0; i If (nQueens[row][i] == 1) {
Return false;
}
}
for (var j=1; j if (nQueens[row-j][col]==1 || (nQueens[row-j][col-j]!=undefined && nQueens[row-j][col-j]==1) || ( nQueens[row-j][col j]!=undefined && nQueens[row-j][col j]==1)) {
Return false;
}
}
return true;
}

function printQueens(queens) {
for (var row=0; row var rowText = '';
for (var col=0; col If (queens[row][col]===undefined) {
Queens[row][col] = 0;
}
rowText = rowText queens[row][col] ' ';
}
console.log(rowText);
}
}

var queens = getNQueens(8);
printQueens(queens);

Results

Copy code The code is as follows:

1  0  0  0  0  0  0  0 
0  0  0  0  1  0  0  0 
0  0  0  0  0  0  0  1 
0  0  0  0  0  1  0  0 
0  0  1  0  0  0  0  0 
0  0  0  0  0  0  1  0 
0  1  0  0  0  0  0  0 
0  0  0  1  0  0  0  0