数独

数独（すうどく）は、3×3のブロックに区切られた 9×9の正方形の枠内に1〜9までの数字を入れるペンシルパズルの一つである。「ナンバープレース（ナンプレ）」とも呼ばれる。

概要

このパズルそのものは1980年代から世界各地のパズル愛好家には知られており、日本においては1990年代後半以降、専門誌も創刊されていたが、2005年にイギリスで大衆層を巻き込んだブームが起こり、外国のブームを追うように2006年から日本でも連載する新聞や雑誌が従前以上に増加した^[1]。

世界パズル選手権では、スケルトンやお絵かきロジック、その他さまざまなパズルとともに数独(SUDOKU)も毎年出題されている。

名称

「数独」という呼称は「数字は独身に限る（すうじはどくしんにかぎる）」の略語で、日本国内においては日本のパズル制作会社ニコリの発行するパズル雑誌『パズル通信ニコリ』をはじめとした、同社の関与する媒体で使用される名称。同社によって商標登録^[2]がされており、日本国内においては同社が制作に関与していないものについては「ナンプレ（ナンバープレース）」等の表記が使われている。2008年、高等学校英語の教科書に取り上げられた数独に関する文章について、教科書検定の結果「特定の商品の宣伝になる恐れがある」との理由で表記を『Sudoku』から『puzzle』などに修正を求められたと報じられた^[3]。

日本国外では同社による商標登録が行われておらず、同社が制作に関与していないものについても「sudoku」の呼称が用いられている場合がある。また、従前からの名称である「number place」「figure place」の呼称も引き続き用いられている。

ルール

空いているマスに1〜9のいずれかの数字を入れる。
縦・横の各列及び、太線で囲まれた3×3のブロック内に同じ数字が複数入ってはいけない。

解法

一つのマスに注目して、そのマスに入る数字を限定する。
一つの列（または3×3のブロック）に注目して、特定の数字が入るマスを探す。

基本的な問題はこの2つで解くことが可能である。具体例としては、

あるブロックとただ一つの数字に注目し、他のブロックで既に決定された列を候補から排除し、数字が入るマスを限定する。
- 例題の上端横に伸びる赤い線の左端に5があり、上段右のブロックの上段には5は入らない。同じく、その下の短い横に伸びる赤い線の左端にも5があり、上段右のブロックの中段には5は入らない。さらに、下段右のブロックの5のある列も上段右のブロックの5の入る候補から排除する。上段右のブロックのまだ赤線の引かれていない2マスの内、一つは既に数字が確定しているので、残った緑色のマスには5が入る以外にない。

中級以上の手筋としては、数字が入るマスは確定しないが、ある制約により数字が入る場所が限定され決定することがある。具体例としては、

ある数字が入る場所が、単一ブロックの同一列に限定されるとき、他のブロックのその列には入らない。
- 例題の中段左のブロックで9が入るのは、上段左のブロックの中央列に9が既にあるので、右側の列である。よって、下段左のブロックでは、9の入る列が左列と確定する。下段中央、下段右のブロックの9の列も既に決まっているので、下段左のブロックの6の左横に9が入ることが確定する。
$n$ $n$ 個の数字が $n$ $n$ 個のマスに入ることが限定されるとき、他の数字はそれらのマスに入らない。
- 例題の下段中央のブロックで、2が入るのは下段のみである。また、6が入るのも下段のみである。よって、下段の二つのマスには2と6のみしか入れず、下段中央のブロックに入るべき他の数字3と5と7は、上段の三つのマスに入ることが限定される。さらにその3と5と7の入る列に注目する。緑色のマスに入るのは既に9と判明しているので、その列の残り2つのマス（下段左のブロックの右上隅と、下段右のブロックの右上隅）に入るのは1と4ということになる。2つのうち下段右のブロックの右上隅のマスに注目すると、その2つ上のマスには既に1が入っているので、このマスに入るのは1ではない、つまり4だということになる。同時にもう片方のマス（下段左のブロックの右上隅）に入るのは1と確定する。

