The 8 Queens Problem: A Backtracking Approach

Felipe B. Mourão, João Vitor de Alencar1

1
University of the Region of Joinville (UNIVILLE)
Joinville – SC – Brazil
felipemourao@univille.br, joaoalencar@univille.br

Abstract. The 8 queens problem is a classic chess challenge that involves po-
sitioning 8 queens on an 8 × 8 board such that no queen attacks another. In
this article, we thoroughly explore this problem, discussing its formulation, its
relevance in search algorithm studies, and present a practical implementation
based on the backtracking technique. The problem serves as an excellent didac-
tic example in computer science courses.
Resumo. The 8 queens problem is a classic challenge that involves positioning
8 queens on a chessboard so that none can attack another. This article explores
the problem’s formulation, its importance in algorithm studies, and presents a
practical implementation using backtracking techniques.

1. Introduction
The 8 queens problem was first proposed by Max Bezzel in 1848 and has since attracted
the interest of mathematicians, computer scientists, and logic enthusiasts. The simplicity
of its formulation contrasts with the complexity involved in finding all possible solutions,
making it a classic example for applying algorithmic techniques such as backtracking.
In chess, a queen can move any number of squares horizontally, vertically, or
diagonally. Therefore, when positioning multiple queens on a board, it is necessary to
ensure that none is under threat from another.
This problem is frequently used to illustrate search techniques, recursion, opti-
mization, and computational complexity.

2. Problem Description
The objective is to find all possible configurations in which 8 queens can be placed on an
8×8 board without any mutual threats. For a solution to be valid, the following conditions
must be met:
• No two queens may occupy the same row.
• No two queens may occupy the same column.
• No two queens may occupy the same diagonal (primary or secondary).
This problem can be generalized to an N × N board, known as the N queens
problem.

3. Solution Algorithm
The most common solution to the 8 queens problem is the application of the backtracking
technique. The idea is to place queens row by row, ensuring that each new queen is in a
safe position relative to the previous ones. If a row has no valid position, the algorithm
backtracks to the previous row and tries a new position.
 3.1. Algorithm Pseudocode
function solve(board, row):
if row >= 8:
display board
return
for each column from 0 to 7:
if position (row, column) is valid:
place queen at (row, column)
solve(board, row + 1)
remove queen from (row, column)

3.2. Position Validation

Checking the validity of a position involves three main conditions: - no other queen may
be in the same column; - none may be on the primary diagonal (row minus column differ-
ence equal); - none may be on the secondary diagonal (row plus column sum equal).

3.3. Solution Search

The algorithm recursively explores all valid board configurations. Each solution found
can be stored or displayed.

4. Implementation
Below, we present a Java implementation that uses the backtracking algorithm to solve the
8 queens problem. The core idea of the algorithm is to place one queen per row, verifying
whether the chosen position is valid—that is, it does not conflict with previously placed
queens. The search proceeds recursively until all 8 queens are safely positioned on the
board.
The main function initializes the board and shuffles the row order based on a seed,
ensuring test reproducibility:
1 public static void main(String[] args) {
2 long seed;
3 if (args.length > 0) {
4 seed = Long.parseLong(args[0]);
5 } else {
6 seed = System.currentTimeMillis();
7 System.out.println("Generated seed: " + seed);
8 }
9
10 List<Integer> rows = new ArrayList<>();
11 for (int i = 0; i < 8; i++) rows.add(i);
12 Collections.shuffle(rows, new Random(seed));
13
14 List<int[]> solution = solve(0, new ArrayList<>(), rows);
15
16 if (solution != null) {
17 printBoard(solution);
18 } else {
19 System.out.println("No solution found.");
20 }
21 }
 The solve function recursively explores all possible valid positions for the
queens using backtracking:
1 private static List<int[]> solve(int rowIdx, List<int[]>
2 placedQueens, List<Integer> rowOrder) {
3 if (rowIdx == 8) {
4 return new ArrayList<>(placedQueens);
5 }
6
7 int currentRow = rowOrder.get(rowIdx);
8
9 for (int col = 0; col < 8; col++) {
10 int[] pos = {currentRow, col};
11 if (isValid(pos, placedQueens)) {
12 placedQueens.add(pos);
13 List<int[]> solution = solve(rowIdx + 1,
14 placedQueens, rowOrder);
15 if (solution != null) return solution;
16 placedQueens.remove(placedQueens.size() - 1);
17 }
18 }
19
20 return null;
21 }

The validity check is performed by the isValid function, ensuring no queen can
attack another:
1 private static boolean isValid(int[] pos, List<int[]>
2 placedQueens) {
3 int newRow = pos[0];
4 int newCol = pos[1];
5
6 for (int[] queen : placedQueens) {
7 int existingRow = queen[0];
8 int existingCol = queen[1];
9
10 if (newCol == existingCol ||
11 Math.abs(newRow - existingRow) == Math.abs(newCol -
12 existingCol)) {
13 return false;
14 }
15 }
16 return true;
17 }

The final board with the solution is displayed, marking queen positions with R:
1 private static void printBoard(List<int[]> solution) {
2 char[][] board = new char[8][8];
3 for (char[] row : board) Arrays.fill(row, ’.’);
4
5 for (int[] queen : solution) {
6 board[queen[0]][queen[1]] = ’R’;
7 }
8
 9 for (char[] row : board) {
10 for (char cell : row) {
11 System.out.print(cell + " ");
12 }
13 System.out.println();
14 }
15 }

5. Results
Below is an example of the program’s output, representing a valid solution:
. . . . R . . . . . R . . . . . . . . . R . . .
. . . . . . R . R . . . . . . . R . . . . . . .
. . R . . . . . . . . . . . R . . . . . . . . R
. . . . . R . . . . . . R . . . . . . . . R . .
R . . . . . . . . . . . . . . R . . R . . . . .
. R . . . . . . . R . . . . . . . . . . . . R .
. . . R . . . . . . . R . . . . . R . . . . . .
. . . . . . . R . . . . . R . . . . . R . . . .
Additionally, the program can be configured to display all 92 valid solutions for
the 8 queens problem.

6. Computational Complexity
The simplest version of the backtracking algorithm for the N queens problem has expo-
nential time complexity, approximately O(N !), as it tries all possible queen permutations
across columns. Additional techniques, such as branch pruning and heuristics, can im-
prove performance, especially for larger values of N .

7. Number of Solutions for Different N

The table below shows the total number of solutions for different board sizes:

Table 1. Number of valid solutions for N queens

N Number of Solutions
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
 8. Conclusion
More than a simple logic puzzle, the 8 queens problem offers a rich opportunity to apply
fundamental computer science techniques. Through recursion and backtracking, efficient
solutions can be explored even within a vast search space. Furthermore, the problem
serves as a foundation for advanced studies in optimization, genetic algorithms, CSPs,
and other artificial intelligence techniques.

References
[1] Knuth, D. E. (1992). The Art of Computer Programming, Volume 4: Generating All
Tuples and Permutations. Addison-Wesley.
[2] Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the
Theory of NP-Completeness. W. H. Freeman.
[3] Russell, S. J., & Norvig, P. (2010). Artificial Intelligence: A Modern Approach. 3rd ed.
Prentice Hall.
[4] Norvig, P. (1995). Paradigms of Artificial Intelligence Programming: Case Studies in
Common Lisp. Morgan Kaufmann.
[5] Dahl, O.-J., Dijkstra, E. W., & Hoare, C. A. R. (1972). Structured Programming. Aca-
demic Press, London. ISBN 0-12-200550-3, pp. 72–82.