N queens problem using backtracking in JavaScript

huangapple go评论73阅读模式
英文:

N queens problem using backtracking in javascript

问题

我尝试使用回溯算法来解决N皇后问题。目标是在一个N x N的棋盘上放置N个皇后,使得它们互不攻击。皇后可以攻击同一行、同一列或对角线上的其他皇后。

我尝试用以下方式解决问题:

function nQueen(boolArrBoard,row){
    if(row === boolArrBoard.length){
        display(boolArrBoard)
        return 1 // 计数
    }

    let count = 0
    // 放置皇后并检查每一行和列
    for(let col = 0; col < boolArrBoard.length; col++){
        // 如果安全就放置皇后
        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){
    // 检查垂直方向
    for(let i = 0; i < row; i++){
       if(boolArrBoard[i][col]){
        return false
       }
    }

    // 检查左对角线
    let maxLeft = Math.min(row,col)
    for(let i = 1; i <= maxLeft; i++){
        if(boolArrBoard[row - i][col - i]){
            return false
        }
    }

    // 检查右对角线
    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}, () => {
    return new Array(n).fill(false)
})
nQueen(boolArrBoard,0)

我遇到了这个错误:

/tmp/Owi55b6DWs.js:15
            boolArrBoard[row][col] = true
                                   ^

TypeError: Cannot set property '0' of undefined
    at nQueen (/tmp/Owi55b6DWs.js:15:36)

请注意,我已经更正了代码中的错误注释并将不正确的HTML编码(如 &lt;&#39;)替换为正确的JavaScript 代码。现在,代码应该可以正常运行,但错误提示中提到的问题是由于布尔数组 boolArrBoard 未正确初始化。我已经在初始化数组时添加了 return,这应该解决这个问题。

英文:

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 &lt; 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 &lt; row; i++){
          if(boolArrBoard[i][col]){
           return false
          }
       }
   
       *//left diagonal*
       let maxLeft = Math.min(row,col)
       for(let i = 1; i &lt;= 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 &lt;= 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(&#39;Q&#39;)
               }
               else{
                   process.stdout.write(&#39;X&#39;)
               }
           }
           console.log()
       }
   }
   
   let n = 4
   let boolArrBoard = Array.from({length: n}, () =&gt; {
       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 &#39;0&#39; 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

答案1

得分: 0

问题在于您的棋盘没有被正确初始化。当您打印boolArrBoard时,很容易看到这一点。它看起来像这样:

[undefined, undefined, undefined, undefined]

导致错误的原因是在这个回调函数中您没有返回任何内容:

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

只需添加return或删除箭头函数中的大括号。

当您使用调试器逐步执行代码时,检查您的变量会很有帮助。

英文:

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}, () =&gt; {
       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.

huangapple
  • 本文由 发表于 2023年2月17日 23:43:27
  • 转载请务必保留本文链接:https://go.coder-hub.com/75486408.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定