java:implement 8 queen using depth first search

Question

i am try to implement 8 queen using depth search for any initial state it work fine for empty board(no queen on the board) ,but i need it to work for initial state if there is a solution,if there is no solution for this initial state it will print there is no solution

Here is my code:

public class depth {
   public static void main(String[] args) {
       //we create a board
       int[][] board = new int[8][8];
       board [0][0]=1;
       board [1][1]=1;
       board [2][2]=1;
       board [3][3]=1;
       board [4][4]=1;
       board [5][5]=1;
       board [6][6]=1;
       board [7][7]=1;

       eightQueen(8, board, 0, 0, false);
       System.out.println("the solution as pair");
       for(int i=0;i<board.length;i++){
           for(int j=0;j<board.length;j++)
               if(board[i][j]!=0)

               System.out.println("  ("+i+" ,"+j +")");
       }
       System.out.println("the number of node stored in memory "+count1);
   }
      public static int count1=0;
     public static void eightQueen(int N, int[][] board, int i, int j, boolean found) {

    long startTime = System.nanoTime();//time start

    if (!found) {
        if (IsValid(board, i, j)) {//check if the position is valid
            board[i][j] = 1;

            System.out.println("[Queen added at (" + i + "," + j + ")");
            count1++;
            PrintBoard(board);


            if (i == N - 1) {//check if its the last queen
                found = true;
                PrintBoard(board);
                double endTime = System.nanoTime();//end the method time

                double duration = (endTime - startTime)*Math.pow(10.0, -9.0);
                System.out.print("total Time"+"= "+duration+"\n");
            }
            //call the next step
            eightQueen(N, board, i + 1, 0, found);
        } else {

            //if the position is not valid & if reach the last row we backtracking
            while (j >= N - 1) {
                int[] a = Backmethod(board, i, j);
                i = a[0];
                j = a[1];

                System.out.println("back at (" + i + "," + j + ")");
                PrintBoard(board);
            }
            //we do the next call
            eightQueen(N, board, i, j + 1, false);
        }
    }

}

public static int[] Backmethod(int[][] board, int i, int j) {
    int[] a = new int[2];
    for (int x = i; x >= 0; x--) {
        for (int y = j; y >= 0; y--) {
            //search for the last queen
            if (board[x][y] != 0) {
                //deletes the last queen and returns the position
                board[x][y] = 0;
                a[0] = x;
                a[1] = y;
                return a;
            }
        }
    }
    return a;
}

public static boolean IsValid(int[][] board, int i, int j) {

    int x;
    //check the queens in column
    for (x = 0; x < board.length; x++) {
        if (board[i][x] != 0) {
            return false;
        }
    }
    //check the queens in row
    for (x = 0; x < board.length; x++) {
        if (board[x][j] != 0) {
            return false;
        }
    }
    //check the queens in the diagonals
    if (!SafeDiag(board, i, j)) {
        return false;
    }
    return true;
}

public static boolean SafeDiag(int[][] board, int i, int j) {

    int xx = i;
    int yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy++;
        xx++;
    }
    xx = i;
    yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy--;
        xx--;
    }
    xx = i;
    yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy--;
        xx++;
    }
    xx = i;
    yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy++;
        xx--;
    }
    return true;
}
public static void PrintBoard(int[][] board) {
    System.out.print(" ");
    for (int j = 0; j < board.length; j++) {
        System.out.print(j);
    }
    System.out.print("\n");
    for (int i = 0; i < board.length; i++) {
        System.out.print(i);
        for (int j = 0; j < board.length; j++) {
            if (board[i][j] == 0) {
                System.out.print(" ");
            } else {
                System.out.print("Q");
            }
        }
        System.out.print("\n");
    }
}


}

for example for this initial state it give me the following error:

Exception in thread "main" java.lang.StackOverflowError

i am stuck, i think the error is infinite call for the method how to solve this problem.

