kristofer / NQueenProblem.java

// Java program to solve N Queen Problem using backtracking public class NQueenProblem { final int N = 4; // A utility function to print solution void printSolution(int board[][]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (board[i][j] == 1) System.out.print("Q "); else System.out.print(". "); } System.out.println(); } } // A utility function to check if a queen can // be placed on board[row][col]. Note that this // function is called when "col" queens are already // placeed in columns from 0 to col -1. So we need // to check only left side for attacking queens boolean isSafe(int board[][], int row, int col) { int i, j; // Check this row on left side for (i = 0; i < col; i++) if (board[row][i] == 1) return false; // Check upper diagonal on left side for (i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j] == 1) return false; // Check lower diagonal on left side for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i][j] == 1) return false; return true; } // A recursive utility function to solve N // Queen problem boolean solveNQUtil(int board[][], int col) { // Base case: If all queens are placed // then return true if (col >= N) return true; // Consider this column and try placing // this queen in all rows one by one for (int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i][col] if (isSafe(board, i, col)) { // Place this queen in board[i][col] board[i][col] = 1; // Recur to place rest of the queens if (solveNQUtil(board, col + 1) == true) return true; // If placing queen in board[i][col] // doesn't lead to a solution then // remove queen from board[i][col] board[i][col] = 0; // BACKTRACK } } // If the queen can not be placed in any row in // this column col, then return false return false; } // This function solves the N Queen problem using // Backtracking. It mainly uses solveNQUtil () to // solve the problem. It returns false if queens // cannot be placed, otherwise, return true and // prints placement of queens in the form of 1s. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. 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; } // Driver program to test above function public static void main(String args[]) { NQueenProblem Queen = new NQueenProblem(); Queen.solveNQ(); } }