N queens problem using backtracking in JavaScript

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

N queens problem using backtracking in javascript

问题

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

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

  1. function nQueen(boolArrBoard,row){
  2.     if(row === boolArrBoard.length){
  3.         display(boolArrBoard)
  4.         return 1 // 计数
  5.     }
  7.     let count = 0
  8.     // 放置皇后并检查每一行和列
  9.     for(let col = 0; col < boolArrBoard.length; col++){
  10.         // 如果安全就放置皇后
  11.         if(isSafe(boolArrBoard,row,col)){
  12.             boolArrBoard[row][col] = true
  13.             count += nQueen(boolArrBoard,row+1)
  14.             boolArrBoard[row][col] = false
  15.         }
  16.     }
  17.     return count
  18. }
  20. function isSafe(boolArrBoard,row,col){
  21.     // 检查垂直方向
  22.     for(let i = 0; i < row; i++){
  23.        if(boolArrBoard[i][col]){
  24.         return false
  25.        }
  26.     }
  28.     // 检查左对角线
  29.     let maxLeft = Math.min(row,col)
  30.     for(let i = 1; i <= maxLeft; i++){
  31.         if(boolArrBoard[row - i][col - i]){
  32.             return false
  33.         }
  34.     }
  36.     // 检查右对角线
  37.     let maxRight = Math.min(row, boolArrBoard.length - col - 1)
  38.     for(let i = 1; i <= maxRight; i++){
  39.         if(boolArrBoard[row - i][col + i]){
  40.             return false
  41.         }
  42.     }
  44.     return true
  45. }
  47. function display(boolArrBoard){
  48.     for( let row in boolArrBoard){
  49.         for(let column in boolArrBoard[row]){
  50.             if(boolArrBoard[row][column]){
  51.                 process.stdout.write('Q')
  52.             }
  53.             else{
  54.                 process.stdout.write('X')
  55.             }
  56.         }
  57.         console.log()
  58.     }
  59. }
  61. let n = 4
  62. let boolArrBoard = Array.from({length: n}, () => {
  63.     return new Array(n).fill(false)
  64. })
  65. nQueen(boolArrBoard,0)

我遇到了这个错误:

  1. /tmp/Owi55b6DWs.js:15
  2.             boolArrBoard[row][col] = true
  3.                                    ^
  5. TypeError: Cannot set property '0' of undefined
  6.     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:

  1.    function nQueen(boolArrBoard,row){
  2.        if(row === boolArrBoard.length){
  3.            display(boolArrBoard)
  4.            return 1 *//count*
  5.        }
  6.    
  7.        let count = 0
  8.        *//placing the queen and checking every row and column*
  9.        for(let col = 0; col &lt; boolArrBoard.length; col++){
  10.            *//place the queen if it is safe *
  11.            if(isSafe(boolArrBoard,row,col)){
  12.                boolArrBoard[row][col] = true
  13.                count += nQueen(boolArrBoard,row+1)
  14.                boolArrBoard[row][col] = false
  15.            }
  16.        }
  17.        return count
  18.    }
  19.    
  20.    function isSafe(boolArrBoard,row,col){
  21.        *//vertical*
  22.        for(let i = 0; i &lt; row; i++){
  23.           if(boolArrBoard[i][col]){
  24.            return false
  25.           }
  26.        }
  27.    
  28.        *//left diagonal*
  29.        let maxLeft = Math.min(row,col)
  30.        for(let i = 1; i &lt;= maxLeft; i++){
  31.            if(boolArrBoard[row - i][col - i]){
  32.                return false
  33.               }
  34.        }
  35.    
  36.        *//right diagonal*
  37.        let maxRight = Math.min(row, boolArrBoard.length - col - 1)
  38.        for(let i = 1; i &lt;= maxRight; i++){
  39.            if(boolArrBoard[row - i][col + i]){
  40.                return false
  41.               }
  42.        }
  43.    
  44.        return true
  45.    }
  46.    
  47.    function display(boolArrBoard){
  48.        for( let row in boolArrBoard){
  49.            for(let column in boolArrBoard[row]){
  50.                if(boolArrBoard[row][column]){
  51.                    process.stdout.write(&#39;Q&#39;)
  52.                }
  53.                else{
  54.                    process.stdout.write(&#39;X&#39;)
  55.                }
  56.            }
  57.            console.log()
  58.        }
  59.    }
  60.    
  61.    let n = 4
  62.    let boolArrBoard = Array.from({length: n}, () =&gt; {
  63.        new Array(n).fill(false)
  64.    })
  65.    nQueen(boolArrBoard,0)

I have encountered this error:

  1. node /tmp/Owi55b6DWs.js
  2. /tmp/Owi55b6DWs.js:15
  3.             boolArrBoard[row][col] = true
  4.                                    ^
  6. TypeError: Cannot set property &#39;0&#39; of undefined
  7.     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时，很容易看到这一点。它看起来像这样：

  1. [undefined, undefined, undefined, undefined]

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

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

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

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

英文:

The problem is that your board is not well initialised. This you can easily see when you print boolArrBoard. It looks like this:

  1. [undefined, undefined, undefined, undefined]

The causing bug is that you didn't return anything in this callback:

  1.    let boolArrBoard = Array.from({length: n}, () =&gt; {
  2.        new Array(n).fill(false)
  3.    })

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
  • backtracking
  • data-structures
  • javascript
  • n-queens
  • recursion
匿名

发表评论

匿名网友

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

确定