以上のような解法が一般に知られている。

初期配置

日本国内で数独の問題を発表するときには、最初に盤面に提示されている数字の位置を対称形や文字などの形にするのが一般的である。

最初にヒントとして配置する数字の数は年々減少し、現在では20～30個程度が多く、中でも24個のものが非常に多い。また、最初にヒントとして配置する数字の数は、少なければ少ないほど難しくなるというわけではなく、難しい数独を作ろうとすると、20～25個程度になる^[4]。

ニコリと世界文化社以外のほとんどの出版社では、問題の最初にヒントとして配置する数字の数は24～38個程度で、易しいほど多く、難しいものほど少なくなっている。

最少個数

数独の初期配置の最少個数は、17個である。2012年1月6日、アイルランドの数学者ゲイリー・マクガイア（英語版）は「数独においてヒントが16個以下のものは解法を持ちえない」ということを証明した。証明にあたっては「ヒッティング・セット・アルゴリズム^[5]」を用いて単純化し、2年間で700万CPU時間をかけ、答えにたどり着いた^[6]。以前は、問題として成立する初期配置の数字の最少個数は結論が出ていなかったが、点対称の問題では18個（初出・パズル通信ニコリ31号、1990年）、線対称（対角線）・非対称の物では17個（後者の初出・パズラー187号、1997年）のものが確認されていた。また、どの初期配置の数字もそれが無かったら唯一解でなくなる問題の初期配置の数字の最多個数は、今のところ35個のものが確認されている^[7]。

なお、複数の解が存在する初期配置の数字の最多個数は77個である^[8]。

標準以外

標準のルール以外だと、表出個数は更に少なくなる。対角線上の数もそれぞれ1つずつ入れる「対角線ナンプレ」では、点対称・線対称（水平もしくは垂直）・非対称の問題で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作）の問題が確認されている^[9]。印刷物の形では発行されていないが、2006年7月に16×16で表出が64個（点対称）のものと62個（非対称）のものが発表されている^[10]。 2011年に16×16の最小表出数がGPCCに取り上げられた^[11]。出題時点では上記の62個が最小となっていたが、2011年4月11日現在56個のものが発見されている。

歴史

フランスの日刊紙「ル・シエクル^[12]」は1892年に、2桁の数字を使用する同様のパズルを掲載している。1895年には別の日刊紙「ラ・フランス^[13]」が1桁の数字で9×9の盤面を埋めるパズルを掲載しているが、これは3×3のブロックを用いていなかった。これらのパズルはしばらくフランスのいくつかの新聞に毎週掲載されていたが、いずれも第一次世界大戦前後には姿を消した。

現在の数独は、アメリカ人建築家ハワード・ガーンス（英語版）が匿名で考案したものである。これは18世紀にスイスの数学者レオンハルト・オイラーが考案した、ラテン方陣あるいはオイラー方陣と呼ばれるものに、3×3のブロックという新たな制限を付け加え、ペンシルパズルとしたものである。これは「ナンバー・プレイス^[14]」の名前で1979年にニューヨークの出版社デル・マガジン社から初めて出版された。当時から「フィギュアー・プレイス^[15]」という名称も存在している。

日本には、ニコリの『月刊ニコリスト』1984年4月号で、「数字は独身に限る」の題で初めて紹介された。命名者はニコリ社長の鍜治真起である。

1988年 4月1日、ニコリから単行本『ペンシルパズル本6・数独1』が刊行された際、ニコリによる公式な略称として「数独」という名称が使用され始めた。以後数年間は「数字は独身に限る」の方が引き続き正式名称で、「数独」が正式名称となったのは1992年 3月1日発行の『パズル通信ニコリ37号はる分』からである。

