メニエスの名のもとに

プログラミング関係を中心としたぐだぐだブログ

プログラム

-O2 と -O3 は大違い

Oだけに。 いやあ、これまでg++ でコンパイルする時に -O3 を付けてたんだけど、-O2 とはそんなに違わないと思ってたんですよ。で、GitHubにソースを置くようになってからautotoolsを使うようになって、Makefile.am でやはり -O3 と指定して訳です。でも、ち…

ナンプレ(数独)問題作成プログラム 生成法解説2

phase3 再帰しながら指定された解法を含むまで全部調べる。 phase3 は再帰アルゴリズム。入力は盤面配列(実は入出力)と検索開始位置と解法指定、出力はあまり言いたくないけど難易度、ただし、マイナスは矛盾があって解けない。ゼロは知っている解法では解…

ナンプレ(数独)問題作成プログラム ドキュメント

ドキュメントは重要、超重要 といいながら、プログラムが出来てからドキュメントを書いているようではいけないわけだが。doxygen ドキュメントを頑張っていれましたよ。まだまだ不足していますが、一気にやる気力はない。ボチボチやるが、ドキュメントなので…

ナンプレ(数独)問題作成プログラム その23 generate

generate の実行形式がmake できるソースをGitHubに上げました。 まあ、例によってバグがあるという可能性は否定できない。というかむしろ高い。 ドキュメントが出来ていない。doxygen を想定してコメントは入れていたけど、実際にはdoxygenをかけていないの…

ナンプレ(数独)問題作成プログラム その22 normalize

normalize analyze の最初の版で目指していたのは、convertによって変わらない解法のリストを出力することであった。それとは別に、convertによって替わり得る問題、つまり実質的には同じ問題を違う問題として出力してしまうという危険性を避ける必要がある…

ナンプレ(数独)問題作成プログラム その21 xywing

analyze を単純化 analyze は無駄に複雑で重い割りに、目的を完全には達成していないので単純化することにしました。苦労してデバッグしたのに、機能をほとんど取ってしまいました。「泣いて馬謖を斬る」という感じでしょうか。いや、三国志は全然詳しくない…

ナンプレ(数独)問題作成プログラム その20 analyze

酔っ払ってプログラムを書いた。 一度作った問題を convert によって変換して何度も使うようにするという考えであった。ところが、convert すると solve で求める解法が違ってしまうので、convertで変わらないような解法の情報を求めようとしていたのであっ…

ナンプレ(数独)問題作成プログラム その19 analysis

バグではなくて仕様です convert のバグと思われた事、convert すると使用する解法アルゴリズムが変わるという事は、バグというよりも仕様でした。前回の結果では、Locked Candidate の数が変わっていたわけですが、その原因はブロックの位置が変わることに…

ナンプレ(数独)問題作成プログラム その18 convert

ケチケチ作戦 digging hole をやった結果からも分かるように、難しいナンプレの問題はなかなか生成できないのである。貴重な存在なのである。そこで、もし見つかったなら、それを大切にしたいと思うわけだ。貴重なものは大切にしよう。 そういうわけで、問題…

ナンプレ(数独)問題作成プログラム その17 digging hole

作ったけど機能してない digging_hole_recursion 関数を作ったけど、機能していない。つまり、穴を増やせていない。可能性としては、(1)バグ、(2)この関数で穴を増やせる確率が低い、たくさん生成すれば穴を増やせる場合もある、(3)対称性を捨てないといけな…

ナンプレ(数独)問題作成プログラム その16 digging hole

debug バグはdigging_hole 関数の中の次の行にありました。 int r = solve(&work, &info); 本来は work ではなく array を指定するべきだった。これは workという変数名が悪いので save に変更しました。さらにそれだけでなく、このままだと前回解いた後の状…

ナンプレ(数独)問題作成プログラム その15 digging hole

digging hole まず、完成形の盤面を用意する prepare_array /** * ナンプレ盤面の完成形を得る。 * ランダムに数字をセットし、再帰的に解く * @param array ナンプレ盤面(出力) * @return 1: 作成できた * @return それ以外: 作成できなかった */ static …

ナンプレ(数独)問題作成プログラム その14 疑似乱数

疑似乱数 これから digging hole アルゴリズムでナンプレの問題を作りたいわけだが、そのために疑似乱数を使う。だいたい何でもいいんだけど、比較的新しい(のでお気に入りの)xsadd を使ってみる。小さいし、速いし、MITライセンスだし。 元のソースはXORS…

