One Pager Cheat Sheet
- You should design an
N-Queen
problem solver that can placen
queens on an x n
square board in a way that no queen is in a mutual attacking position, with a minimum value ofn = 4
and a maximum value ofn = 100
, inO(n^2)
time andO(n)
space complexity. - We need to use a
backtracking algorithm
to solve theNP-Complete 8-Queen problem
due to its large search space ruling out a naive brute force solution. - A
Board Validation Function
is used to check if we can place aQueen
in a cell of the board by looping through the rows and checking if there is a Queen in the same column, and by checking if a Queen appears in the first and second diagonals by observing therow
andcol
variables in a loop. We will return
Trueif a Queen is validly placed at a given
row
andcol
position.- We will start from the first element in the board and attempt to place Queens, incrementing the
row
untilrow
is greater thann
, at which point a solution is found and the board is saved for further backtracking. - The algorithm will recursively evaluate
row
-by-row
for valid positions to place the Queen and add each solution to a list ofresults
beforebacktracking
to the next feasible place. - We will
create a board
bymultiplying a string of size n
andduplicating it n times
, then start thebacktracking process
atrow=0 and col=0
. - We will recursively select
Q
ueen positions and build up the solution list,res
, with a time complexity of O(n^2) and space complexity of board size times res.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
152
}
var assert = require('assert');
​
function solveNQueens(n) {
var board = new Array(n);
// Setup thhe board
for (i = 0; i < n; i++) {
board[i] = new Array(n);
for (j = 0; j < n; j++) {
board[i][j] = '.';
}
}
​
res = recursiveSolveNQueens([], board, 0);
console.log('board', res);
return res;
}
​
function copyBoard(board) {
let newBoard = new Array(board.length);
for (i = 0; i < board.length; i++) {
newBoard[i] = new Array(board[i].length);
for (j = 0; j < board[i].length; j++) {
newBoard[i][j] = board[i][j];
}
}
return newBoard;
}
​
function recursiveSolveNQueens(res, board, row, cols = []) {
if (row === board.length) {
// A solution! add a copy of it
res.push(copyBoard(board));
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Got more time? Let's keep going.
If you had any problems with this tutorial, check out the main forum thread here.