分享一个用Python写的数独自动计算代码

看到首页上分享了数独游戏,我之前学习Python的时候抄了一个自动计算的代码,Pycharm正常运行。

运行后数独81个数字从左上至右下依次输入,需要填的空位输入0.

例:
输入INPUT:010000260000400001003102840740003008000009630000000000009050700064320019500000080

即代表以下数独题目
0 1 0 0 0 0 2 6 0 
0 0 0 4 0 0 0 0 1 
0 0 3 1 0 2 8 4 0 
7 4 0 0 0 3 0 0 8 
0 0 0 0 0 9 6 3 0 
0 0 0 0 0 0 0 0 0 
0 0 9 0 5 0 7 0 0 
0 6 4 3 2 0 0 1 9 
5 0 0 0 0 0 0 8 0 

计算后得到以下答案
4 1 5 9 3 8 2 6 7
6 8 2 4 7 5 3 9 1 
9 7 3 1 6 2 8 4 5 
7 4 6 2 1 3 9 5 8 
2 5 1 7 8 9 6 3 4 
3 9 8 5 4 6 1 7 2 
1 3 9 8 5 4 7 2 6 
8 6 4 3 2 7 5 1 9 
5 2 7 6 9 1 4 8 3 

计算用时
use Time: 0.123000 s

此代码在前人车轮上编写。

欢迎交流探讨。

import time

class point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.available = []
        self.value = 0


def rowNum(p, sudoku):
    row = set(sudoku[p.y * 9:(p.y + 1) * 9])
    row.remove(0)
    return row  # set type


def colNum(p, sudoku):
    col = []
    length = len(sudoku)
    for i in range(p.x, length, 9):
        col.append(sudoku[i])
    col = set(col)
    col.remove(0)
    return col  # set type


def blockNum(p, sudoku):
    block_x = p.x // 3
    block_y = p.y // 3
    block = []
    start = block_y * 3 * 9 + block_x * 3
    for i in range(start, start + 3):
        block.append(sudoku[i])
    for i in range(start + 9, start + 9 + 3):
        block.append(sudoku[i])
    for i in range(start + 9 + 9, start + 9 + 9 + 3):
        block.append(sudoku[i])
    block = set(block)
    block.remove(0)
    return block  # set type


def initPoint(sudoku):
    pointList = []
    length = len(sudoku)
    for i in range(length):
        if sudoku[i] == 0:
            p = point(i % 9, i // 9)
            for j in range(1, 10):
                if j not in rowNum(p, sudoku) and j not in colNum(p, sudoku) and j not in blockNum(p, sudoku):
                    p.available.append(j)
            pointList.append(p)
    return pointList


def tryInsert(p, sudoku):
    availNum = p.available
    for v in availNum:
        p.value = v
        if check(p, sudoku):
            sudoku[p.y * 9 + p.x] = p.value
            if len(pointList) <= 0:
                t1 = time.time()
                useTime = t1 - t0
                showSudoku(sudoku)
                print('\nuse Time: %f s' % (useTime))
                exit()
            p2 = pointList.pop()
            tryInsert(p2, sudoku)
            sudoku[p2.y * 9 + p2.x] = 0
            sudoku[p.y * 9 + p.x] = 0
            p2.value = 0
            pointList.append(p2)
        else:
            pass


def check(p, sudoku):
    if p.value == 0:
        print('not assign value to point p!!')
        return False
    if p.value not in rowNum(p, sudoku) and p.value not in colNum(p, sudoku) and p.value not in blockNum(p, sudoku):
        return True
    else:
        return False


def showSudoku(sudoku):
    for j in range(9):
        for i in range(9):
            print('%d ' % (sudoku[j * 9 + i]), end='')
        print('')


if __name__ == '__main__':
    da = input('INPUT:')
    print(da)
    t0 = time.time()
    ss = list(da)
    sudoku = []
    for x in range(81):
        num = int(ss[x])
        sudoku.append(num)
    pointList = initPoint(sudoku)
    showSudoku(sudoku)
    print('\n')
    p = pointList.pop()
    tryInsert(p, sudoku)

之前试过直接识别截图来得到答案,但是数字识别对比没搞定,后来也就没研究了。

OCR识别有开源的包可以试试

卧槽这都可以自动计算了,还要 :brain:干什么!

1 个赞

数独本来可以让程序自动求解啊,也算是经典的练手小题目了