数独をPrologで解く

SWI-Prologを入れていろいろ遊んでます。
もともとはIchigo-JamでBASIC書いてるプログラムを、CやPrologで書いて比較するって感じでやってました（これはこれで、今後まとめます）。

ハノイの塔、8-Queen、覆面算（これはBASICで書いてない）、そしてCでは書いたことがある数独を解くプログラム。

超ナイーブに書いたところ、4X4のミニ数独は解けたけど、6X6でかなり時間がかかってしまうことが判明。9X9は多分無理！！！
　→単純に空いているところから数字入れて、入れた場所だけでチェックしてる感じ。

問題になるのは、１マス埋めるごとに、たて、横、そして周辺（ブロックになっている）の３つについて、矛盾が生じないかのチェックをしなければならないのに、していないことでした。
　しょうがないので、たて、横、ブロックのリストを全部もってまわって、埋まっている数字が重なっていないかどうかのチェックのみ入れてみました。

　これでなんとか9X9でも数秒程度で解けるようになりました。はふー。

Cだと、必然的に埋まる場所をチェックして先に値を入れていくのですが、これをPrologで実装するのは大変そうです。アルゴリズムの記述はPrologは苦手なのよね。その代わり、成立する条件だけ書けばよいわけなのですが、それだと遅すぎると。。。

いろいろ調べていたら、SWI-Prologには制約論理言語の拡張があるようでして、それを使うと、制約条件だけ記述して、探索は完全にシステム任せになるようです！

　試してみました。記述が少ない！、しかも早いぞ！！！（笑）

　まぁ、記述が楽になるのでいいのですけど、アルゴリズムの記述もプログラムの楽しみの一つですよねぇ。それがないのは、いいことなんでしょうかね？？？？

 ということで、適当に書いたプログラムを晒してみます。

check,check1,check2,check3なんてあまりに適当すぎてなんですけどね。
check,check1で、問題に数字を割り当てていて、
check2,check3で、割り当てた結果で矛盾が生じていないかどうかをチェックしています。
＃ま、みてわかるとも思えませんけど。

あ、実行結果を先につけますが、これだと、元の問題がわからないですねー。あはは。
http://www.conceptispuzzles.com/ja/index.aspx?uri=puzzle/sudoku
ここから問題を拾ってきました。

[2,4,1,3]

[1,3,2,4]

[3,1,4,2]

[4,2,3,1]

true .

[1] 111 ?- solve(6).

[2,5,4,6,3,1]

[6,1,3,5,2,4]

[4,2,6,1,5,3]

[1,3,5,2,4,6]

[5,4,1,3,6,2]

[3,6,2,4,1,5]

true .

[1] 112 ?- solve(10).

[7,4,1,3,6,8,9,2,5]

[3,2,9,7,4,5,6,8,1]

[8,6,5,1,2,9,4,7,3]

[9,8,3,4,1,7,2,5,6]

[6,5,7,2,9,3,8,1,4]

[2,1,4,5,8,6,7,3,9]

[5,9,6,8,3,2,1,4,7]

[4,3,8,6,7,1,5,9,2]

[1,7,2,9,5,4,3,6,8]

true 

------------------------

ここからがプログラム。

solve(N):-

    sudoku(N,X,Y,Z,L),

    check(X,L,[X,Y,Z,L]),

    check(Y,L,[X,Y,Z,L]),

    check(Z,L,[X,Y,Z,L]),

    maplist(writeln,X).

check([],_,_).

check([X|L],L1,ALL) :- 

    check1(X,L1,ALL),

    check(L,L1,ALL).

check1([],[],ALL).

check1([X|L],Y,[A,B,C,List]) :-

    delete(X,Y,L1),

    check2(A,List),

    check2(B,List),

    check2(C,List),

    check1(L,L1,[A,B,C,List]).

delete(X,[X|L],L).

delete(X,[Y|L],[Y|L1]):-

    delete(X,L,L1).

check2([],_):-!.

check2([X|L],L1):-

    check3(X,L1),

    check2(L,L1).

check3([],_):-!.

check3([X|L],L1):-

    var(X),!,check3(L,L1).

check3([X|L],L1):-

    delete(X,L1,L2),

    check3(L,L2).

sudoku(4,[[B11,B21,B31,B41],[B12,B22,B32,B42],[B13,B23,B33,B43],[B14,B24,B34,B44]],

       [[B11,B12,B13,B14],[B21,B22,B23,B24],[B31,B32,B33,B34],[B41,B42,B43,B44]],

       [[B11,B21,B12,B22],[B31,B41,B32,B42],[B13,B23,B14,B24],[B33,B43,B34,B44]],

       [1,2,3,4]):-

    B31 is 1,

    B22 is 3,

    B42 is 4,

    B13 is 3,

    B33 is 4,

    B24 is 2.