世界的な流行は、1997年に59歳のニュージーランド人ウェイン・グールド（英語版））が日本の書店で数独の本を手にとったことに始まる。グールドは6年後、数独をコンピュータで自動生成するプログラムを作る事に成功。イギリスの新聞・タイムズに売り込み、2004年 11月12日から Su Doku の名で連載を開始した。2005年4月から5月にかけてブームに火が付き、インデペンデント、ガーディアン、ザ・サン、デイリー・ミラーなどイギリスの主要日刊紙に軒並み掲載されるという状況になった。2005年7月1日にはテレビ局スカイ・ワンが、数独をテーマにした初のテレビ番組を放映。イギリスでの人気は他国にも飛び火し、パズルとしては1980年頃のルービック・キューブ以来の大流行と言われた。

世界選手権

2006年 3月10日、11日にはイタリアのルッカで初の世界選手権（世界ナンプレ選手権）が開催され、22カ国85名が参加した。優勝はチェコの女性ヤナ・ティローバである。女性が国際的なパズル選手権で優勝するのは世界パズル選手権でも例がないことだった。日本代表はパズル作家の西尾徹也の4位が最高だった。

2007年にはプラハで第2回大会が開催され、個人ではアメリカのトーマス・スナイダーが、チームでは日本が優勝した。また、これに伴い、日本では世界選手権の参加者の選抜を兼ねた日本選手権が行われた。この大会は日本パズル選手権（世界パズル選手権の日本代表選考を兼ねる）と同様世界文化社が主催している。

選手権の正式名称は World Sudoku Championship（世界数独選手権）だが、公式な日本語名は、商標の関係もあり「世界ナンプレ選手権」となっている。

年	開催国	開催都市	個人			団体
年	開催国	開催都市	金	銀	銅	金	銀	銅
2006	イタリア	ルッカ	ヤナ・ティローバ	トーマス・スナイダー	Wei-Hwa Huang	-	-	-
2007	チェコ	プラハ	トーマス・スナイダー	楠井悠平	Peter Hudak	日本	アメリカ合衆国	チェコ
2008	インド	ゴア	トーマス・スナイダー	楠井悠平	Jakub Ondrousek	チェコ	日本	ドイツ
2009	スロバキア	ジリナ	Jan Mrozowski	Branko Ceranic	Robert Babilon	スロバキア	チェコ	セルビア
2010	アメリカ	フィラデルフィア	Jan Mrozowski	Jakub Ondrousek	條秀彰	ドイツ	チェコ	日本
2011	ハンガリー	エゲル	トーマス・スナイダー	森西亨太	Tiit Vunk	ドイツ	チェコ	アメリカ合衆国
2012	クロアチア	クラリェヴィツァ	Jan Mrozowski	森西亨太	條秀彰	日本	チェコ	中国
2013	中国	北京	Jin ce	森西亨太	Jakub Ondroušek	中国	チェコ	日本
2014	イギリス	ロンドン	森西亨太	Tiit Vunk	Bastien Vial-Jaime	日本	ドイツ	中国
2015	ブルガリア	ソフィア	森西亨太	Tiit Vunk	Jakub Ondroušek	日本	中国	チェコ

バリエーション

数独の中には、新しいルールを付加したり一部のルールを変更した物が多く存在する。

大きさの変更

一般的な数独は枠の大きさが9×9であるが、一辺のマスの数を増やして大型化したものが考えられる。ブロック分けの関係上、一辺のマスの数は平方数にすることが多い。16×16や25×25程度のサイズは比較的よく見られ、毎号のように掲載している専門誌もある。これ以上のサイズでは、36×36のものが世界文化社発行の「ナンプレ」1997年11月号に掲載されている。今までにパズル誌で発表された最大の問題は、49×49である。

平方数にせず、各ブロックを長方形に分割した問題もあり、世界選手権においては、6×6（2×3のブロックが6個）の問題が出題されている。

ルールの付加

数独のルールに新たな条件を追加したものがある。代表的なものには以下のようなものがある。追加の条件にはそれ自体が解答のヒントとなるものも多いため、同程度の難易度の通常の問題に比べ初めから数字で埋められているマスは少ないことが多い。

対角線

縦横な3×3のブロックの他に、対角線にも全ての数字が揃うようにしなければならない問題。対角線を強調するために点線が引かれていることも多い。

