pythonで数独(ナンバープレイス)を作る
内定先の研修で、pythonでナンバープレイスを作って解けるまでの早さを競うということをやった。
,5,3,,7,4,,,
,,,8,,,,,
,8,4,6,9,,2,1,
5,3,7,,6,,,2,
1,6,,3,,9,7,4,
8,,9,,,2,6,,
,7,5,9,4,1,3,8,2
4,,,5,3,,1,,7
3,9,1,2,8,7,,5,6
,9,4,,3,,1,,
8,1,2,7,,,,9,6
3,,,1,9,,,,
,3,,9,,4,6,,
,,8,6,1,3,,4,9
,,6,2,,,,,1
4,,3,5,,,,,8
5,,,,2,,7,,
,6,,,,8,4,1,5
上記のようなcsvファイルを用意して、1つの問題毎(つまり9行ずつ)にリストに入れていく。
解き終わったらそれをoutput.csvで出力する
結論としては以下のようになった。
import csv from datetime import datetime questions = [] def get_row_nums(question, y): return {num for num in question[y]} def get_col_nums(question, x): return {question[y][x] for y in range(9)} def get_block_nums(question, x, y): first_x, first_y = x // 3 * 3, y // 3 * 3 return {question[first_y + j][first_x + i] for i in range(3) for j in range(3)} def get_choices(question, x, y): first_choices = {1, 2, 3, 4, 5, 6, 7, 8, 9, ''} return first_choices - get_row_nums(question, y) - get_col_nums(question, x) - get_block_nums(question, x, y) def get_next_position(x, y): return (0, y + 1) if x == 8 else (x + 1, y) def solve(question, x = 0, y = 0): if y == 9: return True if question[y][x] == '': choices = get_choices(question, x, y) for choice in choices: question[y][x] = choice next_x, next_y = get_next_position(x, y) if solve(question, next_x, next_y): return True question[y][x] = '' return False else: next_x, next_y = get_next_position(x, y) return solve(question, next_x, next_y) def read_csv(): with open('./input.csv') as f: question = [] reader = csv.reader(f) for row in reader: question.append([int(x) if x != '' else x for x in row]) if len(question) == 9: questions.append(question) question = [] def write_csv(): with open('./output.csv', 'w', newline='') as f: writer = csv.writer(f) for question in questions: writer.writerows(question) def main(): read_csv() for question in questions: solve(question) write_csv() if __name__ == '__main__': s = datetime.now() print(s, '開始') main() e = datetime.now() print(e, '終了', e - s)
流れとしては、
①一番左上のマスから右に進んでいき、右端に到達したら次の行の最初マスに移動する。get_next_position関数でそれを行っている。
②もし現在のマスに既に数字があるなら、次のマスに移動するのみ。
③もし現在のマスに数字が無ければ、そのマスに入りうる選択肢を1つずつ入れていく。
選択肢は、１～９までの数字から、そのマスの行と列と３×３のブロックにある数字を引けば得られる。
get_row_nums,、get_col_nums,、get_block_nums,、get_choices関数でそれを行っている。
ちなみになぜget_choicesのfirst_choicesに空文字も含んでいるのかというと、
行と列とブロックにある数字を取得する際に空文字をまとめて取得し、後で空文字もまとめて引いてしまおうと思ったからである。
(いちいちif文で空文字かそうでないかを調べる必要が無くなる。)
④最後の右下のマスに数字を入れて次の行に移動したら、そのときは解けたということなのでTrueを返して終了する。
以上のことを再帰を使ってやっている。
最初は全ての空きマスの選択肢を一気に出して、その後で選択肢の数が少ない順にソートし、選択肢の数が一番少ないマスに数字を入れていく……という風にやっていたが、どうも準備に時間がかかりすぎるようで大人しく左上からスタートした方が断然早かった。
それとナンプレの効率的な解き方で検索して、その通りのやり方を実装しようとしたが異常に面倒だったし上のように準備に時間がかかって元も子も無くなりそうだったので辞めた。
もっと良い方法があったら教えていただけると嬉しいです。
