I was trying to implement N-Queens problem using a backtracking algorithm. The goal was to place n queens on an n x n chessboard in such a way that no two queens attack each other. A queen can attack other queens if they are in the same row, column or diagonal.
function nQueen(boolArrBoard,row){
if(row === boolArrBoard.length){
display(boolArrBoard)
return 1 *//count*
}
let count = 0
*//placing the queen and checking every row and column*
for(let col = 0; col < boolArrBoard.length; col++){
*//place the queen if it is safe *
if(isSafe(boolArrBoard,row,col)){
boolArrBoard[row][col] = true
count += nQueen(boolArrBoard,row+1)
boolArrBoard[row][col] = false
}
}
return count
}
function isSafe(boolArrBoard,row,col){
*//vertical*
for(let i = 0; i < row; i++){
if(boolArrBoard[i][col]){
return false
}
}
*//left diagonal*
let maxLeft = Math.min(row,col)
for(let i = 1; i <= maxLeft; i++){
if(boolArrBoard[row - i][col - i]){
return false
}
}
*//right diagonal*
let maxRight = Math.min(row, boolArrBoard.length - col - 1)
for(let i = 1; i <= maxRight; i++){
if(boolArrBoard[row - i][col + i]){
return false
}
}
return true
}
function display(boolArrBoard){
for( let row in boolArrBoard){
for(let column in boolArrBoard[row]){
if(boolArrBoard[row][column]){
process.stdout.write('Q')
}
else{
process.stdout.write('X')
}
}
console.log()
}
}
let n = 4
let boolArrBoard = Array.from({length: n}, () => {
new Array(n).fill(false)
})
nQueen(boolArrBoard,0)
node /tmp/Owi55b6DWs.js
/tmp/Owi55b6DWs.js:15
boolArrBoard[row][col] = true
^
TypeError: Cannot set property '0' of undefined
at nQueen (/tmp/Owi55b6DWs.js:15:36)
Can anyone explain the problem in my code and what shall I do to resolve it or provide the correctecd code
The problem is that your board is not well initialised. This you can easily see when you print boolArrBoard
. It looks like this:
[undefined, undefined, undefined, undefined]
The causing bug is that you didn't return anything in this callback:
let boolArrBoard = Array.from({length: n}, () => {
new Array(n).fill(false)
})
Just add return
or remove the braces in the arrow function.
It would be good if you would inspect your variables while stepping through your code with a debugger.