重ね合わせ

複数の問題がマスを共有している問題。共有された部分のマスはそれぞれの枠の一部であるため、それらすべてから制約を受ける。

リレー

ある問題の解答の一部がそのまま次の問題のヒントとして用いられる。

任意の9マス

9×9の問題の81マスの内、9マスのみ色分けなどによって限定し、その9マスには1から9の数字が一つずつ入るように制限を設ける問題。

合計値

すべてのマスが3×3のブロックとは別に1〜4個程度のブロックに分けられており、各ブロックの合計が指定されている問題。「サムナンプレ」「Killer Sudoku」などと呼ばれる。

入る数字の制限

色分けなどによってマスを分別し、「色つきのマスには偶数のみ入る」などのようにマスに入る数字を制限した問題。

隣り合ったマスの関係

マスの境界線に記号を置くことにより、隣り合ったマスに条件が課せられる問題。以下の2つが多い。

不等号によって隣り合ったマスの大小関係が指定されている。
問題によって指示される記号を挟むマスの数の差が1になる。はさまれない場合の差は2以上が多い。

ルールの変更

ルールの一部を変更したものがある。

最も代表的なものは、本来3×3の正方形であるブロックの形状を変更したものであり、「幾何（模様）ナンプレ」などの名称で呼ばれる。

他に、立方体の表面上に数字を並べる物や、数字が2つ入るマスを設け各列に10個ずつ数字が入る物、などがある。

入る数字の変更

入る数字の表記法を制限して、表記の一部を表示するタイプの問題がある。世界選手権では、以下のようなものを入れる問題が登場した。

電卓などで使用される7セグメントの数字
サイコロの目
英単語

例えば英単語の場合、1（ONE）なら3文字、7（SEVEN）なら5文字など、各マスに入る数字の文字数が指定されており、「4文字のマスの2文字目が"I"」などスペルの一部が与えられ、これを手がかりに解いていく。

コンピュータと数独

前記のウェイン・グールドがタイムズ紙に問題を提供していた例のように、コンピュータを用いて数独の問題を解答したり作成したりすることも広く行われている。日本でも、インフォレストが2004年1月から(外注のプログラマが作成した)プログラムで生成された問題を誌面に掲載しているなど、コンピュータによって作成された問題が商業誌に使用されるも例も多い。

ルールの単純さから多くの解答プログラムが作られており、フリーウェアとして公開されているものも多い。多くのプログラムは9×9の標準の形式の解答しかできないが、大きいサイズの問題や対角線の条件が加わったものなども解けるプログラムもある。

問題作成プログラムは、解の存在をチェックするために解答プログラムを内包することになるため、解答プログラムよりも数は少ない。コンピューターで問題を作成する利点としては、短時間で多くの問題が作れることや、「盤面に17個しかない」などのより限定された条件の問題を作ることができることがあげられる。

ただし、コンピュータで面白い問題が作れるかどうかは別の話である。パズル通信ニコリの編集部及び読者や、西尾徹也のように日本で専門の雑誌が刊行されるよりも前から数独を作っている作家の中には、「コンピュータ作成の問題より人間が手で作った問題の方が解いて面白い」という意見が存在している。

コンピュータゲームの数独

数独専用の電子ゲーム機やウェブサイト上でAdobe Flash（アドビ・フラッシュ）を用いたものなど様々なバリエーションが存在する。以下にゲーム機用のソフトウェアとして発売された代表的なタイトルを挙げる。

