Scribd
Upload
1 views

N Queens Problem Program Explanation

The N-Queens problem involves placing n queens on an n x n chessboard such that no two queens can attack each other. A Java program uses backtracking and depth-first search to explore possible placements, validating each position before placing a queen. The program constructs valid configurations and prints them, demonstrating the solution for n=4 as an example.

Uploaded by

T Naresh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1 views

N Queens Problem Program Explanation

The N-Queens problem involves placing n queens on an n x n chessboard such that no two queens can attack each other. A Java program uses backtracking and depth-first search to explore possible placements, validating each position before placing a queen. The program constructs valid configurations and prints them, demonstrating the solution for n=4 as an example.

Uploaded by

T Naresh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

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 == board.length) {
res.add(construct(board));
return;
}

for (int row = 0; row < board.length; 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 < board.length) {
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 < board.length; i++) {
String s = new String(board[i]);
res.add(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) {
System.out.println("Arrangement " + i);
for (String s: it) {
System.out.println(s);
}
System.out.println();
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.

You might also like