面白いデータを探して

適当に書く。間違えていたら教えてください。

数独を解いてみる

パソコンの大掃除をしていたら大学1年の時に出された課題のプログラムが出てきました。
その時の課題が「数独を解くプログラムを作りなさい」という課題だったのですが、改めてコードを読んでみるとまあ汚いし効率悪いしで散々でした。
正月で少し暇してたし、それを作りなおしてみよう的なのりです。

実装内容

とりあえず、今回は下のような感じで実装します。基本的には数独は正解が唯1通りになるように作られていますが、今回は正解が2つ以上あるような場合にも対応させます。(そういう課題だったので、、、)

  1. 初期盤面をスタックにpush。
  2. スタックが空なら終了。
  3. スタックから盤面 stateをpop。
  4.  stateの空いているマス (x, y)を検索。そのようなマスがなければ stateを正解として記録し2へ。
  5.  state (x, y)に1~9を入れてルール違反が起きるか調べる。ルール違反が起きない場合はその数字を入れた盤面をスタックにpush。
  6. 2へ。

かなり力技だけど、なんとかなるでしょう。

問題について

問題は残っていなかったのでKaggleのものを使用。その関係で問題読み込みなどの部分はやや煩雑。

# -*- coding:utf-8 -*-

from copy import deepcopy
from random import randint

# スタック
class Stack:
    
    def __init__(self):
        self.stack = []
        
    def push(self, data):
        self.stack.append(data)
    
    def pop(self):
        return self.stack.pop(-1)
    
    def get_stack_length(self):
        return len(self.stack)

