はじめに

皆さんこんにちは。今日は深さ優先探索という方法を使って、数独の答えを出力するプログラムの解説をしていく。例題の説明からして難しいので、記事の不備等は、コメントにてご連絡いただけると嬉しい。

例題

nは自然数、N=n^2を満たす自然数とする。このとき横N行縦N列の計N^2個のマス目からなる盤面をつくり、さらに太線でそれぞれn行n列からなるn^2個の区画に分ける。

![a0.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39145/f46ad306-bb0b-87d8-04d2-bd17db4baf79.jpeg)

このときそれぞれのマス目に1からNまでの数字を1つずつ書き込む。ただし、以下の3つの条件を全て満たすものとする。

(A)各行には1,2,3,...,Nが1回ずつ現れる
(B)各列には1,2,3,...,Nが1回ずつ現れる
(C)各区画には1,2,3,...,Nが1回ずつ現れる

以下の[入力例1]や[入力例2]のように、途中まで数字が書き込まれた盤面(問題)がある。これらの盤面の空欄に1,2,3,...,Nの自然数を書き込み、上記の(A)～(C)の条件を満たす盤面(解答)を出力するプログラムを作成せよ。

制約

n=2(N=4)

数独の盤面

![1a.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39145/49abfac9-4697-5932-a5f2-e7dedef019c9.jpeg)

入力例1

[[1,0,3,4],[3,0,0,2],[0,3,0,0],[2,0,0,3]]　*未入力のマス目には0を入力する。

出力例1

[[1,2,3,4],[3,4,1,2],[4,3,2,1],[2,1,4,3]]

数独の盤面

![2a.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39145/e36c9fc1-2145-bee5-7138-fc5d40a0cbec.jpeg)

入力例2

