java - 需要 N Queens 程序的帮助(检查对角线)

Question

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

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

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

对于那些不熟悉 N Queens 谜题的人来说，基本上您在 N x N 棋盘上有 N 个 Queens。每行有一个皇后。如果没有两个皇后共享相同的行、列或对角线，则填充板是一种解决方案。

我已经成功地实现了对行和列的检查。但是，我对如何检查所有对角线感到困惑。我知道如何检查两条主对角线，就像在井字游戏中一样，但我真的无法想象如何检查所有可能的对角线？

谁能提供帮助？

这是我的代码:

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 个皇后都这样做。