Aggressive Style 5

Aggressive Style 5

昨今はコミケ関係を中心に書いています。同人やニコニコ動画方面で活躍される方の相互リンクをお待ちしています。

慶応大学で出題された数独の問題について、調べた事や思った事を書いてみた

今年度の慶応大学の入試問題で、数独(ナンバープレース)に関する問題が出題され、各サイトで話題を呼んでいる。

そこで当ブログでも数独について色々調べてみたので読んで欲しい。まず数独のルールは以下のようになる。

1.数独(ナンバープレース)のルール

数独とは、株式会社ニコリの商標(日本第3327502号など)*1で一般にはナンバープレースと呼ばれる。ここで数独のルールは、nを2以上の自然数とし、N=n^2としたとき、N行N列計N^2のマス目を作り、さらに太線でそれぞれn行n列からなるNつの区画に分ける。このときそれぞれのマス目に1からNまでの数字を、以下の3つの条件を満たして書き込むゲームの事だ。

  1. 各行には1、2、....、Nまでが1回ずつあらわれる。
  2. 各列には1、2、....、Nまでが1回ずつあらわれる。
  3. 各区画には1、2、....、Nまでが1回ずつあらわれる。

又、n=2(4×4)のときのマス目が以下の左のようになり、n=3(9×9)のときのマス目が以下の右のようになる。通例n=3のマス目でゲームが行われる。



2.数独の升目の組み合わせ(解盤面)

今度は数独における升目の埋め方(解盤面)が何通りあるのかを見て行こう。本記事ではn=2とn=3の場合を紹介する。「(私の備忘録:数独の数理より)」に依れば、n=2の場合においては2012年の慶応大学の入試問題として出題されているようだ。問題文は以下のようになる。

2*2のときのマス目組み合わせ(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行目を固定してから、2行目以降の候補を考えているのが上手いので紹介する。


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」  (4) 「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(通り)(終)

とn=2の場合は288通りで済むようだ。一方で「Mathematics of Sudoku(Wikipedia) 」に依れば、n=3の場合の組み合わせはコンピューターに依って行われたらしい。「There are 6670903752021072936960 Sudoku grids (Bertram Felgenhauer and Frazer Jarvis):sudoku enumeration problems」によれば、ある方法により、現在の升目が数独の条件を満たすかを調べていった所、6,670,903,752,021,072,936,960≒6.7 ×10^21通りと非常に多い。

3.過去の問題をC言語を使って解く

2を見ても分かる通り、数独の問題の種類は6,670,903,752,021,072,936,960通りと実質無限大にあるようだ。今度は、「数独の平凡な解法(C言語):配電盤」で掲載されているソースコードを使わせて頂く事で、数独の問題を解こうと思う。

深さ優先探索について

上記のソースコードには「深さ優先探索」というアルゴリズムを用いているようだ。深さ優先探索を簡単に説明すると、下の図のような木構造を深く辿れる所まで辿っていき、辿ったら前の階層に戻ると言う事を繰り返して解を探索する方法である。



慶応大学の入試問題

では今回の慶応大学の数独の問題と答えを見て行こう。


問題:次の条件をみたすように、空欄に1〜9までの数字を入れて表を完成させなさい。

  1. 太線で囲まれたどの9個の3×3のマスにも1〜9までの数字が全て現れる。
  2. どの縦の列、どの横の列にも1〜9までの数字が全て現れる。
  3. 灰色の4個のマスに1〜9までの数字が全て現れる。

たとえば、横の列1と横の列3には3が入っており、また、縦の列Gにも3が入っているから、マスI2には3が入る事が分かる。このようにして、E9=(a)、F4=(b)、F8=(c)、G1=(d)、G7=(e)、G8=(f)、I5=(g)、I8=(h)などを得る。



問題の図

解答

上記のプログラムを走らせ、(3)の条件を満たすものを手作業で探すと下のようになる。案の定答えに誤りがあったので、再度修正を行った。

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

このことから、E9=8、F4=9、F8=2、G1=1、G7=4、G8=9、I5=2、I8=6となる(答)

気がついた点

プログラムを走らせていたら、(3)という条件を抜きにすると以下のような別解2が存在した。この他の答えを知りたい方はこちらをご覧頂きたい。

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

このような点を考えると、この問題の出題者は解の候補を1つに絞る為に、(3)の条件を追加したのではないか?と推測できる。

最後に

本記事では数独について色々調べてみた。月並みであるが、数独について数学、コンピューター的な観点から様々な研究が行われている事に驚いた。入試問題として出題するには不適切だと思うが、研究の対象としては面白いと思った。

参考文献