はじめに

この記事では、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%)"のように指定するだけで、２次元配列をきれいに整形して表示できます。

sudoku88.d

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

関連記事