数独を解くプログラム

数独にはまっている知人がいる。もう何年もDSの数独問題集をやっているというので、脳トレみたいなものかとやってみたが、人間には単純作業のように思えて苦痛だったので解法プログラム(C/C++言語)を書いてみた。

再起呼び出しによる力技で解いているが、サイズ9x9で1秒以内で解ける(Core2 Quad 2.8GHz)。サイズ25x25で約8秒。

// SUDOKU SOLVER // 2013/02/11 ToMo Star Blog #include <stdio.h> #include <stdlib.h> // http://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC #define BAN_SIZE 9 #define SQR_SIZE 3 int ban[BAN_SIZE][BAN_SIZE]= { {5,3,0,0,7,0,0,0,0}, {6,0,0,1,9,5,0,0,0}, {0,9,8,0,0,0,0,6,0}, {8,0,0,0,6,0,0,0,3}, {4,0,0,8,0,3,0,0,1}, {7,0,0,0,2,0,0,0,6}, {0,6,0,0,0,0,2,8,0}, {0,0,0,4,1,9,0,0,5}, {0,0,0,0,8,0,0,7,9} }; void print() { for(int i=0; i<BAN_SIZE; i++){ for(int j=0; j<BAN_SIZE; j++){ printf(" %d", ban[i][j]); if((j+1)%SQR_SIZE==0) printf("|"); } printf("\n"); if((i+1)%SQR_SIZE==0){ for(int j=0; j<BAN_SIZE; j++) if((j+1)%SQR_SIZE==0) printf("+"); else printf("---"); printf("\n"); } } } int empty(int* x, int* y) { for(int i=0; i<BAN_SIZE; i++) for(int j=0; j<BAN_SIZE; j++) if( ban[i][j] == 0 ){ *x = i; *y = j; return 1; } return 0; } int find_number(int x, int y, int n) { //horizontal for(int i=0; i<BAN_SIZE; i++) if( ban[i][y] == n) return 1; //vertical for(int j=0; j<BAN_SIZE; j++) if( ban[x][j] == n) return 1; //square int x0 = (x/SQR_SIZE)*SQR_SIZE; int y0 = (y/SQR_SIZE)*SQR_SIZE; for(int i=0; i<SQR_SIZE; i++) for(int j=0; j<SQR_SIZE; j++) if(ban[x0+i][y0+j] == n) return 1; //diagonal //if( x==y ) // for(int k=0; k<BAN_SIZE; k++) // if( ban[k][k] == n) // return 1; //if( BAN_SIZE-x-1==y ) // for(int k=0; k<BAN_SIZE; k++) // if( ban[BAN_SIZE-k-1][k] == n) // return 1; return 0;// not found } int solve() { int x, y; if(empty(&x,&y)){ for(int k=1; k<=BAN_SIZE; k++){ if( find_number(x,y, k)==0 ){ // not found ban[x][y] = k;//tentative if( solve() ) return 1; ban[x][y] = 0; } } return 0; }else return 1; } int solve_all() { int x, y; if(empty(&x,&y)){ for(int k=1; k<=BAN_SIZE; k++){ if( find_number(x,y, k)==0 ){ // not found ban[x][y] = k;//tentative solve_all(); ban[x][y] = 0; } } return 0; }else{ print(); return 1; } } void main() { /* if(solve()) print(); else printf("No solution!\n"); */ solve_all(); }

空いているマスを探して、可能な数字を仮に入れてみる。という処理を再帰的に呼び出す。マスにどの数字も入れられない場合は失敗なので、前に戻って仮に入れた数字を消して次候補の数字を入れてみる。マスが全部埋まれば完成。

対角線にも同じ数字がそろうようにするルールの場合は、「diagonal」のところのコメントをはずせば解けるはず(動作未確認)。

解が2つ以上ある場合は、「solve_all()」関数で全て出力してくれるはず(こちらも動作未確認)。

数独の問題を作成するアルゴリズムを考えている。人間にとってどういう問題がおもしろいと感じられるのだろう。