Pythonで数独を解いてみた
最近，週末の空いた時間にプログラミングの勉強を始めました．最近まで就活していた研究室の友達によると，データ分析系の仕事を探すならPythonとかRが役に立つとのことだったので，この夏はPythonを勉強することに...
本や教材を使ってプログラミングを勉強するのはどうも性に合わないので，適当に自分で課題を決めて実際にプログラムを組みながら勉強しています．ということで，今回の課題は「Pythonを使って数独を解いてみよう」です．
数独ってなに？
基本ルール
皆さんご存知の通り，【数独】とは数字を使ったパズルのひとつです．ナンバープレースと呼ばれていることもありますね．ルールは実にシンプルで，9*9のマスに3つのルールに従って1～9の数字を入れていくだけのゲームです．
- 縦一列に同じ数が入ってはいけない
- 横一列に同じ数が入ってはいけない
- 3*3で区切られた箱の中に同じ数が入ってはいけない
このルールに乗っ取ってすべての数字を入れることができれば，パズルを解いたことになります．では，実際どのような戦略で解けば良いのでしょうか？
どうやって解くの？
9*9の数独程度の規模の問題だと，コンピュータでランダムに数字を入れていって探索していけば割とすぐに解けてしまうのですが，今回はPythonの勉強ということで，人間と同じアルゴリズムを使って解こうと思います．つまり，同じ行・列・箱の数字を確認し，空欄に入る候補になる数字を探していくといったアルゴリズムです．
第一回では，以下のようなアルゴリズムを目指します．
- それぞれの空欄で候補となる数字を探す．
- 候補が1つに絞れたらマスに数字を入れる．
- 1に戻る．
名付けて，候補が一つだけに絞れるマスを埋めていく作戦です．具体例を使ってアルゴリズムを解説していきます．
この青いマスを埋めるケースを考えてみましょう．まずは，青いマスの縦・横・箱に注目してみます．
オレンジで塗ったエリアが，青いマスと同じ縦・横・箱に属するマスですね．青いマスには，このオレンジのエリアにある数字を入れることはできません．オレンジのエリアにある数字を見てみると【1,2,3,4,6,7,8,9】と，5以外の数字をすべて見つけることができます．
ということは，青のマスに入る候補は5だけなので，ここには5を入れてマスを埋めることができます．今回のコードでは，それぞれの空欄でこの手順を繰り返して数独を解いていきます．
この解法はシンプルですが，高難易度の問題を解くことはできません．第2回では，更に難易度の高い問題を解くアルゴリズムを追加していく予定です．
それでは解法を勉強したところで，早速今回のPythonコードを見ていきましょう．
Pythonコード
基本的に，ソースコードの変数名・コメントはすべて英語で書いています．もしかしたら日本人以外にもシェアする機会があるかもしれないしね！（多分ないけど）
メインコード
# Main function from numpy import * import math if __name__ == "__main__": # 1. Read data from text file sol=read_file() # 2. Display the initial problem print "Initial problem is:" output(sol) # 3. Obtain indices of cells which are not solved pair_indices = index_not_solved(sol) loop = 1 while len(pair_indices) > 0: # 4. Obtain candidates for each unsolved cell candidates = [] for pair_index in pair_indices: candidates.append(find_candidate(sol,*pair_index)) pair_indices = index_not_solved(sol) # 5. Use Unique-Candidate method candidates, pair_indices, sol = unique_candidate(candidates, pair_indices, sol) sol_old = sol # Put some exit statements to avoid infinite loop loop = loop+1 if loop > 100: print 'I cannot solve...' print 'Current solution is:' output(sol) break else: print 'Final solution is:' output(sol)
メインコードでは，それぞれの関数を呼び出してアルゴリズムを回しています．
- 数独の問題データの読み込み（テキストファイル）
- 数独の問題表示
- 空欄のインデックス（行・列番号）を取得
- 空欄に入る候補の数字を取得
- 候補が一つだけに絞れるマスを埋める
（それぞれの番号がソースコードのコメントの番号に対応しています．）
Whileループを使って，問題が解けるまでアルゴリズムをループさせています．無限ループにならないように，解けなかったときにループを抜ける条件を与えています．Pythonでは，while＋elseを使うことで，ループを抜けた場合・抜けなかった場合の処理を一つのWhileループで記述することができます．else後の部分は，Whileループがbreakで止まらずに最後まで回った場合に実行されます．
while (条件): if ループを抜ける条件: (ループを抜ける場合の処理) break else: (ループを抜けなかった場合の処理)
他の言語だと余計に変数を用意したりif文を使ったりしないといけないのですが，これを使うとコンパクトに書けて便利ですね．
数独問題データの読み込み
# Function to read 9x9 SuDoKu problem written in text-format def read_file(): f = open('problem.txt') lines = f.readlines() f.close data = array([9*[0]]*9) # Read data by lines for i,line in enumerate(lines): data[i] = map(int,list(line[:9])) return data
"problem.txt"というテキストファイルから数独の問題を読み込むシンプルな関数です．テキストファイルには，9*9の数字が書かれています．便宜上，空欄の代わりに0を入れています．
このファイルを書き換えれば，好きな問題を解かせることができます．Pythonでテキストファイルを読み込むときは，readlines()を使うことで，行ごとに読み込むことができます．今回は，行ごとに読み込んだ数字を，9*9の配列(data)にそのまま格納しています．
Pythonは，For文の書き方にも特徴がありますね．リストを使ってFor文を書くときは，以下のように書くことができます．
animals = ['cat', 'dog', 'rabbit', 'chicken'] for animal in animals: # Display the name of each animal print animal
このように，リスト（animals）の中身を変数（animal）に代入し，ループさせることができます．enumerate()を使うことで同時にインデックスを得ることもできます．今回のコードでは，行番号が必要なのでenumerate()を使っています．
問題・解答の表示
# Function to output the current solution with SuDoKu view def output(solution): for i in xrange(9): for j in xrange(9): # Print solution (Insert dots instead of zero values) if solution[i,j]==0: print ".", else: print solution[i,j], # Insert vertical lines to divide into 9-segment if (j+1)%3==0 and j<8: print "│", print # Insert horizontal lines to divide into 9-segment if (i+1)%3==0 and i<8: print "─────────────" print '\n'
現在の解答を表示するだけの関数です．一応数独っぽく見せるために，3で割り切れる行・列で罫線を入れて表示しています．実行するとこんな感じ．
メインコードの中では，初期解と最終解を表示するために使っています．
空欄のインデックス取得
# Function to find the pair of index which was still not solved def index_not_solved(solution): pair_index = [] for i in xrange(9): for j in xrange(9): if solution[i,j]==0: pair_index.append([i,j]) return pair_index
現在の解答の中で0（空欄）を探して，そのインデックス（行番号・列番号）を取得する関数です．For文で整数をループさせるときは，xrange()を使うのがベターとのこと．
空欄に入る候補探索
# Function to find candidates def find_candidate(solution,row,col): # Initial candidates from 1 to 9 candidates = [1,2,3,4,5,6,7,8,9] # Check vertical line candidates = list(set(candidates) - set(solution[:,col])) # Check horizontal line candidates = list(set(candidates) - set(solution[row,:])) # Check 3x3 box box_tmp = solution[(3*(row//3)):(3*(row//3)+3),(3*(col//3)):(3*(col//3)+3)] # (Make the box flat list) box_tmp = [flatten for inner in box_tmp for flatten in inner] candidates = list(set(candidates) - set(box_tmp)) return candidates
縦・横・箱をチェックして，候補となる数字を取得する関数です．1～9の数字から，同じ列・行・箱にある数字を取り除いていく方式を取っています．
2つのリストの要素を比較するには，set型を使うのが便利です．リストをset型に置換して引き算することで，同じ列・行・箱にある数字を候補から削除しています．
箱の場合は，3*3の状態から9*1に変形させています．For文はリストを宣言するときにも使うことができます．このケースでは，2つのFor文を使ってリストを平らにしています．innerには行ごとのリスト，flattenには要素レベルのデータが格納されています．少し分かりにくいですが，慣れると便利ですね．
単一候補を埋める
# Function to find solution by Unique-Candidate method def unique_candidate(candidates,pair_indices,sol): cnt_delete = 0 for i, (candidate, pair_index) in enumerate(zip(candidates,pair_indices)): # When the candidate is only one, insert the value to the solution if len(candidate) == 1: sol[pair_index[0],pair_index[1]] = candidate[0] candidates.pop(i-cnt_delete) pair_indices.pop(i-cnt_delete) cnt_delete += 1 return [candidates, pair_indices, sol]
候補が1つに絞れた場合に空欄を数字で埋める関数です．空欄を埋めたあとに，popを使って候補のリストから削除しています．2つのリストを同時に使ってFor文を回したいときは，zip()を使うことで実現できます．
animals = ['cat', 'dog', 'rabbit', 'chicken'] names = ['Tama', 'Pochi', 'Shiro', 'Kokko'] for animal, name in zip(animals, names): print animal, ': ', name
また，enumerate()と組み合わせることで，インデックスを取得することもできます．これらを上手く組み合わせると，余計なコードが減り，よりシンプルに書き上げることができますね．
ソースコードまとめ
実行結果
無事に問題を解くことができました．いくつか違う問題を試してみましたが，やはり難易度の高い問題は解くことができませんでした．次回以降，より難しい問題を解くのを課題にしていきたいと思います．
最後に
いかがだったでしょうか？まだまだPython歴が浅いので，日々勉強の連続ですね．何か間違っているor改善点などありましたら，ぜひぜひコメントに残していただけると嬉しいです．単純なコーディングではなく，色々な要素を取り入れてPythonらしい構文を心掛けたつもりです．ぜひ皆さんもプログラミングを楽しみながら勉強していってみてはいかがでしょうか？
