数独の数理                             戻る

 平成19年5月11日、当HPの掲示板「出会いの泉」に、ゆうさんという方から書き込み
があった。

  私は、現在数独(ナンプレ)について研究しています。9×9が基本なのですが、まず、
 導入として4×4の数独について考えています。4×4の数独は、最低どれだけの数字
 が入っていればパズルとして成立するのかがまだ証明できません。何かよい方法は、
 ありませんか?


 この問いかけに対して、当HPがいつもお世話になっている、らすかるさんが明解に回答
された。(平成19年5月11日付け)

○ 4×4 の数独のパターンは全部で、288通り

 (らすかるさんの解答)

 1行目と2行目、3行目と4行目、1列目と2列目、3列目と4列目は、それぞれ交換可能。
よって、1の位置を例えば、

 1□□□
 □□1□
 □1□□
 □□□1

と固定した場合の解の個数を、24=16倍すれば求められる。

 次に、「2」と「3」と「4」は入れ替え可能なので、

 1 2 □□
 3 4 1 □
 □1□□
 □□□1

と固定した場合の解の個数を、3!=6倍すれば、

 1□□□
 □□1□
 □1□□
 □□□1

の解の個数が求められる。

 1 2 □□
 3 4 1 □
 □1 □□
 □□□1   の解は、

 1234   1243   1234
 3412   3412   3412
 2143   2134   4123
 4321   4321   2341   の3通り。

ここで、

 1243
 3412
 □134
 □321   を満たす場合は上記のように1通りしかないことに注意。

 以上から、求める場合の数は、  3×3!×24=3×6×16=288(通り)


(コメント) らすかるさんの解法は、とても斬新でエレガントですね! 以下に、高校生流の
      解法を考えてみました。


 左上の2×2のマス目には、1,2,3,4 の数字を自由に並べていいので、その順列の
数は、4!=24通り。そのうちの1通り、例えば、

 1 2 □□
 3 4 □□
 □□□□
 □□□□

について、右上の2×2のマス目で、数字の 1 が入る場合は、下記のアまたはイの2通り。

 1 2 □□
 3 4 アイ
 □□□□
 □□□□

 いま、アに、数字の 1 が入るとすると、イには、数字の 2 しか入らない。

 1 2 □□
 3 4 1 2
 □□□□
 □□□□

 このとき、右上の2×2のマス目でア、イ には数字の 3、4 が入り、その場合の数は2通り。

例えば、アには数字の 3、イ には数字の 4 が入る場合:

 1 2 3 4
 3 4 1 2
 □□□□
 □□□□

 この場合について、左下、右下の2×2のマス目において、数字の 1 の入り方は、

 1 2 3 4     1 2 3 4
 3 4 1 2     3 4 1 2
 □1 □□     □□□ 1
 □□□ 1     □1 □□

の2つの場合があるが、残りの数字の入れ方を考えると、

 1 2 3 4
 3 4 1 2
 □1 □□
 □□□ 1
  からは、   1 2 3 4     1 2 3 4
  3 4 1 2     3 4 1 2
  2 1 4 3     4 1 2 3
  4 3 2 1     2 3 4 1
 1 2 3 4
 3 4 1 2
 □□□ 1
 □1 □□
  からは、   1 2 3 4     1 2 3 4
  3 4 1 2     3 4 1 2
  2 3 4 1     4 1 2 3
  4 1 2 3     2 3 4 1

 同様にして、アには数字の 4、イ には数字の 3 が入る場合:

 1 2 4 3
 3 4 1 2
 □□□□
 □□□□

 この場合について、左下、右下の2×2のマス目において、数字の 1 の入り方は、

 1 2 4 3     1 2 4 3
 3 4 1 2     3 4 1 2
 □1 □□     □□□ 1
 □□□ 1     □1 □□

の2つの場合があるが、残りの数字の入れ方を考えると、

 1 2 4 3
 3 4 1 2
 □1 □□
 □□□ 1
  からは、   1 2 4 3
  3 4 1 2
  2 1 3 4
  4 3 2 1
 1 2 4 3
 3 4 1 2
 □□□ 1
 □1 □□
  からは、   1 2 4 3
  3 4 1 2
  4 3 2 1
  2 1 3 4

 以上から、求める場合の数は、 4!×2!×(4+2)=288(通り) となる。


○ 13個の数字があれば、必ず解が一つに定まる

 (らすかるさんの解答)  例えば、12個では、

 12 34
 34 12
 2□4□
 4□2□   のような場合に、解が一つに定まらない。

