白状します。私はズルをしようとしました。雑誌や新聞に掲載されていたり、アプリだったり、ちょっと探してみるといろいろなところに数独(ナンプレ)は隠れています。さらにそれらを解いて応募するとお金だったり図書カードだったりが当たったりします。そんなわけで最近のマイブームは懸賞付き数独を解くことになりつつある私でしたが、ある日のこと「これプログラムで解いたら楽じゃない？」という発想に至りました。
そんな感じで今回は邪な発想から作成したプログラムを紹介しつつ、アルゴリズムの紹介をしていきたいと思います。今回はPythonで書きましたが、数独を解くプログラムは配列の扱いや関数の再帰呼び出しなど勉強になるところは沢山ありますので、プログラミングの練習問題としても優秀だと思います。また、今回はユニットテストも行っていきたいと思います。テストコードを書かないのは愚策と囁かれる昨今ですが、私自身未だにユニットテスト…テストコードすら書いたことがないのでここらで実践しておきたいと思います。
一応書いておきますが、プログラム実行して答えを出して懸賞に応募するのは規約など確認のうえ自己責任でお願いします。
アルゴリズム
では早速コードの紹介をしつつ、今回書いたアルゴリズムを説明していきたいと思います。今回採用した方法は「総当り」です。人間がやろうとすると途方も無いですが、計算機くんに任せればささっとパターンを確認していってくれます。
今回の解法はおそらく沢山ある数独アルゴリズムのなかの1つに過ぎず、またコーディングも言語の有効性をを引き出せていないかもしれませんのであくまで解答の1つとして御覧ください。
フィールドの持ち方
まずは数独全体の計91個の値をどうやって持っているかを紹介していきます。これは単純に9×9の２次元配列(リスト)で持つようにしています。また今回は数独を解くためのプログラムはクラスとして作っていこうと思いますので、下記のようにメンバ変数として宣言します。
class Sudoku:
def __init__(self):
self.field = [[0]*9 for i in range(9)]
"""
>>> field = [[0]*9 for i in range(9)]
>>> field
[[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""解析時には出題時のデフォルトの状態を入力しなくてはいけないので0で初期化する必要はないのですが、データの持ち方が想像しやすくなるかもと思い載せておきました。また今回のプログラムでは0は未入力の状態として扱っていきます。そのため上記の状態はすべてのセルが空白の状態ということになります。
次に、このfiledに値を入れる方法を紹介していきます。今回はシンプルに入力していきたいので、上記の２次元配列の形式でそのまま渡す方法とすべての要素を１行の文字列として渡す方法の２種類に対応しようと思います。前者は主に実装時のちょっとした動作確認時に使用していたものが残っているだけです。後者が本命で、手動入力で実行する手間を削減したく導入してみました。
class Sudoku:
# フィールドをセット
def _input_field(self, field_str='', field=None):
if field_str != '':
field = list(field_str)
self.field = [[int(n) for n in field[i:i+9]] for i in range(0, len(field), 9)]
elif field != None:
self.field = field
else:
self.field = [[0]*9 for i in range(9)]まず２次元配列を渡す方法です。こちらは単純で、この関数を呼び出す前に解析したい配列を作成してある前提なので、関数内ではメンバ変数に入れてあげるだけです。
次に文字列として渡してあげる方法ですが。まずは想定の文字列を紹介します。今回想定している文字列は１行目左のセルから１行目右のセル、続いて２行目左のセルから２行目右のセル…最後に9行目左のセルから９行目右のセルの順番で単純に数字を並べた文字列(空欄は0)です。
そのように与えられた文字列をまず1文字毎の配列に変換します。それがfield = list(field_str)の部分です。これによりfiledの中身は数字1文字を要素に持つ1次配列になります。次にこの１次元配列を9×9の２次元配列にしていきます。このときおそらく適切なライブラリを使用すると簡単に変換することもできると思いますが、今回は泥臭くループを用いて分割していきます。
分割時にここで注意なのは、初期化時で確認できるようにfiledで想定する型は文字列型ではなくint型のため、各要素を数値に変換してあげなくてはいけません。この処理に対応するのが[int(n) for n in field[i:i+9]の部分です。この部分で１次元配列から1行分9個の要素を抜き出しそのそれぞれに対しint変換を行っています。数値になっていないとこの後紹介する座標取得の処理が正常に動作しないのでご注意ください。
「ある座標」に「ある値」が入るかの確認
次に数独を特にあたり次に入れようとしている数字がそのセルに入るかの確認を行う関数を見ていきます。数独のルール上1つセルに対して縦と横そして同グループに同じ数字が入っていないことを確認しなくてはいけません。そのため処理上でも大きく分けて3つの確認を行います。
class Sudoku:
# 入れようとしている値が重複していないか確認する
def _is_valid(self, y, x, field, value):
# 行(横)
if value in field[y]:
return False
# 列(縦)
column = [l[x] for l in field]
if value in column:
return False
# グループ
area_y, area_x = (y // 3) * 3, (x // 3) * 3
area = sum([l[area_x:area_x+3] for l in field[area_y:area_y+3]], [])
if value in area:
return False
return Trueまずは横(行)の確認です。こちらは結構単純でfield[y]で確認したい行の他の値を1次元配列で取得できるため、後はこの中に含まれているかを確認するだけで大丈夫です。もちろん値があれば確認の結果はNGのためFalseを返して終わります。
次に縦(列)の確認です。こちらも1次元配列に落とし込んで値があるかを確認するのですが、行の確認と違いちょっと工夫する必要があります。その工夫部分が[l[x] for l in field]です。各行のx番目が確認したい値なので、それを取得して1次元リストを作成しています。後は行の確認と同じですね。
最後にグループの確認ですが、一番めんどくさいのがこのグループ確認になると思います。グループ確認の第一歩は確認したいセルがどのグループに所属するかを取得します。これには余り抜きの商を使います。商を使うことで1~3,4~6,7~9がそれぞれ0,1,2になると、縦横でこれを計算し0-0のグループから3-3のグループで計算ができそうです。Pythonでは//の演算子を使うことでこれを計算することができます。つまり(y // 3) * 3こんな感じです。商を求めた後、3をけけることで各グループの始点となる座標を得ることができます。最後に求めた始点を元に3行分それぞれで、3要素ずつを取得し1次元配列にまとめることで縦横の判定時と同じように要素が含まれるかを確認しています。
まだ入力していない座標を取得
確認部分を超えられたなら、ここはメチャクチャ簡単です。フィールドの配列内でまだ値を入れていない座標を取得します。つまりループで[0][0]からセルの値を見ていって0が入っている要素を見つけたらその添字を返しているだけです。
class Sudoku:
# 空白のセルの座標を返す
def _next_cell(self, field):
for y in range(len(field)):
for x in range(len(field[0])):
if field[y][x] == 0:
return y, x
return -1, -1もし配列内で0が見つからず最後まで行った場合はその時点で全てのセルが埋まったということなので「最後まで行ったよ」の合図として-1を返します。今回は毎回[0][0]から探し始めますがここは工夫できそうですね。
総当りで仮埋めして解く！
さて最後の項目で最後の難関、再帰部分を書いて完成させていきたいと思います。再帰処理は慣れないと難しいですが頑張ってみたので読み解いてみてください。
# 解く!!!
def _resolve(self, field):
y, x = self._next_cell(field)
if y == -1 and x == -1:
self.field = field
return True
for i in range(1, 10):
if self._is_valid(y, x, field, i):
field[y][x] = i
if self._resolve(field):
return True
field[y][x] = 0
return Falseこの関数を一回実行することで未入力のセルにその時点で入れることができる値を入れて次の自分に託します。その後、最後まで埋まったよの合図が来れば終了し、入らなかったよの合図が来たら自分が入れた値を戻してから終了という処理を行っています。
コード完成！
ここまで紹介したコードをまとめると以下のようになります。紹介していない画面表示系の関数もありますが、基本的にループを回しているだけなので上記を把握できていれば問題ないかと思います。
#coding:utf-8
# 数独を解く！！
class Sudoku:
def __init__(self):
self.field = [[0]*9 for i in range(9)]
def __str__(self):
return self._field_str(True, ' ')
# 入れようとしている値が重複していないか確認する
def _is_valid(self, y, x, field, value):
# 行(横)
if value in field[y]:
return False
# 列(縦)
column = [l[x] for l in field]
if value in column:
return False
# グループ
area_y, area_x = (y // 3) * 3, (x // 3) * 3
area = sum([l[area_x:area_x+3] for l in field[area_y:area_y+3]], [])
if value in area:
return False
return True
# 空白のセルの座標を返す
def _next_cell(self, field):
for y in range(len(field)):
for x in range(len(field[0])):
if field[y][x] == 0:
return y, x
return -1, -1
# フィールドをセット
def _input_field(self, field_str='', field=None):
if field_str != '':
field = list(field_str)
self.field = [[int(n) for n in field[i:i+9]] for i in range(0, len(field), 9)]
elif field != None:
self.field = field
else:
self.field = [[0]*9 for i in range(9)]
# フィールドの内容を文字列で返す
def _field_str(self, lines=True, separator=' '):
end = '\n' if lines else ''
return end.join([separator.join(map(str, l)) for l in self.field])
# Field全体を表示する
def print_field(self, lines=True, separator=' ', _return=False):
field = self._field_str(lines, separator)
if _return:
return field
print(field)
# 解く!!!
def _resolve(self, field):
y, x = self._next_cell(field)
if y == -1 and x == -1:
self.field = field
return True
for i in range(1, 10):
if self._is_valid(y, x, field, i):
field[y][x] = i
if self._resolve(field):
return True
field[y][x] = 0
return False
def resolve(self, field_str = '', field_list = None):
self._input_field(field_str, field_list)
self._resolve(self.field)
if __name__ == '__main__':
sudoku = Sudoku()
sudoku.resolve('023000000070000030005000010201079340084100002037004100300000001010800065700000093')
sudoku.print_field()というわけで、このプログラムを実行すると、resolve()の実行時に渡している問題を勝手に解いて結果を表示してくれます。これで懸賞に応募し放題ですね。
テストコードも用意しておきます
さて本題は終わったのですが、先程も書いたとおり、上記のプログラムには改善できる点があります。今回の記事ではその改善部分を修正するところまでは行わないのですが、せっかくなので今後改修しやすくなるようにテストコードなるものを用意してみようと思います。
世の中でテストの有用性について説かれてもう久しいですが、私はまだちゃんとしたテストというものをやったことがありません。もちろんコーディングの際には、ちょっと実行してみて動くか確認…というのはしますが、それはその場だけの確認であり、将来その部分の処理を修正したときに、本来求められていた仕様を網羅できているかを確認できないのです。というわけで、今回は丁度いい規模のコーディングを行ったので、テストの練習がてら実施していきたいと思います。
Pythonにはテスト用のフレームワークとしてunittestというものがあり、これを使うことで簡単にテストを行うことができます。今回のテストは実際に関数を実行し返ってきた結果が想定している結果と同じになるかという単純な確認を行います。
#coding:utf-8
import unittest
from Sudoku import Sudoku
class TestSudoku(unittest.TestCase):
def test_resolve(self):
sudoku = Sudoku()
sudoku.resolve('023000000070000030005000010201079340084100002037004100300000001010800065700000093')
self.assertEqual(sudoku.print_field(False, '', True),'623941587179658234845327619261579348584136972937284156398765421412893765756412893')
filed = [[0, 2, 3, 0, 0, 0, 0, 0, 0],
[0, 7, 0, 0, 0, 0, 0, 3, 0],
[0, 0, 5, 0, 0, 0, 0, 1, 0],
[2, 0, 1, 0, 7, 9, 3, 4, 0],
[0, 8, 4, 1, 0, 0, 0, 0, 2],
[0, 3, 7, 0, 0, 4, 1, 0, 0],
[3, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 8, 0, 0, 0, 6, 5],
[7, 0, 0, 0, 0, 0, 0, 9, 3]]
sudoku.resolve('', filed)
self.assertEqual(sudoku.print_field(False, '', True),'623941587179658234845327619261579348584136972937284156398765421412893765756412893')
さて上記が今回書いてみたテストコードになります。初学者すぎるので詳しい説明はほかの方にお任せするとして、基本部分で大切なのはunittestをimportするところとテスト用のクラスで継承するところだと思います。あとは自分のテストしたいプログラムに合わせてテストを書いてあげるだけです。
実際にテストをしているのはself.assertEqualの部分です。ここで引数の結果が一致すればテストもパスという流れです。今回は入力として文字列と配列を受け付けているので、その二つ分のテストを書きました。ちゃんとやろうと思えば別の問題や入力自体が誤っている場合なども必要かと思います。今回は最々々低限です。ここまでくればあとはpython -m unittestで実行してあげます。
# python -m unittest
----------------------------------------------------------------------
Ran 1 test in 110.013s
OK実行が完了すると上のような結果が返ってきます。これでテストは完了なので、今後処理を修正するときはこの結果が崩れないように修正していけば使用を満たしていることが確認できるという魂胆です。また、私はメインでGitLabを使用しているので、コミット時に自動でテストをしてくれるよう設定もしておきます。
image: python:3
stages:
- test
test_job1:
stage: test
script:
- python -m unittest今回は単純な環境だけで動作するため、設定は何も難しくなく上記の設定ファイルをディレクトリに設置するだけで大丈夫です。もし環境が特殊だったり、デプロイも合わせて行う場合はもう少し記述が必要ですが、最低限ではこのくらいで十分です。これだけであとは勝手にテストを実施してくれます。参考までに今回の作業リポジトリを置いておきます。
プログラムを書いてみて
さて、というわけで初めてのテストコードまで書いてきました。元々が単純にコーディングするのが好きな人間なので、今回のプログラムを考えていた時間はとても楽しい時間でした。加えて人生で初めてテストコードというものを書いてみて、確かにうまく使えば便利そうだなと言うのが実感できました。
ここまで来るともう満足してしまい、まだ懸賞数独で今回のプログラムを使っていないのですが、まあそれは別の話ということで。今後も面白い題材があれば今回のようにまとめていきたいと思いますのでどうぞよろしくお願いします。
最後に…ズルはだめだゾ (´ﾟ∀ﾟ)σ)’ω`)
