The N-Queens problem is the challenge of placing N chess queens on an N×N chessboard such that no two queens threaten each other. A valid solution requires that no two queens share the same row, column, or diagonal. It is a classic backtracking problem: we place queens one row at a time, and whenever a placement leads to a conflict, we backtrack and try the next column. For N=4 there are 2 solutions; for N=8 there are 92.
N-Queens Problem Implementation in Java
import java.io.*;
class NQueens {
// queenPositions[row] = column where the queen is placed in that row (1-indexed)
int[] queenPositions = new int[20];
/**
* Attempts to place queens from the given row onward.
* Tries every column for the current row; recurses when a safe placement is found.
*
* @param currentRow the row currently being filled (1-indexed)
* @param boardSize total number of rows/columns (N)
*/
void placeQueens(int currentRow, int boardSize) {
for (int col = 0; col < boardSize; col++) {
if (isSafePlacement(currentRow, col)) {
queenPositions[currentRow] = col;
if (currentRow == boardSize) {
// All queens placed successfully -- display the solution
printBoard(queenPositions, boardSize);
} else {
// Move on to place the queen in the next row
placeQueens(currentRow + 1, boardSize);
}
}
}
}
/**
* Checks whether placing a queen at (currentRow, candidateCol) is safe.
* A placement is safe if no previously placed queen shares the same column
* or diagonal.
*
* @param currentRow row being examined
* @param candidateCol candidate column for the queen
* @return 1 if safe, 0 if conflict exists
*/
int isSafePlacement(int currentRow, int candidateCol) {
for (int prevRow = 1; prevRow <= currentRow - 1; prevRow++) {
// Same column conflict
if (queenPositions[prevRow] == candidateCol) return 0;
// Diagonal conflict: |col difference| == |row difference|
if (Math.abs(queenPositions[prevRow] - candidateCol) ==
Math.abs(prevRow - currentRow)) return 0;
}
return 1;
}
/**
* Prints a chessboard representation of one complete solution.
* 'Q' marks a queen; '*' marks an empty cell.
*
* @param queenPositions column positions of queens for each row (1-indexed)
* @param boardSize size of the board (N)
*/
void printBoard(int[] queenPositions, int boardSize) {
char[][] board = new char[boardSize + 1][boardSize + 1];
// Fill the entire board with empty markers
for (int row = 0; row <= boardSize; row++)
for (int col = 0; col <= boardSize; col++)
board[row][col] = '*';
// Place queen markers at the correct positions
for (int row = 1; row <= boardSize; row++)
board[row - 1][queenPositions[row]] = 'Q';
// Print the board
for (int row = 0; row < boardSize; row++) {
for (int col = 0; col < boardSize; col++)
System.out.print(" " + board[row][col]);
System.out.println();
}
System.out.println("-----------------------------------");
}
}
class NQueensMain {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the number of queens (N):");
int boardSize = Integer.parseInt(reader.readLine());
NQueens queens = new NQueens();
queens.placeQueens(1, boardSize); // start placing from row 1
}
}
How the Code Works
queenPositions[row]records which column the queen in a given row is placed in. The array is shared across all recursive calls so it always reflects the current partial solution.placeQueens(currentRow, boardSize)loops through allboardSizecolumns forcurrentRow. IfisSafePlacement()returns safe, the column is recorded and the method recurses into the next row.isSafePlacement()checks two conditions against every already-placed queen in rows 1 throughcurrentRow-1: (a) same column, and (b) diagonal — two queens are on the same diagonal if their absolute column difference equals their absolute row difference.- Base case: when
currentRow == boardSize, all N queens are placed successfully.printBoard()is called to display this solution. - Backtracking: if no column in a row passes the safety check, the loop simply ends for that row and execution returns to the previous recursive call, which tries the next column.
Sample Output
Enter the number of queens (N):
4
* Q * *
* * * Q
Q * * *
* * Q *
-----------------------------------
* * Q *
Q * * *
* * * Q
* Q * *
-----------------------------------
Output Explanation
- For N=4 there are exactly 2 distinct solutions.
- Solution 1: queens at columns (row1=1, row2=3, row3=0, row4=2). No two queens share a row, column, or diagonal.
- Solution 2: queens at columns (row1=2, row2=0, row3=3, row4=1). Again fully non-threatening.
- Each solution is separated by a dashed line. The algorithm finds solutions in lexicographic order of queen column positions.
See Also
- Graph Coloring Algorithm in Java
- Implementing 0-1 Knapsack in Java
- Implementing Greedy (Fractional) Knapsack in Java
- Implementing Merge Sort Algorithm in Java
- Java Program for Longest Common Subsequence (LCS)
Conclusion
The N-Queens problem is the definitive introductory backtracking exercise. Its structure neatly illustrates the “try, check, recurse, undo” pattern that underpins all backtracking algorithms. With N=8 there are 92 solutions, and for larger N the solution count grows rapidly. Try extending the program to count solutions without printing them, or to find only the first solution using an early return.