難易度と面白さを考慮したナンプレの自動作成問題

ナンプレ制作会社では、自動作成ツールが利用されていますが、現状では「面白さ」を考慮するのが難しいという課題があります。そこで、本問題では「難易度」と「面白さ」を考慮したナンプレの初期盤面（ヒント）を自動作成する最適化問題を提案します。

この問題では、初期盤面から決められた手筋を用いてナンプレを解き、各局面の難易度を計算します。その上で、ナンプレ問題の「ヤマ」となるタイミングや、連鎖的に確定する数字の数を評価指標とし、ナンプレの「面白さ」を定量的に評価します。これにより、より魅力的なナンプレ問題の自動作成を目指します。

ナンプレとは

ナンプレ（ナンバープレース）は、9×9の正方形を3×3のブロックに分けた枠内に、1〜9の数字を埋めるパズルです。このパズルは1980年代から世界各地のパズル愛好家に知られていましたが、アメリカのパズル誌に掲載されていた「Number Place」を、1984年にニコリの鍜治真起氏（当時代表取締役）が日本に紹介しました。

最初は「数字は独身に限る」というユニークな名前でしたが、後に「数独」として親しまれるようになります。そして2000年代には「Sudoku」という名前で世界的に広まり、現在でも数億人に楽しまれています。

日本では、1990年代後半から数独専門誌が発行されていましたが、2005年にイギリスで大衆的なブームが起こり、その影響で2006年以降、日本の新聞や雑誌でも数独の連載がさらに増加しました。

ルール

• 空いているマスに、1から9までの数字を1つずつ入れます。0（ゼロ）は使用しません。
• タテ列（9列）、ヨコ列（9列）、そして太線で囲まれた3×3のブロック（9ブロック）のすべてに、1から9の数字がそれぞれ1回ずつ入るようにします。

ナンプレを遊んでみよう

ニコリの公式ページでは、ブラウザで遊べるナンプレが公開されています。ぜひ挑戦してみてください！
👉 ニコリのナンプレページ

ナンプレの自動作問

日々、ナンプレを作って公開しているナンプレ本の制作会社には、ナンプレの問題を自動で作成したいというニーズがあります。コンピュータを使えば、ナンプレ問題の解が存在するかどうかや解が一意であるかを短時間で判定できるため、自動的に問題を生成することが可能です。実際、すでに多くの自動作問ツールが公開されています。しかし、指定した難易度で「面白い」問題を作るのは簡単ではありません。問題の面白さは、難易度だけではなく、さまざまな要素に左右されます。そこで本ページでは、ナンプレの面白さや難易度の指標を定量化して、最適化する問題を出題します。本節では、ナンプレの面白さや難易度を議論する上で必要な初期盤面、手筋、緊張感、達成感について説明します。

初期盤面

まずは、ナンプレの盤面に最初から埋められている数字の数、いわゆるヒント数について説明します。直感的にはヒント数が多いほど問題が簡単になるように思えますが、実際にはヒント数と問題の難易度には必ずしも直接的な関係があるわけではありません。

非常に易しい問題を作ろうとする場合、ヒント数を増やすことで解きやすくなる傾向があります。しかし、ヒント数が極端に少ない問題では、一意の解を持つようにヒントを適切に配置することが難しくなり、結果として難易度の幅が狭まってしまいます。

一方で、ヒントの配置が無駄なく適切であれば、その問題は「解き心地が良い」と評価されます。ヒント数が少なくてもバランスよく配置されていれば、スムーズに解ける問題を作ることが可能です。このように、ヒント数が少ない問題でも、配置次第で解きやすさと難易度のバランスを両立させることができます。

さらに、良質なナンプレにはヒントが線対称や点対称に配置されていることがよく見られます。これにより、見た目の美しさと解きやすさが両立されます。上の画像よりヒント数17で線対称な問題や、18で1から順に決まる問題が例として挙げられており、対称性の重要性が示されています。

また、ヒントの配置には工夫が凝らされることが多く、例えば上の画像のようなL字型のヒント配置など、特定のパターンを使うことで、残りのマスが簡単に決まる場合があります。

手筋

続いて、ナンプレを実際に解く上で必要となる手筋について説明します。3×3のブロック内や各行・各列だけを見ていても、難易度の高いナンプレ問題を解くことはできません。複数のブロックや行・列の情報を総合してマスの目を決定するための考え方は手筋とよばれます。本ナンプレ自動作成問題では、下記の代表的な手筋のなかから指定された手筋のみを使って解けるナンプレを作成します。

ブロッケン (Hidden Single (box))