any idea will be helpful,thanks in advance.

note:the broad is two dimensional array,when i put (1) it means there queen at this point.

note2: we i put the initial state as the following it work:

       board [0][0]=1;
       board [1][1]=1;
       board [2][2]=1;
       board [3][3]=1;
       board [4][4]=1;
       board [5][5]=1;
       board [6][6]=1;
       board [7][1]=1; 

Answer 1

Try to alter your method IsValid in the lines where for (x = 0; x < board.length - 1; x++).

public static boolean IsValid(int[][] board, int i, int j) {
    int x;
    //check the queens in column
    for (x = 0; x < board.length - 1; x++) {
        if (board[i][x] != 0) {
            return false;
        }
    }
    //check the queens in row
    for (x = 0; x < board.length - 1; x++) {
        if (board[x][j] != 0) {
            return false;
        }
    }
    //check the queens in the diagonals
    if (!SafeDiag(board, i, j)) {
        return false;
    }
    return true;
}

Answer 2

[EDIT: Added conditional output tip.]

To add to @StephenC's answer:

This is a heck of a complicated piece of code, especially if you're not experienced in programming Java.

I executed your code, and it outputs this over and over and over and over (and over)

back at (0,0)
 01234567
0
1 Q
2  Q
3   Q
4    Q
5     Q
6      Q
7       Q
back at (0,0)

And then crashes with this

Exception in thread "main" java.lang.StackOverflowError
    at java.nio.Buffer.<init>(Unknown Source)
    ...
    at java.io.PrintStream.print(Unknown Source)
    at java.io.PrintStream.println(Unknown Source)
    at Depth.eightQueen(Depth.java:56)
    at Depth.eightQueen(Depth.java:60)
    at Depth.eightQueen(Depth.java:60)
    at Depth.eightQueen(Depth.java:60)
    at Depth.eightQueen(Depth.java:60)
    ...

My first instinct is always to add some System.out.println(...)s to figure out where stuff is going wrong, but that won't work here.

The only two options I see are to

• Get familiar with a debugger and use it to step through and analyze why it's never stopping the loop
• Break it down man! How can you hope to deal with a massive problem like this without breaking it into digestible chunks???

Not to mention that the concept of 8-queens is complicated to begin with.

---

One further thought:

System.out.println()s are not useful as currently implemented, because there's infinite output. A debugger is the better solution here, but another option is to somehow limit your output. For example, create a counter at the top

private static final int iITERATIONS = 0;

and instead of

System.out.println("[ANUMBERFORTRACING]: ... USEFUL INFORMATION ...")

use

conditionalSDO((iITERATIONS < 5), "[ANUMBERFORTRACING]: ... USEFUL INFORMATION");

Here is the function:

private static final void conditionalSDO(boolean b_condition, String s_message)  {
   if(b_condition)  {
       System.out.println(s_message);
   }
}

Another alternative is to not limit the output, but to write it to a file.

I hope this information helps you.

(Note: I edited the OP's code to be compilable.)

Answer 3

You asked for ideas on how to solve it (as distinct from solutions!) so, here's a couple of hints:

Hint #1:

If you get a StackOverflowError in a recursive program it can mean one of two things:

• your problem is too "deep", OR
• you've got a bug in your code that is causing it to recurse infinitely.

In this case, the depth of the problem is small (8), so this must be a recursion bug.

Hint #2:

If you examine the stack trace, you will see the method names and line numbers for each of the calls in the stack. This ... and some thought ... should help you figure out the pattern of recursion in your code (as implemented!).

Hint #3:

Use a debugger Luke ...

Hint #4:

If you want other people to read your code, pay more attention to style. Your indentation is messed up in the most important method, and you have committed the (IMO) unforgivable sin of ignoring the Java style rules for identifiers. A method name MUST start with a lowercase letter, and a class name MUST start with an uppercase letter.

(I stopped reading your code very quickly ... on principle.)