【Python】【再帰処理】【速度重視】数独を解く（改の改）

はじめに

過去2回、Pythonと数独に関する記事を書きました。
touch-sp.hatenablog.com
touch-sp.hatenablog.com
今回さらに速度アップを目指して改良を加えました。

結果

最初の結果

elapsed_time:166.9490511417389[sec]

1回目の改良の結果

elapsed_time:15.410191297531128[sec]

今回の改良の結果

elapsed_time:1.7875232696533203[sec]

なんと最初と比較して約100倍速くなりました。

Pythonスクリプト

import time
import copy
import textwrap

box_start_list = [0, 3, 6, 27, 30, 33, 54, 57, 60]
position_in_box = [0, 1, 2, 9, 10, 11, 18, 19, 20]

def position_define(x):
    row, col = divmod(x, 9)
    box_start = row//3 * 27 + col//3 * 3
    box_no = box_start_list.index(box_start)
    box_position = position_in_box.index(x-box_start)
    return box_no, box_position

def isOK(_string, _list):
    for each in _list:
        if _string[each[0]] != str(each[1]): return False    
    return True

def isOK_second(_string, number):
    for i in range(9):
        if not (q[box_start_list[i] + position_in_box[int(_string[i])]] in [0, number]): return False
    return True

def Try(answer_list):
    if 0 in answer_list:
        blank =answer_list.index(0)
        for string in all_list[blank]:
            if isOK_sudoku(answer_list, string):
                answer_list[blank] = string
                Try(answer_list)
                answer_list[blank] = 0
    else:
        final_report(answer_list)

def isOK_sudoku(_list, string):
    temp_list = [x for x in _list if x != 0]
    for i in range(9):
        exist_num = [x[i] for x in temp_list]
        if string[i] in exist_num: return False
    return True

def final_report(_list):
    answer = [0] * 81
    for i, string in enumerate(_list):
        for ii in range(9):
            answer[box_start_list[ii] + position_in_box[int(string[ii])]] = i + 1
    print(textwrap.fill(''.join([str(x) for x in answer]), 9))

if __name__ == '__main__':

    start = time.time()

    q = [
    0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 2, 8, 0,
    3, 7, 6, 4, 0, 0, 0, 0, 0,
    7, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 2, 0, 0, 0, 0, 0, 0, 0,
    4, 0, 0, 3, 0, 0, 0, 0, 6,
    0, 1, 0, 0, 2, 8, 0, 0, 0,
    0, 0, 0, 0, 0, 5, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 3
    ]

    with open('sudoku_pre.txt') as f:
        possible_list = [x.strip() for x in f.readlines()]

    while True:
        previous_q = copy.deepcopy(q)

        all_list = []

        for number in range(1, 10):
            each_list = []
            list_1 = [position_define(i) for i, v in enumerate(q) if v == number] 
            for each_string in possible_list:
                if isOK(each_string, list_1):
                    if isOK_second(each_string, number):
                        each_list.append(each_string)
            all_list.append(each_list)

        for index, each_list in enumerate(all_list):
            for i in range(9):
                number_list = list(set([x[i] for x in each_list]))
                if len(number_list) == 1:
                    number = number_list[0]
                    q[box_start_list[i] + position_in_box[int(number)]] = index + 1
        
        if q == previous_q:
            break
    
    answer_list = [0] * 9
    Try(answer_list)

    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")