需要帮助N皇后计划(检查对角线)

Question

我正在开发一个N Queens程序,允许用户输入Queen配置作为String.例如,当提示时,用户可能输入Q ...... Q ..... Q..Q.当显示为板时,它看起来像:

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

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

对于那些不熟悉N Queens拼图的人,基本上你在N x N板上有N皇后区.你每行有一个女王.如果没有两个皇后区共享相同的行,列或对角线,则填充板是一种解决方案.

我已经成功实现了对行和列的检查.但是,我很难过如何检查所有的对角线.我知道如何检查两个主要的对角线,比如在tic tac toe,但我真的无法想象我如何检查所有可能的对角线？

有人可以提供帮助吗？

这是我的代码:

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

如果连接 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)它们就在同一条对角线上。