上の図の左上ブロックで１が入る場所を探すと、右にある１と同じ列にある（矢印が乗っている）マスは１が重複するので、残るマス㋐が１です。右下ブロックで、上や左にある１と重複しないマスはマス㋑だけです。このように3x3ボックスを見てマス目を埋めていくのがHidden Single (box) です。

レッツミー (Hidden Single (line))

上の図の矢印がついたタテ列で１が入る場所を探すと、上の３マスは同じブロックに１があるので入れることはできません。２と３の間と、４のすぐ下のマスは同じヨコ列に１があるので入れることができません。だからマス㋒が１と決まります。このように一つのタテ列に注目してマスに数字を埋めていくのがHidden Single (line) です。

マスミ (Naked Single)

上の図のマス㋓に注目します。㋓と同じヨコ列にはすでに１と２と４、同じタテ列には６と７と８と９、同じブロックには１と３と６があり、どの数字とも重複しないのは５だけとなります。このように特定のマスに入る数字がひとつしかない場合に使える手筋が Naked Single です。

いずれにしても (Locked Candidates)

上の図で、１は中上ブロックで★のどちらかに入りますが、いずれにしても右上ブロックで 矢印の乗ったマスに１は入らず、マス㋔が１となります｡また､１は左中ブロックでは◎のどちらかですが、いずれにしてもマス㋕に１は入らず、マス㋕はNaked Singleにより９になることがわかります。このように、あるマスに入っている数字がほかのマスへ影響を与えることにより、そこから数字を確定させたり不要な候補数字を消去する手筋がLcked Cadidatesです。

予約 (Hidden Subsets)

上の図の左上ブロックで、１と２が入りうるマスはいずれも★の２つ。つまり★は１と２で 「予約」された形になり、他の数字が入らなくなるので、５はマス㋖に入ります。矢印のついたヨコ列では、１と２が入りうるのはいずれも◎の２マスです。６は◎に入らず、マス㋗に入ります。このように、ある行・列・ボックスの中に、特定の数字のペアやトリプルが隠れていることを見つけ出し、マスを埋めていくのがHidden Subsetです。

井桁 (X-Wing, Basic Fish)

上の図より、矢印がついた２つのタテ列で１が入る場所を探すと、それぞれ△と▲の２マスです。これらが同じ２つのヨコ列にあるので、１は２つの△に入るか２つの▲に入るかのどちらかですが、いずれにしても点線が乗ったマスには入らず、中下ブロックで１はマス㋘に入ります。このように、特定の数字が複数の行や列に規則的に現れることを利用して解を進める手筋がX-Wingです。

緊張感

次に、ナンプレの盤面の変化がプレイヤーに与える緊張感について説明します。

ナンプレにはさまざまな解法（手筋）が存在しますが、それぞれの難易度は異なります。たとえば、「ブロッケン」や「レッツミー」は初心者でも直感的に使いやすい手筋です。一方、「井桁」はナンプレの特徴を深く理解した熟練者向けの手法です。

ナンプレでは、与えられたヒントをもとに、数字を確定させてマスを埋めることで解答を進めます。プレイヤーがマスを埋める過程で、数字が少しずつ増えていく状態を、ここでは「盤面」と呼びます。

盤面によっては、「ブロッケン」や「レッツミー」で簡単に解ける場合もあれば、「井桁」を使わなければ解けない盤面になることもあります。また、同じ「ブロッケン」を使う場面でも、1つのマスしか埋められない盤面は、複数のマスを埋められる盤面よりも難易度が高いと感じられます。

ナンプレの問題では、解いていく途中に適度な難易度の盤面が現れることで、プレイヤーの緊張感を保つことができます。このような緊張感が持続する問題は、プレイヤーにとって魅力的で「面白い」と感じられる要素になります。

達成感

ナンプレでは、3×3のブロックや各行・各列で8つの数字が埋まると、残り1マスの数字が自動的に決まります。その結果、特定の手筋を使うことで、連鎖的に次々と数字が埋まり、盤面の解答が一気に進むことがあります。こうした連鎖的に数字を埋められる盤面が現れると、プレイヤーは達成感を強く感じることができます。この連鎖的な数字の決定による達成感は、「面白い」と感じられるナンプレを作問する上で非常に重要な要素です。

問題の定義

本節では、用語や最適化対象となる目的関数の数学的な定義について説明します。

手番

本問題では、与えられたヒント配置に対して「手筋」を用いてマスを埋めることを「一手番」と定義します。各手番において、与えられたヒント配置に対してタテ列、ヨコ列、3×3のブロック内で１マスだけ埋まっていない数字は自動的に埋められます。つまり、基本のルールから自明に決まる数字を埋めることは、一手番として数えません。

盤面の難易度

