在javascript中使用回溯的N皇后问题

mrwjdhj3  于 2023-02-18  发布在  Java
关注(0)|答案(1)|浏览(117)

我尝试用回溯算法来实现N皇后问题。目标是把n个皇后放在一个n × n的棋盘上,这样就不会有两个皇后互相攻击。一个皇后可以攻击其他皇后,如果他们在同一行,同一列或同一条对角线上。

我尝试用以下方法求解:

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)

有人能解释我的代码中的问题吗?我应该怎么做来解决它或提供正确的代码

dgiusagp

dgiusagp1#

问题是您的电路板初始化不好。当您打印boolArrBoard时,您可以很容易地看到这一点。它看起来如下所示:

[undefined, undefined, undefined, undefined]

导致bug的原因是您没有在此回调中返回任何内容:

let boolArrBoard = Array.from({length: n}, () => {
       new Array(n).fill(false)
   })

只需添加return或删除arrow函数中的大括号。
如果您在使用调试器单步调试代码的同时检查变量,那就太好了。

相关问题