ホームに戻る
数独を総当りで解く
０、数独とは
数独は９×９のマスに１から９の数字を埋めるパズルです。
縦の列、横の列、３×３のグループで１〜９の数字が１つずつ入ります。
最初からいくつかの数字が入っており、空白を埋めていきます。
９×９よりマスが大きなものやアルファベットを使った変則もあります。
ここでは９×９で１〜９を埋めていく数独を考えます。
１、はじめに
数独を解くプログラムは総当りであれば簡単に作れます。
おそらく探せばすでにいくつか誰かが作っているでしょう。
今回はＣ言語を使ってコンソール上で動くものを作りました。
時間を測ってみましたが製作時間はデバック込みで３時間ほどかかりました。
さらにこのプログラムに書き足せば数独作成プログラムも作れます。
数独作成の難所は最初に置いた数字の配置について解が必ず１つになることです。
解が複数存在すると数独の問題としては不適切です。
今回作成したプログラムは解を１つ見つけると終了してしまいます。
しかし、作り変えて最後まで総当りして解がいくつあるかを調べることができます。
適当に数字を置いて、解いてみて解が１つであれば数独の問題として使えるということです。
２、アルゴリズム
９×９の左上のマスから右に向けて走査する。
右端へ来たら一段下がり左から右へ走査する。
右下のマスが埋まれば終了となる。
数字は１から９まで試すことになる。
総当りではあるが基本ルールは考慮する。
すなわち、
１、縦、横の列に同じ数字が２個以上あればアウト
２、３×３のグループのマスに同じ数字が２個以上あればアウト
また、数字を９まで試しそれでもダメならひとつ戻って１を足し再開する。
例えば、
最初のコマの数字を１とする。
縦、横、グループのチェックをしＯＫであったとする。
ひとつ右のコマに移動しこのコマの数字を１とする。
このときひとつ左のコマは１なのでアウトとなる。
よって、コマの数字を２にする。
これで縦、横、グループのチェックがＯＫであったとする。
ひとつ右のコマに移動する。
このコマで縦、横、グループのチェックを行う。
しかし、１〜９まですべてアウトであったとする。
このとき数字を０にしてひとつ左に戻る。
コマの数字を１足して３とする。
縦、横、グループのチェックを行いＯＫであったとする。
ひとつ右のコマに移動する。
ただし、考慮する点は「最初から埋まっている数字」について。
この数字は書き換えてはいけない。
よって、このマスに来たら数字を変えず次のマスに行くことにする。
３、具体的な処理
バッファを以下のようにする。
-1 はマスの外を判断するために置いてある。
0 は空白であり数字の１が入れば 1 とする。
下の例は９×９がすべて空白。
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
0, 0, 0, 0, 0, 0, 0, 0, 0,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1
コマ自身の位置を KOMA と表記する。
コマ上の番号を KOMA_NUM と表記する。
最初から数字が固定されているコマを FIXED_KOMA と表記する。
３×３のグループ内の位置情報を以下のようにする。
GROUP_LU, GROUP_U, GROUP_RU
GROUP_L, GROUP_C, GROUP_R
GROUP_LD, GROUP_D, GROUP_RD
そのコマの数字を記録するバッファ。
そのコマの数字が固定かどうかを記録するバッファ。
グループ内の位置情報を記録するバッファ。
以上の３つを用意する。
関数は、
次のコマに進む goToNextKoma を用意。
前のコマに戻る goToPreviousKoma を用意。
これらの関数はコマの数字が固定ならさらに次のコマに移動します。
コマにその数字がおけるかどうかは、
checkKoma 関数内の checkLine と checkGroup で判断します。
総当りの移動は check 関数で行います。
checkKoma がＯＫであれば goToNextKoma とし、
これが最後のマスまで着けばそれが解になり、print します。
checkKoma がＮＧであればそのままのコマで１を足して再 check となります。
もし checkKoma でＮＧであり最大の数字９であれば、
現在のコマを０に戻しひとつ前のコマに戻る必要があります。
この処理は checkMaxKomaNum 関数で行っています。
たまに checkMaxKomaNum で最初のコマ以前に戻ってしまう場合があります。
この場合は解が存在しないということになるので問題自体に不具合があるといえます。
解けるはずの問題をやるわけですから check を繰り返せば必ず最後に着きます。
４、プログラム
#include <stdio.h>
#define BUFFER_SIZE 109
#define FIRST_KOMA 10
#define LAST_KOMA 98
#define MAX_KOMA_NUM 9
#define DIRECTION_UP -10
#define DIRECTION_LEFT -1
#define DIRECTION_RIGHT 1
#define DIRECTION_DOWN 10
#define GROUP_LU 0
#define GROUP_U 1
#define GROUP_RU 2
#define GROUP_L 3
#define GROUP_C 4
#define GROUP_R 5
#define GROUP_LD 6
#define GROUP_D 7
#define GROUP_RD 8
int koma_num_buf[BUFFER_SIZE] = {
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
0, 0, 0, 0, 0, 0, 0, 0, 0,-1,
0, 5, 8, 0, 0, 0, 3, 9, 0,-1,
0, 1, 7, 6, 0, 3, 2, 4, 0,-1,
0, 0, 2, 3, 0, 1, 6, 0, 0,-1,
0, 0, 0, 0, 0, 0, 0, 0, 0,-1,
0, 0, 3, 5, 0, 4, 8, 0, 0,-1,
0, 2, 4, 9, 0, 6, 7, 1, 0,-1,
0, 7, 1, 0, 0, 0, 4, 3, 0,-1,
0, 0, 0, 0, 0, 0, 0, 0, 0,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1
};
int group_buf[BUFFER_SIZE] = {
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
GROUP_LU, GROUP_U, GROUP_RU, GROUP_LU, GROUP_U, GROUP_RU, GROUP_LU, GROUP_U, GROUP_RU, -1,
GROUP_L, GROUP_C, GROUP_R, GROUP_L, GROUP_C, GROUP_R, GROUP_L, GROUP_C, GROUP_R, -1,
GROUP_LD, GROUP_D, GROUP_RD, GROUP_LD, GROUP_D, GROUP_RD, GROUP_LD, GROUP_D, GROUP_RD, -1,
GROUP_LU, GROUP_U, GROUP_RU, GROUP_LU, GROUP_U, GROUP_RU, GROUP_LU, GROUP_U, GROUP_RU, -1,
GROUP_L, GROUP_C, GROUP_R, GROUP_L, GROUP_C, GROUP_R, GROUP_L, GROUP_C, GROUP_R, -1,
GROUP_LD, GROUP_D, GROUP_RD, GROUP_LD, GROUP_D, GROUP_RD, GROUP_LD, GROUP_D, GROUP_RD, -1,
GROUP_LU, GROUP_U, GROUP_RU, GROUP_LU, GROUP_U, GROUP_RU, GROUP_LU, GROUP_U, GROUP_RU, -1,
GROUP_L, GROUP_C, GROUP_R, GROUP_L, GROUP_C, GROUP_R, GROUP_L, GROUP_C, GROUP_R, -1,
GROUP_LD, GROUP_D, GROUP_RD, GROUP_LD, GROUP_D, GROUP_RD, GROUP_LD, GROUP_D, GROUP_RD, -1,
-1,-1,-1,-1,-1,-1,-1,-1,-1
};
int fixed_koma_buf[BUFFER_SIZE];
int getKomaNum(int index){
return koma_num_buf[index];
}
void setKomaNum(int index, int num){
koma_num_buf[index] = num;
}
int getGroup(int index){
return group_buf[index];
}
int isFixed(int index){
if(fixed_koma_buf[index] == 1){
return 1;
}
return 0;
}
int goToNextKoma(int *koma_index){
*koma_index += 1;
if(isFixed(*koma_index) == 1){
goToNextKoma(koma_index);
}
if(getKomaNum(*koma_index) < 0){
goToNextKoma(koma_index);
}
if(*koma_index == (LAST_KOMA + 1)){
return 0;
}
return 1;
}
int goToPreviousKoma(int *koma_index){
*koma_index -= 1;
if(isFixed(*koma_index) == 1){
goToPreviousKoma(koma_index);
}
if(getKomaNum(*koma_index) < 0){
goToPreviousKoma(koma_index);
}
if(*koma_index == (FIRST_KOMA - 1)){
return 0;
}
return 1;
}
int checkDirection(int index, int direction){
int i;
for(i = direction;; i += direction){
if(getKomaNum(index + i) < 0){
break;
}
if(getKomaNum(index) - getKomaNum(index + i) == 0){
return 0;
}
}
return 1;
}
int checkLine(int index){
if(!checkDirection(index, DIRECTION_LEFT))return 0;
if(!checkDirection(index, DIRECTION_UP))return 0;
if(!checkDirection(index, DIRECTION_DOWN))return 0;
if(!checkDirection(index, DIRECTION_RIGHT))return 0;
return 1;
}
int checkGroup(int index){
switch(getGroup(index)){
case GROUP_LU:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + (DIRECTION_RIGHT << 1)) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_DOWN << 1) + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + ((DIRECTION_DOWN + DIRECTION_RIGHT) << 1)) == 0)return 0;
}
break;
case GROUP_U:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_DOWN << 1) + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_DOWN << 1) + DIRECTION_RIGHT) == 0)return 0;
}
break;
case GROUP_RU:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + (DIRECTION_LEFT << 1)) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_DOWN << 1) + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + ((DIRECTION_DOWN + DIRECTION_LEFT) << 1)) == 0)return 0;
}
break;
case GROUP_L:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + (DIRECTION_RIGHT << 1)) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + (DIRECTION_RIGHT << 1)) == 0)return 0;
}
break;
case GROUP_C:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_RIGHT) == 0)return 0;
}
break;
case GROUP_R:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + (DIRECTION_LEFT << 1)) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_DOWN + (DIRECTION_LEFT << 1)) == 0)return 0;
}
break;
case GROUP_LD:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + (DIRECTION_RIGHT << 1)) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_UP << 1) + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + ((DIRECTION_UP + DIRECTION_RIGHT) << 1)) == 0)return 0;
}
break;
case GROUP_D:
{
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_UP << 1) + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_UP << 1) + DIRECTION_RIGHT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_RIGHT) == 0)return 0;
}
break;
case GROUP_RD:
{
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + DIRECTION_UP + (DIRECTION_LEFT << 1)) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + (DIRECTION_UP << 1) + DIRECTION_LEFT) == 0)return 0;
if(getKomaNum(index) - getKomaNum(index + ((DIRECTION_UP + DIRECTION_LEFT) << 1)) == 0)return 0;
}
break;
default:
break;
}
return 1;
}
int checkKoma(int index){
if(!checkLine(index))return 0;
if(!checkGroup(index))return 0;
return 1;
}
void initFixedBuf(){
int i;
for(i = FIRST_KOMA;; i++){
if(i == (LAST_KOMA + 1)){
break;
}
if(getKomaNum(i) > 0){
fixed_koma_buf[i] = 1;
}
else{
fixed_koma_buf[i] = 0;
}
}
}
void print(){
int i;
for(i = 10; i < 99; i++){
printf("%d ", koma_num_buf[i]);
if(i % 10 == 8){
i++;
printf("\n");
}
}
printf("\n");printf("\n");
}
void checkMaxKomaNum(int *index){
if(getKomaNum(*index) == MAX_KOMA_NUM){
setKomaNum(*index, 0);
goToPreviousKoma(index);
checkMaxKomaNum(index);
}
}
int check(int *index){
int num = getKomaNum(*index);
setKomaNum(*index, num + 1);
if(checkKoma(*index)){
goToNextKoma(index);
if(*index > LAST_KOMA){
print();
return 0;
}
}
else{
checkMaxKomaNum(index);
if(*index < FIRST_KOMA){
return 0;
}
}
return 1;
}
int main(){
int index = FIRST_KOMA - 1;
initFixedBuf();
goToNextKoma(&index);
while(check(&index)){}
getchar();
return 0;
}
