暴力解算数独

sudoku.py

import time

import numpy as np


def get_ok(d):
    return np.setdiff1d(np.array([1, 2, 3, 4, 5, 6, 7, 8, 9]), d)


def get_ok_col(data, col):
    return get_ok(data[:, col])


def get_ok_row(data, row):
    return get_ok(data[row])


def get_ok_block(data, row, col):
    br = int(row / 3) * 3
    bc = int(col / 3) * 3
    return get_ok(data[br:br + 3, bc:bc + 3])


def get_ok_values(data, row, col):
    if data[row, col] != 0:
        return np.array([data[row, col]])
    else:
        ok_row = get_ok_row(data, row)
        ok_col = get_ok_col(data, col)
        ok_block = get_ok_block(data, row, col)
        return np.intersect1d(np.intersect1d(ok_row, ok_col), ok_block)


def get_all_ok_values(data):
    ret = list()
    for r in range(0, 9):
        ret.append(list())
        for c in range(0, 9):
            ret[r].append(list())
            ret[r][c] = get_ok_values(data, r, c)
    return ret


def is_finish(data):
    for r in range(0, 9):
        if get_ok_row(data, r).size != 0:
            return False
    for c in range(0, 9):
        if get_ok_col(data, c).size != 0:
            return False
    for r in range(0, 3):
        for c in range(0, 3):
            if get_ok_block(data, r * 3, c * 3).size != 0:
                return False
    return True


def guess_value(data, index):
    if index >= 81:
        if is_finish(data):
            return data
        else:
            return None

    r = int(index / 9)
    c = index % 9
    vs = get_ok_values(data, r, c)
    next_data = data.copy()
    for v in vs:
        next_data[r, c] = v
        ret = guess_value(next_data, index + 1)
        if ret is None:
            continue
        else:
            return ret


if __name__ == "__main__":
    data = np.array([
        [0, 0, 0, 2, 5, 0, 0, 0, 1],
        [0, 0, 0, 0, 0, 0, 3, 0, 7],
        [0, 1, 5, 0, 0, 0, 0, 0, 0],
        [6, 0, 0, 9, 0, 1, 0, 7, 0],
        [0, 2, 0, 0, 0, 6, 0, 0, 0],
        [0, 0, 4, 0, 0, 7, 8, 1, 0],
        [0, 0, 7, 0, 0, 0, 0, 0, 8],
        [0, 0, 0, 0, 0, 0, 4, 9, 0],
        [9, 0, 0, 0, 6, 8, 0, 0, 0]
    ])

    # data = np.array([
    #     [0, 7, 0, 2, 5, 0, 0, 0, 1],
    #     [0, 0, 0, 0, 1, 0, 3, 5, 7],
    #     [0, 1, 5, 0, 0, 0, 0, 0, 0],
    #     [6, 0, 0, 9, 0, 1, 0, 7, 0],
    #     [7, 2, 0, 0, 0, 6, 0, 0, 0],
    #     [0, 9, 4, 0, 2, 7, 8, 1, 6],
    #     [0, 0, 7, 0, 0, 0, 1, 6, 8],
    #     [1, 0, 0, 0, 0, 0, 4, 9, 0],
    #     [9, 4, 0, 1, 6, 8, 7, 0, 5]
    # ])

    print(data)
    print("======================")
    start_t = time.time()
    print(guess_value(data, 0))
    print("process time: {:.4f} s".format(time.time() - start_t))