(18) Back_to_win との決別 （A サーチ新展開）

西山豊著｢数学を楽しむ」の第27話に「Sudokuがイギリスで大ブレイク」がある。この中で「Sudokuはたしかに達成感の味わえるパズルである。クロスワードパズルのように鉛筆と消しゴムというスタイルには向かないような気がする。それは、難しい問題になると数字の配置を仮定することが多く、行き詰った場合どこまで戻ればよいのかわからなくなるからだ。これはやはりパソコン向きのパズルではないのだろうか。」

実際にはそうでなく、数字の見つけ方がいくつもあり、そこに数独の醍醐味があるのだが、その頃にはまずこの仮定法とか山登り法とかいう探索法を何とかしたいという思いでいっぱいであった。

数独の解く過程を山登りに例えると、EasyやMedium　の問題では、山頂(Final answer)にたどり着くルートはいくつものあり、緩やかなルートもあり、険しいルートもあるが、どの道を通っても山頂にたどり着ける。ところが、Hardな問題では、途中に山小屋にたどり着いてもその先、道は二つに分かれていてどちらか一つだけが正しい道なのだ。誤った道を選んでもまた山小屋があり、また道をえらぶ。また山小屋という風なことが数回繰り返し挙句の果てに行き詰まりでもとに戻るということになる。何回も山小屋を通過しているので「どこまで戻ってよいのかわからない」のだ。

back_to_win というのは、いうなれば山小屋が二つ、つまりルートは四つに対応している。だからHard な問題では解けないことになる。ごく初歩のAサーチであった。

Sudoku_Ver9 では　back_to_win マクロと決別し、新たなアルゴリズムの new_class_search というのに変更した。Ver9　では３０ルートまでたどることができるし、何よりその山のぼりの方法に工夫を凝らしたのである。