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

はじめに

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

数独とは

一般的には、3×3のブロックに区切られた9×9の正方形の枠内に1〜9までの数字を入れるパズルです。
ただ、Wikiを見て、正方形の大きさやブロックの区切り方が違うパターンも作れるんだなと知りました。

数独を自作する

「数独を解くプログラム」をせっかく作ったので、数独を試しに自作してみました。
「数独を解くプログラム」があれば、正解が複数存在しないことを確認できます。
「数独（ナンプレ）作って公開」というサイト（現在閉鎖）を使って数独の画像を作成しました。

ソースコード

D言語のコンパイル環境がないという方は、オンラインでD言語を実行できるサイトを利用することもできます。
rectの値を編集すれば、いろんな問題が解けます。(問題の空白部分には0を入れてください)

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でのコンパイル実行例です。

dmd -m64 -release -O sudoku.d

ldc2 -m64 -release -O sudoku.d

実行結果（正解）

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

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

関連記事