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

Question

我正在开发一个 N Queens 程序，该程序将允许用户以字符串形式输入 Queen 配置。例如， 当出现提示时，用户可能会输入类似 Q....Q.....Q..Q 的内容。当显示为板时，它看起来像：

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

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

对于那些不熟悉 N 个皇后拼图的人来说，基本上 N x 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 Queens 计划的帮助

Answer 1

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

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

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

如果 deltaRow == deltaCol ，则皇后位于同一条对角线上。

对所有 N 个皇后都这样做。

Answer 2

如果连接两个皇后的线的斜率为 1 或 -1，我们可以说皇后位于同一条对角线上。

令 q1 和 q2 为保存每个皇后的 x 和 y 位置的数据结构：

xDistance = q1.x - q2.x
yDistance = q1.y - q2.y
slope = xDistance / yDistance

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

Answer 3

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

您必须检查小于零的坐标，只需根据需要将棋盘放大 2 倍（在每个方向上）即可避免上限 - 其他方块始终为空，因此检查它们不会造成任何伤害。

我什至在没有任何棋盘的情况下实现了 N 皇后问题——跟踪行、列和对角线。当时这更快，因为加法比乘法快得多，但现在情况不再如此。