数独の作りやすい配置について
きっかけ
プレアデスさんのこのツイートと
https://gyazo.com/4356c233bd43309f0b4b9894a12235c0
この記事を
を読んだのと、
先日クリスマスナンプレを作ったことで、
配置ごとの作問難易度って何で決まるのかに興味を持ったので、
実際に測ってみる前段階として、仮説を立ててみます。
クリスマスナンプレ
https://gyazo.com/fcf346ab7596f22d57e90008e48ae8f8
▲クリスマスナンプレ
この配置は24表出ですが、作問に苦労したので、
作問難易度としてはどれくらいに位置するのだろうという疑問もありました。
https://gyazo.com/af405e0a79c3ea468f43b4b2982c3332
▲最初22表出のこの配置で作ろうとしたら下の方が全然決まらなかった
作問難易度をどう評価するか
機械的に判定・定義する方法として
その配置の唯一解盤面の数
なんらかの理（アルゴリズム）に沿って数字を入れて行った時に、唯一解盤面が生成されるまでの平均ステップ数
が浮かびました。前者は妥当そうな値が出そうですが、簡単には求まりそうにないです。
後者はアルゴリズムに依存するため、正確ではないかもしれませんが、それっぽい値が求められそうです。
次に、数字配置がこれらの値に相関しそうなパラメータを考えてみます。
作問難易度を決めるパラメータについて
先ほどのクリスマスナンプレについて
そのマスの属する縦・横・ブロックに数字が
6つ以上ある→青
5つある→緑
4つある→黄
3つある→赤
で塗り分けてみました。
https://gyazo.com/c963914bb42f0ba42e76c89558339608
この数をそのマスに効いている表出の数と呼ぶことにします。
同じ表出数でも、赤や黄色が固まっているほど作問が難しい盤面と考えられるのではないか、
という仮説を考えました。
プレアデスさん記事の配置
で紹介されている盤面も塗り分けてみます。
https://gyazo.com/47e7b5308c9823d761fef480b4bafa38
https://gyazo.com/36c8a00167b3017880c4e59502cb6f9a
https://gyazo.com/131d1d25dd01df1d1ab0563b3b45ae45
https://gyazo.com/d42d5f8925639a899cda4029f94a50a7
▲21表出
確定した数字から次の数字が決まっていくと考えると、
効きの個数が同じだったとしても、
赤く塗られたマス（効きの少ないマス）の属する行・列・ブロックに青色マス（効きの多いマス）がないと、
より確定させづらいのではないかと考えられます。
最後の21表出の盤面、赤色が多いだけでなく固まっていたり、周囲に緑マスしかなかったりして、
決めきる難易度が非常に高いように見えます。
色合いだけをみるとクリスマスナンプレ(完成版)はその次ぐらいの作問難易度でしょうか。
候補数字の期待値
あるマスについて、9個ある候補数字を平均していくつ減らせるかが指標になるかもしれません。
ある空白マスのの属する行・列・ブロックについて、
行に数字が3個あると行で見たときのそのマスの候補数は $ 9-3 = 6
列に数字が2個あると候補数は $ 9-2 = 7
ブロックに数字が1個あると候補数は$ 9-1 = 8
全制約を合わせた候補数字数の期待値は
$ 6/9 * 7/9 * 8/9 * 9 = 4.148...
期待値を用いる方が、ヒントの数を単純に加算するよりも精度が高いかもしれません。
その他
関連する話題をメモとして並べます。
難問や良問（難易度バランス、展開を作れる）数独の作問難易度
良問の集合は唯一解盤面の部分集合なので、唯一解盤面の作問難易度にある程度比例しそうです。
多すぎも少なすぎもしないちょうどいい効きの数のマスが多いと展開を制御しやすいかもしれません。
数字なし列・ブロックの数
作問難易度による美しさ評価の一つとして挙げられます
今回の議論で吸収できると考えられます。
使用数字が8種の数独
「ある数字が使われていない」ことも美しさ評価に含められることもあります
同じ数字が固まっているほどヒントとして弱いと考えると、
必ず数字を自然発生させるという制約も生まれます。
参考
同じ数字が多いほど作問難易度は上がるのか
どうなんでしょう......
決まりやすそう→マスが埋まっていきやすい？それとも他の数字が決まりにくくなる？
あまり影響しないかも
三次元スターバトルに変換
9*9の盤面に1から9の数字を埋めることを、9*9*9の盤面の高さ1から高さ9のどこか1マスに星を置く、9*9*9の三次元のスターバトル系のパズルと捉えることもできます。
non-conなどの制約も可視化にも使用。
同じ数字が置かれていることによる、ヒント数字の影響度合いを、影響マスを数えることで捉えられそう。
おまけ
元記事の本来？の利用法として、プレアデスさん記事の配置を使って問題を作りました。
クリスマスナンプレよりやさしめです。
https://gyazo.com/fd6cd343f8c91e93f5d818a834f4fd08
12/26 13:09 盤面の誤りを修正しました
追記
https://gyazo.com/09391a77c092bbf4f9fc88591f566a38
この形の数独は唯一解にできないそうです。
21表出の例は難易度以前に決まらない形だったらしい。