DifficultyEvaluation

パズル問題自動生成時代　-- ナンプレ -- プログラムで問題を解く

難易度判定

難易度判定の必要性

問題をプログラムで解いていくとき、単に解けたというだけではなく、その問題がどのくらい難しいかが分かると都合が良い。

非常に難しい問題なら、解けなくても落ち込まなくてすむ。また、自分で問題を万一作ってしまったときに、その問題の難易度を調べたい場合もあろう。

多くのパズル本やパズル雑誌の問題には、何段階かで難易度を表示しているものだ。人間が解いてちゃんとストップウォッチで計測して、きちんと評価している編集部もあるようだ。

パズルを遊びとして楽しんでいる間はよいが、今日はこれだけの問題の難易度を確認して下さいとか言われて、来る日も来る日も問題を解いて評価するのは、仕事とはいえ大変だろう。

理由は色々考えられるが、難易度判定は欲しい。

個々のテクニックの難易度

色々細かいテクニックが存在することを示した。分類の方法によってテクニックの数は多いに違うが、だいたい１０個程度あると考えられる。

テクニックを適用できると、問題が少しだけ解き進められる。あるマスの数字が決まるという確実な進歩もあるが、あるマスに入れられない数字が１つ決まるだけの、小さな一歩しか前進しない場合もある。

それでも、テクニックが適用できるということは、適用前の状態と、適用後の状態が必ず何か違うということだ。

パズルプログラミングでは、問題を解き進んでいるときの各状態を、状態(State)と呼ぶ。問題を解くということは、最初の問題の状態から、テクニックを適用して、新しい状態にし、その新しい状態に対してまたテクニックを適用してさらに新しい状態にし、これをくり返して解き終えるのである。

理窟っぽくなってしまった。

このときに適用するテクニックには、簡単なものから難しいものまである。普通、テクニックを難易度順に並べておくのだが、ここでは思い付きで、適当に並べる。

テクニック１	タテ、ヨコ、ブロックのいずれかで、８マスの数が既に決まっている場合は、残りの１マスに入る数字はまだ使われていない数字である。
テクニック２	タテ、ヨコ、ブロックのいずれかで、ある数字を入れられるマスが１つしかなければ、その数字をそのマスに入れる
テクニック３	ある空白マスに注目したとき、そのマスを含むタテ、ヨコ、ブロックの中には、既に８種類の数が存在するとき、そのマスは残りの数に決まる
テクニック４	なんだろう
テクニック５	まだあろう
テクニック６	まだまだあろう
テクニックｎ	最終テクニックは、虱潰しにしておこう

実際にちゃんとテクニックを集めたり、難易度順にならべるのは読者に任せた。自分で無理だと思えば、ネットで探せば、だいたい難易度順に並べてくれているので、横着を決め込んでそういうのに従っても構わない。

アルゴリズムの概要

個々の難易度に対するプログラムの断片(メソッドとか関数とか)は、ちまちま作ればできるだろう。テクニックによっては調べるのが面倒だったりするだろうが、手間さえかければプログラムは可能だと思うのでそれも省略する。

個々のテクニックを組み合わせて問題を解くプログラムのソースもあちこちに転がっているようなので、ネットを探されたし。

一番基本的なことだけを書いておこう。

ある状態(問題)が与えられたとき、全てのマスが埋まっていれば解けている。
まだ解けていなければ、虱潰しを除く普通のテクニックを易しい方から順番に適用してみる。もし適用できたら最初(1.)に戻る。
普通のテクニックで駄目だったら、虱潰しをしてしまう。虱潰しをしてしまえば、解がどうなるかは完全に分かる。

これをくり返すだけなのだが、途中で解けないことが分かることがある。

概念図 (結構いい加減だけど、意図は分かるだろう)

なお、プログラムに特別な工夫をすることで、解が２つ以上ある場合を途中で見つけることもできるが、ここでは考えないことにする。多重解は、最終テクニックの虱潰しによって見つけることにしている。

仮定法

上図は、テクニックで何とかならなかった場合に、いきなり虱潰しをやっているが、普通のテクニックを使い尽くしても駄目だったら、仮定法を使うのが普通だ。

仮定法とは、どこかの空きマスの数字を仮定することで１手進んだことにして、その後を普通に解き進めて行く。そして、矛盾(解がない)に到達した場合に、そのとき仮定した手はあり得ないと判断するものだ。

このとき、仮定する直前の状態に戻らないといけないので、何らかの方法で戻せるようにプログラム(実際にはデータ構造)を作っておかなければならない。プログラム的には、バックトラックになるので、どうやればよいかは、バックトラックをキーワードとして調べれば見つけられるだろうから、ここでは説明は省略する。

仮定法については、これ以上の説明はしないが、プログラムで解く場合、非常に良く使う。「虱潰し」で解くのは普通ではなく、「仮定法」で解くのが普通だと確信するが、この本では、普通でない方の話をできるだけする予定だ。

難易度の計算

ナンプレ本には、各問題毎にレベルが表示されていることが多い。３段階くらいから、１０段階くらいまで色々あるようだが、レベル分けをコンピュータで行なう方法を摸索してみよう。１問を調べ終ると、難易度ポイントが計算され、各レベルをポイントの幅で指定できれば楽である。

