8递归递归的非攻击皇后算法

我在编码8皇后问题时遇到了麻烦。我编了一个课程来帮助我解决问题，但由于某种原因，我做错了一些事情。我有点理解应该发生什么。8递归递归的非攻击皇后算法

此外，我们必须使用递归来解决它，但我不知道如何使用我已阅读过的回溯，所以我只是在检查位置是否合法的方法中使用它。

我的板子是String [] [] board = { { "O", "O"...等等8行8列。如果我在概念上弄错了什么或者犯了严重的Java错误，请这样说：D 谢谢！

public void solve() { 
    int Queens = NUM_Queens - 1; 
    while (Queens > 0) { 
     for (int col = 0; col < 8; col++) { 
      int row = -1; 
      boolean c = false; 
      while (c = false && row < 8) { 
       row ++; 
       c = checkPos (row, col); 
      } 
      if (c == true) { 
       board[row][col] = "Q"; 
       Queens--; 
      } 
      else 
       System.out.println("Error"); 
     } 
    } 
    printBoard(); 
} 

// printing the board 
public void printBoard() { 
    String ret = ""; 
    for (int i = 0; i < 8; i++) { 
     for (int a = 0; a < 8; a++) 
      ret += (board[i][a] + ", "); 
     ret += ("\n"); 
    } 
    System.out.print (ret); 
} 

// checking if a position is a legitimate location to put a Queen 
public boolean checkPos (int y, int x) { 
    boolean r = true, d = true, u = true, co = true; 
    r = checkPosR (y, 0); 
    co = checkPosC (0, x); 
    int col = x; 
    int row = y; 
    while (row != 0 && col != 0) { //setting up to check diagonally downwards 
     row--; 
     col--; 
    } 
    d = checkPosDD (row, col); 
    col = x; 
    row = y; 
    while (row != 7 && col != 0) { //setting up to check diagonally upwards 
     row++; 
     col--; 
    } 
    d = checkPosDU (row, col); 
    if (r = true && d = true && u = true && co = true) 
     return true; 
    else 
     return false; 
} 

// checking the row 
public boolean checkPosR (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
      return false; 
    else if (board[y][x].contentEquals("O") && x == 7) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y, x+1); 
} 

// checking the column 
public boolean checkPosC (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
      return false; 
    else if (board[y][x].contentEquals("O") && y == 7) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y+1, x); 
} 

// checking the diagonals from top left to bottom right 
public boolean checkPosDD (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
     return false; 
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 7)) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y+1, x+1); 
} 

// checking the diagonals from bottom left to up right 
public boolean checkPosDU (int y, int x) { 
    if (board[y][x].contentEquals("Q")) 
     return false; 
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 0)) 
     return true; 
    else //if (board[y][x].contentEquals("O")) 
     return checkPosR (y-1, x+1); 
    } 
}

来源

2013-03-05 Tlazolteotl

由于每行只能有一个皇后，所以将棋盘表示为int [8]，其中每个条目都是该行皇后的列位置。这将简化很多事情。 – NPE 2013-03-05 08:44:33

你得到的输出/错误是什么？ – Aashray 2013-03-05 08:46:02

您是否遇到任何代码问题。预期产出是多少？您获得的实际产出是多少？ – Jayamohan 2013-03-05 08:46:14

-1

你正在尝试某种蛮力，但正如你已经提到的，你没有递归。您的程序会尝试将女王放在第一个可能的位置。但最终没有找到解决办法。因此，你的第一个假设（你的第一个女王的位置）是无效的。你必须回到这个状态。并且必须假设你的checkPos（x，y）是false而不是true。

现在一些提示：

如NPE int[N] queens前面提到的是更合适的表示。
总和（皇后）必须是0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28，因为一个位置必须是唯一的。
不是只检查新皇后的位置，你可以检查整个情况。如果在女王（i）= j的N^2中对于所有（i，j）\，在abs（ki）= abs（lj）时不存在（k，l）！=

来源

2013-03-05 11:33:30 user2135069

我有点困惑，你的意思是检查整个情况。你介意写一些代码，以便我能想出一个想法吗？ – Tlazolteotl 2013-03-05 14:00:33

对不起，但是从“没有解决办法”来看，它并没有遵循** first first queen的立场是错误的。 – Ingo 2013-03-05 14:30:46

对，如果无效，你必须首先使最后的假设无效。 – user2135069 2013-03-05 19:13:41

由于这是作业，解决方案，而不是代码。

尝试编写一种方法，该方法只处理需要在单个列上发生的事情;这是你应该使用递归的地方。通过检查是否存在解决方案来进行回溯，如果不存在，则撤消最后的更改（即更改女王位置）并重试。如果您只关注问题的一部分（一列），这比同时考虑所有列更容易。并且正如Quetzalcoatl指出的那样，您在第一个循环中将变量false分配给您的变量。你可能不想这样做。您应该始终在编译器中启用所有警告（使用-Xlint运行javac）并修复它们。

来源

2013-03-05 14:55:52 wds

8递归递归的非攻击皇后算法

回答

相关问题