N-Queen Problem using Backtracking

nqueen-problem

public class NQueenProblem {
    // size of the chess board
    final int N = 4;

    // print the board as a solution
    public void printSolution(int[][] board) {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                System.out.print(" " + board[i][j]
                                 + " ");
            System.out.println();
        }
    }

    // check if at given position, the queen is safe or not
    public boolean isSafe(int[][] board, int row, int col){
        for(int i = 0; i<col; i++) {
            if(board[row][i] == 1)
                return false;
        }

        for(int i = row, j = col; i>=0 && j>=0; i--, j--) {
            if(board[i][j] == 1)
                return false;
        }

        for(int i = row, j = col; i<N && j>=0; i++, j--) {
            if(board[i][j] == 1)
                return false;
        }
        return true;
    }

    // actual logic to solve the N-Queen problem
    boolean solveNQUtil(int[][] board, int col){
        if(col >= N)
            return true;
        
        for(int i=0; i<N; i++) {
            if(isSafe(board, i, col)) {
                board[i][col] = 1;
            
                if(solveNQUtil(board, col+1) == true)
                    return true;
                
                // backtrack in case can't find the position for Queen to place
                board[i][col] = 0;
            }
        }
        return false;
    }

    // caller method
    boolean solveNQ()
    {
        int board[][] = {{0, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 0}
        };

        if (solveNQUtil(board, 0) == false)
        {
            System.out.print("Solution does not exist");
            return false;
        }

        printSolution(board);
        return true;
    }
 
    // starting method
    public static void main(String args[])
    {
        NQueenProblem Queen = new NQueenProblem();
        Queen.solveNQ();
    }
}