Entries

数独を解くプログラムを書いてみた。

コンピュータでパズルを解く」なんてことはもはやよくあることと化している世の中ですが、その中でも特によくネタにされるものとしては数独(ナンバープレイス)があるでしょう。実際、コンピュータを用いて問題を生成する取り組みは数多くあります。例えば、

数字を入れたい位置を指定したらそれに見合った問題を自動生成するよ! JavaだからOSを問わず遊べるね☆

スパコンを駆使して超難易度の数独作ったぜ、ワイルドだろぉ~? →やってみたら簡単だったorz

HSPでスマホ用アプリが作れる? よっしゃ数独アプリ作るか→割と面白い

などなど。ということで私も、数独を解くプログラムを自作してみることにしました。


○Webページを参考に試行錯誤

 とは言っても、何もないところから良いプログラムは生まれません。「先達はあらまほしきことなり」と誰かが言っていましたし、「車輪の再発明」という言葉もあります。で、色々ググっていると、面白いページを見つけました。

http://www2.tokai.or.jp/deepgreen/shortnotes/numberplace/algorithm.htm

 ……なにこれヤバイ。マジヤバ。
 何がヤバイかって、その解法が洗練されていること。よくある「普通の解き方」(行・列・ブロックで入らない候補数字を消しておく、n国同盟等)のエッセンスをたった6つの要素にまとめてしまうというその発想が凄い。大雑把にまとめると、
 ・Sbitサーチ(候補数字が1つだけのマスはその数字に確定)
 ・Ubitサーチ(行・列・ボックス内である数字がある1つのマスにしか入らない場合、その数字はそこで確定)
 ・InterSection(行・列・ボックスで交差する場合の処理)
 ・Enclosure(n国同盟)
 ・Exclosure(n国同盟)
 ・Negation(背理法)
といったところです。で、実際に使ってみると、難問もビシバシ撃破できるところが素晴らしい(「世界一難しい数独」レベルだと、流石にNegationを2段積まないと無理だったけど)。ま、n国同盟をゴリゴリ計算で出せたらそりゃ強いでしょと。
 自分が実装したコードはちょっと見せられませんが(汚い実装だという意味で)、興味がある方は自力で組んでみてはいかがでしょうか? Enclosureを多段forループ無しで作るのは難しいですよ(ボソッ

 ぶっちゃけバックトラックで組んだ方が手っ取り早かった件


↓自力で組んだEnclosure関数。modeが当該ページ上のnね。
/* Enclosure(number, mode) */
/* 場合分けせず、modeの値に応じて動的に処理する */
int Enclosure(int number[][NUM_MAX], int mode){
int flg = 0, temp[NUM_MAX], *pos, i, j, k, sum, chk, tmp;
pos = (int *)malloc(sizeof(int) * mode);
for(k = 0; k < mode; k++)
pos[k] = k;
while(1){
/* OR操作 */
for(k = 0; k < NUM_MAX; k++)
temp[k] = number[pos[0]][k];
for(i = 0; i < NUM_MAX; i++){
for(j = 1; j < mode; j++)
temp[i] |= number[pos[j]][i];
}
/* 候補数字数を数える */
sum = 0;
for(k = 0; k < NUM_MAX; k++)
sum += temp[k];
/* 分岐 */
if(sum < mode){
/* 解なし */
return -1;
}else{
if(sum == mode){
/* 反映 */
for(i = 0; i < NUM_MAX; i++){
chk = 0;
for(k = 0; k < mode; k++){
if(pos[k] == i){
chk = 1;
break;
}
}
if(chk == 0){
for(k = 0; k < NUM_MAX; k++){
if((temp[k] == 1) && (number[i][k] == 1)){
number[i][k] = 0;
if(flg == 0)
flg = 1;
}
}
}
}
}
}
/* 次の組み合わせへと移動 */
chk = 0;
for(i = mode - 1; i > -1; i--){
if(pos[i] == i - mode + NUM_MAX){
if(i == 0){
chk = 1;
break;
}
continue;
}
tmp = pos[i] + 1;
for(j = i; j < mode; j++){
pos[j] = tmp;
tmp++;
}
break;
}
if(chk == 1)
break;
}
free(pos);
return flg;
}

関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/42-a1e86e52

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

10 ≪│2017/11│≫ 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: