Lesson 19 · 19 of 20
Recursion and backtracking · C
Solve the N-queens problem in C with recursion and backtracking: try an option, carry on, and undo it when it leads nowhere.
The N-queens problem is to place N queens on an N×N board so that none attacks another: not in the same row, column or diagonal. Since each row holds exactly one queen, it is enough to store in col[r] the column of the queen in row r.
safe checks whether a queen can go in column c of row row by looking only at the rows above. There is an attack if they share a column (col[r] == c) or a diagonal: on a diagonal, the distance between columns equals the distance between rows, abs(col[r] - c) == row - r.
place is recursive and uses backtracking: it tries each column of the current row; if it is safe, it places the queen and calls itself for the next row. When that call returns, whether it found something or not, the loop moves on to the next column and col[row] is overwritten: that undoes the choice with no extra code.
The base case is row == N: every row has a queen, so it is a solution. All of them are counted and only the first is drawn. With 6 queens there are 4 solutions; with 8, the chessboard, there are 92.
Backtracking works for any "choose, check and step back" problem: sudokus, mazes, timetables or permutations. Branches that are not safe are abandoned early, which is why it is far faster than trying every combination.
Code · main.c
#include <stdio.h>#include <stdlib.h>#define N 6int col[N], solutions = 0; // col[r]: the column of the queen in row r// Can a queen go at (row, c) without attacking the rows above?int safe(int row, int c) { for (int r = 0; r < row; r++) if (col[r] == c || abs(col[r] - c) == row - r) return 0; // column or diagonal return 1;}void place(int row) { if (row == N) { // all rows filled: a solution if (++solutions == 1) // draw only the first one for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) printf(c == col[r] ? " Q" : " ."); printf("\n"); } return; } for (int c = 0; c < N; c++) if (safe(row, c)) { col[row] = c; // try this column... place(row + 1); // ...solve the rest recursively... } // ...and backtrack: the loop tries the next one}int main(void) { place(0); printf("%d queens on a %dx%d board: %d solutions\n", N, N, N, solutions); return 0;}Output · cc main.c -o main && ./main
. Q . . . . . . . Q . . . . . . . Q Q . . . . . . . Q . . . . . . . Q . 6 queens on a 6x6 board: 4 solutions
Key points
- Recursion: a function that calls itself on a smaller problem.
- There must always be a base case that stops it.
- Backtracking: choose, go on, undo the choice.
- Dropping impossible branches early saves almost all the work.
Exercise
Set N to 8 and check that you get 92 solutions; then also count how many times safe is called and compare it with the 8⁸ ways of putting one queen in each row.