Need Help With N Queens Program ( checking diagonals )

Question

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:

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.

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

Answer 1

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.)

For example, say you have two queens Q1 and Q2. Calculate the absolute value of the differences in their rows and columns.

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

If deltaRow == deltaCol, the queens are on the same diagonal.

Just do that for all N queens.

Answer 2

We can say that the queens are on the same diagonal if the slope of the line connecting the 2 queens is either 1 or -1.

Let q1 and q2 be data structures holding the x and y positions of each queen:

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.