Need help with N Queens (diagonal check)

Question

I am working on a N Queens program that will allow the user to enter Queen configuration as String. For example, when prompted, the user can enter something like Q .... Q ..... Q..Q. which when displayed in the form of a board will look like this:

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

This program is simple in the sense that it assumes that the user is entering valid information. I would like the main part of the program to work before I go back and add error handling.

For those who are not familiar with the N Queens puzzle, basically you have N Queens on the N x N circuit board. You have one queen in a row. A populated board is the solution if no two Queens have the same rows, columns, or diagonals.

I have successfully performed row and column checks. However, I'm at a standstill about how I can check all the diagonals. I know how to check two main diagonals, for example, in tic tac toe, but I really can’t imagine 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

Answer 1

I don't think you want to check all the diagonals, but instead you can check all the queens. You can check if two queens are on the same diagonal by checking the differences between the rows and columns of two Qs. If the differences coincide, they are on the same diagonal. (In principle, if the slope of the line between the two queens is + -1, they are on the same diagonal.)

For example, let's 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 it for all Queens N.

Answer 2

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

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

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

So if (slope.abs() == 1) , then they are on the same diagonal.

Answer 3

Diagonals can be expressed as y = x + c or y = c - x. Your 4x4 board will have a total of 10 diagonals, 5 for each equation. Figure out c (they vary depending on the size of the board) and the loop on x, calculate y.

You will need to check that the coordinates are less than zero, the upper boundaries can be avoided by simply making the 2x board as large (in each direction) as needed - the remaining squares are always empty, so checking them does not cause harm.

I even implemented the N queens problem without a board at all - track rows, columns and diagonals. It was faster at the time, because addition was much faster than multiplication, but that is no longer the case.