N皇后计划需要帮助（检查对角线）

Question

我正在研究一个N皇后计划，允许用户输入皇后配置作为一个字符串。例如， 出现提示时，用户可能会输入类似Q .... Q ..... Q..Q。当显示为电路板时，它看起来像：

Q . . . 
. Q . . 
. . . Q 
. . Q . 
Is not a solution! 

该程序很简单，它假定用户将输入有效信息。我想在返回并添加错误处理之前让程序的主要部分工作。

对于那些不熟悉N皇后拼图的人，基本上你在N×N棋盘上有N张皇后。你每行有一个女王。如果没有两个皇后共享相同的行，列或对角线，则填充板是解决方案。

我已成功实施对行和列的检查。然而，我很难理解我如何检查所有的对角线。我知道如何检查两个主对角线，就像在井字游戏中一样，但我真的无法想象我如何检查所有可能的对角线？

任何人都可以提供帮助吗？

这里是我的代码：

import java.util.Scanner; 
public class NQueens { 


    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int qCount; 
     boolean solution = true; 


     System.out.println("Enter the String to test:"); 
     board = sc.nextLine(); 

     int boardLen = board.length(); 
     int maxDim = (int) Math.sqrt(boardLen); 
     char[][] gameBoard = new char[maxDim][maxDim]; 


     int counter = 0; 
     for (int i = 0; i < maxDim; i++) 
     { 
      for (int j = 0; j < maxDim; j++) 
      { 
       gameBoard[ i ][ j ] = board.charAt(counter); 
       counter++; 
      } 

     } 


     System.out.println(""); 
     System.out.println(""); 




    //check rows  

    for (int i = 0; i < maxDim; i++) 
    { 
     int queenCount = 0; 

     for (int j = 0; j < maxDim; j++) 
     { 
      if (gameBoard[ i ][ j ] == 'Q') 
      { 
       queenCount++; 


       if (queenCount > 1) 
       { 
        solution = false; 
        break; 

       } 


      } 


     } 

    } 


    // check columns 

    for (int i = 0; i < maxDim; i++) 
    { 
     int queenCount = 0; 

     for (int j = 0; j < maxDim; j++) 
     { 
      if (gameBoard[ j ][ i ] == 'Q') 
      { 
       queenCount++; 

       if (queenCount > 1) 
       { 
        solution = false; 
        break; 
       } 
      } 
     } 
    } 


    // print the board 

    for(int i = 0; i < maxDim; i++) 
    { 
     for (int j = 0; j < maxDim; j++) 
     { 
      System.out.print(gameBoard[ i ][ j ] + " "); 
     } 

     System.out.println(); 

    } 

    // print whether or not the placement of queens is a solution 
    if (solution) 
    { 
     System.out.println("Is a solution!"); 

    } 

    else 
    { 
     System.out.println("Is not a solution!"); 

    } 

    }//end main 

}//end class 

感谢 了解更多：需要帮助N皇后计划

Answer 1

我不认为你要检查所有的对角线，但你可以检查所有女王代替。您可以通过检查两个Q的行和列之间的差异来检查两个皇后是否在同一对角线上。如果差异相同，则它们在相同的对角线上。 （基本上，如果两个皇后之间的直线斜率为+ -1，则它们在同一对角线上。）

例如，假设您有两个皇后Q1和Q2。计算行和列的差异的绝对值。

deltaRow = abs(Q1 row - Q2 row) 
deltaCol = abs(Q1 col - Q2 col) 

如果deltaRow == deltaCol，皇后位于相同的对角线上。

只需要为所有N个皇后做。

Answer 2

对角线可以表示为y = x + c或y = c-x的形式。你的4x4板子总共有10个对角线，每个方程5个。找出c（它们根据电路板尺寸而变化）并在x上循环，计算y的值。

您必须检查小于零的坐标，可以通过简单地将电路板按照大小（在每个方向上）按需要放大2倍来避免上限 - 其他方块总是空的，因此检查它们是因为无害。

我甚至在没有电路板的情况下实现了N皇后问题 - 跟踪行，列和对角线。当时这是更快的，因为加法比乘法快得多，但不再是这种情况。

Answer 3

如果连接2个皇后的线的斜率是1或-1，我们可以说皇后位于相同的对角线上。

让q1和q2是抱在一起女王的x和y位置数据结构：

xDistance = q1.x - q2.x

yDistance = q1.y - q2.y

slope = xDistance/yDistance

所以if (slope.abs() == 1)那么他们在同一对角线。