多数のテクニックニックがあったが、それぞれのテクニックに、テクニックポイント(難易度ポイント)を与えてみよう。

テクニック	ポイント
テク１	1
テク２	4
テク３	10
テク４	20
テク５	25
テク６	40
テク７	50
テク８	80
テク９	100

とりあえず、各テクニックに対して、整数値で難易度を付けてみよう。後で調整することになると思うので、調整可能なようにプログラムを組んでおこう。

個々のテクニックの難易度ポイントが分かったら、問題の難易度ポイントを考えよう。実は、何も考えず、

問題の難易度ポイント = Σ(一手ごとの難易度ポイント)

としてみよう。つまり、１手決まって、状態が進む毎に難易度ポイントを加算していく。

とりあえず適当に決めたポイントで、パズル本の問題を一気に解いてみよう。できることなら、やさしい問題から難しい問題に順番に並んでいると思われる問題を100問くらい解いてみて、難易度ポイントが昇順に並んでいれば、まずは成功だが、なかなかそうはならないだろう。

実際の一手毎の難易度ポイントは、表よりも低くなっている。それは、一手の決まり方は、必ずしも１つのテクニックで決まるものではなく、複数のテクニックのどれで決めても良い場合には、その１手の難易度はもっと低く評価しているためである。

難易度のチューニング

問題の難易度は、一手ごとの難易度ポイントの総和と仮定した。この仮定は正しいことと考えて、もし本１冊の計算結果の難易度ポイントの並びが良くなかったら、調整(テクニックポイントのチューニング)をしよう。

本の問題が難易度順に正しく並んでいると仮定すると、横軸に問題番号、縦軸に難易度ポイントをプロットすると、以下のような図になる。

上図は、かなり調整が進んだ段階だ。右の方は難問で、難問に関しては、人間でさえ評価が分かれてしまうことがしばしばあるので、右側の発散はとりあえず無視しよう。

左の、初級から中級程度の問題に対しては、右肩上がりで、並んでいることが望ましい。

上の図でも、一部の点(青〇)が上または下にかなり外れていると思われる問題である。ずれている原因は、大きく分けて２つある。

(１) 上に飛びだした場合

特定のテクニックのポイントを高くつけ過ぎた場合もあるが、実際には、もっと簡単なテクニックで解けるのに、

プログラムは易しいテクニックを使わなかった。
やさしいテクニックをプログラムに組みこむこと自体を忘れた。
本当は難しい問題なのに、問題評価者が間違えた。

などが考えられる。

(２) 下に飛びだした場合

この場合も色々考えられる。

難しいテクニックに低いポイントを与えてしまった。
本当はやさしい問題なのに、問題評価者が疲れて、問題を解くのに苦労した。

(１)、(２)の場合に、原因をハッキリさせて、プログラム側に問題がありそうだったら、調整しよう。延々と調整すると、しだいに上下の飛び出しが少ない、右肩上がりの図になるはずだ。

【補足】

本によって、難易度の精度は非常に異なる。どのように異なるかは、非常に高度な話になってしまうのと、実際の問題集を示して議論しないと意味が薄れるので、これ以上は書かない。

もっと詳しく調べたい場合には、パズル本をせっせと入手し、問題を自分で延々と入力して、調査されたい。そうすると、パズル本(出版社、編者)の傾向や能力が判別できることを保証しよう。

レベル分け

難易度ポイントは、あくまでもプログラム側の都合である。だから、整数値あるいは実数値で出れば十分であろう。

しかし、問題は、最終的には人間が解いて楽しむ(苦しむ)ものであり、人間にとって分かりやすい分類をしないと役に立たない。

現状のシステム(※)は、とりあえず13段階にしてある。レベル 1〜10 を、普通のナンプレ本の難易度範囲に合わせている。しかし、勝手に難しい問題も出来ることがある。さらに、非常に難しい、難問を欲しい変人もいるであろうから、私自身が解く気が起きない、あるいは解けないレベルの問題を11以上に設定している。

ということで、主観を思いっきり入れたレベル分けをしている。

だいたい、3段階ずつで区切るこで、以下のようになっている。

レベル	説明	難易度ポイント合計
1〜3	やさしい	〜80
4〜6	ふつう	〜130
7〜9	難しい	〜300
10〜12	とても難しい	〜3000
13	人間には無理	3000以上

せいぜい、レベル10までしか出題したくないと思っている。どうしても難問が欲しいという場合に限り、レベル12までを提供しているが、それでもレベル12はお薦めしていない。

レベル13は、極端に難しいテクニックが何度も出てきたか、あるいは虱潰しで答が1つしか無いことが確認できた場合である。虱潰しでしか分からなかった場合はレベル14とするのもあろうが、人間が解くような問題ではないだろうと思った問題はレベル13に統一している。そして、この問題は、通常はごみ箱に直行にしている。

実際のレベル分けは、難易度ポイントポイント以外も利用している。そのあたりの詳しいことは、忘れなければ後で述べる。

(※補足) 現状のシステムというのは、本記事を書いた2006年当時の自動生成システムのことであり、このサイトで紹介している自動生成システムとは異なる。

Home

パズル問題自動生成時代

ナンプレ

パズル問題自動生成時代 -- ナンプレ -- プログラムで問題を解く