川合秀実の数独研究に関するドキュメント#4
(11) sc125f （2018年02月ごろ）
- Exocetショックから1年間、私はq2 ratingに代わる難易度指標の自作に取り組んできました。
- それでようやくまあこんなものかと思えるレベルに達しました。それを説明します。
- (a)数独は正解を探すゲームではなく、ペンシルマークを消していくゲームである。
- 私はそれまで数独は「正解を探すゲーム」だと思っていました。だから問題が与えられたときに、正解に至る経路に注目し、そこまでに解法アルゴリズムが適用できない（＝仮置きが必要な）局面が何度あるかを重視していました。
- でも http://www.sudokuwiki.org/sudoku.htm などの数独ソルバーはそのようには問題を解きません。これらの数独ソルバーは列挙された解放テクニックを使って、「不正解のペンシルマークを消していく」ことで数独を解いていきます。だから正解に至る経路などどうでもいいのです。いかに不正解を不正解だと判断するのが困難になっているのか、つまりはそこなのです。
- ということで、sc125fでは盤面の不正解ペンシルマークのすべてに点数を付けます。このペンシルマークを不正解だと見抜くのはどれほど難しいのか、それだけを評価するわけです。
- そしてもっとも点数が低いところのペンシルマークを消します。そしたらまたその状態で残りの不正解ペンシルマークのすべてに点数をつけなおし、またその中で一番低いところを消して・・・ということをすべての不正解ペンシルマークが消えるまで繰り返します。こうしてすべての不正解ペンシルマークが消えるまでに最大で何点のペンシルマークを攻略する必要があったのかを覚えておいて、それをこの問題のスコアだとするのです。
- (b)全工程内での最大値のみを採用し、そこに至るまでの手間やそれ以降の手間の程度は一切加味しない。
- 一番難しい局面に至る前に、それよりは易しいテクニックをいくつか使わせるような問題はよく見かけますが、そういうときに、その分を評価して何らかの加算するべきかどうかという問題があります。sc125fでは加算しないことにしています。なぜなら私が重視しているのは、数独ソルバで解けるかどうかなのであって、それ以外の些細なことの積み重ねで、ソルバに解ける問題がソルバに解けない問題よりも難しいなどと誤判定するかもしれないリスクを避けたかったからです。
- (c)解法アルゴリズムをそのまま実装することはしない。
- 解法アルゴリズムをそのまま実装するのは、以前挫折しているので、これをやろうとはしていません。別の観点から解法アルゴリズムを整理して一般化し、解法の高度さをレベル分けして、難易度の計算に使っています。これについては後で詳しく説明します。
(12) 二択数
(13) 解の個数判定ルーチン高速化競争 （2018年11月ごろ）
(14) 希少数字・純希少数字・希少二択
(15) 転置対称性・対角線対称性・市松対称性 （2018年12月ごろ）
![[K Wiki]](k.jpg "[K Wiki]")
