【Python】数独を解くプログラムを作る part2 効率化編

前回はこちら↓↓

part1の振り返り

part1では、このようなプログラムを作りました。

sudoku_1.py

from stopwatch import measure_time


# 数独問題を表す2次元配列を定義（空欄を0に設定）
TABLE1 = [[9, 0, 6, 7, 0, 5, 4, 0, 2],
          [0, 0, 0, 6, 9, 4, 0, 0, 0],
          [4, 0, 7, 0, 3, 0, 5, 0, 9],
          [2, 5, 0, 3, 7, 1, 0, 8, 6],
          [0, 7, 3, 5, 6, 9, 1, 2, 0],
          [1, 6, 0, 4, 8, 2, 0, 5, 7],
          [7, 0, 1, 0, 2, 0, 6, 0, 5],
          [0, 0, 0, 1, 4, 6, 0, 0, 0],
          [6, 0, 8, 9, 0, 7, 2, 0, 1]]

# 高難度版テーブル
TABLE2 = [[0, 0, 0, 0, 1, 0, 9, 2, 0],
          [0, 6, 0, 0, 5, 0, 0, 0, 0],
          [0, 7, 1, 0, 0, 0, 0, 5, 0],
          [0, 2, 0, 0, 0, 6, 3, 1, 0],
          [0, 0, 0, 7, 0, 0, 0, 0, 9],
          [9, 3, 0, 4, 0, 0, 0, 0, 5],
          [3, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 1, 0, 5, 0, 0, 7],
          [1, 0, 0, 3, 6, 2, 0, 0, 0]]

# 全部埋まった想定のテーブル
TABLE_COMP = [[1 for i in range(9)] for j in range(9)]


