[Pythonアルゴリズム]深さ優先探索より、数独の答えを出力するプログラム

<h2>はじめに</h2>
<p>皆さんこんにちは。</br>今日は深さ優先探索という方法を使って、数独の答えを出力するプログラムの解説をしていく。例題の説明からして難しいので、記事の不備等は、コメントにてご連絡いただけると嬉しい。</p>
<h2>例題</h2>
<p>nは自然数、N=n^2を満たす自然数とする。このとき横N行縦N列の計N^2個のマス目からなる盤面をつくり、さらに太線でそれぞれn行n列からなるn^2個の区画に分ける。</p>
![a0.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39145/f46ad306-bb0b-87d8-04d2-bd17db4baf79.jpeg)
<p>このときそれぞれのマス目に1からNまでの数字を1つずつ書き込む。ただし、以下の3つの条件を全て満たすものとする。</p>
<ul><li>(A)各行には1,2,3,...,Nが1回ずつ現れる</li><li>(B)各列には1,2,3,...,Nが1回ずつ現れる</li><li>(C)各区画には1,2,3,...,Nが1回ずつ現れる</li></ul>
<p>以下の[入力例1]や[入力例2]のように、途中まで数字が書き込まれた盤面(問題)がある。これらの盤面の空欄に1,2,3,...,Nの自然数を書き込み、上記の(A)～(C)の条件を満たす盤面(解答)を出力するプログラムを作成せよ。</p>

<h4>制約</h4> <span>n=2(N=4)</span>
<h4>数独の盤面</h4> 
![1a.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39145/49abfac9-4697-5932-a5f2-e7dedef019c9.jpeg)
<h4>入力例1</h4> <span>[[1,0,3,4],[3,0,0,2],[0,3,0,0],[2,0,0,3]]　*未入力のマス目には0を入力する。</span>
<h4>出力例1</h4> <span>[[1,2,3,4],[3,4,1,2],[4,3,2,1],[2,1,4,3]]</span>
<h4>数独の盤面</h4> 
![2a.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39145/e36c9fc1-2145-bee5-7138-fc5d40a0cbec.jpeg)
<h4>入力例2</h4><span>[[4,0,0,0],[0,0,0,0],[1,0,4,0],[0,0,0,2]]　*未入力のマス目には0を入力する。</span>
(出典:<a href="https://sudoku.tokyo/mini-sudoku.php">https://sudoku.tokyo/mini-sudoku.php 問題番号:6596750</a>)
<h4>出力例2</h4><span>[[4,3,2,1],[2,1,3,4],[1,2,4,3],[3,4,1,2]]</span>

<h2>プログラム作成の手順</h2><p>数独の解答作成のプログラムの作り方は、大まかにまとめると以下の2段階に分けられる。</p><ol><li><b>判定部分を作成</b>:<b>マス目(y,x)</b>が、問題の(A)(B)(C)を満たすか判定するプログラムを作成。マス目の縦、横、ブロック毎に1〜Nの数字が1個ずつ使われているか確認する。</li><li><b>マス目に数字を置く</b>:空いているマス目に1〜Nの数字を置いていき、前項を満たすようならば次のマス目を調べる。このときマス目(0,0),(1,0),...,(N-1,0),(1,0),(1,1),...,(N-1,N-1)と横に調べていく。</li></ol>
<p>上記1でマス目(y,x)のみを調べる理由は、再帰が進まなくなるからである。(自分の経験上、一つのマス目のみに数字が入力される)</p>
<h2>1:マス目(y,x)を判定するプログラム</h2>
<h4>(A) マス目の縦の判定する部分</h4>
<p>まず縦x列目に、1〜Nの数字が1つずつ使われているか調べるプログラムを作成する。<br>マス目(x,0),(x,1),...,(x,N-1)において、1~Nがいくつあるか配列にカウントしていく。このとき1が1つ、2が1つ・・・Nが1つというように各数字が1つずつ使われていればTrue,使われていなければFalseを返す。</p>
```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
```
<h4>(B) マス目の横の判定する部分</h4>
<p>こちらは縦(列)の場合と同様の判定を行えば良い。</p>
```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
```
<h4>(C) マス目のブロック部分の判定する部分</h4>
<p>ブロックは縦colblock目、横rowblock目・・・というように判定していく。例えば4*4(n=2,N=4)の数独ならば0番目と2番目に太線が来る。太線は縦横とも1<=k<=nとして、(k*n-1)番目に来るため 
、k * n番目に始点、k * (n+1)番目に終点が来る。</p>
<p>このkをcolBlock,rowBlockに置き換えて、縦と横のブロックの始点から終点まで1〜Nの数字が1つずつ含まれるかどうか調べていく。</p>
```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
```
<h4>(A)〜(C)をとりまとめる</h4>
<p>最後に(A)〜(C)全ての条件をとりまとめる。(A)〜(C)のひとつでも条件を満たさなければ、Falseを返す。</p>
```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
```
<p>＊尚、本部分のプログラム作成にあたり、@wsldenli氏の「<a href="https://qiita.com/wsldenli/items/78596c8775a0673f255e">Pythonで数独を解く -Qiita</a>」を真似させていただいた。

<h2>プログラム全体</h2>
```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>