javascriptrecursiondata-structuresbacktrackingn-queens

N queens problem using backtracking in javascript


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.

I tried solving this way:

   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)

I have encountered this error:

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


Solution

  • 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.