$tt$ 番目の手番における盤面を $S(t)S(t)$ とし、盤面 $S(t)S(t)$ のそれぞれのマスに適用できる手筋の集合を $A(t)A(t)$ とします（ $A(t)A(t)$ はすべてのマスにすべての手筋を総当たりして列挙します。なお、同じ手筋でも異なるマスに適用するならば、 $A(t)A(t)$ の異なる要素だと考えます）。このとき、盤面 $S(t)S(t)$ の難易度 $d(t)d(t)$ は、「 $A(t)A(t)$ のいずれかの要素を発見する難しさ」だと考えられます。 $A(t)A(t)$ に初級レベルの手筋が少数でも含まれていれば簡単になりますが、上級レベルの手筋が多数含まれていてもあまり簡単にはなりません。このように、盤面の難易度とは並列抵抗を流れる電流に似た性質をもっています。そこで、難易度 $d(t)d(t)$ を集合 $A(t)A(t)$ の手筋のレベルの逆数の総和の逆数として定義します。

$$d(t)=\frac{1}{\sum _{a\in A(t)}\frac{1}{\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}(a)}}d(t)\; =\; \backslash frac\{1\}\{\backslash sum\_\{a\; \backslash in\; A(t)\; \}\; \backslash frac\{1\}\{\; \backslash mathrm\{level\}(a)\}\}$$

ここで $aa$ は手筋の集合 $A(t)A(t)$ に含まれる手筋であり、 $\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}(a)\backslash mathrm\{level\}(a)$ は $aa$ のレベルです。 $\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}(a)\backslash mathrm\{level\}(a)$ は以下のように設定します。なお、「いずれにしても」と「予約」は細かい手筋の違いでレベルが変動します。

• ブロッケン: 1
• レッツミー: 2
• マスミ: 5
• いずれにしても: 5 ~ 15
• 予約: 10 ~ 25
• 井桁: 35

盤面の難易度の計算の具体的例として、下図のような盤面を仮定して説明します。左の青い矢印がついたタテ列で１が入る場所を探すと、上の３マスは同じブロックに１があるので入れることはできません。同様に２と３の間のマス、４のすぐ下のマスも同じヨコ列に１があるので入れることができません。よって、マス A が１と決まります。これはレッツミーを用いて A を決定可能であることを意味します。続いて右上ブロックで１が入る場所を探すと、下にある１と同じ列にある（赤矢印が乗っている）マスと、左上にある１と同じ行にあるマスは１が重複するので、残るマス B が１と決まります。これはブロッケンを用いて B を決定可能であることを意味します。この盤面の難易度 $d(t)d(t)$ は $\frac{1}{1+\frac{1}{2}}=\frac{2}{3}\backslash frac\{1\}\{1\; +\; \backslash frac\{1\}\{2\}\}\; =\; \backslash frac\{2\}\{3\}$ と計算できます。

連鎖数

各手番について、基本ルールから自動的に決まる数字の個数を 連鎖数 と定義し、 $c(t)c(t)$ と表記します。ここで、「自動的に決まるマス」とは、ある盤面に特定の手筋を適用した際に、他の手筋を必要とすることなく、3×3のブロック内や各行・各列の状況を確認するだけで数字が確定するマスのことを指します。この操作は、確定するマスがなくなるまで繰り返し適用されるものとします。つまり、連鎖的に自動で確定するすべてのマスを埋め終えるまでの過程を含めて、 $c(t)c(t)$ に反映します。

難易ピーク度

難易度の変化からプレイヤーの緊張感を算出するために、以下の式で定義される $tt$ 手番目の難易ピーク度 $p(t)p(t)$ を算出します。

$$p(t)=\sum _{i=1}^T\frac{d(t)-d(i)}{\mathrm{\mid }t-i{\mathrm{\mid }}^2}p(t)\; =\; \backslash sum\_\{i\; =\; 1\}^\; \{T\}\; \backslash frac\{d(t)\; -\; d(i)\}\{|t\; -\; i|^2\}$$

ここで $TT$ はナンプレを解き終わった（全てのマスに数字が埋まった）時点の手番数です。

盤面の更新

次にナンプレの盤面の更新について説明します。本問題では、各手番においていずれかの手筋を適用して盤面に新たな数字を埋めていきます。各手番において適用できる手筋は複数存在しますが、その中から一つの手筋が選ばれて盤面が更新されます。つまり、難易度の計算の具体例に使用した下図のレッツミーとブロッケンの手筋が適用可能な盤面では、レッツミーとブロッケンのどちらかを採用して数字を埋めます。そのため、レッツミーで盤面を更新する場合と、ブロッケンで盤面を更新する場合で次の盤面は異なります。

