It is a backtracking method to solve the problem. Basically, it is a NxN chessboard which has N queens. It should not attack each other.
Java Implementation:
- Create a public class with main() function.
- Add four functions solveNQueensPbm(),backtracking(),isItSafe(),printItBoard().
- solveNQueensPbm() – create a character array. add the data. Call the backtracking() function.
- backtracking() – it checks the row with n value and call the printItBoard() function. use for loop to perform backtracking().
- printItBoard() -It prints the board and queens value.
- ‘main()’- it creates the value for n and calls the solveNQueensPbm() to get the output.
Program:
import java.util.Arrays;
public class NQueensEg {
public static void
solveNQueensPbm(int n) {
char[][]
board1 = new char[n][n];
for (char[]
q_row : board1) Arrays.fill(q_row, '.');
backtracking(board1, 0, n);
}
private static
void backtracking(char[][] board1, int q_row, int n) {
if (q_row ==
n) {
printItBoard(board1);
return;
}
for (int q_col
= 0; q_col < n; q_col++) {
if
(isItSafe(board1, q_row, q_col, n)) {
board1[q_row][q_col] = 'Q';
backtracking(board1, q_row + 1, n);
board1[q_row][q_col] = '.';
}
}
}
private static
boolean isItSafe(char[][] board1, int q_row, int q_col, int n) {
for (int i =
0; i < q_row; i++) {
if
(board1[i][q_col] == 'Q') return false;
}
for (int i =
q_row, j = q_col; i >= 0 && j >= 0; i--, j--) {
if
(board1[i][j] == 'Q') return false;
}
for (int i =
q_row, j = q_col; i >= 0 && j < n; i--, j++) {
if
(board1[i][j] == 'Q') return false;
}
return true;
}
private static
void printItBoard(char[][] board1) {
for (char[]
q_row : board1) {
System.out.println(new String(q_row));
}
System.out.println();
}
public static void
main(String[] args) {
int n = 4;
solveNQueensPbm(n);
}
}
Output:
C:\raji\blog>javac NQueensEg.java
C:\raji\blog>java NQueensEg
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
This output has 4 columns in each row. Q refers ‘queens’. It
does not cross each other.
That’s the way, the Java Program to implement N queens
Problem was done successfully. Keep coding!!!
No comments:
Post a Comment