JAPL 研究会資料 2006/1/28
数独（
SUDOKU）パズルを J で解く
－
Labs システムによる Hui のプログラムのトレース－
Solving SUDOKU Puzzle in J
－
Hui’s Program Tracing in Labs System－
西川 利男
Toshio.Nishikawa@kiu.ne.jp
数独（
SUDOKU）パズルに筆者が親しむようになったのは次のようないきさ
つからである。昨年１０月の初め、山下紀幸氏から“数独について知りません
か？”との
FAX メールが入った。その後二、三日して読売新聞紙上(2005/10/15)
で数独パズルが紹介された。ところが、筆者の妻はもっと以前に毎日新聞でや
っ た こ と が あ る と 言 っ て い る 。 後 に 山 下 氏 に よ り 毎 日 新 聞 で の 紹 介 記 事
(2005/10/7)も送られてきた。
次なる大きなきっかけは、中野嘉弘氏から最近の
Vector 誌に R. Hui により
数独パズルを解く
J のプログラムが載っている[1]との知らせとともに、論文コ
ピーが送られてきた。
同時に山下氏からはニコリ社の「数独２１」なる問題・
解答集も贈られた。
筆者が「
Excel による数独の楽しみ」なる小文を読売新聞社に投稿し、昨年暮、
JAPLA シンポジウムで「Ｊによる数独パズル」を発表したのは[2]、このような
動機からである。
Hui による数独パズルの解を求める J のプログラムはコンパクトで強力であ
る。筆者にとってプログラムは分かり易いものではなかったが、おおよその流
れはつかめた。また、最新版の
J5 でしか動かない原始関数などを一部手直し、
J4, J3, さらには DOS 版の JPC でも動くようにした。
今回の発表は
Hui のプログラムを解説するというより、J の Labs システム上
でプログラム実行の流れをデモとして紹介する。
[1] Roger Hui, “A Sudoku Solver in J”, Vector, vol 21, No.4, p.49 (2005). [2] 西川利男「J のオブジェクト指向プログラミング(OOP)」
JAPLA シンポジウム資料、2005/12/10 (2005). その１－J の OOP とは
（以下は
Labs システムの実行文書である）
--- Lab: Explain Hui's SUDOKU Program Author: Explained by T. Nishikawa Originally programmed by R. Hui Press <Ctrl+A> to advance. -- (1 of 35) Introduction --- さあ、これから数独パズルをやってみましょう！ 問題は読売新聞に出された例です。 ) load 'user\nhui_sud.js' see ym +---+---+---+ |.5.|7.1|.4.| |7.3|...|1.2| |.8.|4.6|.9.| +---+---+---+ |9.4|.6.|8.3| |...|8.7|...| |1.8|.5.|6.9| +---+---+---+ |.1.|6.3|.8.| |5.6|...|7.1| |.3.|5.9|.2.| +---+---+---+ -- (2 of 35) Introduction (continued) --- 数独とは、空いたセルを次のルールにしたがい、 つぎつぎに数字で埋めていくパズルです。 「ヨコに同じ数字があってはならない」 「タテに同じ数字があってはならない」 「ブロック内に同じ数字があってはならない」 簡単そうで、なかなかむずかしいでしょう。 J では、これを一瞬に解いてしまうことができます。 )
see ym, sudoku ym
+---+---+ |+---+---+---+|+---+---+---+| ||.5.|7.1|.4.|||659|721|348|| ||7.3|...|1.2|||743|985|162|| ||.8.|4.6|.9.|||281|436|597|| |+---+---+---+|+---+---+---+| ||9.4|.6.|8.3|||974|162|853|| ||...|8.7|...|||365|897|214|| ||1.8|.5.|6.9|||128|354|679|| |+---+---+---+|+---+---+---+| ||.1.|6.3|.8.|||412|673|985|| ||5.6|...|7.1|||596|248|731|| ||.3.|5.9|.2.|||837|519|426|| |+---+---+---+|+---+---+---+| +---+---+ -- (3 of 35) Pre-definition --- 数独では、行ごと、列ごと、ブロックごとの 取り出し、検索などの処理が必要です。 そのため準備として、いくつかの定義を行います。 )
j =: (]/. i.@#) ,{;~3#i.3 r =: 9#i.9 9 c =: 81$|:i.9 9 b =: (,j{9#i.9) { j I =: ~."1 r,.c,.b R =: j, (,|:)i.9 9 regions =: R"_ {"_ 1 ]
free =: 0&= > (1+i.9)"_ e."1 I&{
-- (4 of 35) Pre-definition (continued) --- r は行ごとのインデックスを表します。 r と入力してください。 ) -- (5 of 35) Pre-definition (continued) --- c は列ごとのインデックスを表します。 c と入力してください。 ) -- (6 of 35) Pre-definition (continued) --- j を使って、b は ブロックごとのインデックスを表します。 j と入力してください。 b と入力してください。 ) -- (7 of 35) Pre-definition (continued) --- I は行、列、ブロックをまとめて、 ユニークな（重複したものを除いた）セルの インデックスを表します。 I と入力してください。 ) -- (8 of 35) Candidates --- 以上の準備をした上で、 free ym とすると、 初期データ ym の空いた場所に、候補として入れられる数字を ブール表示したパラメータを出力します。 free ym と入力してください。 ) -- (9 of 35) Candidates (continued) --- これらのパラメータの意味を見てみましょう。 なお、ここでは行、列は１オリジンで示します。 第１行目＝１行１列のセルのパラメータ 1 2 3 4 5 6 7 8 9 --- 値 0 1 0 0 0 1 0 0 0 このセルには数字 2 と 6 とが候補として入れられる。 第２行目＝１行２列のセルのパラメータ 1 2 3 4 5 6 7 8 9 --- 値 0 0 0 0 0 0 0 0 0 このセルには入れられない。
第３行目＝１行３列のセルのパラメータ 1 2 3 4 5 6 7 8 9 --- 値 0 1 0 0 0 0 0 0 1 このセルには数字 2 と 9 とが候補として入れられる。 このようにして、 値 0 0 0 0 0 0 0 0 0 値 0 1 1 0 0 0 0 1 1 値 0 0 0 0 0 0 0 0 0 第７行目＝１行７列のセルのパラメータ 1 2 3 4 5 6 7 8 9 --- 値 0 0 1 0 0 0 0 0 0 このセルには数字 3 だけが入れられ、確定する。 ) -- (10 of 35) Candidates (continued) --- これをわかり易く示すプログラムを作ってみましょう。 次のプログラムを作ったあとで ) N =: 1 + i.9 NN =: >, {N;N NNN =: '(',"1 (": NN),"1 ,') = ' FRE =: (free ym)#N
NFR =: NNN ,"1 ":FRE -- (11 of 35) Candidates (continued) --- セル（行 列）に対して入れられる数字の候補を見るには NFR と入力してください。 ) -- (12 of 35) Candidates (continued) --- これらの候補の頻度を一覧表として見るには 以下のように行います。 数字はその場所に入れられる候補の数を示します。 )
see FREQ =: +/"1 free ym +---+---+---+ |2.2|.4.|1.2| |.3.|122|.2.| |1.2|.2.|2.2| +---+---+---+ |.2.|2.1|.3.| |322|.5.|322| |.2.|2.2|.1.| +---+---+---+ |2.3|.3.|3.2| |.3.|133|.1.| |2.1|.4.|1.2| +---+---+---+ -- (13 of 35) Candidates (continued) --- まず、１は候補が一つに確定することを示します。 たとえば、３行１列のセルには１つだけの数字が入れられ、その値は 関数 cand を使って、つぎのように示されます。 他のセルでもやってみましょう。 )
cand 3 1 2 -- (14 of 35) Search Values --- これをまとめて行うには 関数 ac を使って、つぎのように取り出されます。 ) AC =: ac@free ym see AC +---+---+---+ |...|...|3..| |...|9..|...| |2..|...|...| +---+---+---+ |...|..2|...| |...|...|...| |...|...|.7.| +---+---+---+ |...|...|...| |...|2..|.3.| |..7|...|4..| +---+---+---+
-- (15 of 35) Search Values (continued) --- 次に頻度表で１以外は、 値が一つに確定しない場所です。 ) see FREQ +---+---+---+ |2.2|.4.|1.2| |.3.|122|.2.| |1.2|.2.|2.2| +---+---+---+ |.2.|2.1|.3.| |322|.5.|322| |.2.|2.2|.1.| +---+---+---+ |2.3|.3.|3.2| |.3.|133|.1.| |2.1|.4.|1.2| +---+---+---+
-- (16 of 35) Search Values (continued) --- たとえば、 ２行２列のセルでは ３つの値が候補になります。 その値は次のようになります。 ) cand 2 2 4 6 9
-- (17 of 35) Search Values (continued) --- しかし、この場合でも 同じ行、同じ列、同じブロック内に たった１回だけ、現れる値であれば この場合は確定することになります。 関数 cand1 を使って、 ２行２列であれば つぎのようにして調べられます。 ) cand1 2 2 Row: 4 5 5 6 6 8 8 9 9 9 Column: 2 2 2 2 4 4 6 6 7 7 9 9 Block: 1 2 2 2 2 4 6 6 9 9
-- (18 of 35) Search Values (continued) --- 数字４はただ１回だけ現れます。
つまり、この場所では
４が候補として、確定します。 )
-- (19 of 35) Search Values (continued) --- ところが、１行１列の場所で 同様のテストをすると ) cand 1 1 2 6 cand1 1 1 Row: 2 2 2 3 3 6 6 8 8 9 9 Column: 2 2 2 2 3 4 4 6 6 8 Block: 1 2 2 2 2 4 6 6 9 9
-- (20 of 35) Search Values (continued) --- たった１回だけ、現れるという条件にあてはまる
値は見つかりません。
つまり、候補は確定しません。 他の場所でもやってみてください。 )
-- (21 of 35) Search Values (continued) --- このように２つ以上の候補があるものでも、 行、列、ブロック内でのユニーク性を利用して １つに確定することができます。 これを、まとめて行うには 関数 ar を使って、つぎのように取り出されます。 ) see AR =: ar@free ym +---+---+---+ |...|...|...| |.4.|..5|...| |..1|...|..7| +---+---+---+ |...|1..|.5.| |3..|.9.|2..| |...|3..|...| +---+---+---+ |...|...|...| |...|...|.3.| |8..|.1.|...| +---+---+---+
-- (22 of 35) Search Values (continued) --- つまり、これら両方の数字の値を、 空いた場所に入れることが出来るのです。 ) see ACR =: AC >. AR +---+---+---+ |...|...|3..| |.4.|9.5|...| |2.1|...|..7| +---+---+---+ |...|1.2|.5.| |3..|.9.|2..| |...|3..|.7.| +---+---+---+ |...|...|...| |...|2..|.3.| |8.7|.1.|4..| +---+---+---+
-- (23 of 35) Search Values (continued) --- したがって、初期値と合わせれば
第一ステップとして、次の解が得られます。 )
see ASS_1 =: ym + ACR +---+---+---+ |.5.|7.1|34.| |743|9.5|1.2| |281|4.6|.97| +---+---+---+ |9.4|162|853| |3..|897|2..| |1.8|35.|679| +---+---+---+ |.1.|6.3|.8.| |5.6|2..|731| |837|519|42.| +---+---+---+ -- (24 of 35) Repeat --- まだ、埋まっていないセルがありますね。 これを埋めるには、今の解を初期値として 先の処理を繰り返せば、良いのです。 下記の関数 func を定義して行います。 )
func =: + (ac >. ar)@free see func ASS_1
+---+---+---+ |659|721|34.| |743|985|162| |281|436|597| +---+---+---+ |974|162|853| |365|897|214| |128|354|679| +---+---+---+ |412|673|985| |596|2.8|731| |837|519|426| +---+---+---+ -- (25 of 35) Repeat (continued) --- つまり、関数 func を次々に繰り返し実行して 空いたセルを埋めて行けばよいのです。 たとえば、４回繰り返すには 下記のようにします。 )
see ASS_4 =: func^:(i.4) ym
+---+---+---+---+ |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| ||.5.|7.1|.4.|||.5.|7.1|34.|||659|721|34.|||659|721|348|| ||7.3|...|1.2|||743|9.5|1.2|||743|985|162|||743|985|162|| ||.8.|4.6|.9.|||281|4.6|.97|||281|436|597|||281|436|597|| |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| ||9.4|.6.|8.3|||9.4|162|853|||974|162|853|||974|162|853|| ||...|8.7|...|||3..|897|2..|||365|897|214|||365|897|214|| ||1.8|.5.|6.9|||1.8|35.|679|||128|354|679|||128|354|679|| |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| ||.1.|6.3|.8.|||.1.|6.3|.8.|||412|673|985|||412|673|985|| ||5.6|...|7.1|||5.6|2..|731|||596|2.8|731|||596|248|731|| ||.3.|5.9|.2.|||837|519|42.|||837|519|426|||837|519|426|| |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| +---+---+---+---+
-- (26 of 35) Repeat (continued) --- また、各ステップで入れられた数字を示すのには
関数 diff を用いて次のようにします。 )
see diff ASS_4
+---+---+---+---+ |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| ||.5.|7.1|.4.|||...|...|3..|||6.9|.2.|...|||...|...|..8|| ||7.3|...|1.2|||.4.|9.5|...|||...|.8.|.6.|||...|...|...|| ||.8.|4.6|.9.|||2.1|...|..7|||...|.3.|5..|||...|...|...|| |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| ||9.4|.6.|8.3|||...|1.2|.5.|||.7.|...|...|||...|...|...|| ||...|8.7|...|||3..|.9.|2..|||.65|...|.14|||...|...|...|| ||1.8|.5.|6.9|||...|3..|.7.|||.2.|..4|...|||...|...|...|| |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| ||.1.|6.3|.8.|||...|...|...|||4.2|.7.|9.5|||...|...|...|| ||5.6|...|7.1|||...|2..|.3.|||.9.|..8|...|||...|.4.|...|| ||.3.|5.9|.2.|||8.7|.1.|4..|||...|...|..6|||...|...|...|| |+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+| +---+---+---+---+ -- (27 of 35) Repeat (continued) --- したがって、最終解を得るには、 値が確定するまで処理を繰り返す J の便利な機能を用いて 以下のように行えば良いのです。 )
see ASS_N =: func ^:_ ym +---+---+---+ |659|721|348| |743|985|162| |281|436|597| +---+---+---+ |974|162|853| |365|897|214| |128|354|679| +---+---+---+ |412|673|985| |596|248|731| |837|519|426| +---+---+---+ -- (28 of 35) Guess --- 以上の関数は、Hui のプログラムでは assign として定義されてます。 このように易しい問題は、これで解が求まりますが、 難しい問題はこれだけでは、求まりません。 「数独２１」から、 No.99, Hard の問題を見てみましょう。 ) see su21_99 +---+---+---+ |..4|81.|...| |..2|...|3..| |1..|.94|6..| +---+---+---+ |74.|...|...| |.9.|.2.|.5.| |...|...|.83| +---+---+---+ |..7|13.|..2| |..6|...|1..| |...|.45|8..|
+---+---+---+
-- (29 of 35) Guess (continued) --- これをためしに解いてみましょう。
このように解は全く求まりません。 )
see sux =: assign su21_99 +---+---+---+ |..4|81.|...| |..2|...|3..| |1..|.94|6..| +---+---+---+ |74.|...|...| |.9.|.2.|.5.| |...|...|.83| +---+---+---+ |..7|13.|..2| |..6|...|1..| |.19|.45|8..| +---+---+---+ -- (30 of 35) Guess (continued) --- この理由を頻度表を作って、調べてみましょう。 )
see bx =: +/"1 free sux +---+---+---+ |44.|..4|433| |44.|332|.46| |.43|4..|.23| +---+---+---+ |..4|435|243| |3.3|4.5|2.4| |332|534|4..| +---+---+---+ |32.|..3|33.| |54.|324|.44| |2..|3..|.32| +---+---+---+ -- (31 of 35) Guess (continued) --- このように候補値の頻度が高い場所が多く、 これではユニークな候補はなかなか見つけられません。 ためしに、いくつかの場所の候補値を見てみましょう。 ) sux cand 1 1 3 5 6 9 sux cand 1 2 3 5 6 7 sux cand 1 6 2 3 6 7 sux cand 1 7 2 5 7 9 sux cand 1 8 2 7 9 sux cand 1 9 5 7 9 -- (32 of 35) Guess (continued) --- 頻度値が最小のものが現れるインデックス ind と そのときの候補の値を つぎのようにして求めます。 ) ind =: 1 + 9 9#: (i. <./) (bx) {10, 1, 2, 3, 4, 5, 6, 7, 8, 9 ind 2 6
sux cand ind 6 7 -- (33 of 35) Guess (continued) --- すると ２行６列のセルには ６ と ７ が候補として可能性があることが分かります。 ) -- (34 of 35) Guess (continued) --- Hui のプログラムではこのような考えで推論を行う guess という関数が用意されていて、 可能性のある２つの場合が求められます。 )
see guess sux
+---+---+ |+---+---+---+|+---+---+---+| ||..4|81.|...|||..4|81.|...|| ||..2|..6|3..|||..2|..7|3..|| ||1..|.94|6..|||1..|.94|6..|| |+---+---+---+|+---+---+---+| ||74.|...|...|||74.|...|...|| ||.9.|.2.|.5.|||.9.|.2.|.5.|| ||...|...|.83|||...|...|.83|| |+---+---+---+|+---+---+---+| ||..7|13.|..2|||..7|13.|..2|| ||..6|...|1..|||..6|...|1..|| ||.19|.45|8..|||.19|.45|8..|| |+---+---+---+|+---+---+---+| +---+---+ -- (35 of 35) Guess (continued) --- 最終的にはこのような推論を含めた関数 sudoku により以下のように解が求められます。 )
see su21_99, sudoku su21_99 +---+---+ |+---+---+---+|+---+---+---+| ||..4|81.|...|||364|812|579|| ||..2|...|3..|||982|756|314|| ||1..|.94|6..|||175|394|628|| |+---+---+---+|+---+---+---+| ||74.|...|...|||743|581|296|| ||.9.|.2.|.5.|||698|423|751|| ||...|...|.83|||521|967|483|| |+---+---+---+|+---+---+---+| ||..7|13.|..2|||457|138|962|| ||..6|...|1..|||836|279|145|| ||...|.45|8..|||219|645|837|| |+---+---+---+|+---+---+---+| +---+---+ End of lab
プログラム・リスト
NB. Hui's Sudoku Solving Program
NB. Modified executable in J3, J4, JPC by T. Nishikawa, 2006/1/2 j =: (]/. i.@#) ,{;~3#i.3 r =: 9#i.9 9 c =: 81$|:i.9 9 b =: (,j{9#i.9) { j I =: ~."1 r,.c,.b R =: j, (,|:)i.9 9 regions =: R"_ {"_ 1 ]
free =: 0&= > (1+i.9)"_ e."1 I&{
ok =: (27 9$1)"_ -:"2 (0&= +. ~:"1)@regions ac =: +/ .*&(1+i.9) * 1: = +/"1
Ip =: # i.@# NB. I.(indices) is defined as Ip ar =: 3 : 0 m=: 1=+/"2 R{y. jj =: Ip +. /"1 m k =: 1 i."1~ jj{m i =: ,(k{"_1 |:"2 (jj{R){y.) #"1 jj{R (1+k) i}81$0 )
assign =: (+ (ac >. ar)@free)^:_"1 guessa =: 3 : 0
if. -. 0 e. y. do. ,:y. return. end. b =. free y.
i =. (i.<./) (+/"1 b){10,}.i.10 y. +"1 (1+ Ip i{b)*/i=i.81 )
guess =: ; @: (<@guessa"1)
sudoku =: guess @: (ok #]) @: assign ^:_ @ ,
see0 =: ({&'.123456789') @ (9 9&$) @ , NB. modified by TN see1 =: (3 3 ,: 3 3)&(<;.3) @ see0 NB. modified by TN NB. see1 =: (;~9$1 0 0)&(<;.1) @ ({&'.123456789') @ (9 9&$) @ , see =: <@see1"1`see1@.(1:=#@$) diff =: * 0&=@}:@(0&,) x0 =: ] ;._2 (0 : 0) 2 0 0 6 7 0 0 0 0 0 0 6 0 0 0 2 0 1 4 0 0 0 0 0 8 0 0 5 0 0 0 0 9 3 0 0 0 3 0 0 0 0 0 5 0 0 0 2 8 0 0 0 0 7 0 0 1 0 0 0 0 0 4 7 0 8 0 0 0 6 0 0 0 0 0 0 5 3 0 0 8 ) x =: , 0". x0 f =: + (ac >. ar)@free g =: guess @:(ok#])@:assign
NB. Yomiuri Shimbun 2005/10/15 ym =: , 0".] ;._2 (0 : 0) 0 5 0 7 0 1 0 4 0 7 0 3 0 0 0 1 0 2 0 8 0 4 0 6 0 9 0 9 0 4 0 6 0 8 0 3 0 0 0 8 0 7 0 0 0 1 0 8 0 5 0 6 0 9 0 1 0 6 0 3 0 8 0 5 0 6 0 0 0 7 0 1 0 3 0 5 0 9 0 2 0 )
NB. Sudoku21, p.10 No.1 Easy su21_1 =: , 0". ] ;._2 (0 : 0) 0 0 0 0 0 2 5 0 3 0 3 1 0 0 0 0 0 8 0 2 4 0 5 1 0 0 0 0 0 0 0 1 7 0 6 5 2 6 0 0 0 0 0 4 7 7 1 0 5 6 0 0 0 0 0 0 0 6 8 0 2 9 0 4 0 0 0 0 0 8 3 0 6 0 3 4 0 0 0 0 0 )
NB. Sudoku21, p.110 No.99 Hard su21_99 =: , 0". ] ;._2 (0 : 0) 0 0 4 8 1 0 0 0 0 0 0 2 0 0 0 3 0 0 1 0 0 0 9 4 6 0 0 7 4 0 0 0 0 0 0 0 0 9 0 0 2 0 0 5 0 0 0 0 0 0 0 0 8 3 0 0 7 1 3 0 0 0 2 0 0 6 0 0 0 1 0 0 0 0 0 0 4 5 8 0 0 )
NB. Sudoku with Dyalog APL, J. Clark's Example clark =: , 0". ] ;._2 (0 : 0) 0 3 4 0 0 5 0 0 0 0 7 5 0 2 0 1 0 0 0 0 0 0 0 0 8 7 5 3 4 0 0 0 0 0 0 9 0 0 0 2 6 0 3 4 0 0 6 0 3 4 0 0 0 0 0 0 3 5 8 0 0 9 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 )
NB. Nishikawa's Utility Functions cand =: 3 : 0
ym cand y. :
ind =: +/9 1 * _1 + y. v =. ind { (free x.)#>:i.9 (v>0) # v ) wr =: 1!:2&2 cand1 =: 3 : 0 ym cand1 y. : M =: +/"2 R{free x. B =. ((3#.<. 3%~ "(0)_1+y.){M) # >:i.9 R =. ((9 + {. _1+y.){M) # >:i.9 C =. ((18 + {: _1+y.){M) # >:i.9 wr 'Row: ', ": (R>0) # R wr 'Column: ', ": (C>0) # C 'Block: ',": (B>0) # B )
NB Sudoku Data Display Conversion
subs=: [. & ((((e.&) ((# i.@#)@)) (@])) })
NB. convert data from Nishikawa's format to Hui's format n2h =: 3 : '9 9$0 subs _ (, y.)'
NB. convert data from Hui's format to Nishikawa's format h2n =: 3 : '9 9$_ subs 0 (, y.)'
