有効な数独盤面には解が1つだけあります。各行・各列・3 × 3 のボックスに 1 から 9 までの数字がそれぞれ一度だけ現れるよう、空欄を盤面上で埋めます。
アプローチ
各行・各列・各ボックスについて、すでに使われている数字を9ビットのマスクで記録します。ビット d は数字 d + 1 を表し、ビットが立っていればその数字は配置できません。したがって、空欄に置ける数字は、全ビットのマスクのうち対応する行・列・ボックスのいずれのマスクにも含まれていないビットです。
各再帰ステップで残りの空欄を調べ、候補数字が最も少ないマスを選びます（最小残余値、MRV）。制約の強いマスを先に選ぶことで、分岐数を早い段階で減らせます。候補がないマスがあれば、その探索経路は失敗です。そうでなければ候補を一つずつ試します。盤面に数字を書き込み、対応する3つのマスクのビットを立ててから再帰します。失敗した経路ではビットを消し、マスを '.' に戻します。成功した場合はすぐに返るため、完成した盤面が入力に残ります。
空欄は最大81個で、最悪の場合の探索時間は指数時間です（各空欄で最大9通り）。MRVにより矛盾を早く検出し、分岐を絞ることで実際の探索を効率化します。補助領域は再帰スタックと固定サイズのマスクを合わせて O(81) で、盤面はその場で更新します。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution {
private static final int FULL = (1 << 9) - 1;
private char[][] board;
private final int[] rows = new int[9];
private final int[] columns = new int[9];
private final int[] boxes = new int[9];
public void solveSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
rows[i] = 0;
columns[i] = 0;
boxes[i] = 0;
}
this.board = board;
for (int row = 0; row < 9; row++) {
for (int column = 0; column < 9; column++) {
char cell = board[row][column];
if (cell != '.') {
int bit = 1 << (cell - '1');
int box = (row / 3) * 3 + column / 3;
rows[row] |= bit;
columns[column] |= bit;
boxes[box] |= bit;
}
}
}
solve();
}
private boolean solve() {
int bestRow = -1;
int bestColumn = -1;
int bestCandidates = 0;
int fewestChoices = 10;
for (int row = 0; row < 9; row++) {
for (int column = 0; column < 9; column++) {
if (board[row][column] != '.') {
continue;
}
int box = (row / 3) * 3 + column / 3;
int candidates = FULL & ~(rows[row] | columns[column] | boxes[box]);
int choices = Integer.bitCount(candidates);
if (choices < fewestChoices) {
bestRow = row;
bestColumn = column;
bestCandidates = candidates;
fewestChoices = choices;
if (choices <= 1) {
break;
}
}
}
if (fewestChoices <= 1) {
break;
}
}
if (bestRow == -1) {
return true;
}
if (bestCandidates == 0) {
return false;
}
int box = (bestRow / 3) * 3 + bestColumn / 3;
while (bestCandidates != 0) {
int bit = bestCandidates & -bestCandidates;
bestCandidates -= bit;
int digit = Integer.numberOfTrailingZeros(bit);
board[bestRow][bestColumn] = (char) ('1' + digit);
rows[bestRow] |= bit;
columns[bestColumn] |= bit;
boxes[box] |= bit;
if (solve()) {
return true;
}
rows[bestRow] &= ~bit;
columns[bestColumn] &= ~bit;
boxes[box] &= ~bit;
board[bestRow][bestColumn] = '.';
}
return false;
}
}