数独の解法
今回は皆さんお馴染みのパズル「数独 (ナンバープレース)」の解法プログラムを作ってみましょう。
●数独とは？
数独は 9×9 の盤を用いて、縦 9 列、横 9 行のそれぞれに 1 から 9 までの数字をひとつずつ入れます。また、太線で囲まれた 3×3 の枠内にも 1 から 9 までの数字をひとつずつ入れます。ただし、縦、横、枠の中で、同じ数字が重複して入ることはありません。
パズルの解き方 [*1] ですが、基本的には次の条件を満たすマスを探して数字を確定していきます。
- 置くことができる数字がただひとつしかない場合
- 縦、横、枠の中で、数字を置くことができるマスがひとつしかない場合
(1) は簡単ですね。(2) は次の例をみてください。
置くことができる数字
--------------------------
８
Ａ [4,5,7,9]
Ｂ [4,5,7]
６
２
Ｃ [3,5,7]
１
Ｄ [4,5,9]
Ｅ [4,9]
これは縦 1 列を抜き出したものです。マス C に注目してください。C には 3, 5, 7 を置くことができるので、条件 (1) で確定することはできません。ここで縦全体を見てください。この中で、数字 3 を置くことができるのは、このマスしかありませんね。したがって、C は 3 に確定することができるのです。同じように、横の関係、枠の関係で数字を確定することができます。
条件を満たすマスを探して数字を確定していくと、そのことで新たに (1) か (2) を満たすマスが出てくるので、それを探して数字を確定していきます。これを繰り返すことで、数独を解くことができます。本ページではこれを「確定サーチ」と呼ぶことにします。数独の多くは、この確定サーチで解くことができるのですが、実はこれでは解けない難しい問題があるのです。
このような難しい問題をどうやって解くのか、M.Hiroi には見当もつきませんが、コンピュータを使えば「試行錯誤」という力技で解を見つけることができます。つまり、適当な数字を選んでマスを埋めていき、矛盾するようであれば元に戻って違う数字を選び直せばいいわけです。最近のパソコンはハイスペックなので、9 行 9 列盤の数独であれば単純なバックトラックで簡単に解くことができます。
[*1] 今回説明した数独の解き方は基本的なもので、ネットを検索すればナンプレの解法テクニックを解説したサイトがたくさん見つかると思います。
●盤面の定義
最初に盤面を定義します。次の図を見てください。
盤面を 2 次元配列 board で表します。要素は 0 から 9 までの数字です。0 が空き場所を表します。board[x][y] の x が行 (横) を、y が列 (縦) を表します。枠の左上の位置 (x1, y1) は、次の式で求めることができます。
x1 = (x / 3) * 3, y1 = (y / 3) * 3
整数の割り算なので、0, 1, 2 は 0 に、3 ,4, 5 は 1 に、6, 7, 8 は 2 になります。それに 3 を掛け算すれば、枠の左上の位置を求めることができます。
また、枠の番号 g は次の式で求めることができます。
g = (x / 3) * 3 + y / 3
y = 0 の場合、x の値で 0, 3, 6 になればいいので、(x / 3) * 3 で求めることができます。x = 0 の場合、y / 3 で 0, 1, 2 になります。あとは、これを足し算すればいいわけです。
●縦横枠のチェック
縦、横、枠で同じ数字がないかチェックするプログラムは次のようになります。
リスト : 縦、横、枠のチェック
#define N 9
// 盤面
int board[N][N];
// 横のチェック
bool check_line(int n, int x)
{
for (int i = 0; i < N; i++) {
if (board[x][i] == n) return false;
}
return true;
}
// 縦のチェック
bool check_column(int n, int y)
{
for (int i = 0; i < N; i++) {
if (board[i][y] == n) return false;
}
return true;
}
// 枠のチェック
bool check_group(int n, int x, int y)
{
int x1 = (x / 3) * 3;
int y1 = (y / 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[x1 + i][y1 + j] == n) return false;
}
}
return true;
}
// 数字をおけるかチェックする
bool check(int n, int x, int y)
{
return check_column(n, y) && check_line(n, x) && check_group(n, x, y);
}
関数 check_line は x 行目に引数 n と同じ数字があるかチェックします。関数 check_column は y 列目に引数 n と同じ数字があるかチェックします。関数 check_group は位置 (x, y) が属する枠の中で、引数 n と同じ数字があるかチェックします。関数 check は、これら 3 つの関数を呼び出して、位置 (x, y) に数字 n を置くことができれば true を返します。
●単純なバックトラックによる解法
最後に、深さ優先探索で解を求める関数 solver を作ります。
リスト : 数独の解法 (1)
void solver(int n)
{
if (n == N * N)
print_board();
else {
int x = n / N;
int y = n % N;
if (board[x][y] != 0)
solver(n + 1);
else {
for (int i = 1; i <= N; i++) {
if (check(i, x, y)) {
board[x][y] = i;
solver(n + 1);
board[x][y] = 0;
}
}
}
}
}
引数 n が N * N と等しい場合、すべてのマスに数字を置くことができました。関数 print_board で解を表示します。そうでなければ、引数 n を位置 (x, y) に変換します。board[x][y] が空き場所でなければ、solver を再帰呼び出しして次のマスをチェックします。
空き場所の場合、1 から 9 までの数字を関数 check に渡して、その数字を位置 (x, y) に置くことができるかチェックします。返り値が true の場合、board[x][y] に数字 i をセットして、solver を再帰呼び出しします。戻ってきたら board[x][y] を空き場所 (0) に戻すことをお忘れなく。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリスト１ をお読みください。
●実行例 (1)
それでは、実際に数独を解いてみましょう。
リスト : 問題 (出典: 数独 - Wikipedia の問題例)
int q00[N][N] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
$ clang -O2 numpla0.c $ ./a.out 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 0.001
ヒント (初期配置の数字) が多い問題であれば、単純な深さ優先探索でも一瞬で解を求めることができます。そこで、もう少し難しい問題を解いてみましょう。deepgreen さん が作成された ナンプレ問題集 より問題 c1, d1, e1, h1, h2, k3, k4, x2 を試してみたところ、実行時間は次のようになりました。
表 : 実行結果 問題 : Hint : 秒 ------+------+------- c1 : 22 : 0.015 d1 : 21 : 0.081 e1 : 24 : 0.015 h1 : 23 : 0.002 h2 : 24 : 0.005 k3 : 24 : 0.077 k4 : 21 : 0.193 x2 : 24 : 0.033 ------+------+------- 全体 : : 0.422 実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz 最適化オプション : -O2
どの問題も 0.2 秒未満で解くことができました。このように、9 行 9 列盤の数独は単純なバックトラックで簡単に解くことができます。このままでも十分に速いのですが、高速化する余地はまだ残っています。今回の処理で時間がかかっているのは、数字を選択する処理です。空き場所に置くことができる数字を簡単に求めることができれば、もっと速くなると思われます。
●データ構造を工夫する
そこで、空き場所に置くことができる数字をデータとして持たせることにします。置くことができる数字は、各マスごとに持たせるのが自然な考え方です。必要なときに数字を直に求めることができますし、マスに数字を置いたならば、そのマスが属している縦、横、枠のマスに対して数字を削除すればいいわけです。
この方法では、縦と横で 16 個、枠で 4 個、合計で 20 個のマスを書き換えることになります。最近のパソコンはハイスペックなので、この程度であれば高速に動作すると思いますが、もっとクールな方法が 参考文献 [1] に書かれています。それは、「縦、横、枠のそれぞれについて、置くことができる数字をビットで管理する」という方法です。今回はこの方法を採用することにします。
ビットと数字の関係は次のように定義しましょう。
bit 9 8 7 6 5 4 3 2 1 0 => 数字に対応させる
---------------------
1 1 1 1 1 1 1 1 1 0 => 0x3fe : すべての数字を置くことができる
第 0 ビットはダミーとします。置くことができる数字は対応するビットをセットし、そうでなければビットをクリアします。
縦、横、枠の状態は、配列 yflag, xflag, gflag で管理することにしましょう。次の図を見てください。
左上隅のマス◎に注目してください。縦で使われている数字は 2, 6, 9 なので、yflag[0] の値は 2 進数で表すと 0110111010 になります。横は 1, 3, 7, 8, 9 が使われているので、xflag[0] の値は 0001110100 となります。枠 gflag[0] の値は、2, 3, 8, 9 が使われているので 0011110010 となります。
マス◎に置くことができる数字は、この 3 つの状態でビットが立っている数字、つまり、ビットの論理積で求めることができます。
9876543210
----------
xflag[0] => 0110111010
yflag[0] => 0001110100
gflag[0] => 0011110010
AND ----------
0000110000
マス◎に置くことができる数字は 4, 5 であることがわかります。
このように、縦、横、枠に分けて数字を管理するため、マスに置くことができる数字は、いちいち AND 演算しなければ求めることができません。ところが、マスに数字を置くときは縦、横、枠の該当するビットをクリアするだけで済ますことができます。
●盤面とフラグの定義
それではプログラムを作りましょう。最初にデータ構造を定義します。次のリストを見てください。
リスト : データ構造の定義 // 盤面 int board[N][N]; // フラグ int xflag[N], yflag[N], gflag[N];
盤面 board の数字はビットの位置で表すことにします。空き場所は今までと同じく 0 で表します。配列 xflag, yflag, gflag は行、列、枠のフラグを格納します。フラグの初期化は関数 init_board で行います。
●フラグの操作
次はフラグを書き換える関数を作りましょう。
リスト : フラグの操作
// グループ番号を求める
int get_group(int x, int y)
{
return (x / 3) * 3 + y / 3;
}
// 数字を置く
void set_number(int n, int x, int y)
{
board[x][y] = n;
xflag[x] ^= n;
yflag[y] ^= n;
gflag[get_group(x, y)] ^= n;
}
// 数字を削除する
void del_number(int n, int x, int y)
{
board[x][y] = 0;
xflag[x] ^= n;
yflag[y] ^= n;
gflag[get_group(x, y)] ^= n;
}
関数 get_group は位置 (x, y) が属する枠の番号を求めます。関数 set_number は数字 n を board[x][y] にセットし、xflag, yflag, gflag のビットをクリアします。関数 del_number は board[x][y] を空き場所に戻し、xflag, yflag, gflag のビットをオンにします。どちらの関数も排他的論理和 (xor) を使ってビットのオンオフを行っています。
次はフラグを初期化する関数 init_board を作ります。
リスト : 盤面の初期化
void init_board(int q[][N])
{
for (int i = 0; i < N; i++)
xflag[i] = yflag[i] = gflag[i] = 0x3fe;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int n = q[i][j];
if (n == 0)
board[i][j] = n;
else
set_number(1 << n, i, j);
}
}
}
xflag, yflag, zflag はすべての数字のビットを 1 にセットした値 (0x3fe) に初期化します。次に、二重の for ループで引数 q のデータを取り出し、外部変数 board にセットします。n が 0 ならば、そのまま board にセットします。そうでなければ、1 を n ビット左へシフトして、それを set_number に渡して board とフラグの値を更新します。
次は空き場所に置くことができる数字を求める関数 get_numbers を作ります。
リスト : 置くことができる数字を求める
int get_numbers(int x, int y)
{
return xflag[x] & yflag[y] & gflag[get_group(x, y)];
}
get_numbers は簡単で、xflag, yflag, gflag の論理積を求めるだけです。
●バックトラックによる解法
最後にバックトラックで解を求める関数 solver を作ります。
リスト : 数独の解法 (2)
void solver(int n)
{
if (n == N * N)
print_board();
else {
int x = n / N;
int y = n % N;
if (board[x][y] != 0)
solver(n + 1);
else {
for (int m = get_numbers(x, y); m > 0; m &= m - 1) {
int i = m & (-m);
set_number(i, x, y);
solver(n + 1);
del_number(i, x, y);
}
}
}
}
get_numbers で置くことができる数字を求め、m & (-m) で一番右側のビットを取り出して変数 i にセットします。あとは、set_number で数字 i を書き込み、solver を再帰呼び出しします。戻ってきたら、del_number で空き場所に戻して、m &= m - 1 で一番右側のビットをクリアします。
あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト２ をお読みください。
●実行結果 (2)
実行時間は次のようになりました。
表 : 実行結果 (単位 : 秒) 問題 : Hint : (1) : (2) ------+------+-------+------- c1 : 22 : 0.015 : 0.004 d1 : 21 : 0.081 : 0.017 e1 : 24 : 0.015 : 0.003 h1 : 23 : 0.002 : 0.001 h2 : 24 : 0.005 : 0.001 k3 : 24 : 0.077 : 0.016 k4 : 21 : 0.193 : 0.042 x2 : 24 : 0.033 : 0.008 ------+------+-------+------- 全体 : : 0.422 : 0.092
実行時間はどの問題でも速くなりました。全体では約 4.6 倍速くなっているので、ビット操作の効果は十分に出ていると思います。
●確定サーチ
数独 (9 行 9 列盤) を解くだけならば、これ以上の高速化は必要ないのですが、ついでに「確定サーチ」も試してみることにしましょう。関数 init_board でヒント数字を解析したら、空き場所に対して確定サーチを行います。確定サーチで注意する点は、確定できなかったマスでも、ほかのマスで数字が決定することで、確定できる場合があることです。したがって、一度だけ調べるのではなく、数字が確定したマスがある限り、何度でも調べなければいけません。プログラムは次のようになります。
リスト : 確定サーチ + バックトラック
bool decide_number(void)
{
while (true) {
int c = decide_cell();
c += decide_line();
c += decide_column();
c += decide_group();
if (c == 0) break;
}
return is_finish();
}
void solver1(int q[][N])
{
init_board(q);
clock_t s = clock();
if (decide_number()) {
printf("finish!\n");
print_board();
} else {
printf("backtack!\n");
solver(0);
}
printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
}
関数 solver1 は solver を呼び出す前に確定サーチを行う関数 decide_number を呼び出します。decide_number の返り値が true であれば、解が見つかりました。print_board で盤面を表示します。false の場合は solver を呼び出してバックトラックで解を探します。
decide_number は while ループの中で 4 つの関数を呼び出します。decide_cell は置くことができる数字がひとつしかないマスを探します。decide_column は縦方向の中で置くことができるマスがひとつしかない数字を探します。decide_line が横方向の中で、decide_group が枠の中で数字を決定できるマスを探します。
これらの関数の返り値は確定したマスの個数です。確定したマスが一つでもあれば、確定サーチを繰り返します。確定したマスがひとつも無い場合は break で while ループを脱出して、関数 is_finish を呼び出します。is_finish は空き場所が一つでもあれば false を返し、空き場所がない (解くことができた) 場合は true を返します。
●置ける数字がひとつしかないマスを探す
次は関数 decide_cell を作ります。
リスト : 置ける数字がひとつしかないマスを探す
int decide_cell(void)
{
int c = 0;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (board[x][y] == 0) {
int n = get_numbers(x, y);
if (bit_count(n) == 1) {
set_number(n, x, y);
c++;
}
}
}
}
return c;
}
decide_cell は簡単です。二重の for ループで盤面の要素を取り出し、その値が 0 であれば、get_numbers で置くことができる数字を求めます。そして、bit_count でビット 1 の個数を求め、それが 1 であれば (x, y) に数字 n を置くことができます。set_number で数字を書き込んでから、変数 c をインクリメントします。最後に return で c を返します。
●縦横枠で置くことができる数字を探す
縦、横、枠の確定サーチはほとんど同じ処理なので、縦方向で確定できる数字を探す関数 decide_column だけ説明することにします。
リスト : 縦方向の確定サーチ
int decide_column_sub(int y)
{
int c = 0;
for (int m = yflag[y]; m > 0; m &= m - 1) {
int n = m & (-m), c1 = 0, x1;
for (int x = 0; x < N; x++) {
if (board[x][y] == 0 && get_numbers(x, y) & n) {
if (++c1 > 1) break;
x1 = x;
}
}
if (c1 == 1) {
set_number(n, x1, y);
c++;
}
}
return c;
}
int decide_column(void)
{
int c = 0;
for (int y = 0; y < N; y++)
c += decide_column_sub(y);
return c;
}
実際の処理は関数 dicide_column_sub で行います。yflag[y] から y 列目の未確定の数字を取り出して変数 m にセットします。m & (-m) で一番右側のビット (数字) を取り出して変数 n にセットします。次の for ループで、その数字を置くことができる場所の個数をカウントします。board[x][y] が空き場所 (0) で、get_numbers(x. y) と n の論理積が真であれば、n を位置 (x, y) に置くことができます。
カウント c1 をインクリメントして、それが 1 より大きくなったら、その数字はまだ決定することができません。break で for ループを脱出して次の数字を調べます。そうでなければ、x の値を変数 x1 にセットします。for ループが終了したら、c1 が 1 かチェックします。そうであれば、set_number で n を (x1, y) に書き込み、変数 c をインクリメントします。最後に return で c を返します。
あとは特に難しいところはないでしょう。詳細は プログラムリスト３ をお読みください。
●実行結果 (3)
実行時間は次のようになりました。
表 : 実行結果 (単位 : 秒)
問題 : Hint : (1) : (2) : (3)
------+------+-------+-------+-----------
c1 : 22 : 0.015 : 0.004 : 0.001
d1 : 21 : 0.081 : 0.017 : 0.000 (確)
e1 : 24 : 0.015 : 0.003 : 0.000
h1 : 23 : 0.002 : 0.001 : 0.000 (確)
h2 : 24 : 0.005 : 0.001 : 0.000 (確)
k3 : 24 : 0.077 : 0.016 : 0.000
k4 : 21 : 0.193 : 0.042 : 0.003
x2 : 24 : 0.033 : 0.008 : 0.003
------+------+-------+-------+-----------
全体 : : 0.422 : 0.092 : 0.008
(確) は確定サーチだけで解けたことを表します。実行時間は速すぎで計測不能 (0.000) な問題が多くありました。確定サーチの効果は大きいことがわかります。ただし、どのような問題でも高速に解けるわけではなく、基本的な確定サーチだけでは限界があるようです。興味のある方はいろいろ試してみてください。
なお、バックトラックを使わないで数独を解く方法もあります。興味のある方は拙作のページ Scheme Programming パズルの解法 [6] [7] をお読みください。
●参考文献
- 松田晋, 『実践アルゴリズム戦略 解法のテクニック <第11回> バックトラックによる｢数独｣の解法』, C MAGAZINE 1993 年 3 月号, ソフトバンク
●プログラムリスト１
/*
* numpla0.c : 数独の解法
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N 9
// 盤面
int board[N][N];
// 横のチェック
bool check_line(int n, int x)
{
for (int i = 0; i < N; i++) {
if (board[x][i] == n) return false;
}
return true;
}
// 縦のチェック
bool check_column(int n, int y)
{
for (int i = 0; i < N; i++) {
if (board[i][y] == n) return false;
}
return true;
}
// 枠のチェック
bool check_group(int n, int x, int y)
{
int x1 = (x / 3) * 3;
int y1 = (y / 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[x1 + i][y1 + j] == n) return false;
}
}
return true;
}
// 数字をおけるかチェックする
bool check(int n, int x, int y)
{
return check_column(n, y) && check_line(n, x) && check_group(n, x, y);
}
// 盤面の表示
void print_board(void)
{
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
printf("%d ", board[x][y]);
}
printf("\n");
}
}
// 数独の解法
void solver(int n)
{
if (n == N * N)
print_board();
else {
int x = n / N;
int y = n % N;
if (board[x][y] != 0)
solver(n + 1);
else {
for (int i = 1; i <= N; i++) {
if (check(i, x, y)) {
board[x][y] = i;
solver(n + 1);
board[x][y] = 0;
}
}
}
}
}
// 問題を board にコピー
void copy_question(int q[][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = q[i][j];
}
}
}
// 問題 (出典: 数独 - Wikipedia の問題例)
int q00[N][N] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
void test(int q[][N])
{
copy_question(q);
clock_t s = clock();
solver(0);
printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
}
int main(void)
{
test(q00);
return 0;
}
●プログラムリスト２
/*
* numpla1.c : 数独の解法
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N 9
// 盤面
int board[N][N];
// フラグ
int xflag[N], yflag[N], gflag[N];
// ビットカウント
int bit_count(unsigned int n)
{
unsigned int a = (n & 0x55555555) + ((n >> 1) & 0x55555555);
unsigned int b = (a & 0x33333333) + ((a >> 2) & 0x33333333);
unsigned int c = (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f);
unsigned int d = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff);
return (d & 0xffff) + (d >> 16);
}
// グループ番号を求める
int get_group(int x, int y)
{
return (x / 3) * 3 + y / 3;
}
// 置くことができる数字を求める
int get_numbers(int x, int y)
{
return xflag[x] & yflag[y] & gflag[get_group(x, y)];
}
// 数字を置く
void set_number(int n, int x, int y)
{
board[x][y] = n;
xflag[x] ^= n;
yflag[y] ^= n;
gflag[get_group(x, y)] ^= n;
}
// 数字を削除する
void del_number(int n, int x, int y)
{
board[x][y] = 0;
xflag[x] ^= n;
yflag[y] ^= n;
gflag[get_group(x, y)] ^= n;
}
// 盤面の表示
void print_board(void)
{
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
printf("%d ", bit_count(board[x][y] - 1));
}
printf("\n");
}
}
// 数独の解法
void solver(int n)
{
if (n == N * N)
print_board();
else {
int x = n / N;
int y = n % N;
if (board[x][y] != 0)
solver(n + 1);
else {
for (int m = get_numbers(x, y); m > 0; m &= m - 1) {
int i = m & (-m);
set_number(i, x, y);
solver(n + 1);
del_number(i, x, y);
}
}
}
}
// 初期化
void init_board(int q[][N])
{
for (int i = 0; i < N; i++)
xflag[i] = yflag[i] = gflag[i] = 0x3fe;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int n = q[i][j];
if (n == 0)
board[i][j] = n;
else
set_number(1 << n, i, j);
}
}
}
//
// 問題は省略
//
void test(int q[][N])
{
init_board(q);
clock_t s = clock();
solver(0);
printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
}
int main(void)
{
clock_t s = clock();
test(q_c1);
test(q_d1);
test(q_e1);
test(q_h1);
test(q_h2);
test(q_k3);
test(q_k4);
test(q_x2);
printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
return 0;
}
●プログラムリスト３
/*
* numpla2.c : 数独の解法 (バックトラック＋確定サーチ)
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N 9
// 盤面
int board[N][N];
// フラグ
int xflag[N], yflag[N], gflag[N];
// ビットカウント
int bit_count(unsigned int n)
{
unsigned int a = (n & 0x55555555) + ((n >> 1) & 0x55555555);
unsigned int b = (a & 0x33333333) + ((a >> 2) & 0x33333333);
unsigned int c = (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f);
unsigned int d = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff);
return (d & 0xffff) + (d >> 16);
}
// グループ番号を求める
int get_group(int x, int y)
{
return (x / 3) * 3 + y / 3;
}
// 置くことができる数字を求める
int get_numbers(int x, int y)
{
return xflag[x] & yflag[y] & gflag[get_group(x, y)];
}
// 数字を置く
void set_number(int n, int x, int y)
{
board[x][y] = n;
xflag[x] ^= n;
yflag[y] ^= n;
gflag[get_group(x, y)] ^= n;
}
// 数字を削除する
void del_number(int n, int x, int y)
{
board[x][y] = 0;
xflag[x] ^= n;
yflag[y] ^= n;
gflag[get_group(x, y)] ^= n;
}
// 盤面の表示
void print_board(void)
{
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (board[x][y] == 0)
printf("0 ");
else
printf("%d ", bit_count(board[x][y] - 1));
}
printf("\n");
}
}
// バックトラックによる解法
void solver(int n)
{
if (n == N * N)
print_board();
else {
int x = n / N;
int y = n % N;
if (board[x][y] != 0)
solver(n + 1);
else {
for (int m = get_numbers(x, y); m > 0; m &= m - 1) {
int i = m & (-m);
set_number(i, x, y);
solver(n + 1);
del_number(i, x, y);
}
}
}
}
// 初期化
void init_board(int q[][N])
{
for (int i = 0; i < N; i++)
xflag[i] = yflag[i] = gflag[i] = 0x3fe;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int n = q[i][j];
if (n == 0)
board[i][j] = n;
else
set_number(1 << n, i, j);
}
}
}
//
// 確定サーチ
//
// マス
int decide_cell(void)
{
int c = 0;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (board[x][y] == 0) {
int n = get_numbers(x, y);
if (bit_count(n) == 1) {
set_number(n, x, y);
c++;
}
}
}
}
return c;
}
// 縦
int decide_column_sub(int y)
{
int c = 0;
for (int m = yflag[y]; m > 0; m &= m - 1) {
int n = m & (-m), c1 = 0, x1;
for (int x = 0; x < N; x++) {
if (board[x][y] == 0 && get_numbers(x, y) & n) {
if (++c1 > 1) break;
x1 = x;
}
}
if (c1 == 1) {
set_number(n, x1, y);
c++;
}
}
return c;
}
int decide_column(void)
{
int c = 0;
for (int y = 0; y < N; y++)
c += decide_column_sub(y);
return c;
}
// 横
int decide_line_sub(int x)
{
int c = 0;
for (int m = xflag[x]; m > 0; m &= m - 1) {
int n = m & (-m), c1 = 0, y1;
for (int y = 0; y < N; y++) {
if (board[x][y] == 0 && get_numbers(x, y) & n) {
if (++c1 > 1) break;
y1 = y;
}
}
if (c1 == 1) {
set_number(n, x, y1);
c++;
}
}
return c;
}
int decide_line(void)
{
int c = 0;
for (int x = 0; x < N; x++)
c += decide_line_sub(x);
return c;
}
// 枠 (x, y) は左上の位置
int decide_group_sub(int x, int y)
{
int c = 0;
for (int m = gflag[get_group(x, y)]; m > 0; m &= m - 1) {
int n = m & (-m), c1 = 0, x1, y1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[x + i][y + j] == 0 && get_numbers(x + i, y + j) & n) {
if (++c1 > 1) goto end;
x1 = x + i;
y1 = y + j;
}
}
}
end:
if (c1 == 1) {
set_number(n, x1, y1);
c++;
}
}
return c;
}
int decide_group(void)
{
int c = 0;
for (int x = 0; x < N; x += 3) {
for (int y = 0; y < N; y += 3) {
c += decide_group_sub(x, y);
}
}
return c;
}
// 解けたか
bool is_finish()
{
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (board[x][y] == 0) return false;
}
}
return true;
}
// 確定サーチ
bool decide_number(void)
{
while (true) {
int c = decide_cell();
c += decide_line();
c += decide_column();
c += decide_group();
if (c == 0) break;
}
return is_finish();
}
//
// 問題は省略
//
// バックトラック＋確定サーチ
void solver1(int q[][N])
{
init_board(q);
clock_t s = clock();
if (decide_number()) {
printf("finish!\n");
print_board();
} else {
printf("backtack!\n");
solver(0);
}
printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
}
int main(void)
{
clock_t s = clock();
solver1(q_c1);
solver1(q_d1);
solver1(q_e1);
solver1(q_h1);
solver1(q_h2);
solver1(q_k3);
solver1(q_k4);
solver1(q_x2);
printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
return 0;
}
改訂 2023 年 4 月 8 日