ナンプレ(数独)問題作成プログラム その13

前回のプログラムを実行出来るように solve.c の main を変更する。 たいした変更じゃないのでMSaito/NumPl · GitHubを見て。 で、実行すると、 ./solve -r " 6 31 9 9 427 7 1 6 7 8 5 2 5 143 9 8 24 61 " quiet = 0 recursion = 1 argc = 1 ??6?31?9? ??9…

ナンプレ(数独)問題作成プログラム その12

バグ修正 前回のバグはつまらないところにありました。バグってのはたいていつまらないところにあるもんです。 if ((mask & multiple) != multiple) { continue; } これ、multiple の中に mask が含まれるかという判定をしていたのです。 もう集合演算はビッ…

ナンプレ(数独)問題作成プログラム その11

solve.c /** 候補を減らす関数タイプ */ typedef int (*solver_t)(numpl_array *); /** 関数の数 */ static const int max_solvers = 5; /** 関数 */ static solver_t solvers[] = { kill_single, kill_hidden_single, kill_locked_candidate, kill_tuple, k…

ナンプレ(数独)問題作成プログラム その11

doxygen 一度Javaをやった人間は javadoc のようなドキュメントがないとなんとなく不安になる。Doxygen: Main Pageはjavadocのようなことをいくつかの言語を対象にやってくれるソフトである。 これまでのアルゴリズムを使って問題を解くプログラム solve.c …

ナンプレ(数独)問題作成プログラム その10

念のため このブログはナンプレ練習 - Google Play の Android アプリ,ナンプレ練習お試し版 - Google Play の Android アプリの問題作成プログラムについて説明しています。 これまでのプログラムはMSaito/NumPl · GitHubにあります。 X-Wing, Sword Fish, …

ナンプレ(数独)問題作成プログラム その9

tuple (二国同盟、三国同盟、裏二国同盟、……) ひとつの行(縦、横、ブロック)に注目する。その行内に、二つの数字だけで二カ所のマスを埋めていたり、三つの数字だけで三カ所のマスを埋めていたりしたら、それ以外のマスには、その数字は入らない。 図の例…

ナンプレ(数独)問題作成プログラム その8

Locked Candidate Locked Candidate というのは列または行とブロックの共通部分を見て、片方にしかない数字があればもう片方から消せるというもの。日本語分かりにくい。(いや、俺の説明がわかりにくい) この図でいうと、行とブロックに共通部分がある。5…

ナンプレ(数独)問題作成プログラム その7

昨日のプログラムには間違いがあった。 昨日の記事も修正したけどMSaito/NumPl · GitHubの方がたぶん正しい。 矛盾のチェック 昨日の記事でも言っていた矛盾のチェックは、行単位ではない方がいいという件。 static int check_array(sudoku_array * array) {…

ナンプレ(数独)問題作成プログラム その6

わかってたまるかポインター ナンプレの問題を解くために rows, cols, blocks という配列を constants.c に定義したのだが、これらの配列をまとめて扱いたい時がある。そのために all_lines[] = { rows, cols, blocks}; というように定義したい。どう書いた…

ナンプレ(数独)問題作成プログラム バグ2

またしてもバグ 昨日のバグを修正して、検証しようとしていたら、別の問題に遭遇。もうやる気なくなってきたよ。 このスクリーンショットがその問題。紫色の1468がNaked Quadruple になっている。1468だけで四カ所を占有しているので、それ以外の場所の1468…

ナンプレ(数独)問題作成プログラム その4

SIMD Within A Register の実際のプログラムは、16ビットにしてそれ以外は前回の説明の通りにプログラムすると static inline uint16_t ones16(uint16_t x) { x = (x & UINT16_C(0x5555)) + ((x >> 1) & UINT16_C(0x5555)); x = (x & UINT16_C(0x3333)) + ((…

ナンプレ(数独)問題作成プログラム その2

プログラミング言語を決める プログラムを書き始める前には、どのプログラミング言語で記述するかを決定する必要がある。しかし、この世には星の数ほどプログラミング言語があるし、今この瞬間にも新しいプログラミング言語が誕生しているかも知れない。 既…

ナンプレ(数独)問題作成プログラム その1

数独の難易度を決めるのは難易度が高い 少し数独をやると、易しい問題では物足りなくなって難しい問題を解きたくなる。また、プログラマーの場合は、自分が解くのではなく、数独を解くプログラムを作りたくなってくる。そうすると、数独の解き方のページを探…