数独
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/02/13 06:43 UTC 版)
![]() |
同様のパズルそのものは1980年代から世界各地のパズル愛好家には知られていた。日本においては1990年代後半以降、専門誌も創刊されていたが、2005年にイギリスで大衆層を巻き込んだブームが起こり、外国のブームを追うように2006年から日本でも連載する新聞や雑誌が従前以上に増加した[1]。
世界パズル選手権では、スケルトンやお絵かきロジック、その他さまざまなパズルとともに数独 (SUDOKU) も毎年出題されている。
名称
アメリカのパズル誌に載っていた「Number Place」というパズルを、パズル制作会社ニコリの代表取締役鍜治真起が、名称だけ「数字は独身に限る」(略して、数独)と変えて日本で発表したことが始まりで[2][3]、同社の関与する媒体で使用される名称である。同社によって商標登録[4] がされており、日本国内においては同社が制作に関与していないものについては「ナンプレ(ナンバープレース)」などの表記が使われている。
2008年、高等学校英語の教科書に取り上げられた数独に関する文章について、教科書検定の結果「特定の商品の宣伝になる恐れがある」との理由で表記を「Sudoku」から「puzzle」などに修正を求められたと報じられた[5]。
一方、日本国外では同社による商標登録が行われておらず、同社が制作に関与していないものについても「sudoku」の呼称が用いられている場合が多い。また、従前からの名称である「number place」「figure place」の呼称も引き続き用いられている。
遊び方
基本的なルールは簡単で、下記の3つだけである。
- 空いているマスに、1〜9のいずれかの数字を入れる。
- 縦・横の各列に、同じ数字が重複して入ってはいけない。
- 太線で囲まれた3×3のグループ(以降「ブロック」と呼ぶ)内に、同じ数字が重複して入ってはいけない。
解法
- 一つのマスに注目して、そのマスに入る数字を限定する。
- 一つの列(またはブロック)に注目して、特定の数字が入るマスを探す。
基本的な問題はこの2つで解くことが可能である。具体例としては、
- あるブロックとただ一つの数字に注目し、他のブロックで既に決定された列を候補から排除し、数字が入るマスを限定する。
- 例題の上端横に伸びる赤い線の左端に5があり、上段右のブロックの上段には5は入らない。同じく、その下の短い横に伸びる赤い線の左端にも5があり、上段右のブロックの中段には5は入らない。さらに、下段右のブロックの5のある列も上段右のブロックの5の入る候補から排除する。上段右のブロックのまだ赤線の引かれていない2マスの内、一つは既に数字が確定しているので、残った緑色のマスには5が入る以外にない。
中級以上の手筋としては、数字が入るマスは確定しないが、ある制約により数字が入る場所が限定され決定することがある。具体例としては、
- ある数字が入る場所が、単一ブロックの同一列に限定されるとき、他のブロックのその列には入らない。
- 例題の中段左のブロックで9が入るのは、上段左のブロックの中央列に9が既にあるので、右側の列である。よって、下段左のブロックでは、9の入る列が左列と確定する。下段中央、下段右のブロックの9の列も既に決まっているので、下段左のブロックの6の左横に9が入ることが確定する。
- 個の数字が個のマスに入ることが限定されるとき、他の数字はそれらのマスに入らない。
- 例題の下段中央のブロックで、2が入るのは下段のみである。また、6が入るのも下段のみである。よって、下段の2つのマスには2と6のみしか入れず、下段中央のブロックに入るべき他の数字3と5と7は、上段の3つのマスに入ることが限定される。さらにその3と5と7の入る行に注目する。緑色のマスに入るのは既に9と判明しているので、その行の残り2つのマス(下段左のブロックの右上隅と、下段右のブロックの右上隅)に入るのは1と4ということになる。2つのうち下段右のブロックの右上隅のマスに注目すると、その2つ上のマスには既に1が入っているので、このマスに入るのは1ではない、つまり4だということになる。同時にもう片方のマス(下段左のブロックの右上隅)に入るのは1と確定する。
以上のような解法が一般に知られている。
初期配置
日本国内で数独の問題を発表するときには、最初に盤面に提示するヒントとなる数字の配置(初期配置)を点対称形にするのが一般的である。ただし、ナンプレなど、他の名称で作成・公開されているものについては、必ずしもこの規則に従っていない。
初期配置の数字の数は年々減少し、現在では20〜30個程度が多く、中でも24個のものが非常に多い。また、初期配置の数字の数は、少なければ少ないほど難しくなるというわけではなく、難しい数独を作ろうとすると、20〜25個程度になる[6]。
ニコリと世界文化社を除くほとんどの出版社では、初期配置の数字の数は24〜38個程度で、易しいものほど多く、難しいものほど少なくなっている。
最少個数
数独の初期配置の数字の最少個数は、17個である。2012年1月6日、アイルランドの数学者 Gary McGuire は「数独においてヒントが16個以下のものは解法を持ちえない」ということを証明した。証明にあたっては「ヒッティング・セット・アルゴリズム[7]」を用いて単純化し、2年間で700万CPU時間をかけ、答えにたどり着いた[8]。以前は、問題として成立する初期配置の数字の最少個数は結論が出ていなかったが、点対称の問題では18個(初出・パズル通信ニコリ31号、1990年)、線対称(対角線)・非対称のものでは17個(後者の初出・パズラー187号、1997年)のものが確認されていた。 また、どの初期配置の数字もそれが無かったら唯一解でなくなる問題の初期配置の数字の最多個数は、今のところ35個のものが確認されている[9]。
なお、複数の解が存在する初期配置の数字の最多個数は77個である[10]。
標準以外
標準のルール以外の場合、初期配置の数字の数はさらに少なくすることができる。対角線上でも同じ数字が重複してはいけない「対角線ナンプレ」では、点対称・線対称(水平もしくは垂直)・非対称の問題で12個のものが確認されている。ブロックの形を変更した「幾何ナンプレ」では、ブロックの形状次第では8個で問題が成立する。このタイプの問題の場合、N×N のサイズでは初期配置の数字の数が N-1 個の問題を作ることができる。この形式を含め、数字が意味を持たない形式の場合、初期配置の数字の数が N-2 個以下で一意解の問題を作ることができない。
数字が意味を持つ場合、初期配置の数字の数をさらに少なくすることができる。隣接マスの相互関係を利用する「不等式ナンプレ」や、数字の合計を利用する「サムナンプレ」では、マスに1つも数字が入っていない問題が出題されることがある。「1つ違いナンプレ」は隣接するマスの相互関係を利用する問題だが、これは初期配置の数字の数を0にすることはできない。
大きい問題
標準ルールでマスの数を増やした形式については、あまり調べられていない。
これらに対して統計を取った例はほとんどないが、ニコリ発行の『数独通信』によれば、16×16で74個(『数独通信』Vol.1(2006年2月) とくしん作)・25×25で241個(『パズル・ザ・ジャイアント』Vol.11(2000年7月)Pukupuku作)の問題が確認されている[11]。 印刷物の形では発行されていないが、2006年7月に16×16で初期配置の数字の数が64個(点対称)のものと62個(非対称)のものが発表されている[12]。 2011年に16×16の場合の初期配置の数字の最小個数がGPCCに取り上げられた[13]。出題時点では上記の62個が最小となっていたが、2011年4月11日現在56個のものが発見されている。
また、2018年10月6日、「アスキードワンゴ」「すうがくぶんか」「和から」共同主催の「数の祭典 MATH POWER 2018」において3✕3を280個連結したものをニコニコ動画で公開生中継し21時間経過したところで完成、ギネス記録として認定された[14]。
- ^ 西山豊「Sudokuがイギリスで大ブレイク」『数学セミナー』(日本評論社), Vol.45, No.5, 40-44, 2006年5月
- ^ “「数独」の名付け親、鍜治真起さん死去 ニコリを設立:朝日新聞デジタル” (日本語). 朝日新聞デジタル. 2021年8月18日閲覧。
- ^ “「数独」鍜治真起さん死去 読者参加でファン拡大、世界に2億人” (日本語). 毎日新聞. 2021年8月18日閲覧。
- ^ 英文表記「Sudoku」も含む。日本第3327502号、日本第4936155号、日本第4980699号、日本第5056856号、日本第5060568号。
- ^ 社会部 村井正美; 社会部 渡辺光彦 (2008年3月26日). “[解説]高校教科書検定…1冊で383か所指摘も、文科省の厳しさ浮き彫り”. YOMIURI ONLINE (読売新聞社). オリジナルの2008年5月17日時点におけるアーカイブ。
- ^ 「数独データランド」(数独通信Vol.16、ニコリ、2009年11月10日)
- ^ 英: hitting-set algorithm
- ^ 数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論
- ^ ヒント数最大のナンプレ 稲葉のパズル談話室 2008年6月16日
- ^ 瀬山士郎 編 『数学は楽しい』日経サイエンス、2010年2月18日。ISBN 978-4-532-51169-2。
- ^ ニコリ『数独通信』Vol.18(2010年5月)P.44-45「数独データランド」
- ^ プログラミングパズル雑談コーナー 2006年7月10日の書き込み
- ^ GPCC 2011(2011年5月29日閲覧)
- ^ “ギネス世界記録™達成!TIM提供、世界最大のマルチナンプレ・パズル ~『数学の祭典 MATH POWER 2018』にて正式認定~” (日本語). Webシステム開発/教育ソリューションのタイムインターメディア. 2021年4月22日閲覧。
- ^ 仏: Le Siècle
- ^ 仏: La France
- ^ 英: number place
- ^ 英: figure place
- ^ 「鍜治真起の足あと」P.50 ニコリ刊
- ^ Jarvis, Frazer; Ed Russell (2005年9月7日). “There are 5472730538 essentially different Sudoku grids ... and the Sudoku symmetry group”. Frazer Jarvis's home page. 2006年9月16日閲覧。
- ^ 数字のパズルの本 | WEBニコリ
- >> 「数独」を含む用語の索引
- 数独のページへのリンク