java 需要 N Queens 计划的帮助（检查对角线）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3209165/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Need Help With N Queens Program ( checking diagonals )
提问by Codebug
I'm working on an N Queens program that will allow the user to enter a Queen configuration as a String. For example, when prompted, the user might enter something like Q....Q.....Q..Q. which when displayed as a board would look like:
我正在开发一个 N Queens 程序，该程序将允许用户将 Queen 配置作为字符串输入。例如，当提示时，用户可能会输入类似 Q....Q.....Q..Q 的内容。当显示为板时，它看起来像：
Q . . .
. Q . .
. . . Q
. . Q .
Is not a solution!
This program is simple in that it assumes that the user will enter valid information. I would like to get the main part of the program working before I go back and add error handling.
该程序很简单，因为它假定用户将输入有效信息。我想在返回并添加错误处理之前让程序的主要部分工作。
For those not familiar with the N Queens puzzle, basically you have N Queens on an N x N board. You have one Queen per row. A populated board is a solution if no two Queens share the same row, column or diagonal.
对于那些不熟悉 N Queens 谜题的人来说，基本上你在 N x N 板上有 N 个皇后。每排有一个皇后。如果没有两个皇后共享相同的行、列或对角线，则填充板是一种解决方案。
I have successfully implemented checks for the rows and columns. However, I am stumped as to how I can check all the diagonals. I know how to check the two main diagonals, like in tic tac toe, but I really can't visualize how I can check all possible diagonals?
我已经成功地实现了对行和列的检查。但是，我对如何检查所有对角线感到困惑。我知道如何检查两条主要对角线，就像井字游戏一样，但我真的无法想象如何检查所有可能的对角线？
Can anyone offer help?
任何人都可以提供帮助吗？
Here is my code:
这是我的代码：
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
Thanks Read more: Need Help With N Queens Program
谢谢阅读更多：需要 N 皇后计划的帮助
回答by Bill the Lizard
I don't think you want to check all the diagonals, but you can check all the queens instead. You can check to see if two queens are on the same diagonal by checking the differences between the rows and columns of the two Qs. If the differences are the same, they're on the same diagonal. (Basically, if the slope of the line between the two queens is +-1, they're on the same diagonal.)
我认为您不想检查所有对角线，但您可以检查所有皇后。您可以通过检查两个 Q 的行和列之间的差异来检查两个皇后是否在同一对角线上。如果差异相同，则它们位于同一对角线上。（基本上，如果两个皇后之间的线的斜率为 +-1，则它们在同一对角线上。）
For example, say you have two queens Q1 and Q2. Calculate the absolute value of the differences in their rows and columns.
例如，假设您有两个皇后 Q1 和 Q2。计算它们的行和列中差异的绝对值。
deltaRow = abs(Q1 row - Q2 row)
deltaCol = abs(Q1 col - Q2 col)
If deltaRow == deltaCol, the queens are on the same diagonal.
如果deltaRow == deltaCol，则皇后在同一对角线上。
Just do that for all N queens.
对所有 N 个皇后都这样做。
回答by A. Sallai
We can say that the queens are on the same diagonal if the slopeof the line connecting the 2 queens is either 1 or -1.
如果连接 2 个皇后的线的斜率为 1 或 -1 ，我们可以说皇后在同一对角线上。
Let q1and q2be data structures holding the x and y positions of each queen:
让q1和q2成为保存每个皇后的 x 和 y 位置的数据结构：
xDistance = q1.x - q2.x
yDistance = q1.y - q2.y
slope = xDistance / yDistance
So if (Math.abs(slope) == 1)then they are on the same diagonal.
那么if (Math.abs(slope) == 1)它们在同一对角线上。
回答by Loren Pechtel
Diagonals can be expressed in the form of y = x + c or y = c - x. Your 4x4 board will have a total of 10 diagonals, 5 for each equation. Figure out the c's (they vary based on the board size) and loop on x, calculate the y's.
对角线可以表示为 y = x + c 或 y = c - x 的形式。您的 4x4 棋盘总共有 10 条对角线，每个方程有 5 条对角线。找出 c 的（它们因电路板尺寸而异）并在 x 上循环，计算 y 的。
You'll have to check for coordinates less than zero, the upper bounds can be avoided by simply making the board 2x as big (in each direction) as need be--the other squares are always empty so checking them causes no harm.
您必须检查小于零的坐标，只需根据需要将棋盘（在每个方向上）放大 2 倍就可以避免上限——其他方块总是空的，因此检查它们不会造成伤害。
I have even implemented the N queens problem with no board at all--track the rows, columns and diagonals. At the time this was faster because addition was a lot faster than multiplication but that's no longer the case.
我什至在完全没有板的情况下实现了 N 个皇后问题——跟踪行、列和对角线。当时这更快，因为加法比乘法快得多，但现在已经不是这样了。