class SudokuSolver:
    
    def __init__(self, problem):
        self.stack = Stack()
        self.stack.push(problem)
        self.answer = []
    
    def solve(self):
        """
        ありうる全正解について探索する
        """
        # スタックが空になるまで繰り返す
        while self.stack.get_stack_length() > 0:
            self.solve_one_step()
                
    def solve_one_step(self):
        """
        探索の1ステップ分
        """
        # 盤面をpop
        _state = self.stack.pop()
        # 埋まっていないマスを検索
        _x = 0
        _y = 0
        while _y != 9:
            if _state[_y][_x] == 0:
                break
            # 埋まっていれば次のマスを見る
            _x += 1
            if _x == 9:
                _x = 0
                _y += 1
        # _y == 9 ならばその盤面は正解状態
        if _y == 9:
            self.answer.append(_state)
        # _y != 9 のときそのマスに入りうる全数字を入れたものをstackにpush
        else:
            for _num in range(1, 10):
                if not self._check_error(_state, _num, _x, _y):
                    _next_state = deepcopy(_state)
                    _next_state[_y][_x] = _num
                    self.stack.push(_next_state)
    
    def _check_error(self, state, num, x, y):
        """
        現在の盤面に新しい数字を入れた際にルール違反が発生するか判定
        
        Parameters
        ----------
        state : list(9*9)
            判定したい盤面
        num : int
            入力したい数値
        x : int
            入力したい位置(横), 0<=x<=8
        y : int
            入力したい位置(縦), 0<=y<=8
        
        Returns
        -------
        ルール違反が発生する->True
        ルール違反が発生しない->False
        """
        # 横の判定
        if any([True if state[y][_x]==num else False for _x in range(9)]):
            return True
        # 縦の判定
        if any([True if state[_y][x]==num else False for _y in range(9)]):
            return True
        # 3*3ブロックの判定
        # ブロックの左上の位置を取得
        _x_upper_left = (x // 3) * 3
        _y_upper_left = (y // 3) * 3
        if any([True if state[_y][_x]==num else False \
                for _y in range(_y_upper_left, _y_upper_left + 3)\
                for _x in range(_x_upper_left, _x_upper_left + 3)]):
            return True
        return False
    
    def print_answer(self):
        n = 1
        for answer in self.answer:
            print("answer", n)
            for row in answer:
                row = [str(row[i]) for i in range(9)]
                print(" ".join(row))
            n += 1

# 問題の読み込みとか
# 100000題の中からランダムに1題解く
problem_number = randint(1, 1000000)
print("selected problem number is", problem_number)
with open("sudoku.csv", "r") as f:
    for i in range(problem_number+1):
        line = f.readline()
    line = line.split("\n")[0]
    line = line.split(",")
    prob = line[0]
    ans = line[1]
print("--problem--")
problem = [[prob[i*9+j] for j in range(9)] for i in range(9)]
for row in problem:
    print(" ".join(row))
print("--solver answer--")
problem = [[int(prob[i*9+j]) for j in range(9)] for i in range(9)]
ss = SudokuSolver(problem) # ソルバの呼び出し
ss.solve() # 解いてる
ss.print_answer() # ソルバの正解出力
print("--answer--") # 実際の正解出力
answer = [[ans[i*9+j] for j in range(9)] for i in range(9)]
for row in answer:
    print(" ".join(row))

何回か実行してみる

selected problem number is 712451
--problem--
0 8 9 1 0 0 0 0 7
0 0 0 0 5 0 0 0 0
0 1 3 6 8 2 0 0 0
6 4 0 0 9 7 0 8 0
0 3 0 2 4 0 5 0 9
0 0 5 0 0 0 0 0 0
8 5 0 0 0 0 6 0 4
0 0 4 0 0 0 1 9 2
2 0 1 0 0 3 0 0 0
--solver answer--
answer 1
5 8 9 1 3 4 2 6 7
4 2 6 7 5 9 8 1 3
7 1 3 6 8 2 9 4 5
6 4 2 5 9 7 3 8 1
1 3 8 2 4 6 5 7 9
9 7 5 3 1 8 4 2 6
8 5 7 9 2 1 6 3 4
3 6 4 8 7 5 1 9 2
2 9 1 4 6 3 7 5 8
--answer--
5 8 9 1 3 4 2 6 7
4 2 6 7 5 9 8 1 3
7 1 3 6 8 2 9 4 5
6 4 2 5 9 7 3 8 1
1 3 8 2 4 6 5 7 9
9 7 5 3 1 8 4 2 6
8 5 7 9 2 1 6 3 4
3 6 4 8 7 5 1 9 2
2 9 1 4 6 3 7 5 8
selected problem number is 114612
--problem--
1 4 0 6 0 7 9 5 0
0 3 0 0 2 0 0 0 6
0 0 0 0 5 0 1 0 0
0 0 8 4 0 0 5 6 9
7 0 0 0 0 1 0 0 2
9 2 0 0 3 0 0 0 8
2 5 0 9 0 0 0 8 0
6 0 7 0 0 0 4 3 0
0 0 3 7 0 5 0 0 0
--solver answer--
answer 1
1 4 2 6 8 7 9 5 3
5 3 9 1 2 4 8 7 6
8 7 6 3 5 9 1 2 4
3 1 8 4 7 2 5 6 9
7 6 5 8 9 1 3 4 2
9 2 4 5 3 6 7 1 8
2 5 1 9 4 3 6 8 7
6 9 7 2 1 8 4 3 5
4 8 3 7 6 5 2 9 1
--answer--
1 4 2 6 8 7 9 5 3
5 3 9 1 2 4 8 7 6
8 7 6 3 5 9 1 2 4
3 1 8 4 7 2 5 6 9
7 6 5 8 9 1 3 4 2
9 2 4 5 3 6 7 1 8
2 5 1 9 4 3 6 8 7
6 9 7 2 1 8 4 3 5
4 8 3 7 6 5 2 9 1

うまく動いてるっぽいです。
実行時間は問題によりますが0.06秒~0.01秒くらいでした。

最後に

良ければ数独の答えが2個できてしまわないかのチェックくらいに使ってやってください。