TIM Labs

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

| コメント(0) | トラックバック(0)
ナンプレブームが今も続いていて、今年もMATH POWER 2018 に巨大合体ナンプレ世界一(?)を提供することになった。
去年は国政選挙に邪魔されて、六本木のニコファーレが使えず、会場が青山になったが、今年はニコファーレの予定である。
巨大合体ナンプレは現在鋭意制作中であり、世界一になるかどうかはまだ分からない。

さて今回は、合体ナンプレの話ではなく、サイズが9x9の単体のナンプレ問題の話をしよう。

NPSame1.png NPSame2.png
さて、この2つの問題、何が違うだろうか?

ナンプレでは、数字の1から9の値には、数値的な意味はなく、単に9種類の異なるものの意味しかない。
だから、数字ではなく、漢数字の壱弐参四五六七八九でもよいし、鮃鮎鯛鰯鰍鰆鰻鯨鮭でも構わないし、マンガのキャラクタ9人でも何でもよい。

さて、上の2つだが、上の問題から、ナンプレの問題としての性質を変えずに、見かけだけ違うようにする変換(インチキ変換)を施して下の問題を作っている。

よく知られている手法は、

  • 数字を入れ替える。いわゆる置換。
  • 回転、反転などの対称移動。
  • 問題の数字(ヒント)の位置に依存するが、入れ替え可能な縦列の組、横列の組がある。
である。

実は、上の2つの問題は、この手法を使って変形しただけであり、見かけだけを変えたものである。

それでも、見た目がこれだけ違うと、同じ問題と思わない人がほとんどではないかと思う。

さて、今回は、質問を投げて終わりにしょう。

  1. 上側の問題に、どのような変換を施せば下側の問題になるであろうか?
  2. 2つのナンプレ問題の同一性は、どういうアルゴリズムで効率的に検証できるか?

これは、ナンプレ、あるいはパズルに限ったことではなく、プログラミングにおいても時々遭遇する問題である。

秋の夜長に、じっくりと考えてみよう。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/733

コメントする

このブログ記事について

このページは、fujiが2018年8月30日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「末尾の連続する改行文字を削除する」です。

次のブログ記事は「USBデバイスをlsしよう」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