○ 解が一つに決まるパターンで数字の最小個数は、4個

 (らすかるさんの解答)  例えば、

 1□□□
 □□2□
 3□□□
 □□4□   という例は、解が一つしかない。また、数字3つでは解が一つしかないパター
        ンが存在しないことは、プログラムによる全数調査で調べられる。

 らすかるさんによれば、数字3つの場合、解のパターンの最小個数は3個だそうだ。


 当HPがいつもお世話になっている未菜実さんからも情報が寄せられた。
                                      (平成19年5月11日付け)

  数学セミナー 2006年5月号「Sudokuがイギリスで大ブレイク」(西山 豊)に次のよ
 うなことが載っている。

   4×4では、288個のパターンだが、9×9だと、9!×722×27×27704267971
  即ち、約 6.671×1021個になる。
     (B.フェルゲンハウエルとF.ジャービスによる(2005年))

   唯一解の存在は、非対称で17個のヒント数字、対称で18個と過去の発表から想定さ
  れているが、きちんと数学的に証明されたわけではないとのことである。


 また、未菜実さんのHP「数理パズル入門」でも、数独の問題が載せられている。何やら難
しそうな予感...。

 未菜実さんによれば、数独の歴史については、Wikipedia の「数独」が詳しいそうだ。

(追記) 平成19年7月10日付け

 数独は、時間つぶしに一つずつ数字を埋めていくものだと思っていたが、Excel のVBAや
