+---+---+---+---+---+---+ | \ | | | | | / | | +---+---+---+---+---+---+ | | \ | | | / | | | +---+---+---+---+---+---+ | - | - | Q | - | - | - | +---+---+---+---+---+---+ | | / | | | \ | | | +---+---+---+---+---+---+ | / | | | | | \ | | +---+---+---+---+---+---+ | | | | | | | \ | +---+---+---+---+---+---+例えば n = 4 の場合,解は以下の2つである.
+---+---+---+---+ +---+---+---+---+ | | Q | | | | | | Q | | +---+---+---+---+ +---+---+---+---+ | | | | Q | | Q | | | | +---+---+---+---+ +---+---+---+---+ | Q | | | | | | | | Q | +---+---+---+---+ +---+---+---+---+ | | | Q | | | | Q | | | +---+---+---+---+ +---+---+---+---+
n | 解の個数 |
1 | 1 |
2 | 0 |
3 | 0 |
4 | 2 |
5 | 10 |
6 | 4 |
7 | 40 |
n | 解の個数 | 対称解を除いた個数 |
1 | 1 | 1 |
2 | 0 | 0 |
3 | 0 | 0 |
4 | 2 | 1 |
5 | 10 | 2 |
6 | 4 | 1 |
7 | 40 | 6 |
traverse(部分解 a) { if(aは解) return; forall (拡張方向 i) { if( a を i方向に拡張可能 ) { 部分解 b = aをi方向に一段階拡張した部分解; traverse(b); } } }例えば,部分解を変数n (問題サイズ), 変数k (これまで置いた駒数), 配列a (サイズkの配列で,これまでの各駒を置いた位置) に保持することにすると:
int nqueens(int n, int k, int *a) { if (n == k) return 1; else { int s = 0; int i; for (i = 0; i < n; i++) { if (extend_ok(i, n, k, a)){ /* allocate an array for a partial solution */ int *b = alloca((k + 1) * sizeof(int)); memcpy(b, a, k * sizeof(int)); b[k] = i; s += nqueens(n, k + 1, b); } } return s; } }のようにすれば,部分解(n, k, *a) (n個のうちk個を置いた部分解で, これまでのk個の位置は配列aに保持)から, 部分解 (n, k+1, *b) (k+1個目をiの位置に置くように拡張) へと拡張できる. (C言語では引数で配列を渡そうとしてもコピーされないので, 明示的にコピーしている)