|
| 1 | +/* Java program to solve N Queen Problem using |
| 2 | +backtracking */ |
| 3 | +public class NQueenProblem { |
| 4 | + final int N = 4; |
| 5 | + |
| 6 | + /* A utility function to print solution */ |
| 7 | + void printSolution(int board[][]) |
| 8 | + { |
| 9 | + for (int i = 0; i < N; i++) { |
| 10 | + for (int j = 0; j < N; j++) |
| 11 | + System.out.print(" " + board[i][j] |
| 12 | + + " "); |
| 13 | + System.out.println(); |
| 14 | + } |
| 15 | + } |
| 16 | + |
| 17 | + /* A utility function to check if a queen can |
| 18 | + be placed on board[row][col]. Note that this |
| 19 | + function is called when "col" queens are already |
| 20 | + placed in columns from 0 to col -1. So we need |
| 21 | + to check only left side for attacking queens */ |
| 22 | + boolean isSafe(int board[][], int row, int col) |
| 23 | + { |
| 24 | + int i, j; |
| 25 | + |
| 26 | + /* Check this row on left side */ |
| 27 | + for (i = 0; i < col; i++) |
| 28 | + if (board[row][i] == 1) |
| 29 | + return false; |
| 30 | + |
| 31 | + /* Check upper diagonal on left side */ |
| 32 | + for (i = row, j = col; i >= 0 && j >= 0; i--, j--) |
| 33 | + if (board[i][j] == 1) |
| 34 | + return false; |
| 35 | + |
| 36 | + /* Check lower diagonal on left side */ |
| 37 | + for (i = row, j = col; j >= 0 && i < N; i++, j--) |
| 38 | + if (board[i][j] == 1) |
| 39 | + return false; |
| 40 | + |
| 41 | + return true; |
| 42 | + } |
| 43 | + |
| 44 | + /* A recursive utility function to solve N |
| 45 | + Queen problem */ |
| 46 | + boolean solveNQUtil(int board[][], int col) |
| 47 | + { |
| 48 | + /* base case: If all queens are placed |
| 49 | + then return true */ |
| 50 | + if (col >= N) |
| 51 | + return true; |
| 52 | + |
| 53 | + /* Consider this column and try placing |
| 54 | + this queen in all rows one by one */ |
| 55 | + for (int i = 0; i < N; i++) { |
| 56 | + /* Check if the queen can be placed on |
| 57 | + board[i][col] */ |
| 58 | + if (isSafe(board, i, col)) { |
| 59 | + /* Place this queen in board[i][col] */ |
| 60 | + board[i][col] = 1; |
| 61 | + |
| 62 | + /* recur to place rest of the queens */ |
| 63 | + if (solveNQUtil(board, col + 1) == true) |
| 64 | + return true; |
| 65 | + |
| 66 | + /* If placing queen in board[i][col] |
| 67 | + doesn't lead to a solution then |
| 68 | + remove queen from board[i][col] */ |
| 69 | + board[i][col] = 0; // BACKTRACK |
| 70 | + } |
| 71 | + } |
| 72 | + |
| 73 | + /* If the queen can not be placed in any row in |
| 74 | + this column col, then return false */ |
| 75 | + return false; |
| 76 | + } |
| 77 | + |
| 78 | + /* This function solves the N Queen problem using |
| 79 | + Backtracking. It mainly uses solveNQUtil () to |
| 80 | + solve the problem. It returns false if queens |
| 81 | + cannot be placed, otherwise, return true and |
| 82 | + prints placement of queens in the form of 1s. |
| 83 | + Please note that there may be more than one |
| 84 | + solutions, this function prints one of the |
| 85 | + feasible solutions.*/ |
| 86 | + boolean solveNQ() |
| 87 | + { |
| 88 | + int board[][] = { { 0, 0, 0, 0 }, |
| 89 | + { 0, 0, 0, 0 }, |
| 90 | + { 0, 0, 0, 0 }, |
| 91 | + { 0, 0, 0, 0 } }; |
| 92 | + |
| 93 | + if (solveNQUtil(board, 0) == false) { |
| 94 | + System.out.print("Solution does not exist"); |
| 95 | + return false; |
| 96 | + } |
| 97 | + |
| 98 | + printSolution(board); |
| 99 | + return true; |
| 100 | + } |
| 101 | + |
| 102 | + // driver program to test above function |
| 103 | + public static void main(String args[]) |
| 104 | + { |
| 105 | + NQueenProblem Queen = new NQueenProblem(); |
| 106 | + Queen.solveNQ(); |
| 107 | + } |
| 108 | +} |
| 109 | + |
0 commit comments