D言語で数独を解くプログラムを書く

# はじめに
別の[記事](#関連記事)で数独の組合せが何通りかを調べています。
その際に必要となる「数独を解くプログラム」をD言語で実装します。

# 数独とは
一般的には、3×3のブロックに区切られた9×9の正方形の枠内に1〜9までの数字を入れるパズルです。
ただ、[Wiki](https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC)を見て、正方形の大きさやブロックの区切り方が違うパターンも作れるんだなと知りました。

# 数独を自作する
「数独を解くプログラム」をせっかく作ったので、数独を試しに自作してみました。
「数独を解くプログラム」があれば、正解が複数存在しないことを確認できます。
「数独（ナンプレ）作って公開」というサイト（現在閉鎖）を使って数独の画像を作成しました。
![sudoku.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675901/6430f52e-0167-332e-daca-74a3e026f853.png)

# ソースコード
D言語のコンパイル環境がないという方は、[オンラインでD言語を実行できるサイト](https://qiita.com/devmynote/items/e9d6020fa55a1ac984dd)を利用することもできます。
`rect`の値を編集すれば、いろんな問題が解けます。(問題の空白部分には`0`を入れてください)

```d:sudoku.d
import std.datetime;
import std.stdio;

const NUM = 9;
const ROW = NUM;
const COL = NUM;
const BLOCK_ROW = 3;
const BLOCK_COL = NUM / BLOCK_ROW;
ubyte[COL][ROW] rect =
		   [[0, 2, 0, 0, 0, 0, 0, 8, 0],
			[0, 0, 6, 7, 0, 0, 1, 0, 0],
			[7, 8, 0, 0, 0, 3, 0, 0, 6],
			[0, 1, 0, 5, 0, 0, 0, 0, 0],
			[0, 0, 8, 0, 0, 1, 5, 0, 7],
			[0, 0, 0, 9, 0, 0, 3, 0, 0],
			[5, 0, 0, 0, 0, 4, 0, 3, 0],
			[0, 0, 1, 0, 0, 2, 0, 6, 0],
			[0, 3, 0, 6, 0, 0, 9, 0, 0]];
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 - 1 ){
			count++;
			writefln("answer = %d", count);
			writefln("%(%(%d %)\n%)", rect);
			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()
{
	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();
	solve(0, 0);
	long time = (Clock.currStdTime() - starttime) / 10_000;
	writefln("time   = %d ms", time);
}
```

# コンパイルコマンド例
`DMD`、`LDC`でのコンパイル実行例です。

```text:
dmd -m64 -release -O sudoku.d

ldc2 -m64 -release -O sudoku.d
```

# 実行結果（正解）
自作した問題は、正解が１つなので、以下の通りに表示されます。
正解が複数あり得る場合は、すべての正解を表示します。
また、同じ行に同じ数字があるなど、問題が不正な場合は、`Illegal initial value`と出力して、プログラムを終了します。

```text:
answer = 1
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 5 3 7 6 9 8
3 9 8 2 6 1 5 4 7
6 7 5 9 4 8 3 1 2
5 6 7 8 9 4 2 3 1
9 4 1 3 7 2 8 6 5
8 3 2 6 1 5 9 7 4
time   = 6 ms
```
# 関連記事
https://qiita.com/devmynote/items/e9d6020fa55a1ac984dd

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

https://qiita.com/devmynote/items/7e678379a014646267e8

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