Solve a classic puzzle and see how much work pruning saves.
What to build
A backtracking program that counts the ways to place n queens, and shows the first one.
Requirements
- Place one queen in each row, trying columns from 1 to
n. - Check a position against the earlier queens before recursing.
- Count every solution, and remember the first one found.
Input
One number n.
Output
The first line has the number of solutions. The second line has the column of the queen in each row, from row 1 to row n, separated by spaces, or none if there are no solutions.
Constraints
1 ≤ n ≤ 8.
Example
Input:
4
Output:
2
2 4 1 3
Why it works
Without pruning there are nⁿ ways to place one queen per row. Checking each queen as soon as it is placed abandons a whole branch at the first clash, so only a small part of those ways are ever visited.
Examples
4
2 2 4 1 3
3
0 none
Hints
Hint 1
Place exactly one queen per row. For each row, try the columns in increasing order.
Hint 2
A new queen clashes with an earlier one when they share a column, or when the column difference equals the row difference.
Hint 3
Save the first complete placement you find, since trying columns in increasing order makes it the first in dictionary order.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
int n, solutions = 0;
int col[9], first[9];
int safe(int r, int c) {
for (int i = 0; i < r; i++)
if (col[i] == c || abs(col[i] - c) == r - i) return 0;
return 1;
}
void place(int r) {
if (r == n) {
if (solutions == 0)
for (int i = 0; i < n; i++) first[i] = col[i];
solutions++;
return;
}
for (int c = 1; c <= n; c++) {
if (safe(r, c)) {
col[r] = c;
place(r + 1);
}
}
}
int main(void) {
scanf("%d", &n);
place(0);
printf("%d\n", solutions);
if (solutions == 0) printf("none\n");
else {
for (int i = 0; i < n; i++) printf("%d ", first[i]);
printf("\n");
}
return 0;
}