java:8 queens using depth first search [duplicate]

Question

This question already has answers here:

java:implement 8 queen using depth first search (3 answers)

Closed 8 years ago.

I implemented depth first search for 8 queen and it works fine for empty board, but I need to modify it to accept any initial state. I modified it but it gives an error. I don't know how to correct this.

Here is my code:

public class depth {
    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");
        }
    }

    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);    
    }
}

Here is the error:

 Exception in thread "main" java.lang.StackOverflowError

It does not work for any initial state. I don't know where the problem is, and I need it to print "no solution" if it does not find any solution.

Answer 1

This code leads to a dead lock where the same function keeps getting called recursively. Method: eightQueen checks if location (i,j) is valid. In your case the first values for i and j are (0,0) respectively.

It increments j till it reaches 7 and then returns first queen position (0,0). The else loop never increments i, and all available locations are unsafe, therefore it ends up in an infinite loop.

You need to revisit the code.

Answer 2

The method eightQueen call itself indefinitely.