ナンプレの同一問題の判定


2018年 08月 30日

ナンプレブームが今も続いていて、今年もMATH POWER 2018 に巨大合体ナンプレ世界一(?)を提供することになった。
去年は国政選挙に邪魔されて、六本木のニコファーレが使えず、会場が青山になったが、今年はニコファーレの予定である。
巨大合体ナンプレは現在鋭意制作中であり、世界一になるかどうかはまだ分からない。
さて今回は、合体ナンプレの話ではなく、サイズが9x9の単体のナンプレ問題の話をしよう。
NPSame1.png NPSame2.png
さて、この2つの問題、何が違うだろうか?
ナンプレでは、数字の1から9の値には、数値的な意味はなく、単に9種類の異なるものの意味しかない。
だから、数字ではなく、漢数字の壱弐参四五六七八九でもよいし、鮃鮎鯛鰯鰍鰆鰻鯨鮭でも構わないし、マンガのキャラクタ9人でも何でもよい。
さて、上の2つだが、上の問題から、ナンプレの問題としての性質を変えずに、見かけだけ違うようにする変換(インチキ変換)を施して下の問題を作っている。
よく知られている手法は、
  • 数字を入れ替える。いわゆる置換。
  • 回転、反転などの対称移動。
  • 問題の数字(ヒント)の位置に依存するが、入れ替え可能な縦列の組、横列の組がある。
である。
実は、上の2つの問題は、この手法を使って変形しただけであり、見かけだけを変えたものである。
それでも、見た目がこれだけ違うと、同じ問題と思わない人がほとんどではないかと思う。
さて、今回は、質問を投げて終わりにしょう。
  1. 上側の問題に、どのような変換を施せば下側の問題になるであろうか?
  2. 2つのナンプレ問題の同一性は、どういうアルゴリズムで効率的に検証できるか?
これは、ナンプレ、あるいはパズルに限ったことではなく、プログラミングにおいても時々遭遇する問題である。
秋の夜長に、じっくりと考えてみよう。