関数を駆使されて解を求める手順の自動化を図った方がおられる。

 神奈川県の林 勇一郎さんが、「数独全自動」というプログラムを公開された。

 (上記をクリックして適当なフォルダに保存(29.9KB)し、解凍(119KB)してご利用下さい。

 Excel ファイルを開いて、セル K1 : S9 に問題であらかじめ与えられている数字を入力
し、入力が終わったら、「数独」のボタンをクリック。直ちに解の探索が始まります。

 数独に関する書籍は数多いですが、手元にある本で、難問と言われる問題を実行させて
みたら、わずか2秒で解が求まりました。

 試しに未菜実さんのHP「数理パズル入門」にのっている数独の問題(2007.4.14)を
やらせてみたら、何と40秒もかかりました!

 未菜実さんの問題は、「超」がつくくらいの難問ですね!

 このファイルを使うと、パズルの醍醐味が味わえなくなりそうですが、逆に、新しい問題を
作るときに応用できそうで使い道は無限大ですね...。このような貴重なファイルを公開さ
れた林さんに感謝いたします。

 なお、「数独」という名称は、パズル制作会社「ニコリ」の登録商標になっているので、一般
には、「ナンバープレイス(ナンプレ)」と呼んだ方がいいようだ。

 ナンプレの解法のテクニックは、解いていくうちに自然と身に付くと思うが、次の2つが基本
的なスタンスとなろう。

 (1)数字の配列を見て、入るべき数字を書き込む

 (2)マス目に入るであろう数字の候補をあげ、数字の配列から、候補を絞り込む

 いま、たくさんのナンプレの書籍や新聞のパズル欄が充実しているので、暇を見つけて挑
戦されてはどうでしょうか。


(追記) 平成24年2月18日付け

 慶應義塾大学 薬学部(2012)の入試問題に、上記で考察された「4×4 の数独」の問
題が出題された。

 数独が脚光を浴びた時代に中学・高校時代を送った受験生にとっては馴染みのある問題
と思われるが、「場合の数」を求めることは未経験と思われ、当HP読者の受験生にとっては
経験済みで取り組みやすかったのではないかと思われる。

 予備校の問題レベルでは、「難」に分類されているが、それほど高級な技を使うこともない
ので、難易レベルでは「易」としてもおかしくはない。

慶應義塾大学 薬学部(2012)

 右図のように、4行4列の計16個のマス目をつくり、さらに太線で

それぞれ2行2列からなる4つの区画に分ける。それぞれのマス目

に1から4までの数字を1つずつ書き込む。

 ただし、以下の3つの条件を全て満たすものとする。
  

  (イ) 各行には1、2、3、4が1回ずつあらわれる。

  (ロ) 各列には1、2、3、4が1回ずつあらわれる。

  (ハ) 各区画には1、2、3、4が1回ずつあらわれる。

 このとき、数字の書き込み方は全部で何通りあるか。

(解) 1行目に、1、2、3、4を並べる方法の数は、4!=24通り

   そのうちの1通り、例えば、「1、2、3、4」と並んでいるものとする。このとき、2行目の

  並べ方は、次の4通り。

 (1) 「3、4、1、2」  (2) 「3、4、2、1」  (3) 「4、3、1、2」  (1) 「4、3、2、1」

  (1) 「3、4、1、2」 の場合、3行目、4行目の並べ方は、

      「2、1、4、3」 、「2、3、4、1」 、「4、1、2、3」 、「4、3、2、1」
      「4、3、2、1」 、「4、1、2、3」 、「2、3、4、1」 、「2、1、4、3」

  (2) 「3、4、2、1」 の場合、3行目、4行目の並べ方は、

      「2、1、4、3」 、「4、3、1、2」
      「4、3、1、2」 、「2、1、4、3」

  (3) 「4、3、1、2」 の場合、3行目、4行目の並べ方は、

      「2、1、4、3」 、「3、4、2、1」
      「3、4、2、1」 、「2、1、4、3」

  (4) 「4、3、2、1」 の場合、3行目、4行目の並べ方は、

      「2、1、4、3」 、「2、4、3、1」 、「3、1、4、2」 、「3、4、1、2」
      「3、4、1、2」 、「3、1、4、2」 、「2、4、1、3」 、「2、1、4、3」

 したがって、求める場合の数は、4!×(4+2+2+4)=24×12=288(通り)  (終)


(コメント) 慶應義塾大学薬学部は、元の共立薬科大学。東京理科大学薬学部が郊外に
      移転したせいか、都心の薬学部として人気・レベルとも格段にあがっていますね!


 当HPがいつもお世話になっているHN「GAI」さんからの出題です。
                                      (平成26年2月20日付け)

 数独やナンプレと呼ばれているパズルが一時期ブームでした。(ある航空会社ではパイロ
ットに当日のナンプレ禁止令が出されていたとか。)

 うわさには聞いていたが自ら実際にやったことは無かった。あることで、この数独の初級
問題に挑戦してみました。やってみると、それはハマルはハマル。次は中級の問題と次々
に挑戦したくなっていきます。

 推理の方法や効率良い手順が一問一問異なっていて、それぞれが別々のストーリーを
辿っていきます。

 そこで、既にこのパズルにはまっている方、次の問題に挑戦してみて下さい。

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



(コメント) 構図がハート形なんて、お洒落ですね!解くのに、結構時間がかかりました。次
      のような解になるでしょうか?

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

 とあるAKBファンさんも同様の解を得られました。(平成26年2月20日付け)


(追記) 当HPがいつもお世話になっているHN「ks」さんからの投稿です。
                                     (平成28年11月30日付け)

 数独の完成形をつくることを考えました。たとえば、1行目に、1から9まで埋めます。2行目
に、4から3までサイクリックに埋めます。3行目に、7から6まで埋めます。4行目に、2から1
まで埋めます。

 このようにすると完成形ができますが、他にも簡潔に作る方法がありそうです。勿論、縦の
列による方法もあります。

 最初の1行目が9!通りあります。実際、ものすごい数の場合があるようなので、どういう
シャフルをするか、ご教示ください。

 123456789
 456789123
 789123456
 234567891
 567891234
 891234567
 345678912
 678912345
 912345678


 らすかるさんからのコメントです。(平成28年11月30日付け)

 全パターン数を求めるということでしょうか。全パターン数を求めるには、おそらく細かい場
合分けをして数えていって合計するしかないと思います。(手作業では無理です。)

 以前自分でプログラムを作って数えたことがありますが、全パターン数は、
6,670,903,752,021,072,936,960(およそ 6.67×1021)通りでした。

 この値を検索して見つかるサイトを眺めると、パターン数を簡単な計算で出すことができな
いこともわかると思います。


 ksさんからのコメントです。(平成28年12月1日付け)

 すべては望んでいません。現在可能な方法で9!通り作れますが、さらに縦に順列を行え
ば増えそうです。重複の可能性もありますが...。他にどんなシャフルがあるかどうかという
ことなんです。いろいろ難しい問題にも興味がありますが...。


 らすかるさんからのコメントです。(平成28年12月1日付け)

 9!とは、どういうパターンを想定されているのでしょうか。当然1行目の数字だけ入れ替え
ても成り立たなくなりますよね。もしかして、9!は単に1行目のパターン数というだけで、2行
目以降は考えない場合9!通り、という意味でしょうか。


 ksさんからのコメントです。(平成28年12月2日付け)

 こちらの勘違いかもしれませんが、

 a,b,c,d,e,f,g,h,i
 d,e,f,g,h,i,a,b,c
 g,h,i,a,b,c,d,e,f
 b,c,d,e,f,g,h,i,a
 e,f,g,h,i,a,b,c,d
 h,i,a,b,c,d,e,f,g
 c,d,e,f,g,h,i,a,b
 f,g,h,i,a,b,c,d,e
 i,a,b,c,d,e,f,g,h

 1行目を変えると自動的に他の行もかわります。縦の順列を考えると重複が心配されます。


 らすかるさんからのコメントです。(平成28年12月2日付け)

 なるほど、つまり、「最初の1行目が、9!通りあります」ではなく、「1〜9の数字の入れ替
えで9!通りあります」という意味なのですね。そうすると、「縦の順列」というのも「1〜9の数
字の入れ替え」なので、全パターンが重複し、全部で9!通りになると思います。

 他のパターン生成方法としては、

・1〜3行目の行の入れ替え
・4〜6行目の行の入れ替え
・7〜9行目の行の入れ替え
・1〜3列目の列の入れ替え
・4〜6列目の列の入れ替え
・7〜9列目の列の入れ替え
・1〜3行目、4〜6行目、7〜9行目の入れ替え
・1〜3列目、4〜6列目、7〜9列目の入れ替え

を考えれば、入れ替え方法としては、(3!)^8=1679616通りとなります。ただし、元があのパタ
ーンの場合は多数の重複が発生すると思いますので、重複を削除して何通りになるかはよ
くわかりません。


 ksさんからのコメントです。(平成28年12月2日付け)

 いつも、ご指導いただきありがとうございます。数独の挑戦をして、ある程度解き方は、慣
れでできるようになりました。それで問題をつくることも挑戦したいと思いました。完成形から、
抜いていき、元に戻ることを考えています。今のところ、同じ数をすべて抜く場合、あるいは、
真ん中のブロックの9個を抜くと、元の一つに戻ることがわかります。実際の初級の問題でも、
40個くらいは抜かれています。よりたくさんの数を抜いた問題を作るコツがありましたら、ご
教授ください。地道に、一個一個抜いてもとに戻ることができることを確認しながら作ってい
く方法もあるかもしれませんが...。何かヒントのようなものでも...。適当に30個くらい抜
いても元に戻すことができるのか、やってみたいと思います。


 ksさんからのコメントです。(平成28年12月3日付け)

 市販のものと同じように空欄を作り解いてみました。解が運よく一つになった場合と、元の
見本は解が一つに決まるのですが、違う完成形だと同じ空欄でも複数解になる場合があり
ます。将来的に、その区別が分かればいいですけど。後、解を求めることができる空欄のパ
ターンが課題ですね。


 ksさんからのコメントです。(平成28年12月4日付け)

 数独の条件は、縦横と区画にすべての数があることですが、さらに、斜めも1から9までが
入るものを作ってみました。ご賞味ください。

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


 カルピスさんからのコメントです。(平成28年12月4日付け)

 ksシェフさん、今晩のディナーとして頂きました。美味しかったです。「斜め」の隠し味が効
いていました。


 GAI さんからのコメントです。(平成28年12月5日付け)

 数独で有名な株式会社ニコリが算額奉納したというものらしいです。
デザイン的に三をイメージしているような

 自分は、専用ソフトで出してしまいましたが・・・、問題としての評価を聞きたいです。

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



(コメント) 私も解いてみました。

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



 カルピスさんからのコメントです。(平成28年12月6日付け)

 私は、9色で「色分け」して上記と同じ解を得ました。やはり、てこずりました。


 ksさんからのコメントです。(平成28年12月5日付け)

 カルピスさん、ありがとうございます。ノリがいいですね。「賞味」ではなく、鑑賞にすれば、
食べられなくて済んだのでしょうか?ご指摘のように、斜めから先に作り、1,2,5,8,9を
配置しました。後は自動的に埋まりました。

 GAIさんの問題むずかいそうですが、挑戦します。ほかにハート型もやっていますが、まだ、
途中ですけど。

 昨年から数独に挑戦して、慣れてきました。「代走」のが安くて難易度の星がついていまし
て、残っている個数が38個で星一つ、残っている個数27からすると、レベル5くらいにくらい
ですが、レベル4くらいかもしれません。10分くらいでした。


 ksさんからのコメントです。(平成28年12月7日付け)

 縦横とななめ一筋だけ、の完成形をつくりました。

  834 267 591
  759 183 426
  612 945 378

  591 834 267
  426 759 183
  378 612 945

  267 591 834
  183 426 759
  945 378 612

 この形から抜いていけば問題がつくれますので、渦巻き型も作ってみたいですね。


 カルピスさんからのコメントです。(平成28年12月7日付け)

 私は10年位前に初めて数独に出会い、やるほどに速くなっていくのですが、やはり、当時
どうやって問題を作るのだろう? と私も考えました。創る人は大変だな〜と思いつつ、全く
分かりませんでした。今回「初めて」数独の問題の作り方が分かりました。有難うございまし
た。

 「渦巻き型」も良いですね。来年の年賀状用に「2017」「H29」「トリ」もいいかもです。


 ksさんからのコメントです。(平成28年12月7日付け)

 ありがとうございます。市販の問題のように適当にぬいていけば、できると思いますが、答
えが複数になるときがあります。最小で17残すことができるそうですね!