ぱずるまにあ: 1999年 2月25日、ヒューマンより発売された。ヒューマン倒産後はハムスターより発売。機種はPlayStationで、2007年からはPlayStation Portable用にゲームアーカイブスにてダウンロード配信も開始された。ナンバープレース、ナンバークロスワード、スケルトン+αの4種類のパズルゲームが収録されている。
SUDOKU 数独: 2006年 3月23日、ハドソンより発売。対応機種はニンテンドーDS。ボタン操作とタッチペン操作の切り替えが可能。ニコリが問題提供で協力している。日本国外では任天堂より「Sudoku Gridmaster」「Sudoku master」のタイトルで発売されている（パズルシリーズの項も参照）。
ナンプレアドバンス: 2006年4月6日、サクセスより発売。対応機種はゲームボーイアドバンス。問題数が非常に多いのが特徴。問題提供はスカイネットコーポレーション。
カズオ: 2006年4月27日、ソニー・コンピュータエンタテインメントより発売。対応機種はPSP。日本以外では「Go! Sudoku（英語版）」のタイトルで発売されている。また、オンラインのランキングや対戦などにも対応したPlayStation 3版もオンライン配信専用タイトルとして発売されている。
THE イラストパズル&数字パズル: 2006年4月27日、ディースリー・パブリッシャーよりSIMPLE DSシリーズ Vol.7として発売。お絵かきロジックと数独を1本のソフトに収録。オリジナル問題の作成機能が付いている。対応機種はニンテンドーDS。
Brain Age、Brain Training: 任天堂『脳を鍛える大人のDSトレーニング』の日本国外版には数独が収録されている。日本では『ちょっと脳を鍛える大人のDSiトレーニング数独編』に収録されている。
眠れない夜とパズルの日には…。: 2006年9月28日、ジャレコより発売。カックロなど5種類のパズルを1本のソフトに収録。対応機種はニンテンドーDS。ニコリが問題提供で協力している。また、自動生成の問題も出題できる。
ナンプレ: 2007年 6月6日、iTunes Store にてダウンロード販売開始。対応機種は iPod（第五世代でソフトウェア1.2以降）。iPod のクイックホイールで操作。エレクトロニック・アーツより提供。海外でのタイトルは「Sudoku」。
ニコリの数独: 2010年 11月25日、第一集がハムスターより発売。ニコリとの共同開発で数独以外のパズルも収録。PlayStation Portable版の他、ニンテンドー3DS版も発売された。

数独の組み合わせパターン数

数独の組み合わせパターン数は、回転や反射や順列や名前を変更することなどの左右対称を考慮に入れると、54億7273万0538になるとエド・ラッセルとフレーザージャービスによって示されている^[16]。

参考文献

脚注

^ 西山豊「Sudokuがイギリスで大ブレイク」『数学セミナー』（日本評論社）, Vol.45, No.5, 40-44, 2006年 5月
^ 英文表記「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日閲覧）
^ 仏: Le Siècle
^ 仏: La France
^ 英: number place
^ 英: figure place
^ 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ニコリ

外部リンク

[1] 西山豊「Sudokuがイギリスで大ブレイク」『数学セミナー』（日本評論社）, Vol.45, No.5, 40-44, 2006年 5月

[2] 英文表記「Sudoku」も含む。日本第3327502号、日本第4936155号、日本第4980699号、日本第5056856号、日本第5060568号。

[3] 社会部村井正美; 社会部渡辺光彦 (2008年3月26日). “［解説］高校教科書検定…1冊で383か所指摘も、文科省の厳しさ浮き彫り”. YOMIURI ONLINE (読売新聞社). オリジナルの2008年5月17日時点におけるアーカイブ。

[4] 「数独データランド」（数独通信Vol.16、ニコリ、2009年 11月10日）

[5] 英: hitting-set algorithm

[6] 数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論

[7] ヒント数最大のナンプレ稲葉のパズル談話室 2008年 6月16日

[8] 瀬山士郎編『数学は楽しい』日経サイエンス、2010年2月18日。ISBN 978-4-532-51169-2。

[9] ニコリ『数独通信』Vol.18（2010年5月）P.44-45「数独データランド」

[10] プログラミングパズル雑談コーナー 2006年 7月10日の書き込み

[11] GPCC 2011（2011年 5月29日閲覧）

[12] 仏: Le Siècle

[13] 仏: La France

[14] 英: number place

[15] 英: figure place

[Jarvis_and_Russell-16] 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日閲覧。

[17] ニコリ出版物のご案内 - WEBニコリ

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

数独

概要

名称

ルール

解法