JAPLA研究会資料 2010/9/ Excel_

Size: px

Start display at page:

Download "JAPLA研究会資料 2010/9/ Excel_"

しょうりすみい
5 years ago
Views:

1 JAPLA 研究会資料 2010/12/4 Sudoku_Lab.doc 数独 on Excel_J を楽しむ -J Sudoku でどうやって数独の問題を解くか - 西川利男 3. 数独 on Excel_J で楽しむ数独パズルがまだ根強く人気を保っている 3 大新聞には毎日あきもせず連載されている数独が出だした頃マイワイフが相当凝っていたがやめてしまったところが絵の方がうまくいかないのであろうか最近また毎日のようにやっているそのワイフがいわく初級の問題は最近はすぐ解けるが中級となるとなかなか解けないけれどもコンピュータで解いてしまっては面白くないのでいやだという J の仲間のあいだでは有名な Hui のプログラムにより難なく解けるそしてさらに数独 on Excel_J では紙とエンピツではなく楽しみつつ解くこともできる [4] 数独 on Excel/J では問題を入力した後つぎのようにして解が求められる CTRL-l 数独データをロードする (Excel 画面と J_Sudoku システムへ ) CTRL-s J_Sudoku で解を求める CTRL-r 結果を Excel で表示するもちろんふつうのとおりに入力して楽しむこともできる (CTRL-m でお手伝い ) - 1 -

次は面白くないという数独 on Excel_J による回答である数独には数年前私自身もかなり凝って Hui の J のプログラム sudoku の解析を Lab システムを用いて行ったが [1] 必ずしも満足いくものではなかった Hui の J プログラムを理解するにはこれをそのまま走らせる前に紙とエンピツでそのアルゴリズムを追うことが極めて有益である今回 sudoku

2 次は面白くないという数独 on Excel_J による回答である数独には数年前私自身もかなり凝って Hui の J のプログラム sudoku の解析を Lab システムを用いて行ったが [1] 必ずしも満足いくものではなかった Hui の J プログラムを理解するにはこれをそのまま走らせる前に紙とエンピツでそのアルゴリズムを追うことが極めて有益である今回 sudoku プログラムの処理をあらためて見直し筆者なりにいくつかの便利な関数を追加したまた sudoku Lab システムの説明をわかり易くしたり一部修正改定をおこなったなお最初の部分の説明は筆者のワイフ靖子流の紙とエンピツによる数独攻略法である [1] 西川利男数独 (SUDOKU) パズルを J で解く -Labs システムによる Hui のプログラムのトレース - JAPLA 研究会資料 2006/1/28 [2] 西川利男 J のオブジェクト指向プログラミング - その 4-J-Grid による数独パズルをもっと使いやすく - J 研究会資料 2006/3/25 [3] 西川利男 J の OOP と Grid プログラミング - その 5-J による数独パズル - 棋譜の自動記録と棋譜データによる実行 JAPLA 究会資料 2006/6/24-2 -

3 [4] 西川利男 Excel から J を使う - 数独 on Excel_J への応用 JAPLA 研究会資料 2010/9/25 毎日新聞 10/26 掲載の問題 A0 =: main_1026 see A 靖子流攻略法ではまず問題の中で何回も表れる数字から手をつける AA =: (0&~: # ]) A0 NB. extract nonzero numbers AA NU =: >: i.9 FR =: +/"1 NU = / AA NB. frequency of numbers NU,:FR つまり数字 1 は 3 回, 数字 2 は 4 回, 数字 3 は 1 回,.. 現れる以上を参考にまず左上ブロックで数字 8 を入れることをやってみる 2 行目 3 行目には数字 8 がある 1 列目には数字 8 があるそれならば数字 8 が 1 行 3 列に入ることがすぐわかる同様にして左中ブロックで数字 2 を入れることをやってみる 4 行目 5 行目には数字 2 がある 3 列目には数字 2 があるそれならば数字 2 が 6 行 1 列に入ることがすぐわかる同様にして左下ブロックで数字 5 を入れることをやってみる 8 行目には数字 5 がある 2 列目と 3 列目には数字 5 があるそれならば数字 5 が 7 行 1 列に入ることがすぐわかる - 3 -

4 この攻略法だけで新聞掲載の初級の問題はほとんど解けるということであるコンピュータのプログラムではこの処理は関数 ar によりすべてのブロックをまとめて行っている see A これとは別の攻略法がある行列ブロックを仔細に見るとそこだけで候補が 1 つにしぼられ数字が決まる場合があるところで問題のセルを通じて入れられる数字の候補の可能性の頻度を見てみる NB. check candidate frequency see +/"1 free A NB. 1 shows determined cell, (6, 4), (5, 7) A0 cand A0 cand つまりセル (6, 4) では数字は 3 に確定しセル (5, 7) では数字は 6 に確定するこの処理は関数 ac で行うなおここではセル (6, 4) などの表記は 1 オリジンである - 4 -

5 see A さて今回セルに入れられる候補の数字のすべてを出力する便利なツール candlist を開発したここで紹介しよう J のコーディングは後述 candlist A

6 なおすでに決まったが (1, 3) セルは A0 cand のように 4 通りもある Hui のプログラムではこれを決定するには次のように行う A0 cand1 1 3 Row: Column: Block: この表は次のことを表す 1 行目のセルに注目すると 1 は 3 回 2 は 2 回... 8 は 1 回現れる 3 列目のセルに注目すると 3 は 6 回 4 は 3 回... 8 は 3 回現れる同じブロックでは 2 は 3 回 3 は 7 回... 8 は 1 回現れるこれから 1 回だけ現れるのは 8 しかないそこで 8 に決まる! 以上 free で入れられる場所を求めてこれに関数 ac と ar とにより定まる候補をまとめて行う関数 func =: (ac >. ar)@free を用いて最初のステップが決まる NB. operate func =: (ac >. ar)@free NB. first step determined A1 =: func A0 see A

7 このステップは次のように続けられる see A see A A2 =: func A1 see A

8 A3 =: func A2 see A A4 =: func A3 see A これらをまとめて表示する see func^:(i.5) A

9 またそれぞれのステップで入れられた数字はつぎのようになる see diff func^:(i.5) A 最終結果は次のようになった see func^:(6) A

10 なお Hui のプログラムでは以上の処理では一意的には決まらないもっと難しい問題に対してはそれぞれの解の可能性のトリーを平行して解の検索を進めるいわゆる推論エンジン guess を用意しているくわしくは sudoku の解析の Lab システムをご覧いただきたい

数独（SUDOKU）パズルをJで解く

数独（SUDOKU）パズルをJで解く 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 パズルに筆者が親しむようになったのは次のようないきさつからである