[[4,0,0,0],[0,0,0,0],[1,0,4,0],[0,0,0,2]]　*未入力のマス目には0を入力する。 (出典:https://sudoku.tokyo/mini-sudoku.php 問題番号:6596750)

出力例2

[[4,3,2,1],[2,1,3,4],[1,2,4,3],[3,4,1,2]]

プログラム作成の手順

数独の解答作成のプログラムの作り方は、大まかにまとめると以下の2段階に分けられる。

判定部分を作成:マス目(y,x)が、問題の(A)(B)(C)を満たすか判定するプログラムを作成。マス目の縦、横、ブロック毎に1〜Nの数字が1個ずつ使われているか確認する。
マス目に数字を置く:空いているマス目に1〜Nの数字を置いていき、前項を満たすようならば次のマス目を調べる。このときマス目(0,0),(1,0),...,(N-1,0),(1,0),(1,1),...,(N-1,N-1)と横に調べていく。

上記1でマス目(y,x)のみを調べる理由は、再帰が進まなくなるからである。(自分の経験上、一つのマス目のみに数字が入力される)

1:マス目(y,x)を判定するプログラム

(A) マス目の縦の判定する部分

まず縦x列目に、1〜Nの数字が1つずつ使われているか調べるプログラムを作成する。
マス目(x,0),(x,1),...,(x,N-1)において、1~Nがいくつあるか配列にカウントしていく。このとき1が1つ、2が1つ・・・Nが1つというように各数字が1つずつ使われていればTrue,使われていなければFalseを返す。

```Python # 縦列に答えがあっているか調べる def checkQuestionRow(self,Row): # 1～Nの数字がいくつ含まれるかを格納する配列 num = [0 for m in range((self.N + 1))] # 縦0列目～縦(N-1)列目までを走査する for x in range(0,self.N): # 1～Nがいくつ含まれるか調べる for m in range(1,self.N+1): #(x,Row)のマス目の値がmのとき if m == self.question[x][Row]: # 数字がmの個数に+1する num[m] = num[m] + 1 # 縦列(x)内で、数字が2つ以上使われて場合はFalseを返す for m in range(1,self.N+1): if num[m] > 1: return False return True ```

(B) マス目の横の判定する部分

こちらは縦(列)の場合と同様の判定を行えば良い。

```Python def checkQuestionCol(self,Col): # 1～Nの数字がいくつ含まれるかを格納する配列 num = [0 for m in range((self.N + 1))] # 横0行目～横(N-1)行目までを走査する for y in range(0,self.N): for m in range(1,self.N+1): if m == self.question[Col][y]: num[m] = num[m] + 1 # 行内で、数字が2つ以上使われて場合はFalseを返す for m in range(1,self.N+1): if num[m] > 1: return False return True ```

(C) マス目のブロック部分の判定する部分

ブロックは縦colblock目、横rowblock目・・・というように判定していく。例えば4*4(n=2,N=4)の数独ならば0番目と2番目に太線が来る。太線は縦横とも1<=k<=nとして、(k*n-1)番目に来るため、k * n番目に始点、k * (n+1)番目に終点が来る。

このkをcolBlock,rowBlockに置き換えて、縦と横のブロックの始点から終点まで1〜Nの数字が1つずつ含まれるかどうか調べていく。

```Python # 2*2，3*3のブロックごとに、1～Nの数字が1つずつ出現しているか調べる def checkQuestionBlock(self,rowBlock,colBlock): # ブロックの開始地点(colBlock* n ,rowBlock* n)を定義 startCol = colBlock * self.n startRow = rowBlock * self.n # ブロックの終了地点(colBlock* {n+1} ,rowBlock* {n+1})を定義 endCol = (colBlock + 1) * (self.n) endRow = (rowBlock + 1) * (self.n) # 1～Nの数字がいくつ含まれるかを格納する配列 num = [0 for m in range((self.N + 1))] # ブロック毎に走査を行う for y in range(startCol,endCol): for x in range(startRow,endRow): for m in range(1,self.N+1): if m == self.question[y][x]: num[m] = num[m] + 1 # ブロック内で、数字が2つ以上使われている場合はFalseを返す for m in range(1,self.N+1): if num[m] > 1: return False return True ```

(A)〜(C)をとりまとめる

最後に(A)〜(C)全ての条件をとりまとめる。(A)〜(C)のひとつでも条件を満たさなければ、Falseを返す。

```Python # 現在の(x,y)の解が合っているかどうか調べる def checkQuestion(self,x,y):

    # まず全てのRowに１～Nまでの数字が含まれているか調べる
    if self.checkQuestionRow(x) == False:
        return False

    # 次に全てのColに１～Nまでの数字が含まれているか調べる
    if self.checkQuestionCol(y) == False:
        return False

    # 最後にブロック毎に１～Nまでの数字が含まれているか調べる
    colBlock = x // self.n
    rowBlock = y // self.n
    if self.checkQuestionBlock(colBlock,rowBlock) == False:
        return False

    return True

<h2>2:マス目に数字を置く(深さ優先探索 Depth-First Search)</h2>
<p>数独のマス目への数字の置き方は、以下の手順で実装する。</p>
<ol><li>再帰の終了条件を書く。主に縦列がNに差し掛かったら再帰を打ち切る。</li><li>マス目(y,x)に既に数字が置かれている場合は、マス目(y,x+1)。すでに横の終端にいる時はマス目(0,y+1)に再帰させていく。</li><li>マス目(y,x)に既に数字が置かれていない場合は、まずマス目(y,x)に1〜Nの数字を置いてみる。置いてみた結果、(A)〜(C)の条件を満たす時はTrueを返す。加え2.と同じようにマス目(y,x+1)又は(0,y+1)へと再帰させる。</li><li>3.でマス目(y,x)に1〜Nの全ての数字が条件を満たさないときは、マス目(y,x)の値を数字置く前{0}に戻す。</li></ol>
<p>このように次へ次へと掘り進んで行って、条件を満たさない場合はひとつ前に戻って考え直す探索法を<b>深さ優先探索(Depth-First Search)</b>と言う。</p>
```Python
    # 深さ優先探索より、数独の解を探索する
    def solve(self,question,x=0,y=0):

        # 最終列の次の列に差し掛かったら、再帰を終了する
        if x == 0 and y == self.N:
            return True

        # マス目に既に数字が置かれているとき
        if self.question[y][x] != 0:

            # 最終行にたどり着いたら、次の列の最初を調べる
            if x == self.N-1:
                if self.solve(self.question,0,y+1):
                    return True

            # 最終行以外の場合は、次の行を調べる
            else:
                if self.solve(self.question,x+1,y):
                    return True

        # マス目に数字が置かれていないとき
        else:

            for m in range(1,self.N+1):

                # まず数字iをマス(x,y)に仮置きする
                self.question[y][x] = m

                # 判定が通ったら、マス(x,y)の値をmで確定する
                if self.checkQuestion(x,y) == True:
                    self.question[y][x] = m

                    # デバッグ用
                    # print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(m) + ")")

                    # 最終行にたどり着いたら、次の列の最初を調べる
                    if x == self.N-1:
                        if self.solve(self.question,0,y+1):
                            return True
                    # 最終行以外の場合は、次の行を調べる
                    else:
                        if self.solve(self.question,x+1,y):
                            return True

            # 判定が通らない場合は、マス目を元に戻す
            self.question[y][x] = 0
            return False

＊尚、本部分のプログラム作成にあたり、@wsldenli氏の「Pythonで数独を解く -Qiita」を真似させていただいた。

プログラム全体

```Python:Sudoku.py import os import sys

class Sudoku():

# データを初期化
def __init__(self):

    # 小枠の大きさ
    self.n = 2

    # 大枠と数値の終端を定義
    self.N = self.n * self.n

    # 問題の全ての配列を0で初期化する
    self.question = [[0 for i in range((self.N))] for j in range((self.N))]

# 横行に答えがあっているか調べる
def checkQuestionRow(self,Row):

    # 1～Nの数字がいくつ含まれるかを格納する配列
    num = [0 for m in range((self.N + 1))]

    # 横0行目～横(N-1)行目までを走査する
    for x in range(0,self.N):

        # 1～Nがいくつ含まれるか調べる
        for m in range(1,self.N+1):

                #(x,Row)のマス目の値がmのとき
                if m == self.question[x][Row]:

                    # 数字がmの個数に+1する
                    num[m] = num[m] + 1

    # 列Row内で、数字が2つ以上使われて場合はFalseを返す
    for m in range(1,self.N+1):
        if num[m] > 1:
            return False

    return True

# 縦:列Colにおいて、1～Nの数字が1つずつ出現しているか調べる
# 基本、checkQuestionRowと同じ動作
def checkQuestionCol(self,Col):

    # 1～Nの数字がいくつ含まれるかを格納する配列
    num = [0 for m in range((self.N + 1))]

    # 縦0列目～横(N-1)列目までを走査する
    for y in range(0,self.N):
        for m in range(1,self.N+1):
                if m == self.question[Col][y]:
                    num[m] = num[m] + 1

    # 列内で、数字が2つ以上使われて場合はFalseを返す
    for m in range(1,self.N+1):
        if num[m] > 1:
            return False

    return True

# 2*2，3*3のブロックごとに、1～Nの数字が1つずつ出現しているか調べる
def checkQuestionBlock(self,rowBlock,colBlock):

    # ブロックの開始地点(colBlock* n ,rowBlock* n)を定義
    startCol = colBlock * self.n
    startRow = rowBlock * self.n

    # ブロックの終了地点(colBlock* {n+1} ,rowBlock* {n+1})を定義
    endCol =  (colBlock + 1) * (self.n)
    endRow =  (rowBlock + 1) * (self.n)

    # 1～Nの数字がいくつ含まれるかを格納する配列
    num = [0 for m in range((self.N + 1))]

    # ブロック毎に走査を行う
    for y in range(startCol,endCol):
        for x in range(startRow,endRow):
            for m in range(1,self.N+1):
                if m == self.question[y][x]:
                    num[m] = num[m] + 1

    # ブロック内で、数字が2つ以上使われて場合はFalseを返す
    for m in range(1,self.N+1):
        if num[m] > 1:
            return False

    return True

# 現在の(x,y)の解が合っているかどうか調べる
def checkQuestion(self,x,y):

    # まず全ての行RowにNまでの数字が含まれているか調べる
    if self.checkQuestionRow(x) == False:
        return False

    # 次に全ての列Colに１～Nまでの数字が含まれているか調べる
    if self.checkQuestionCol(y) == False:
        return False

    # 最後にブロック毎に１～Nまでの数字が含まれているか調べる
    colBlock = x // self.n
    rowBlock = y // self.n
    if self.checkQuestionBlock(colBlock,rowBlock) == False:
        return False

    return True

# 深さ優先探索より、数独の解を探索する
def solve(self,question,x=0,y=0):

    # 最終列の次の列に差し掛かったら、再帰を終了する
    if x == 0 and y == self.N:
        return True

    # マス目に既に数字が置かれているとき
    if self.question[y][x] != 0:

        if x == self.N-1:
            if self.solve(self.question,0,y+1):
                return True
        else:
            if self.solve(self.question,x+1,y):
                return True

    # マス目に数字が置かれていないとき
    else:

        for m in range(1,self.N+1):
           self.question[y][x] = m
            # デバッグ用
            # print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(self.question[y][x]) + ")")

            if self.checkQuestion(x,y) == True:
                self.question[y][x] = m

                if x == self.N-1:
                    if self.solve(self.question,0,y+1):
                        return True
                else:
                    if self.solve(self.question,x+1,y):
                        return True

        self.question[y][x] = 0
        # デバッグ用
        # print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(self.question[y][x]) + ")")
        return False

メイン関数

if name == 'main':

# 問題データ
Sudoku = Sudoku()
Sudoku.question =[[1,0,3,4],[3,0,0,2],[0,3,0,0],[2,0,0,3]]
# Sudoku.question =[[4,0,0,0],[0,0,0,0],[1,0,4,0],[0,0,0,2]]

print("Question")
print(Sudoku.question)
Sudoku.solve(Sudoku.question,0,0)
print("Answer")
print(Sudoku.question)


<h2>その他参考にしたサイト</h2>
○　<a href="http://shochandas.xsrv.jp/number/sudoku.htm">数独の数理(http://shochandas.xsrv.jp/number/sudoku.htm)</a>
問題の説明は、2012年の慶応大学の入試問題を真似した。ちなみに4*4の数独の答えの盤面は全部で288通りあるらしい。

<h2>バックナンバー</h2>
<a href="https://qiita.com/ryuichi69/items/17e89d0693086cfb3aff">・Python3で配列をクイックソートする</a>
<a href="https://qiita.com/ryuichi69/items/bf47c4ea061036d8ca1b">・Pythonで最大部分配列問題(maximum subarray problem)を解く</a>