はじめに
この記事では、8x8 数独の答えになる組み合わせが何通りあるかを調べます。
8x8数独の答え（一例）
数独の特徴
8x8数独には以下の特徴があります。
可能というのは、数独の答えとして成立するという意味で使っています。
さらに、代表的なパターンの組み合わせを調べれば、同じだけの組み合わせが存在するという意味になります。
組み合わせを算出するための処理時間を大幅に短縮するために、これらの特徴を利用します。
法則１：数字は交換が可能
以下は、先ほどの答えの1と8を交換した例です。
実際には1～8の数字をどのように交換しても、答えとして成立します。
このため、代表的なパターンの組合せだけを算出すればよく、$\frac{1}{8!} = \frac{1}{40320}$に短縮できます。
法則２：同じブロック内の行は交換が可能
具体的には1行目と2行目、3行目と4行目、5行目と6行目、7行目と8行目はそれぞれ交換可能です。
以下は、3行目と4行目を交換した例です。
それぞれのブロック行について、処理時間を$\frac{1}{2}$に短縮できます。
法則３：同じブロック内の列は交換が可能
具体的には1列目から4列目、5列目から8列目はそれぞれ交換可能です。
以下は、5列目と7列目を交換した例です。
それぞれのブロック列について、処理時間を$\frac{1}{4!} = \frac{1}{24}$に短縮できます。
法則４：ブロック行の交換が可能
ブロックごと交換することも可能です。
以下は2つ目と3つ目のブロック行を交換した例です。
法則５：ブロック列の交換が可能
左右のブロックを交換した例です。
処理時間短縮の工夫
-
１行目の赤枠部分について、以下の代表的なパターンの組み合わせを算出すればよいです。（法則１により）
これにより、処理時間を$\frac{1}{8!} = \frac{1}{40320}$に短縮できます。 -
２行目の青枠部分についても、以下の代表的なパターンの組み合わせを算出すればよいです。（法則１と法則３により）
これにより、処理時間を$\frac{1}{4!} = \frac{1}{24}$に短縮できます。 -
１列目の水色枠部分について、本来の組合せは$6! = 720$通りあります。
ただし、法則２により$\frac{1}{2^3} = \frac{1}{8}$に、法則４により、$\frac{1}{3!} = \frac{1}{6}$に短縮できます。（あわせて$\frac{1}{48}$）
結局、$6! \times \frac{1}{2^3} \times \frac{1}{3!} = 15$通りについて、調べればよくなります。
ソースコード
これまでの話をふまえて、以下のようにソースコードを実装しました。
水色枠については、以下の条件を満たす代表的な15パターンを調べます。
- $A < C < E$ （その他の組合せは法則４を使って省略）
- $A < B$ 、 $C < D$ 、$E < F$（その他の組合せは法則２を使って省略）
組合せはpermutations関数、条件での絞り込みはfilter関数を使ってコンパクトに記述できました。
赤枠、青枠、水色枠以外の部分は、上の行から総当たりで組み合わせを調べました。
また、7行目まで入る数字がすべて確定すると、8行目は一意に決まるので、8行目のチェックは省略しています。
これにより、処理時間を30%程度短縮できます。
その他、writefln関数で出力書式を"%(%(%d %)\n%)"のように指定するだけで、２次元配列をきれいに整形して表示できます。
import std.array : array;
import std.algorithm.iteration : filter, permutations;
import std.datetime;
import std.stdio;
const NUM = 8;
const ROW = NUM;
const COL = NUM;
const BLOCK_ROW = 4;
const BLOCK_COL = NUM / BLOCK_ROW;
ubyte[COL][ROW] rect;
bool[NUM][ROW] yoko;
bool[NUM][COL] tate;
bool[NUM][BLOCK_COL][BLOCK_ROW] block;
long count;
bool push(int x, int y, int n)
{
if ( yoko[y][n] == false
&& tate[x][n] == false
&& block[y / BLOCK_COL][x / BLOCK_ROW][n] == false ){
rect[y][x] = cast(ubyte)(n + 1);
yoko[y][n] = true;
tate[x][n] = true;
block[y / BLOCK_COL][x / BLOCK_ROW][n] = true;
return ( true );
}
return ( false );
}
void pop(int x, int y, int n)
{
rect[y][x] = 0;
yoko[y][n] = false;
tate[x][n] = false;
block[y / BLOCK_COL][x / BLOCK_ROW][n] = false;
}
bool next(ref int x, ref int y)
{
if ( x == COL - 1 ){
if ( y == ROW - 2 ){
count++;
return ( false );
} else {
x = 0;
y++;
}
} else {
x++;
}
return ( true );
}
void solve(int x, int y)
{
if ( rect[y][x] > 0 ){
if ( next(x, y) ){
solve(x, y);
}
return;
}
for ( int n = 0; n < NUM; n++ ){
if ( push(x, y, n) ){
int x0 = x;
int y0 = y;
if ( next(x, y) ){
solve(x, y);
}
x = x0;
y = y0;
pop(x, y, n);
}
}
}
void main()
{
rect = [[1, 2, 3, 4, 5, 6, 7, 8],
[5, 6, 7, 8, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]];
for ( int y = 0; y < ROW; y++ ){
for ( int x = 0; x < COL; x++ ){
if ( rect[y][x] > 0 ){
if ( push(x, y, rect[y][x] - 1) == false ){
writeln("Illegal initial value");
return;
}
}
}
}
long starttime = Clock.currStdTime();
int group;
auto arrays = [2, 3, 4, 6, 7, 8].permutations.filter!(
a => a[0] < a[2] && a[2] < a[4] && a[0] < a[1] && a[2] < a[3] && a[4] < a[5]);
foreach ( a; arrays ){
auto arr = a.array;
for ( int y = 2; y < ROW; y++ ){
push(0, y, arr[y - 2] - 1);
}
group++;
writefln("- group %02s -\n%(%(%d %)\n%)", group, rect);
long startCount = count;
solve(0, 0);
long time = (Clock.currStdTime() - starttime) / 10_000;
writefln("time = %,3d ms", time);
writefln("count = %,3d", count - startCount);
for ( int y = 2; y < ROW; y++ ){
pop(0, y, arr[y - 2] - 1);
}
}
writefln("sub total = %,3d", count);
writefln("total = %,3d", count * 24 * 48 * 40320);
}
実行結果（答え）
実行の結果、8x8の数独の答えになる組み合わせは、29,136,487,207,403,520通りであることがわかりました。
処理時間は、およそ282秒にまで短縮できました。
まだまだ時間短縮できるネタはありますが、処理時間が5分を切り、ソースコードもコンパクトに記述できているので、この記事はここまでにしたいと思います。
- group 01 -
1 2 3 4 5 6 7 8
5 6 7 8 0 0 0 0
2 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
time = 18,161 ms
count = 39,675,696
・・・省略・・・
- group 15 -
1 2 3 4 5 6 7 8
5 6 7 8 0 0 0 0
2 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0
time = 282,521 ms
count = 44,614,848
sub total = 627,283,968
total = 29,136,487,207,403,520
関連記事