JAVA program to solve N Queens problem

ALGORITHM:

The N Queens problem is a classic problem which falls under various categories of algorithm design such as backtracking, brute force searching etc.

For further research on this problem use these links:

Wikipedia 

http://www.math.utah.edu/~alfeld/queens/queens.html 

http://mathworld.wolfram.com/QueensProblem.html 

 Okay, now let's comeback to the problem, N queens problem is a classic problem in which we have arrange N queens in a chessboard of dimension N*N, such that no queens should attack each other. 

A perfect solution to this problem have been a headache for mathematicians and programmers around the globe. A simple solution though not so ideal solution is posted here.

The problem is solved by a recursive backtracking algorithm the queens are placed in different optimal positions and checked whether it leads to the solution. if not the current position is backtracked and next possible position is checked.
          We start with the leftmost column and we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.

1. Start with first column
2. If all queens are placed return true
3. For the column passed to the function check every row position whether the queen can be placed safely(this is checked using a utility function named isSafe) if so the row is marked as a part of solution and recurse the function for next column. return true if it leads to solution otherwise backtrack.
4.  If all rows have been tried return false which triggers backtracking

CODE:

import java.util.Scanner;

class nQueens {
    static int[][] board;
    static int size;
    static boolean solveProblem(int col){
        if (col>size-1)
            return true;
        for (int i=0;i<size;i++){
            if(isSafe(i,col)){
                board[i][col]=1;
                if(solveProblem(col+1))
                    return true;
                board[i][col]=0;
            }
        }
        return false;
    }

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

    static void printBoard(){
        for (int i=0;i<size;i++) {
            System.out.print("\n");
            for (int j=0;j<size;j++) {
                System.out.print(board[i][j]+"\t");
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter n: ");
        size = in.nextInt();
        board = new int[size][size];
        int i,j;
        for(i=0;i<size;i++)
            for(j=0;j<size;j++)
                board[i][j]=0;
        if (solveProblem(0)) {
            printBoard();
        }
        else {
            System.out.println("No soln...");
        }
    }
}