8x8 数独の答えになる組み合わせは何通りか

# はじめに
この記事では、8x8 数独の答えになる組み合わせが何通りあるかを調べます。

## 8x8数独の答え（一例）
![sudoku88.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/d265a3be-ccd3-4d58-a1c3-f354e718c1ae.png)

# 数独の特徴
8x8数独には以下の特徴があります。
可能というのは、数独の答えとして成立するという意味で使っています。
さらに、代表的なパターンの組み合わせを調べれば、同じだけの組み合わせが存在するという意味になります。
組み合わせを算出するための処理時間を大幅に短縮するために、これらの特徴を利用します。

## 法則１：数字は交換が可能
以下は、先ほどの答えの`1`と`8`を交換した例です。
実際には`1`～`8`の数字をどのように交換しても、答えとして成立します。
このため、代表的なパターンの組合せだけを算出すればよく、$\frac{1}{8!} = \frac{1}{40320}$に短縮できます。
![sudoku88a.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/c8ac3b6b-0724-ca2c-b35b-d5d116cb8493.png)

## 法則２：同じブロック内の行は交換が可能
具体的には`1`行目と`2`行目、`3`行目と`4`行目、`5`行目と`6`行目、`7`行目と`8`行目はそれぞれ交換可能です。
以下は、`3`行目と`4`行目を交換した例です。
それぞれのブロック行について、処理時間を$\frac{1}{2}$に短縮できます。
![sudoku88b.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/7fbb527b-3dca-eb8e-77f3-f69a39e81e0d.png)

## 法則３：同じブロック内の列は交換が可能
具体的には`1`列目から`4`列目、`5`列目から`8`列目はそれぞれ交換可能です。
以下は、`5`列目と`7`列目を交換した例です。
それぞれのブロック列について、処理時間を$\frac{1}{4!} = \frac{1}{24}$に短縮できます。
![sudoku88c.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/0b31b54a-2fae-7ac9-3430-cf06b5f5f04c.png)

## 法則４：ブロック行の交換が可能
ブロックごと交換することも可能です。
以下は`2`つ目と`3`つ目のブロック行を交換した例です。
![sudoku88d.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/59163ee9-690f-83aa-8848-af5c2e21480d.png)

## 法則５：ブロック列の交換が可能
左右のブロックを交換した例です。
![sudoku88e.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/03763e55-f8d5-881b-9e30-08be7efdd2ca.png)

# 処理時間短縮の工夫
* １行目の赤枠部分について、以下の代表的なパターンの組み合わせを算出すればよいです。（法則１により）
これにより、処理時間を$\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$通りについて、調べればよくなります。
![sudoku88f.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/c562a44c-7f3c-8b03-2347-9c1a32ad3dbb.png)

## ソースコード
これまでの話をふまえて、以下のようにソースコードを実装しました。
水色枠については、以下の条件を満たす代表的な15パターンを調べます。

* $A < C < E$ （その他の組合せは法則４を使って省略）
* $A < B$ 、 $C < D$ 、$E < F$（その他の組合せは法則２を使って省略）

組合せは[permutations関数](https://dlang.org/phobos/std_algorithm_iteration.html#.permutations)、条件での絞り込みは[filter関数](https://dlang.org/phobos/std_algorithm_iteration.html#.filter)を使ってコンパクトに記述できました。

赤枠、青枠、水色枠以外の部分は、上の行から総当たりで組み合わせを調べました。
また、7行目まで入る数字がすべて確定すると、8行目は一意に決まるので、8行目のチェックは省略しています。
これにより、処理時間を30%程度短縮できます。

その他、[writefln関数](https://dlang.org/phobos/std_stdio.html#.writefln)で出力書式を`"%(%(%d %)\n%)"`のように指定するだけで、２次元配列をきれいに整形して表示できます。

``` d: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分を切り、ソースコードもコンパクトに記述できているので、この記事はここまでにしたいと思います。

``` text:コマンドプロンプト
- 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
```

# 関連記事

https://qiita.com/devmynote/items/017ca6c32dd1e45be4b9

https://qiita.com/devmynote/items/81c4bf8ccdc836fa2bd8