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

はじめに

前回非常に短いスクリプトで数独を解くことにトライしました。
touch-sp.hatenablog.com

今回は速度重視で解いてみます。

結果

前回の結果

elapsed_time:166.9490511417389[sec]

今回の結果

elapsed_time:15.410191297531128[sec]

10倍の速度アップに成功しました。
誤解のないように説明しますが簡単な問題であれば数秒（場合によっては1秒未満）で解けます。時間がかかる難問を解いた時の比較をしています。

方法

事前準備

あらかじめこちらのスクリプトを実行して「sudoku_pre.txt」を作成ます。

def isOK(number, question_list):
    check_list = [x // 3 for x in question_list if x != 9]
    if number // 3 in check_list: 
        return False
    else:
        return True

def Try(question_list):
    if 9 in question_list:
        blank = question_list.index(9)
        for i in range(0, 9):
            if isOK(i, question_list):
                question_list[blank] = i
                Try(question_list)
                question_list[blank] = 9
    else:
        ok_list.append(''.join([str(x) for x in question_list]))

def isOK_second(string, question_list):
    check_list_1 = [int(x[0]) % 3 for x in question_list if x != 0]
    if int(string[0]) % 3 in check_list_1: return False

    check_list_2 = [int(x[1]) % 3 for x in question_list if x != 0]
    if int(string[1]) % 3 in check_list_2: return False

    check_list_3 = [int(x[2]) % 3 for x in question_list if x != 0]
    if int(string[2]) % 3 in check_list_3: return False

    return True

def Try_second(question_list):
    if 0 in question_list:
        blank = question_list.index(0)
        for i in ok_list:
            if isOK_second(i, question_list):
                
                question_list[blank] = i
                Try_second(question_list)
                question_list[blank] = 0
    else:
        ok_final.append(''.join(question_list))

ok_list= []
q = [9, 9, 9]
Try(q)

ok_final = []
q = [0, 0, 0]
Try_second(q)

with open('sudoku_pre.txt', 'w') as f:
    f.write('\n'.join(ok_final))

実行スクリプト

import time
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()]

    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)

    answer_list = [0] * 9
    Try(answer_list)

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

方法の解説

まずはこのような正解図を考えます。

この正解図を下図の黄色に塗られた3×3のBOXが９個集まったものと考えて下さい。

数独のルールとしておのおののBOX内には1～9の数字が入っています。
「1」に注目してBOX内のどこに存在するかを数値化します。
数値化する時には下図のルールに従うことにします。

それぞれのBOXを探すと「1」はこのように9桁の数字に数値化できると思います。

「318526137」

1つの数字に着目して配置できる可能性を考えていくと実は
9*6*3*6*4*2*3*2*1 = 46656通りしかありません。
前半のスクリプトはとり得る46656通りの数字をすべて書き出すためのものです。

1～9の数字に対して46656通りの数字から重複しないようにひとつずつ抽出しているのが後半のスクリプトになります。

2021年8月13日追記

この記事の後に書いた記事です。良かったらこちらも見て下さい。
touch-sp.hatenablog.com