数独

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナンバープレースから転送)
移動: 案内検索
数独の問題例

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

概要[編集]

2005年イギリスで人気となり、海外で火のついたブームを追うように2006年から日本でも連載する新聞や雑誌が増えた[1]

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

名称[編集]

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

日本国外では「sudoku」の呼称が一般的である[要出典]アメリカ合衆国においては「sudoku」と「number place」の双方で呼ばれている。

ルール[編集]

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

解法[編集]

解き方の例-1
右上のブロックに注目して5の位置を確定させる
  • 一つのマスに注目して、そのマスに入る数字を限定する。
  • 一つの列(または3×3のブロック)に注目して、特定の数字が入るマスを探す。

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

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


解き方の例-2
左下のブロックに注目して9の位置を確定させる

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

  • ある数字が入る場所が、単一ブロックの同一列に限定されるとき、他のブロックのその列には入らない。
    • 例題の中段左のブロックで9が入るのは、上段左のブロックの中央列に9が既にあるので、右側の列である。よって、下段左のブロックでは、9の入る列が左列と確定する。下段中央、下段右のブロックの9の列も既に決まっているので、下段左のブロックの6の左横に9が入ることが確定する。
  • 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個程度になる[3]

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

最少個数[編集]

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

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

標準以外[編集]

標準のルール以外だと、表出個数は更に少なくなる。対角線上の数もそれぞれ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作)の問題が確認されている[8]。 印刷物の形では発行されていないが、2006年7月に16×16で表出が64個(点対称)のものと62個(非対称)のものが発表されている[9]2011年に16×16の最小表出数がGPCCに取り上げられた[10]。出題時点では上記の62個が最小となっていたが、2011年4月11日現在56個のものが発見されている。

歴史[編集]

1895年7月6日、フランスの日刊紙「ラ・フランス」に掲載されたパズル

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

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

日本には、ニコリの『月刊ニコリスト』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 日本の旗 森西亨太 日本の旗 條秀彰 日本の旗 日本 チェコの旗 チェコ 中華人民共和国の旗 中国

バリエーション[編集]

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

大きさの変更[編集]

各ブロックが長方形の問題例

一般的な数独は枠の大きさが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個ずつ数字が入る物、などがある。

入る数字の変更[編集]

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

例えば英単語の場合、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 AgeBrain 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になるとエド・ラッセルとフレーザージャービスによって示されている[15]

参考文献[編集]

関連文献[編集]

ニコリの数独本
ニコリの数独本は以下の通り[16]
文藝春秋の単行本
パズル作家50名が自ら「傑作」と認める数独を100問厳選して収録した本。
同人誌
個人が発行した本。
  • 大野豊 『数独の体系的解法 初歩から超難度までそして、Art Inkala (フィンランド) へ』 大野豊、2011年8月。
毎日新聞名古屋開発の数独本
Dr. 数独が編纂したもの。
プログラム学習本
Java言語で数独の問題を作る本。
小説
以下の数独小説は2007年から2009年にかけて出版された。

脚注[編集]

  1. ^ 西山豊「Sudokuがイギリスで大ブレイク」数学セミナー』(日本評論社), Vol.45, No.5, 40-44, 2006年5月
  2. ^ 社会部 村井正美; 社会部 渡辺光彦 (2008年3月26日). “[解説]高校教科書検定…1冊で383か所指摘も、文科省の厳しさ浮き彫り”. YOMIURI ONLINE (読売新聞社). オリジナル2008年5月17日時点によるアーカイブ。. https://web.archive.org/web/20080517055035/http://www.yomiuri.co.jp/kyoiku/news/20080326ur03.htm 
  3. ^ 「数独データランド」(数独通信Vol.16、ニコリ、2009年11月10日
  4. ^ : hitting-set algorithm
  5. ^ 数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論
  6. ^ ヒント数最大のナンプレ 稲葉のパズル談話室 2008年6月16日
  7. ^ 『数学は楽しい』 瀬山士郎、日経サイエンス2010年2月18日ISBN 978-4-532-51169-2
  8. ^ ニコリ『数独通信』Vol.18(2010年5月)P.44-45「数独データランド」
  9. ^ プログラミングパズル雑談コーナー 2006年7月10日の書き込み
  10. ^ GPCC 20112011年5月29日閲覧)
  11. ^ : Le Siecle
  12. ^ : La France
  13. ^ : number place
  14. ^ : figure place
  15. ^ 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日閲覧。
  16. ^ ニコリ出版物のご案内 - WEBニコリ

関連項目[編集]

外部リンク[編集]