Home > Web Front-end > JS Tutorial > JavaScript implementation of N Queens problem algorithm puzzle solution_javascript skills

JavaScript implementation of N Queens problem algorithm puzzle solution_javascript skills

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Release: 2016-05-16 16:23:52
Original
1729 people have browsed it

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
Related labels:
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Issues
What are JavaScript hook functions?
From 1970-01-01 08:00:00
0
0
0
What is JavaScript garbage collection?
From 1970-01-01 08:00:00
0
0
0
c++ calls javascript
From 1970-01-01 08:00:00
0
0
0
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template