本問題では、モンテカルロ木探索により確率的に次の盤面を決定することで難易度、難易ピーク度、連鎖数を算出します。このとき、実際にプレイヤーがナンプレを解く際の手筋の選択確率は均一ではなく，選ばれやすい手筋というのもが存在します。本問題では、ナンプレ制作会社のタイムインターメディア様にご協力を頂き、プレイヤーの実際の選好を基準に手筋の選択確率を決定しました。なお、モンテカルロ木探索の乱数シードは固定し、同一のヒントは必ず同じ盤面から評価されるように設定しています。そのため、同じ盤面が異なる難易度、難易ピーク度、連鎖数になることはありません。

解表現

本問題では、ユーザはナンプレの問題として最初に与えるヒントを解として送信します。送信する解は、各要素が0から9の整数の81次元配列です。配列の各要素はナンプレの各マスに対応しており、左上がインデックスが0、右上のインデックスが8、左下のインデックスが71、右下のインデックスが80になるように対応しています。すなわち、左上から右側にインデックスが上昇して、一番右端に到達した場合は1つ下の段に移動する形でインデックスが振られています。配列の要素の数字は、0は空マス、1から9はそれぞれの数字がマスが入っていることを意味します。

目的関数

本問題の目的関数は、2目的で緊張感の観点からの面白さ（ $f_{1}f\_1$ ）の最大化と連鎖的なマス目の決定に関する面白さ（ $f_{2}f\_2$ ）の最大化で構成されます。

緊張感の観点からの面白さ（ $f_{1}f\_1$ ）

緊張感を評価するため、難易ピーク度 $p(t)p(t)$ が最も大きい上位二つの手番を見つけます。 緊張感を保つためには、二つのピークが出来る限り離れていた方がよいため、以下の目的関数 $f_{1}f\_1$ を用いて緊張感の観点から見た問題の面白さを評価します。

$$f_1=\frac{\mid t_1-t_2\mid }{T}f\_1\; =\; \backslash frac\{\backslash left|\; t\_1-\; t\_2\; \backslash right|\}\{T\}$$

ここで、 $t_{1}t\_1$ は難易ピーク度が最も大きい手番数、 $t_{2}t\_2$ は難易ピーク度が２番目に大きい手番数です。

連鎖的なマス目の決定に関する面白さ（ $f_{2}f\_2$ ）

連鎖的なマス目の決定に関する面白さは、最も連鎖した手番の連鎖数を用いて以下ように評価します。

$$f_2=\frac{\max \{c(t)\mid t\in T\}}{81}f\_2\; =\; \backslash frac\{\; \backslash max\; \backslash \{\; c(t)\; \backslash mid\; t\; \backslash in\; T\; \backslash \}\}\{81\}$$

このとき、 $f_{1}f\_1$ においてピークの位置を一手番離すことと $f_{2}f\_2$ において連鎖数を一つ増やすことの価値を同程度にそろえるため、 $f_{2}f\_2$ では最大連鎖数を81で割っています。

最小化問題への変換

OptHubのシステムの都合上、最小化問題として定式化する必要があるため、 $g_1=-f_1,g_2=-f_{2}g\_1\; =\; -f\_1,\; g\_2=-f\_2$ の2目的の最小化問題として出題します。

単目的での利用

本問題を単目的問題で利用する場合には、環境変数MULTI_OBJECTIVEをfalseに設定します。MULTI_OBJECTIVEをfalseにした場合は、環境変数OBJECTIVE_WEIGHTで定義された重み $(w_1,w_2)(w\_1,\; w\_2)$ に基づく加重和 $h=w_1{g}_1+w_2{g}_{2}h\; =\; w\_1\; g\_1\; +\; w\_2\; g\_2$ を目的関数として利用できます。

制約条件

実際のナンプレ作問では、ヒントの配置には工夫が凝らされることが多く、ナンプレを自動作問する上でも特定の位置のみヒントを配置したいというケースが頻出します。本問題では、ヒントの配置があらかじめ設定されており、この配置以外の位置にヒントを設定した解は制約違反解となります。ヒント配置の制約条件は競技ごとにHINT_PATTERNという環境変数によって与えられます。競技に設定されている環境変数の値は、各競技の詳細ページをご覧ください。HINT_PATTERNの0と1はそれぞれ、ヒントを入れない | 入れる ことを表します。

また、ナンプレとしてルールに違反したヒント（解いていくと基本ルールに矛盾するヒント）や最終的な盤面がひとつに決まらない（複数の解が存在する）ヒント、ナンプレを上述の手筋のみで解けないヒントも制約違反解となります。また、環境変数X_WINGがfalseに設定されている問題では、井桁 (X-Wing, Basic Fish)を手筋から除いて目的関数の計算や解けるかどうかの判定を行います。

参考文献

• タイムインターメディア パズルページ
• Sudoku - Wikipedia (英語)
• ニコリHP