プログラムにナンプレを解かせたい - その4

プログラム（C言語）にナンプレ（数独）を解かせる↓の続編です。

o-treetree.hatenablog.com

パワーアップして、それなりに満足できるクォリティに仕上がったので。

丁寧なメモ・雑な説明、という感じで連載します。

使用方法

ダウンロード・インストール

今回はgithubにデータを置いています。要らない記述が残ってたり（後で見返すときのためコメント付きで）なんか整ってない部分とかありますが、後々説明するか、こそっと書き換えます笑

GitHub - oha-yashi/sudoku: ナンプレ攻略プログラム

そこにも書いてありますが、ターミナルやらコマンドプロンプトを開いて （C言語を使える環境で）以下のコマンドを順番に打ち込みます。

$ git clone https://github.com/oha-yashi/sudoku
$ cd sudoku
$ make compile

cloneできなかったら無理やりダウンロードしてsudokuフォルダに入れてください。はい。

make compileで失敗したら大体、makefileのコマンド冒頭のインデントがスペースになってしまっているのでtabにすれば通ります。

追記：makeってwidowsだと無いんですか、知らんかった。頑張ってインストールしてください（投げやり）。まあ、

cc -c source/calc.c
cc -c source/fileio.c
cc -c source/main.c
cc -c source/menu.c
cc -c source/setting.c
cc -o solveSudoku main.o calc.o fileio.o menu.o setting.o -lncurses

make compileの代わりにこれ↑をディレクトリsudokuで実行してもいけます。

ダウンロード、コンパイル完了したら

$ make do

で実行です。

操作

上下左右キーで移動、0~9キーで入力、その他機能をところどころのキーに割り当てています。

PCゲームでよくあるawsdで左上下右、というのは対応してません。

今時矢印キーない奴は雑魚でしょw知らんけど。

僕が使ってるのmacbookなのでテンキーじゃないから、awsdで操作すると1234あたりのキーと手がぶつかるのでそういう仕様になりました。

• $ $(赤色)は現在見ているマス
• ! !(青色)はマスに入る候補が2つのマス。ちょっと前、手動で候補を切り替えないと進まなかった時代に参考にしていた。
• ? ?(緑色)はマスに入る候補が3つのマス。

実際

次の盤面をファイル読み込みで解いてみます。それなりの難問です。

別に、矢印キーで移動してマス目を埋めていっても構いません。

それはそれで、1つ入れたり移動するたびに（ただの移動の時にも候補の探索を行なっている）数字が埋まっていくので楽しいですが、一気に解にたどり着くため事前にテキストデータにしておきます。

0 . 準備

読み込むファイルを用意します。コンパイルしたディレクトリにnpというフォルダがあるのでそこにdemo1.datというファイルを作ります。（名前は自由に書き換えて構いませんが、置く場所はnpフォルダ限定です）。

demo1.datの中身は次のようにします。詳しいことは後々。

%1d
000 400 065
080 000 000
700 090 000
000 000 120
065 008 000
004 000 000
000 600 009
100 000 700
000 005 000

1行目は呪文だと思っていただいて、その下に盤面と同様の数字が並んでいるのがわかると思います。

1 . 実行

コンパイルした（実行ファイルsudokuSolveがある）ディレクトリで

$ make do

2 . 開始画面が表示される

なんでもいいのでキーを打ちます。[Enter]

3 . 初期画面

今回は自作ファイルを読み込むので、i

4 . ファイル名入力

今回、読み込みファイルはnp/demo1.datです。npフォルダの中にあるのは指定済み。demo1.dat[Enter]

5 . 読み込み完了

もう一回[Enter]

6 . 数字が入る

この後は[Enter]連打で終わりまで行きます

7 . 完成!!

無事全マスが埋まりました。終わりなのでq

8 . 終了画面

なんでもいいのでキーを押して終了します。

盤面データの扱い

途中経過をセーブするときはwを押しますが、そうするとnp/save.datにそのときの状態（マス目と候補）が16進数データとして保存されます。

こんな感じです。（ちなみにこれはさっきの盤面データを読み込んだ直後にセーブしたものです）

%x
020c 020e 020e 4010 019e 009e 031c 6040 5020 
027c 8100 034e 01be 01fe 00de 037c 03fa 01fe 
7080 01be 01ce 01be 9200 02de 037c 03fa 01fe 
0388 0388 0388 02b8 02f8 02d8 1002 2004 01fe 
028c 6040 5020 02be 02fe 8100 037e 03fe 01fe 
03ec 03ee 4010 03be 03fe 03de 037e 03fe 01fe 
01bc 01bc 01bc 6040 01de 01de 017e 017e 9200 
1002 037e 037e 035e 035e 035e 7080 03fe 03fe 
03de 03de 03de 03de 03de 5020 03fe 03fe 03fe 
saved at 2020/03/27 07:32:36

これは、前回プログラムにナンプレを解かせたい - その3 - おはやし日記の最後に思いついたやつをちょい改良した形式です。

スペース削減のために16進数で表現されているが実態は16ビットのビット列で処理しています。

ビット	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0		16進数
x_1	0	1	0	1	0	0	0	0	0	0	1	0	0	0	0	0		5020
x_2	0	0	0	0	0	0	1	0	1	0	1	1	1	1	1	0		02be
用途	a	a	a	a	0	0	b	b	b	b	b	b	b	b	b	0

• a : 確定した数字 0001 ~ 1001 x>>12で取り出せる。また、16進数4桁にしたとき最上位に現れる。
• b : i=1~9の候補フラグ x>>i & 1 で取り出せる

上の表では

• x_1 = 0x5020(0xは16進数の印) --- aが5で、bは（右から0始まりで）5ビット目に1が立っているので、5が入ると確定しているマスの状態を表しています

• x_2 = 0x02be --- aが0で、bは1, 2, 3, 4, 5, 7, 9ビット目に1が立っているので、マスに入る候補が1, 2, 3, 4, 5, 7, 9のどれかであることを表しています

とりあえずここまででアップしちゃおうかな。おしまい。

続き↓