LoginSignup
1
5

More than 3 years have passed since last update.

@ryuichi_matsumoto(竜一 松本)

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

Last updated at Posted at 2020-01-16

はじめに

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

例題

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

a0.jpg

このときそれぞれのマス目に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

入力例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

入力例2

[[4,0,0,0],[0,0,0,0],[1,0,4,0],[0,0,0,2]]　未入力のマス目には0を入力する。
(出典: 問題番号:6596750)

出力例2

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

プログラム作成の手順

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

  1. 判定部分を作成:マス目(y,x)が、問題の(A)(B)(C)を満たすか判定するプログラムを作成。マス目の縦、横、ブロック毎に1〜Nの数字が1個ずつ使われているか確認する。
  2. マス目に数字を置く:空いているマス目に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を返す。

    # 縦列に答えがあっているか調べる
    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) マス目の横の判定する部分

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

    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つずつ含まれるかどうか調べていく。

    # 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を返す。

    # 現在の(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

2:マス目に数字を置く(深さ優先探索 Depth-First Search)

数独のマス目への数字の置き方は、以下の手順で実装する。

  1. 再帰の終了条件を書く。主に縦列がNに差し掛かったら再帰を打ち切る。
  2. マス目(y,x)に既に数字が置かれている場合は、マス目(y,x+1)。すでに横の終端にいる時はマス目(0,y+1)に再帰させていく。
  3. マス目(y,x)に既に数字が置かれていない場合は、まずマス目(y,x)に1〜Nの数字を置いてみる。置いてみた結果、(A)〜(C)の条件を満たす時はTrueを返す。加え2.と同じようにマス目(y,x+1)又は(0,y+1)へと再帰させる。
  4. 3.でマス目(y,x)に1〜Nの全ての数字が条件を満たさないときは、マス目(y,x)の値を数字置く前{0}に戻す。

このように次へ次へと掘り進んで行って、条件を満たさない場合はひとつ前に戻って考え直す探索法を深さ優先探索(Depth-First Search)と言う。

    # 深さ優先探索より、数独の解を探索する
    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」を真似させていただいた。

プログラム全体

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)

その他参考にしたサイト

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

バックナンバー

・Python3で配列をクイックソートする
・Pythonで最大部分配列問題(maximum subarray problem)を解く

1
5
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
5