SudokuNQueen.java

public class Main {
static final int N = 4;

// print the final solution matrix
static 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();
}
}

// function to check whether the position is safe or not
static boolean isSafe(int board[][], 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 < N; i++, j--)
if (board[i][j] == 1)
return false;

return true;
}

// The function that solves the problem using backtracking
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;

for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;

if (solveNQueen(board, col + 1))
return true;

//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}

public static void main(String args[])
{
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };

if (!solveNQueen(board, 0)) {
// Solution does not exist
System.out.println("Solution does not exist");
return;
}

printSolution(board);

}
}