sudoku(6,[[B11,B21,B31,B41,B51,B61],[B12,B22,B32,B42,B52,B62],[B13,B23,B33,B43,B53,B63],

[B14,B24,B34,B44,B54,B64],[B15,B25,B35,B45,B55,B65],[B16,B26,B36,B46,B56,B66]],

       [[B11,B12,B13,B14,B15,B16],[B21,B22,B23,B24,B25,B26],[B31,B32,B33,B34,B35,B36],

[B41,B42,B43,B44,B45,B46],[B51,B52,B53,B54,B55,B56],[B61,B62,B63,B64,B65,B66]],

       [[B11,B21,B31,B12,B22,B32],[B13,B23,B33,B14,B24,B34],[B15,B25,B35,B16,B26,B36],

[B41,B51,B61,B42,B52,B62],[B43,B53,B63,B44,B54,B64],[B45,B55,B65,B46,B56,B66]],

       [1,2,3,4,5,6]):-

    B11 is 2,

    B61 is 1,

    B22 is 1,

    B52 is 2,

    B33 is 6,

    B43 is 1,

    B34 is 5,

    B44 is 2,

    B25 is 4,

    B55 is 6,

    B16 is 3,

    B66 is 5.

sudoku(10,[[B11,B21,B31,B41,B51,B61,B71,B81,B91],[B12,B22,B32,B42,B52,B62,B72,B82,B92],

[B13,B23,B33,B43,B53,B63,B73,B83,B93],[B14,B24,B34,B44,B54,B64,B74,B84,B94],

[B15,B25,B35,B45,B55,B65,B75,B85,B95],[B16,B26,B36,B46,B56,B66,B76,B86,B96],

[B17,B27,B37,B47,B57,B67,B77,B87,B97],[B18,B28,B38,B48,B58,B68,B78,B88,B98],

[B19,B29,B39,B49,B59,B69,B79,B89,B99] ],

       [[B11,B12,B13,B14,B15,B16,B17,B18,B19],[B21,B22,B23,B24,B25,B26,B27,B28,B29],

[B31,B32,B33,B34,B35,B36,B37,B38,B39],[B41,B42,B43,B44,B45,B46,B47,B48,B49],

[B51,B52,B53,B54,B55,B56,B57,B58,B59],[B61,B62,B63,B64,B65,B66,B67,B68,B69],

[B71,B72,B73,B74,B75,B76,B77,B78,B79],[B81,B82,B83,B84,B85,B86,B87,B88,B89],

[B91,B92,B93,B94,B95,B96,B97,B98,B99] ],

       [

[B11,B21,B31,B12,B22,B32,B13,B23,B33],[B14,B24,B34,B15,B25,B35,B16,B26,B36],

[B17,B27,B37,B18,B28,B38,B19,B29,B39],

[B41,B51,B61,B42,B52,B62,B43,B53,B63],[B44,B54,B64,B45,B55,B65,B46,B56,B66],

[B47,B57,B67,B48,B58,B68,B49,B59,B69],

[B71,B81,B91,B72,B82,B92,B73,B83,B93],[B74,B84,B94,B75,B85,B95,B76,B86,B96],

[B77,B87,B97,B78,B88,B98,B79,B89,B99]

       ],

       [1,2,3,4,5,6,7,8,9]):-

    B41 is 3,

    B51 is 6,

    B71 is 9,

    B22 is 2,

    B82 is 8,

    B13 is 8,

    B43 is 1,

    B63 is 9,

    B34 is 3,

    B54 is 1,

    B74 is 2,

    B94 is 6,

    B15 is 6,

    B95 is 4,

    B16 is 2,

    B36 is 4,

    B56 is 8,

    B76 is 7,

    B47 is 8,

    B67 is 2,

    B97 is 7,

    B28 is 3,

    B88 is 9,

    B39 is 2,

    B59 is 5,

    B69 is 4.

IchigoJamの変態BASIC

速度はかなり遅いIchigoJamです。8080の1Mhzより遅いような感じですからね。

ループカウンタを１０００くらい回すと１０秒近くかかります！？

そして、幾つか変態とも呼べる機能があるのです。

そのひとつが、GOTO文の飛び先に式を入れることができるという機能です。

つまり、

GOTO 100

ではなく

A=100

GOTO A

って感じで動いてしまうのです！？？

これを利用して、ハノイの塔をちょろっと書き換えます。

（リストは最後につけます）

なんとなんと、４つあったIF文がたった１つになっちゃいました！！！

この一個も頑張れば減らせそうなんですが、論理演算使ってやるのもどうかな？と思うので、やっていません。

　それにしても、手続きを記述するだけとは言え、IF文一個でハノイの塔って動いちゃうんですねぇ。あひゃひゃ。

　種明かしは、スタックフレームに、次に実行すべき行数を入れて、そこに飛んでいくっていうだけなんです。まぁ、なんかアセンブラで、飛び先を直接書き換えてジャンプするみたいな、本当に低級言語な機能だと思います（褒めてます）。

