はじめに
皆さんこんにちは。今日は深さ優先探索という方法を使って、数独の答えを出力するプログラムの解説をしていく。例題の説明からして難しいので、記事の不備等は、コメントにてご連絡いただけると嬉しい。
例題
nは自然数、N=n^2を満たす自然数とする。このとき横N行縦N列の計N^2個のマス目からなる盤面をつくり、さらに太線でそれぞれn行n列からなるn^2個の区画に分ける。
このときそれぞれのマス目に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)数独の盤面
入力例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]]数独の盤面
入力例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を返す。
(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 sysclass 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>