N-Queens Problem and Program
Explanation
N-Queens Problem
Imagine you have a chessboard of size `n x n`. Your task is to place `n` queens on this board
such that no two queens can attack each other. In chess, a queen can move any number of
squares:
- Vertically (up and down)
- Horizontally (left and right)
- Diagonally
If two queens are in the same row, column, or diagonal, they can attack each other. Our goal
is to place the queens in a way that none of them can attack the others.
How the Program Solves the Problem
The program uses a method called **backtracking** to try different placements of the
queens on the board. Let's break down the program:
1. Setup the Board
The board is represented as a 2D array of characters, where `'.'` means an empty space, and
`'Q'` means a queen.
```java
char[][] board = new char[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = '.';
```
2. Backtracking with DFS (Depth-First Search)
The program tries to place a queen in each column, starting from the first column. It checks
every row in that column to see if placing a queen there is safe.
- **If placing a queen is safe:** The program places the queen and moves to the next column.
- **If not safe:** The program tries the next row in the same column.
If all columns have queens placed safely, this is a valid solution, and the board configuration
is saved.
```java
void dfs(int col, char[][] board, List<List<String>> res) {
if (col == [Link]) {
[Link](construct(board));
return;
}
for (int row = 0; row < [Link]; row++) {
if (validate(board, row, col)) {
board[row][col] = 'Q';
dfs(col + 1, board, res);
board[row][col] = '.';
}
}
}
```
3. Validating Queen Placement
Before placing a queen, the program checks if the position is safe by making sure no other
queen is already placed in:
- The same row
- The same column
- The diagonals
```java
boolean validate(char[][] board, int row, int col) {
int duprow = row;
int dupcol = col;
// Check upper diagonal on the left side
while (row >= 0 && col >= 0) {
if (board[row][col] == 'Q') return false;
row--;
col--;
}
row = duprow;
col = dupcol;
// Check left side in the same row
while (col >= 0) {
if (board[row][col] == 'Q') return false;
col--;
}
row = duprow;
col = dupcol;
// Check lower diagonal on the left side
while (col >= 0 && row < [Link]) {
if (board[row][col] == 'Q') return false;
col--;
row++;
}
return true;
}
```
4. Constructing the Solution
When a valid configuration is found, the program converts the board into a list of strings.
Each string represents a row on the board.
```java
List<String> construct(char[][] board) {
List<String> res = new LinkedList<String>();
for (int i = 0; i < [Link]; i++) {
String s = new String(board[i]);
[Link](s);
}
return res;
}
```
5. Printing the Results
Finally, all valid configurations are printed out. For example, with `n = 4`, the output shows
all the possible ways to arrange 4 queens on a 4x4 board without any of them threatening
each other.
```java
public static void main(String args[]) {
int N = 4;
List<List<String>> queen = solveNQueens(N);
int i = 1;
for (List<String> it: queen) {
[Link]("Arrangement " + i);
for (String s: it) {
[Link](s);
}
[Link]();
i += 1;
}
}
```
Step-by-Step Example for 4-Queens
Step 1: Start with an empty 4x4 board:
....
....
....
....
Step 2: Place a queen in the first column (Column 0) in the first row:
Q...
....
....
....
Step 3: Move to the next column (Column 1) and try to place another queen.
The only safe place is row 2.
Q...
....
.Q..
....
Step 4: Move to Column 2 and place another queen.
The safe place is row 3.
Q...
....
.Q..
..Q.
Step 5: Move to Column 3 and place the last queen.
The only safe place is row 1.
Q...
..Q.
.Q..
..Q.
Conclusion
The N-Queens problem is solved by systematically trying different arrangements on the
board, backtracking when a conflict is found, and saving valid configurations. The Java
program handles this using simple loops, condition checks, and recursion.