そして、似たような変態機能がまだあるので、それを使うと、もしかしたら、オセロくらいは作れるかもしれません。こっちの紹介も後日やってみようと思います。

　そうそう、IF文も減ったので、実行速度は通常版より３割か４割くらい早くなりました。でもね、お仕事でこういうプログラム書いちゃダメですよ！！！（笑）

　つーか、書いた本人以外には、理解できないこと間違いなしです！！

解析できた方は、是非とも連絡くださいませ。

10    PRINT"TOWER OF HANOI"

20    A=1:C=0

30    [4]=1000

40    INPUT"LEVEL:",B

50    [5]=B

60    [6]=0

70    [7]=2

80    [8]=1

100  IF[A*5]>1 GOTO 200

140  PRINT [A*5],":",[A*5+1],"->",[A*5+2]

150  C=C+1

160 A=A-1

170 GOTO [A*5+4]

200 [A*5+4]=300

210 A=A+1

220 [A*5]=[(A-1)*5]-1

230 [A*5+1]=[(A-1)*5+1]

240 [A*5+2]=[(A-1)*5+3]

250 [A*5+3]=[(A-1)*5+2]

260 GOTO 100

300 PRINT [A*5],":",[A*5+1],"->",[A*5+2]

310 C=C+1

320 [A*5+4]=160

330 A=A+1

340 [A*5]=[(A-1)*5]-1

350 [A*5+1]=[(A-1)*5+3]

360 [A*5+2]=[(A-1)*5+2]

370 [A*5+3]=[(A-1)*5+1]

380 GOTO 100

1000 PRINT"TOTAL:",C

1010 END

IchigoJamでプログラム書いてみた

教育用ワンボード？コンピュター、IchigoJamです。

使える言語はBASICのサブセット。変数はA-Zの26個の整数型と[0]-[99]の100個の整数型１次元配列。
　メモリは公称4kByteですが、メインが1K,そしてセーブエリアが1KX３つです。

BASIC自体が高校の頃以来なので、とても懐かしい！

そして、なぜか「ハノイの塔」を解くプログラムを書いてみた。
ハノイの塔は、Cとか再帰的呼び出しができる言語の特徴を説明するのに使われるわけなのですが、再帰っておいしいの？？って感じのBASICで書いてみます。

　とはいいつつつも、再帰以外の解法を考えるのが面倒なので、古の、再帰呼び出しを自分でコントロールするBASICプログラムです。

塔には0,1,2とIDを振って、そこに置かれる円盤は、数字のIDが付いているものとして、円盤を動かす操作をプリントすることで解法を出力することにします。たとえば、円盤１を０から２へ動かすのは

1:0->2

とします。
　できたプログラムを動かすとこんな感じです。

　

再帰的呼び出しをコントロールするのには、１次元配列をつかって、ローカルスタックフレームを作ります。
　ナイーブに作ったリストはこんな感じ。

10    PRINT"TOWER OF HANOI"

20    A=1

30    C=0

40    INPUT"LEVEL:",B

50    [5]=B

60    [6]=0

70    [7]=2

80    [8]=1

90    [9]=0

100  IF A<1 1000="" goto="" p="">

110  IF[A*5+4]=2 GOTO 500

120  IF[A*5+4]=1 GOTO 300

130  IF[A*5]>1 GOTO 200

140  PRINT [A*5],":",[A*5+1],"->",[A*5+2]

150  C=C+1

160  A=A-1

170 GOTO 100

200 [A*5+4]=1

210 A=A+1

220 [A*5]=[(A-1)*5]-1

230 [A*5+1]=[(A-1)*5+1]

240 [A*5+2]=[(A-1)*5+3]

250 [A*5+3]=[(A-1)*5+2]

260 [A*5+4]=0

270 GOTO 100

300 PRINT [A*5],":",[A*5+1],"->",[A*5+2]

310 C=C+1

320 [A*5+4]=2

330 A=A+1

340 [A*5]=[(A-1)*5]-1

350 [A*5+1]=[(A-1)*5+3]

360 [A*5+2]=[(A-1)*5+2]

370 [A*5+3]=[(A-1)*5+1]

380 [A*5+4]=0

390 GOTO 100

500 A=A-1

510 GOTO 100

1000 PRINT"TOTAL:",C

1010 END

ゲームマーケット2015

こどもの日にあったゲームマーケットです。
会場はビッグサイトの西2会場。L字型になっていてとにかく広い。前回より通路スペースやテーブルの間がゆったりしています。準備中なのでガラガラの状態がこれです。

ブースはこんな感じです。

開始３０分で会場は凄い人。かなり広いはずなのに。。。あっとう間にこんな感じ。

プレイエリアも常に回転中で、こんな感じ。

ほとんど休みなしで、他のブースはちょっとみただけで終了しちゃいました。

毎回、人数は増えているみたいです。次もこないとね。