スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ナンプレにおける解の個数について

ナンプレ (ナンバープレース、数独) の問題を出題する際、その解はただ一つであることが要求されます。そのことを踏まえたうえで、「ヒントとして最初に配置する数字は何個まで減らせるか」という疑問に対し、ついに結論が出ました。

最初に配置された数字が 16 個以下のとき、解が常に複数存在してしまうことが、アイルランドの数学者 Gary McGuire 氏によって最近 (2012年1月7日) 証明されました。

Nature:Mathematician claims breakthrough in Sudoku puzzle
GIGAZINE:数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論

※ ちなみに、Nature の記事に図として掲載されているナンプレの問題は、解を複数もちます。

最初に配置された数字が 17 個以上のとき、解がただ一つであるような問題は複数存在します。以下のサイトでは、最初に配置された数字がちょうど 17 個の問題を多数紹介しています。

Minimum Sudoku

ある問題が解をただ一つだけもつとき、その解と合致するように数字を増やしていけば、解はただ一つのままです (解と合致しないように数字を追加したら解は存在しなくなります)。

一方で、最初に配置された数字が 17 個より多い問題で、数字を一つでも減らすと解がただ一つにならないものがあります。例えば、

0,2,0,0,0,0,0,8,0,
4,0,0,7,8,0,0,0,3,
0,0,9,1,0,3,4,0,0,
0,0,0,3,0,5,0,0,0,
0,6,0,0,0,0,0,1,0,
0,0,7,2,0,0,3,6,0,
0,0,1,0,0,2,9,0,0,
6,0,0,0,7,0,0,0,1,
0,7,0,0,0,0,0,4,0

※ 空白のマスを 0 で表しています。

は、最初に配置された数字が 26 個で、いずれかの数字を減らすと解を複数個もちます。

複数の解をもつ問題において、最初に配置された数字の個数は最多で 77 個です。例えば、

0,0,3,4,5,6,7,8,9,
4,5,6,7,8,9,1,2,3,
7,8,9,1,2,3,4,5,6,
0,0,4,3,6,5,8,9,7,
3,6,5,8,9,7,2,1,4,
8,9,7,2,1,4,3,6,5,
5,3,1,6,4,2,9,7,8,
6,4,2,9,7,8,5,3,1,
9,7,8,5,3,1,6,4,2

は、以下の二つの解をもちます。

1,2,3,4,5,6,7,8,9,
4,5,6,7,8,9,1,2,3,
7,8,9,1,2,3,4,5,6,
2,1,4,3,6,5,8,9,7,
3,6,5,8,9,7,2,1,4,
8,9,7,2,1,4,3,6,5,
5,3,1,6,4,2,9,7,8,
6,4,2,9,7,8,5,3,1,
9,7,8,5,3,1,6,4,2

2,1,3,4,5,6,7,8,9,
4,5,6,7,8,9,1,2,3,
7,8,9,1,2,3,4,5,6,
1,2,4,3,6,5,8,9,7,
3,6,5,8,9,7,2,1,4,
8,9,7,2,1,4,3,6,5,
5,3,1,6,4,2,9,7,8,
6,4,2,9,7,8,5,3,1,
9,7,8,5,3,1,6,4,2

最初に配置された数字が 78 個以上のものは、複数の解をもちません。実際、空白マスが 3 個以下のとき、それらのマスに入る数字は最初に配置された数字から一意的に決定されてしまいます。

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。