# m行n列のセルに数値kを入れたとき、そのkが条件を満たすか判定する関数
def check_cell(t, m, n, k):
    n_set1, n_set2, n_set3 = set(), set(), set()
    # 行に対してのチェック
    for cell in t[m]:
        if cell != 0:
            n_set1.add(cell)
    # 列に対してのチェック
    for r in t:
        if r[n] != 0:
            n_set2.add(r[n])
    # エリアに対してのチェック
    for a in range(3 * (m // 3), 3 * (m // 3) + 3):
        for b in range(3 * (n // 3), 3 * (n // 3) + 3):
            if t[a][b] != 0:
                n_set3.add(t[a][b])
    # これら3つのsetの和集合を取る
    n_union = n_set1.union(n_set2, n_set3)
    # 差集合をとり、まだ使われていない数字を取得
    n_not_used = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(n_union)
    # kが選択可能な数値かどうかを真偽値で返す
    return k in n_not_used


# 一番左上の空欄を取得する関数
def find_next_blank(t):
    for i, items in enumerate(t):
        for j, item in enumerate(items):
            if item == 0:
                # 順にマス目を調べ、0が初めてあった座標を返す
                return i, j
    # 81マスの中に一度も0がなければ(-1, -1)を返す
    return -1, -1


# 数独を解く関数
def do(t):
    r, c = find_next_blank(t)
    # rに-1が格納されていれば、数独完成済み
    if r == -1:
        return True
    # 1 ~ 9の数字を順番にcheck_cell()関数で判定
    for num in range(1, 10):
        # 条件を満たしていればnumを格納
        if check_cell(t, r, c, num):
            t[r][c] = num
            # do()関数自身を呼び出し
            if do(t):
                return True
            t[r][c] = 0
    # 1 ~ 9まで一つも条件を満たさなければ戻るためFalseを返す
    return False


# 完成したTABLEが実際に正しいかどうかを判定する関数
def check_table(t):
    status = True
    for r in range(9):
        for c in range(9):
            # この関数は第4引数の数値が使われていない数字かどうかを判定するため
            # 一度でもTrue -> 完成済みTABLEのどこかに重複が発生している
            if check_cell(t, r, c, t[r][c]):
                status = False
    return status


# 数独テーブルを表示する関数
def display_table(t):
    for _ in t:
        print(_)


# 実行部分
# 未完成状態の数独の表示
display_table(TABLE1)
# 数独を解く
print("↓")
print("処理時間 : " + measure_time(do, TABLE1))
# 完成後の数独の表示
display_table(TABLE1)
# check_table()関数で完成後の数独が適切な常態かチェック
w = "この解答は正しいです。" if check_table(TABLE1) else "この解答は正しくありません"
print(w)

空欄数の少ない簡単な数独のTABLE1なら処理時間は短いですが。

実行結果

[9, 0, 6, 7, 0, 5, 4, 0, 2]
[0, 0, 0, 6, 9, 4, 0, 0, 0]
[4, 0, 7, 0, 3, 0, 5, 0, 9]
[2, 5, 0, 3, 7, 1, 0, 8, 6]
[0, 7, 3, 5, 6, 9, 1, 2, 0]
[1, 6, 0, 4, 8, 2, 0, 5, 7]
[7, 0, 1, 0, 2, 0, 6, 0, 5]
[0, 0, 0, 1, 4, 6, 0, 0, 0]
[6, 0, 8, 9, 0, 7, 2, 0, 1]
↓
処理時間 : 1.4159 ms
[9, 8, 6, 7, 1, 5, 4, 3, 2]
[3, 2, 5, 6, 9, 4, 7, 1, 8]
[4, 1, 7, 2, 3, 8, 5, 6, 9]
[2, 5, 4, 3, 7, 1, 9, 8, 6]
[8, 7, 3, 5, 6, 9, 1, 2, 4]
[1, 6, 9, 4, 8, 2, 3, 5, 7]
[7, 4, 1, 8, 2, 3, 6, 9, 5]
[5, 9, 2, 1, 4, 6, 8, 7, 3]
[6, 3, 8, 9, 5, 7, 2, 4, 1]
この数独は正しいです。

空欄が多く難度の高いTABLE2のような数独の場合、目に見えて処理時間が跳ね上がります。

実行結果

[0, 0, 0, 0, 1, 0, 9, 2, 0]
[0, 6, 0, 0, 5, 0, 0, 0, 0]
[0, 7, 1, 0, 0, 0, 0, 5, 0]
[0, 2, 0, 0, 0, 6, 3, 1, 0]
[0, 0, 0, 7, 0, 0, 0, 0, 9]
[9, 3, 0, 4, 0, 0, 0, 0, 5]
[3, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 5, 0, 0, 7]
[1, 0, 0, 3, 6, 2, 0, 0, 0]
↓
処理時間 : 424.5753 ms
[5, 4, 3, 8, 1, 7, 9, 2, 6]
[8, 6, 9, 2, 5, 3, 4, 7, 1]
[2, 7, 1, 6, 4, 9, 8, 5, 3]
[7, 2, 4, 5, 9, 6, 3, 1, 8]
[6, 1, 5, 7, 3, 8, 2, 4, 9]
[9, 3, 8, 4, 2, 1, 7, 6, 5]
[3, 5, 6, 9, 7, 4, 1, 8, 2]
[4, 9, 2, 1, 8, 5, 6, 3, 7]
[1, 8, 7, 3, 6, 2, 5, 9, 4]
この数独は正しいです。

そのため、プログラムがこのままでは、数独テーブルの空欄の数によって実行時間が大きく変わり不便です。
それもそのはずで、このdo関数内では、最初に見つけた空欄にとりあえず1から順に数値を入れて辻褄が合えば次に進み、矛盾したら一つ戻るという深さ優先探索法を採用しています。
空欄の数を$n$個としたとき、最大で$9^n$通りのパターンを調べる必要があります。
例で言うと、TABLE2は空欄の数が55個なので、運が悪いと約3.04E+52(3恒河沙)通りの計算が必要になります、馬鹿げてる。

そのため、運よくトントン拍子に進めばすぐに終わりますが、何度も何度も巻き戻ったり、終盤で矛盾を発見して大きく巻き戻ったりした場合、時間を相当ロスします。

実は前回のpart1の途中で、このようなことを書いていました。

正直要素が少ない順から埋めたら簡単ですが、ここはあえて我慢..
(入りうる数字の候補が少ない順に埋めていく処理は次回以降の予定です)

今回はまさに、要素が少ない順に埋める。という処理を実装していきます。
深さ優先探索という全探索型の処理から、空欄に入りうる数字の候補が少ない順から格納していく処理に改良していきます。
ただ、基本的に空欄と入れる数字の順番が変わるだけで、基本的なdo()関数内の処理の動きはあまり変わらず、再帰関数という形で作っていきます。

改良の軌跡

check_cell()関数の変更

まず最初に、check_cell()関数の最後の行の処理を変えました。
今まではreturn k in n_not_usedという記述で、kがn_not_usedに含まれているかどうかを真偽値で返していました。
今回は入りうる数字の集合自体が欲しいため、便宜上関数を書き換え直接集合を返すようにします。

# m行n列のセルに格納することが可能な数字を列挙する関数
def check_cell(t, m, n):
    n_set1, n_set2, n_set3 = set(), set(), set()
    # 行に対してのチェック
    for cell in t[m]:
        if cell != 0:
            n_set1.add(cell)
    # 列に対してのチェック
    for r in t:
        if r[n] != 0:
            n_set2.add(r[n])
    # エリアに対してのチェック
    for a in range(3 * (m // 3), 3 * (m // 3) + 3):
        for b in range(3 * (n // 3), 3 * (n // 3) + 3):
            if t[a][b] != 0:
                n_set3.add(t[a][b])
    # これら3つのsetの和集合を取る
    n_union = n_set1.union(n_set2, n_set3)
    # 差集合をとり、まだ使われていない数字を取得
    n_not_used = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(n_union)
    # m, nに入りうる数字の集合を返す
    return n_not_used

現時点でのすべての空欄位置をリストで返す関数を定義

新たに全ての空欄を見つける関数を追加してみました。

# 空欄をすべて取得し、2次元配列で返す関数
def find_all_blank(t):
    blank_list = []
    for i, items in enumerate(t):
        for j, item in enumerate(items):
            if item == 0:
                blank_list.append((i, j))
    return blank_list


print(find_all_blank(TABLE1))

実行結果

[(0, 1), (0, 4), (0, 7), (1, 0), ... , (8, 4), (8, 7)]

前回は一番左上の空欄の位置のみを取得していましたが、tuple型の位置情報をリストに入れたblank_listを返しています。
この関数で取得した空欄マス座標のリストから、今度はそれぞれのマスに対応した入りうる数字の候補もリストで取得したいと思います。

---

空欄に入りうる数字が少ない順にソートして返す関数の定義

• ひな形関数の作成

# 空欄の座標と、その空欄に入りうる数字の集合を2つのリストで返す関数
def sort_blank_cell(t):
    if not find_all_blank(t):
        return -1, -1
    # 空欄に入る数字の候補リストと、空欄の座標リスト
    n_list = []
    blank_cell_list = []
    # 2つのリストに値を追加
    for blank_cell in find_all_blank(t):
        blank_cell_list.append((blank_cell[0], blank_cell[1]))
        n_list.append(check_cell(t, blank_cell[0], blank_cell[1])
    return blank_cell_list, n_list


# 空欄マスの座標リストを表示
print(sort_blank_cell(TABLE1)[0])
# そのマスに対応する入りうる数字の集合のリストを表示
print(sort_blank_cell(TABLE1)[1])

実行結果

[(0, 1), (0, 4), (0, 7), ... , (8, 4), (8, 7)]
[{8, 1, 3}, {1}, {1, 3}, ... , {5}, {3, 4}]

まず、if not find_all_blank(t):という条件分岐の記述ですが、
Pythonのlistは、要素が空である場合、Falseを返す仕様があります。
そのため、この条件文の中の処理は、find_all_blank()関数の戻り値が空のリスト、つまり空欄が一つもなかった時にTrueとなり実行されます。
上の条件文がTrueの時、tupleで-1, -1を返すように作りました。
Falseの時は下に行きます。空欄に入りうる数字の候補の集合を格納するためのリストと、それに紐づいた空欄の座標を格納するためのリストを作ります。

find_all_blank()関数で取得した空欄マスの座標リストを一つずつループします。そのうちの一つをblank_cellとしたとき、
blank_cell[0]が空欄の行番号、blank_cell[1]が空欄の列番号となり、これらをtuple型でblank_cell_listに追加していきます。
check_cell()関数に直近で取得した行、列情報を元に、その空欄マスで入りうる数字の集合を取得し、n_listに追加します。

このループが終わると、全ての空欄の座標情報と、その空欄に入りうる数字の集合のリストが完成します。
今回はこの2つのリストを返しています。

実行結果を見ると、まず上段に空欄マスが列挙されていて、下にはその空欄に対応する数字の候補の集合が列挙されています。
ただ、この時点ではソートされていないため、このままでは役に立ちません。

• ひな形関数からソートして返す関数に改良

ここが一番苦労しました。
空欄マスの座標と数字の集合を紐づけた状態で、かつ数字の集合の要素数が少ない順にソートする方法を模索してトライしてはエラーが出て、の繰り返しでした。
今回完成したプログラムも、可読性が高いとは言えませんね...

# 空欄を入りうる数字が少ない順にソートし、その空欄の座標と候補の集合を返す関数
def sort_blank_cell(t):
    if not find_all_blank(t):
        return -1, -1
    # 空欄に入る数字の候補リストと、空欄の座標リスト
    n_list = []
    blank_cell_list = []
    # 2つのリストに値を追加
    for blank_cell in find_all_blank(t):
        blank_cell_list.append((blank_cell[0], blank_cell[1]))
        n_list.append(check_cell(t, blank_cell[0], blank_cell[1]))

    # 数字の候補リストを、集合の要素数昇順にソートするための要素番号リストを作成
    indices = [*range(len(n_list))]
    # 要素番号リストを、n_list要素数昇順にソート
    sorted_indices = sorted(indices, key=lambda i: len(n_list[i]))
    # ソートされた要素番号をもとに、n_list, blank_cell_listもソート
    n_list_sorted = [n_list[i] for i in sorted_indices]
    blank_cell_list_sorted = [blank_cell_list[i] for i in sorted_indices]

    return blank_cell_list_sorted, n_list_sorted


# 空欄マスの座標リストを表示
print(sort_blank_cell(TABLE1)[0])
# そのマスに対応する入りうる数字の集合のリストを表示
print(sort_blank_cell(TABLE1)[1])

実行結果

[(0, 4), (2, 5), (3, 6), (4, 0), ... , (1, 1), (7, 6)]
[{1}, {8}, {9}, {8}, ... , {8, 1, 2, 3}, {8, 9, 3, 7}]

indices = [*range(len(n_list))] という処理があります。
この*(アスタリスク)は、アンパック(unpack)と呼ばれ、その働きは直後に記述されているコレクションの要素を複数の変数に展開して代入することが出来ます。
アンパックについて詳しくはこちらを参照してください。

上記の処理では、range()関数のイテラブル（反復可能）な戻り値をアンパッキングしてindicesリストに格納しています。
これによって得られるリストは、[0, 1, 2, 3, 4, ... , 30, 31]という空欄数と同じ数の等差な要素番号リストですが、せっかくなので使ってみました。

sorted_indices = sorted(indices, key=lambda i: len(n_list[i])) は、先ほど作った要素番号リストを、ラムダ式を利用して
空欄に入りうる数字の集合の要素数が少ない順にソートした配置を、このindicesリストにも適用しています。
このソートによって得られるsorted_indicesは、[1, 11, 14, 15, 16, ... , 4, 26]といったリストになっています。
この番号が何を表しているかというと、入る候補の少ない空欄順にソートした時の、要素番号のリストになっています。

そのため、このsorted_indicesを利用すると、空欄マスのリストも、入る数字の候補のリストも、同じくソートすることが出来ます。

• n_list_sorted = [n_list[i] for i in sorted_indices]
• blank_cell_list_sorted = [blank_cell_list[i] for i in sorted_indices]

この2行が実際のソート処理です。n_listとblank_cell_listを、要素番号がsorted_indicesと一致するようにソートされています。
sort_blank_cell()関数は、この2つのソートされたリストを返すように設計しました。

---

数独を解く関数の改良

part1で作成したdo()関数の処理構造をもとにして、改良されたdo_v2()関数を作成しました。

# 数独を解く関数、候補が少ないマス目から候補を一つずつ格納
def do_v2(t):
    blank_cell_list, n_list = sort_blank_cell(t)
    # blank_cell_listに-1が格納されていれば、数独完成済み
    if blank_cell_list == -1:
        return True
    r = blank_cell_list[0][0]
    c = blank_cell_list[0][1]
    # numを格納
    for num in n_list[0]:
        t[r][c] = num
        # do_v2()関数自身を呼び出し
        if do_v2(t):
            return True
        t[r][c] = 0
    # 一つも条件を満たさなければ戻るためFalseを返す
    return False

まず冒頭で、sort_blank_cell()関数を呼び出し、引数に渡された数独テーブルデータに対応するすべての空欄マスと、その空欄が候補に持つ数字のリストを、候補が少ない順にソートした上で取得し、blank_cell_listとn_listに格納しています。

もし数独が既に完成している場合は、blank_cell_listに-1が格納されるため、その場合この関数はTrueを返すようにしました。

この関数は再帰処理によって繰り返し呼び出されることが前提であるため、行、列はblank_cell_listの最初のtupleデータのみを参照し取得します。その結果r, cには、一番優先して埋めるべき空欄マスの行番号、列番号が格納されます。
そしてその空欄マスに対応した数字の候補の集合から、1つずつその空欄への格納を試してみます。
その際、再帰処理を行い、Trueが返ってきたとき、同じくTrueを返すようにします。
もしFalseが返ってきた場合は、該当するマス目に0を代入してやり直します。

完成

sudoku_2.py

from stopwatch import measure_time

# 数独問題を表す2次元配列を定義（空欄を0に設定）
TABLE1 = [[9, 0, 6, 7, 0, 5, 4, 0, 2],
          [0, 0, 0, 6, 9, 4, 0, 0, 0],
          [4, 0, 7, 0, 3, 0, 5, 0, 9],
          [2, 5, 0, 3, 7, 1, 0, 8, 6],
          [0, 7, 3, 5, 6, 9, 1, 2, 0],
          [1, 6, 0, 4, 8, 2, 0, 5, 7],
          [7, 0, 1, 0, 2, 0, 6, 0, 5],
          [0, 0, 0, 1, 4, 6, 0, 0, 0],
          [6, 0, 8, 9, 0, 7, 2, 0, 1]]


# m行n列のセルに格納することが可能な数字を列挙する関数
def check_cell(t, m, n):
    n_set1, n_set2, n_set3 = set(), set(), set()
    # 行に対してのチェック
    for cell in t[m]:
        if cell != 0:
            n_set1.add(cell)
    # 列に対してのチェック
    for r in t:
        if r[n] != 0:
            n_set2.add(r[n])
    # エリアに対してのチェック
    for a in range(3 * (m // 3), 3 * (m // 3) + 3):
        for b in range(3 * (n // 3), 3 * (n // 3) + 3):
            if t[a][b] != 0:
                n_set3.add(t[a][b])
    # これら3つのsetの和集合を取る
    n_union = n_set1.union(n_set2, n_set3)
    # 差集合をとり、まだ使われていない数字を取得
    n_not_used = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(n_union)
    # m, nに入りうる数字の集合を返す
    return n_not_used


# 空欄を入りうる数字が少ない順にソートし、その空欄の座標と候補の集合を返す関数
def sort_blank_cell(t):
    if not find_all_blank(t):
        return -1, -1
    # 空欄に入る数字の候補リストと、空欄の座標リスト
    n_list = []
    blank_cell_list = []
    # 2つのリストに値を追加
    for blank_cell in find_all_blank(t):
        blank_cell_list.append((blank_cell[0], blank_cell[1]))
        n_list.append(check_cell(t, blank_cell[0], blank_cell[1]))
    # 数字の候補リストを、集合の要素数昇順にソートするための要素番号リストを作成
    indices = [*range(len(n_list))]
    # 要素番号リストを、n_list要素数昇順にソート
    sorted_indices = sorted(indices, key=lambda i: len(n_list[i]))
    # ソートされた要素番号をもとに、n_list, blank_cell_listもソート
    n_list_sorted = [n_list[i] for i in sorted_indices]
    blank_cell_list_sorted = [blank_cell_list[i] for i in sorted_indices]

    return blank_cell_list_sorted, n_list_sorted


# 空欄をすべて取得し、2次元配列で返す関数
def find_all_blank(t):
    blank_list = []
    for i, items in enumerate(t):
        for j, item in enumerate(items):
            if item == 0:
                blank_list.append((i, j))
    return blank_list


# 数独を解く関数、候補が少ないマス目から候補を一つずつ格納
def do_v2(t):
    blank_cell_list, n_list = sort_blank_cell(t)
    # blank_cell_listに-1が格納されていれば、数独完成済み
    if blank_cell_list == -1:
        return True
    r = blank_cell_list[0][0]
    c = blank_cell_list[0][1]
    # numを格納
    for num in n_list[0]:
        t[r][c] = num
        # do_v2()関数自身を呼び出し
        if do_v2(t):
            return True
        t[r][c] = 0
    # 一つも条件を満たさなければ戻るためFalseを返す
    return False


# 完成したTABLEが実際に正しいかどうかを判定する関数
def check_table(t):
    status = True
    for r in range(9):
        for c in range(9):
            # この関数は第4引数の数値が使われていない数字かどうかを判定するため
            # 一度でもTrue -> 完成済みTABLEのどこかに重複が発生している
            if t[r][c] in check_cell(t, r, c):
                status = False
    return status


# 数独テーブルを表示する関数
def display_table(t):
    for _ in t:
        print(_)


# 実行部分
# 未完成状態の数独の表示
display_table(TABLE1)
# 数独を解く
print("↓")
print("処理時間 : " + measure_time(do_v2, TABLE1))
# 完成後の数独の表示
display_table(TABLE1)
# check_table()関数で完成後の数独が適切な状態かチェック
w = "この解答は正しいです。" if check_table(TABLE1) else "この解答は正しくありません"
print(w)

というわけでTABLE1で実行してみます。結果はいかに・・・

実行結果

[9, 0, 6, 7, 0, 5, 4, 0, 2]
[0, 0, 0, 6, 9, 4, 0, 0, 0]
[4, 0, 7, 0, 3, 0, 5, 0, 9]
[2, 5, 0, 3, 7, 1, 0, 8, 6]
[0, 7, 3, 5, 6, 9, 1, 2, 0]
[1, 6, 0, 4, 8, 2, 0, 5, 7]
[7, 0, 1, 0, 2, 0, 6, 0, 5]
[0, 0, 0, 1, 4, 6, 0, 0, 0]
[6, 0, 8, 9, 0, 7, 2, 0, 1]
↓
処理時間 : 2.1794 ms
[9, 8, 6, 7, 1, 5, 4, 3, 2]
[3, 2, 5, 6, 9, 4, 7, 1, 8]
[4, 1, 7, 2, 3, 8, 5, 6, 9]
[2, 5, 4, 3, 7, 1, 9, 8, 6]
[8, 7, 3, 5, 6, 9, 1, 2, 4]
[1, 6, 9, 4, 8, 2, 3, 5, 7]
[7, 4, 1, 8, 2, 3, 6, 9, 5]
[5, 9, 2, 1, 4, 6, 8, 7, 3]
[6, 3, 8, 9, 5, 7, 2, 4, 1]
この解答は正しいです。

1.4159 ms -> 2.1794 ms
part1の全探索型プログラムより若干遅くなってますね。

という事で今度はより高難度なTABLE2で試してみましょう。

実行結果

[0, 0, 0, 0, 1, 0, 9, 2, 0]
[0, 6, 0, 0, 5, 0, 0, 0, 0]
[0, 7, 1, 0, 0, 0, 0, 5, 0]
[0, 2, 0, 0, 0, 6, 3, 1, 0]
[0, 0, 0, 7, 0, 0, 0, 0, 9]
[9, 3, 0, 4, 0, 0, 0, 0, 5]
[3, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 5, 0, 0, 7]
[1, 0, 0, 3, 6, 2, 0, 0, 0]
↓
処理時間 : 16.948 ms
[5, 4, 3, 8, 1, 7, 9, 2, 6]
[8, 6, 9, 2, 5, 3, 4, 7, 1]
[2, 7, 1, 6, 4, 9, 8, 5, 3]
[7, 2, 4, 5, 9, 6, 3, 1, 8]
[6, 1, 5, 7, 3, 8, 2, 4, 9]
[9, 3, 8, 4, 2, 1, 7, 6, 5]
[3, 5, 6, 9, 7, 4, 1, 8, 2]
[4, 9, 2, 1, 8, 5, 6, 3, 7]
[1, 8, 7, 3, 6, 2, 5, 9, 4]
この解答は正しいです。

424.5753 ms -> 16.948 ms

ということで、こちらは比較にならないほど早くなっていることが分かります。

---

おまけ

さらに、今回は世界最難度といわれる数独も用意しました。

これをdo()関数とdo_v2()関数で実行して処理時間を比較してみます。

sudoku_2.py

# 最難度版テーブル
TABLE3 = [[8, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 3, 6, 0, 0, 0, 0, 0],
          [0, 7, 0, 0, 9, 0, 2, 0, 0],
          [0, 5, 0, 0, 0, 7, 0, 0, 0],
          [0, 0, 0, 0, 4, 5, 7, 0, 0],
          [0, 0, 0, 1, 0, 0, 0, 3, 0],
          [0, 0, 1, 0, 0, 0, 0, 6, 8],
          [0, 0, 8, 5, 0, 0, 0, 1, 0],
          [0, 9, 0, 0, 0, 0, 4, 0, 0]]


# 実行用関数
def run_sudoku(func, t):
    print("処理時間 : " + measure_time(func, t))
    # 完成後の数独の表示
    display_table(t)
    # check_table()関数で完成後の数独が適切な状態かチェック
    w = "この解答は正しいです。" if check_table(t) else "この解答は正しくありません"
    print(w)


# 実行
run_sudoku(do, TABLE3)
run_sudoku(do_v2, TABLE3)

do()実行結果

処理時間 : 1.7117662 s
[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]
この解答は正しいです。

do_v2()実行結果

処理時間 : 191.3825 ms
[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]
この解答は正しいです。

8倍くらいでしょうか

結果

今回の改良によって、必ずしも早くなるわけではありませんが、数独の空欄が多く難易度が高ければ高いほど、効率化したこちらのほうが処理速度は早くなりそうです。

次回、気が向けばまた更なる効率化を試してみるかもしれません。

追記

コメント欄でわざわざsortせずminでよくね？とご指摘があったため確かにそうだと思い新たに関数追加

# 他共通関数省略


# 空欄に入りうる数字が少ないものを、数字の集合とともに返す関数
def min_blank_cell(t):
    if not find_all_blank(t):
        return -1, -1
    # 空欄に入る数字の候補リストと、空欄の座標リスト
    n_list = []
    blank_cell_list = []
    # 2つのリストに値を追加
    for blank_cell in find_all_blank(t):
        blank_cell_list.append((blank_cell[0], blank_cell[1]))
        n_list.append(check_cell(t, blank_cell[0], blank_cell[1]))
    indices = [*range(len(n_list))]
    # 集合の要素数が一番少ない要素番号を取得
    min_indice = min(indices, key=lambda i: len(n_list[i]))
    # 上で取得した要素番号をもとに、紐付く空欄座標と数字の集合を返す
    return blank_cell_list[min_indice], n_list[min_indice]


# 数独を解く関数、候補が少ないマス目から候補を一つずつ格納
def do_v3(t):
    blank_cell, n_list = min_blank_cell(t)
    # blank_cellに-1が格納されていれば、数独完成済み
    if blank_cell == -1:
        return True
    r = blank_cell[0]
    c = blank_cell[1]
    # numを格納
    for num in n_list:
        t[r][c] = num
        # do_v3()関数自身を呼び出し
        if do_v3(t):
            return True
        t[r][c] = 0
    # 一つも条件を満たさなければ戻るためFalseを返す
    return False


print(measure_time(do_v3, TABLE1))  # 2.641 ms
print(measure_time(do_v3, TABLE2))  # 21.2106 ms

なんで遅くなるんだ...？