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 difference in their rows and columns.

deltaRow = Q1 row - Q2 row
deltaCol = Q1 col - Q2 col

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

Just do that for all N queens.

Answer 2

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.

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.

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.