python数独问题解决

sudoku包:

'''


数独表示:
*     |0 1 2 |3 4 5 |6 7 8 -col
--------------------------
0| 9  |      |      |  
1| 10 |  18  |  21  |  24  
2| 11 |      |      |  
--------------------------
3| 12 |      |      |  
4| 13 |  19  |  22  |  25  
5| 14 |      |      |  
----------------------------
6| 15 |      |      |  
7| 16 |  20  |  23  |  26  
8| 17 |      |      |  
============================
 | 安全标识存储位置
row

a[row][col]



'''  
import time  
from collections import namedtuple


# 安全标识
# 1 -9  记录col信息
# 10-18 记录row信息
# 18-26 记录九宫格
safe = {0:[],1:[],2:[],3:[],4:[],5:[],6:[],7:[],8:[], \  
        9: [],10:[],11:[],12:[],13:[],14:[],15:[],16:[],17:[],\
        18:[],19:[],20:[],21:[],22:[],23:[],24:[],25:[],26:[]}

can_do = {}  
for i in range(9):  
    for j in range(9):
        can_do[(i,j)] = {1,2,3,4,5,6,7,8,9}

#print(can_do)


# 要检查哪些地方从这里查找就好
#  (i,j) -> 0-26
check_list = {}  
for i in range(9):  
    for j in range(9):
        check_list[(i,j)] = [i,j+9,18+i//3+3*(j//3)]
# print(check_list)

# 0-26 -> (i,j)
be_check_list = {}  
for i in range(27):  
    be_check_list[i] = set()

for i in check_list:  
    for j in check_list[i]:
        be_check_list[j].add(i)

#print(be_check_list)



# 测试用数据
Sudoku_test = [[0, 0, 4, 0, 0, 7, 0, 0, 0], [5, 0, 0, 0, 0, 0, 0, 0, 0], [0, 6, 0, 0, 0, 0, 0, 3, 0], \  
         [0, 0, 0, 0, 0, 8, 0, 0, 9], [0, 5, 0, 0, 0, 4, 0, 0, 0], [3, 1, 0, 0, 0, 0, 0, 2, 0], \
         [2, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 8, 0, 0, 0, 0, 0, 4], [0, 0, 0, 3, 0, 0, 0, 0, 0]]

# Sudoku_test = [[0 for i in range(9)]for i in range(9)]


# copy函数提供安全可靠的字典拷贝copy
def copy(dict):  
    result = {}
    for i in dict:
        result[i] = dict[i].copy()
    return result

def listcopy(list):  
    result = []
    for i in list:
        result.append(i.copy())
    return result



class SudokuObj():  
    def __init__(self,pos,val):
        self.col = pos[1]
        self.row = pos[0]
        self.val = val


class Sudoku():  
    '''数独类,提供判断安全,悔棋方法'''
    def __init__(self,list):
        # 记录数独的内容
        self.sudoku = listcopy(list)
        # 安全标识
        self.safe = copy(safe)
        self.can_do = copy(can_do)
        # 存储填入数字个数
        self.sum = 0
        self.num = [0 for i in range(10)]
        # 更新安全标识
        for row in range(9):
            for col in range(9):
                if self.sudoku[row][col] != 0:
                    self.can_do[(row,col)] = set()
                    for needcheck in check_list[(row,col)]:
                        if self.sudoku[row][col] not in self.safe[needcheck]:
                            self.safe[needcheck].append(self.sudoku[row][col])
                    for i in check_list[(row,col)]:
                        for pos in be_check_list[i]:
                            self.can_do[pos].discard(self.sudoku[row][col])
                    self.sum += 1
                    self.num[self.sudoku[row][col]] += 1
        # print(self.safe)
        # print(self.can_do)
        #self.avl = {i for i in self.can_do if len(self.can_do[i])!=0}
        # 构造栈来存储填入的数字以及safe的状态
        self.regret = []
        self.safe_regret = []
        self.can_do_regret = []


    def updatesafe(self,sudokuobj):
        '''填入sudokuobj后更新safe'''
        for needcheck in check_list[(sudokuobj.row,sudokuobj.col)]:
            if self.sudoku[sudokuobj.row][sudokuobj.col] not in self.safe[needcheck]:
                self.safe[needcheck].append(sudokuobj.val)
        return True

    def update_can_do(self,sudokuobj):
        '''填入sudokuobj后更新can_do'''
        for i in check_list[(sudokuobj.row,sudokuobj.col)]:
            for pos in be_check_list[i]:
                self.can_do[pos].discard(sudokuobj.val)
        return True

    def issafe(self,sudokuobj):
        '''sudokuobj能否填入'''
        for needcheck in check_list[(sudokuobj.row,sudokuobj.col)]:
            if sudokuobj.val in self.safe[needcheck]:
                return False
        return True

    def register(self,sudokuobj):
        '''填数,可以填,填入return True,不然不变return False'''
        '''
        if self.issafe(sudokuobj):
            self.regret.append(sudokuobj)
            self.safe_regret.append(copy(self.safe))
            self.can_do_regret.append(copy(self.can_do))
            self.sudoku[sudokuobj.row][sudokuobj.col] = sudokuobj.val
            self.updatesafe(sudokuobj)
            self.update_can_do(sudokuobj)
            self.sum += 1
            self.num[sudokuobj.val] += 1
            return True
        return False
        '''
        self.regret.append(sudokuobj)
        #self.safe_regret.append(copy(self.safe))
        self.can_do_regret.append(copy(self.can_do))
        self.sudoku[sudokuobj.row][sudokuobj.col] = sudokuobj.val
        #self.updatesafe(sudokuobj)
        self.update_can_do(sudokuobj)
        self.sum += 1
        self.num[sudokuobj.val] += 1
        #self.avl.discard((sudokuobj.row,sudokuobj.col))
        return True

    def reg(self):
        '''悔棋方法'''
        sudokuobj = self.regret.pop()
        #self.safe = self.safe_regret.pop()
        self.can_do = self.can_do_regret.pop()
        self.sudoku[sudokuobj.row][sudokuobj.col] = 0
        self.sum -= 1
        self.num[sudokuobj.val] -= 1
        #self.avl.add((sudokuobj.row,sudokuobj.col))
        return True

    def isfull(self):
        '''判断是否已经填满'''
        return self.sum == 81



    def __str__(self):
        s = "="*40+"\n"
        for i in range(9):
            s += "|"
            for j in range(9):
                s += "| %s "%(str(self.sudoku[j][i]) if self.sudoku[j][i] != 0 else " ")
                if j%3 == 2:
                    s += "|"
            s += "|\n"
            if i%3 == 2:
                s += "=" * 40 + "\n"
            else:
                s += "-" * 40 + "\n"
        return s







need_to_test = []  
for i in range(9):  
    for j in range(9):
        need_to_test.append((i,j))

time_start = 0

def playSudoku_hard(sudoku,state=True):

    # global times
    if __name__ != "__main__":
        global time_start
        if state:
            time_start = time.time()


        if time.time() - time_start > 100:
            return False


    # 如果棋盘已经填满了就直接print出来并且return True
    if sudoku.isfull():
        if __name__ == "__main__":
            print(sudoku)
        return True

    # if max([sudoku.num[i] for i in range(5,10)]) > 8:
    if False:
        value = max(range(5,10),key=lambda x :sudoku.num[x])
        for position in [i  for i in need_to_test if value in sudoku.can_do[i]]:
            sudoku.register(SudokuObj(position,value))
            if playSudoku_hard(sudoku):
                return True
            sudoku.reg()
        return False
    else:
    # 从可能性少的格子开始搜索
        # for position in sorted(need_to_test,key = lambda x:len(sudoku.can_do[x])) if sudoku.sum >= 40 else need_to_test:
        for position in [max([i for i in need_to_test if sudoku.sudoku[i[0]][i[1]] == 0],key=lambda x:-len(sudoku.can_do[x]))] if sudoku.sum <= 70 else need_to_test:
        # for position in sorted(need_to_test, key=lambda x: len(sudoku.can_do[x])):
        # for position in [max(sudoku.avl,key=lambda x:-len(sudoku.can_do[x]))]:
        # for position in need_to_test:
            # print(position)
            # 在所有非零的位置填数
            if sudoku.sudoku[position[0]][position[1]] == 0:
                # flag用来记录是否可以有可以填的值,如果没有就为True
                # for value in sorted(range(1,10),key=lambda x : -sudoku.num[x]) if sudoku.sum <= 40 else range(1,10):
                for value in range(1,10):
                    if value not in sudoku.can_do[position]:
                        continue
                # 如果可以填入,填入并且递归计算,计算完后擦去所用的数字
                    if sudoku.register(SudokuObj(position,value)):
                        # if times >= 30:
                            # return True
                        # print(sudoku)
                        # times += 1
                        if playSudoku_hard(sudoku,False):
                            return True
                        sudoku.reg()
                # 没有可以填的值就return False,意味着无解
                return False
    return True

def playSudoku_easy(sudoku,search = 0,state = True):

    # global times
    if __name__ != "__main__":
        global time_start
        if state:
            time_start = time.time()

        if time.time() - time_start > 100:
            return False


    # 如果棋盘已经填满了就直接print出来并且return True
    if sudoku.isfull():
        if __name__ == "__main__":
            print(sudoku)
        return True

    # 从可能性少的格子开始搜索
    for position in need_to_test[search:]:
        # print(position)
        # 在所有非零的位置填数
        if sudoku.sudoku[position[0]][position[1]] == 0:
            # flag用来记录是否可以有可以填的值,如果没有就为True
            for value in range(1,10):
                if value not in sudoku.can_do[position]:
                    continue
                # 如果可以填入,填入并且递归计算,计算完后擦去所用的数字
                if sudoku.register(SudokuObj(position,value)):
                    #print(sudoku)
                    if playSudoku_easy(sudoku,search + 1,False):
                        return True
                    sudoku.reg()
            # 没有可以填的值就return False,意味着无解
            return False
    return True


def sudokutest(test,testmethod = playSudoku_hard):  
    index = 0
    Sudoku_test = [[0 for i in range(9)] for i in range(9)]
    for i in range(9):
        for j in range(9):
            Sudoku_test[i][j] = int(test[index])
            index += 1
    Sudoku_use = Sudoku(Sudoku_test)
    if __name__ == "__main__":
        print("原来问题:\n",Sudoku_use,"解答:")
    t = time.time()
    b_avail = testmethod(Sudoku_use)
    time_use = time.time()-t
    if __name__ == "__main__":
        print("no answer"if not b_avail else"")
        print("用时:%.10f"%(time_use))
    return time_use

if __name__ == "__main__":  
    time_use = 0

    # 简单级别

    ##time_use += sudokutest("037090010600050000020000609302009865708020401061048007406035008579001324283974150")
    ##time_use += sudokutest("000045076000007030504000980010206349000090007945013628483679001107532860250184000")
    ##time_use += sudokutest("400060003000007001080020000709040520000000360300058197128504906547693812930182070")
    ##time_use += sudokutest("050000060000023000004008000190070003028035006700689142561802374200341608040750901")
    ##time_use += sudokutest("000800007000006000105000000001260094402397158078050003010085079749612305086039402")
    ##time_use += sudokutest("000000000000000000000000000000000000000000000000000000000000000000000000000000000")


    #困难级别

    ##time_use += sudokutest("800109076070000085000070000180900040003080709020510008016000004000700000049021800")
    ##time_use += sudokutest("005300000000000800000000007000089000003000050000060090000900041780002000600000000")
    ##time_use += sudokutest("006000000108000070000504000000000000000080060024009003050000209000000400007010000")
    ##time_use += sudokutest("001020070245000900003000006072601000000000000000209051090000020004070890300000645")
    ##time_use += sudokutest("000085003106000000002009007200300085801000000000004009004000000000020531000070000")


    ##time_use += sudokutest("300600008120000000000000000000007200009000400006300000908000006000012000000004000")
    ##time_use += sudokutest("000000030107064000000900010030005002002000009005200700600001000900000000000870045")
    ##time_use += sudokutest("305060000060000000200007041000300000400001020000070000000400810000000003790008060")
    ##time_use += sudokutest("980000500003170090005002004000620300050301000070000100007204050600080020020000403")
    ##time_use += sudokutest("051042000306700000800003100002309600000060400008020000000005310000180704007900020")



    ##time_use += sudokutest("200050800001000030000070000000003000000901006080000700870000000050000000000006010")
    ##time_use += sudokutest("300600008120000000000000000000007200009000400006300000908000006000012000000004000")
    ##time_use += sudokutest("000080040000000000093000600820000000000903005000600000700010000400000023000000900")
    ##time_use += sudokutest("960000000000020000000038005700600000008000003000050000000400760003000100000000040")
    ##time_use += sudokutest("000062000700000480000100000002070000000000500000301900000000006500400000000080020")

    ##sudokutest("200050800001000030000070000000003000000901006080000700870000000050000000000006010")

    ##print("用时:%.10f"%(time_use/5))


    # sudokutest("12034567890000000000000000000000000000000000000000000000000000000000000000000000000000000")

    ## playSudoku(Sudoku(Sudoku_test))

    ##sudokutest("360500024100600003000430000000000316003000500759000000000074000900006005240005098")
    ##sudokutest("000000000000000000000000000000000000000000000000000000000000000000000000000000000")
    ##sudokutest("800000000003600000070090200050007000000045700000100030001000068008500010090000400")
    ##sudokutest("142000387003040201080132005090000106000520704000004000608200009020000000001070000")
    ##sudokutest("041020000000000007080005200610080000000010460000490050006000000437009106102000090")
    ##sudokutest("003279000020501009000080003000060500690003000005000000000000064700600080060920007")
    ##sudokutest("000000097000000000000010003000000000001800270000000000000030000600000000090040000")
    ##sudokutest("000000007000004001000000500006003050080000000300050000900076000008000030005000070")

    ##sudokutest("500000000020010080000000000000000000003001000102000000700000000200300064001000920")

    #easy method is quicker than hard method
    sudokutest("001003000300000480000090000000000000100080000000000000000000047400600000600407009",playSudoku_easy)

generate包:

from random import choice  
import random

class Generate():  
    """
    Generate Sudoku written by Kurt Wang
    """

    def __init__(self,NORMS = 9,CELL = 3,EMPTY = 0):
        self.sudoku_copy = [[EMPTY for x in range(NORMS)] for y in range(NORMS)]
        self.NORMS = NORMS
        self.CELL = CELL
        self.EMPTY = EMPTY

    def printSudoku(self, sudoku):
        """
        print Sudoku as human readable
        """

        text = ''
        for row in range(self.NORMS):
            for col in range(self.NORMS):
                text = text + str(sudoku[row][col]) + ' '
                if (col + 1) % self.NORMS == 0:
                    text = text + '\n'
        #print(text)

    def generateGame(self, removeCount):
        """
        generate a Sudoku game
        """

        sudoku = self.generateSudoku()
        for i in range(removeCount):
            row = random.randint(0, self.NORMS - 1)
            col = random.randint(0, self.NORMS - 1)
            sudoku[row][col] = self.EMPTY

        self.printSudoku(sudoku)
        return sudoku

    def generateSudoku(self):
        """
        geneate Sudoku
        """

        # create empty Sudoku
        sudoku = [[self.EMPTY for x in range(self.NORMS)] for y in range(self.NORMS)]

        # save current un-modify status
        self.copySudoku(sudoku, self.sudoku_copy)

        while(not self.generate(sudoku)):
            pass

        self.printSudoku(sudoku)
        return sudoku

    def generate(self, sudoku):
        """
        genearte Sudoku, if there is no suitable constraints, return False
        """

        # reset sudoku to un-modify
        sudoku = self.copySudoku(self.sudoku_copy, sudoku)

        for row in range(self.NORMS):
            for col in range(self.NORMS):
                # get constraints for point sudoku[row][col]
                constraints =  self.getConstraints(sudoku, row, col)
                if len(constraints) == 0:
                    # nothing to select, return False
                    return False

                # random select one from constraints
                sudoku[row][col] = int(choice(constraints))
        return True

    def copySudoku(self, source, dist):
        """
        create a deep copy of sudoku
        """

        for row in range(self.NORMS):
            for col in range(self.NORMS):
                dist[row][col] = source[row][col]
        return dist

    def getConstraints(self, sudoku, row, col):
        """
        return constraints for given row, col
        """

        constraints = set([1, 2, 3, 4, 5, 6, 7, 8, 9])

        # remove row
        constraints = self.removeRowConflict(sudoku, constraints, row)

        # remove col
        constraints = self.removeColConflict(sudoku, constraints, col)

        # remove 3x3 cell
        constraints = self.removeCellConflict(sudoku, constraints, row, col)

        return list(constraints)

    def removeRowConflict(self, sudoku, constraints, row):
        """
        remove confilct in row
        """

        return constraints - set(sudoku[row])

    def removeColConflict(self, sudoku, constraints, col):
        """
        remove confilct in col
        """

        colList = []
        for i in range(self.NORMS):
            for j in range(self.NORMS):
                if j == col:
                    colList.append(sudoku[i][j])

        return constraints - set(colList)

    def removeCellConflict(self, sudoku, constraints, row, col):
        """
        remove confilct in cell
        """

        cellList = []

        # cell start index
        rowCell = row // self.CELL * self.CELL
        colCell = col // self.CELL * self.CELL

        for i in range(rowCell, rowCell + self.CELL):
            for j in range(colCell, colCell + self.CELL):
                cellList.append(sudoku[i][j])

        return constraints - set(cellList)

if __name__ == "__main__":

    generate = Generate()
    print(generate.generateGame(80))

test.py

import sudoku  
from generate import *  
from time import time

time_max = -float("inf")  
timelist = []

for i in range(10000):  
    generate = Generate()
    game = generate.generateGame(120)
    t = time()
    sudoku.playSudoku_hard(sudoku.Sudoku(game))
    timeuse = time() - t
    print("做完%d题了"%(i+1))
    timelist.append(timeuse)
    if timeuse > time_max:
        time_max = timeuse
        game_hardest = game


print("最长用时间",time_max)  
print("最难游戏:\n",sudoku.Sudoku(game))  
print("平均用时间:",sum(timelist)/10000)

finddifficultproblem.py

import sudoku  
from generate import *  
from time import time  
from functools import reduce

def add(x, y):  
    return x + y

turn = lambda lst:reduce(add,list(map(str,lst)))  
turn_sdk = lambda lst :reduce(add,list(map(turn,lst)))

play_times = 1  
difficult_times = 0  
need_to_write = ""

try:  
    while True:
        if play_times%20 == 0:
            print("||第%d次测试,难题数目%d||" % (play_times,difficult_times))
        generate = Generate()
        game = generate.generateGame(120)
        t = time()
        sudoku.playSudoku_hard(sudoku.Sudoku(game))
        timeuse = time() - t
        if timeuse > 1:
            difficult_times += 1
            print("遇到难题%d..."%(difficult_times))
            need_to_write += turn_sdk(game) + "\nuse time:%.2f\n" % (timeuse)
        play_times += 1
except KeyboardInterrupt:  
    print("%d次测试%d次难题"%(play_times,difficult_times))
    print("正在计算\n",sudoku.Sudoku(game))
    print(turn_sdk(game))
    need_to_write += turn_sdk(game) + "\nthe last"
    with open('difficult_sudoku.txt', 'w') as f:
        f.write(need_to_write)
    print("输入结束")

找到的测试数据点:

ps.由于是开了多个pycharm进行所以速度比正常用idle慢了不少,所以挑选里面运行时间长的来测试吧

309 difficult problems in 25492tests  
400000000050400109009000020010500400000002010907010002000000000000700000001000000  
use time:2.73  
070001000000080000008600070400000005007000020000000090000004000060000904740120000  
use time:37.33  
000000000007000004000081700000004070400000900060090000000070000070009000040005000  
use time:67.16  
000007002708000030040320000000500000000700000200000800034050009107000200002070010  
use time:2.03  
070000000002000000400000300056090000200000800004000000900000065500000200020064008  
use time:4.82  
800000000005002007000000093100000300000000750000000900000000009500000000000000001  
use time:100.00  
903000700000000100400007000002000305000000000109000000000400910300000050001000000  
use time:100.00  
000709500521000006003000000008003000030001000000000000000100000200300080300590000  
use time:29.09  
001003000300000480000090000000000000100080000000000000000000047400600000600407009  
use time:100.00  
600097400000320000070000000000600000300970000500103000001000000809000204000200509  
use time:1.24  
000600000504000002069070000100000050040800320030000000600000000000105000000700006  
use time:2.69  
004006000900000000008000000000670300000000000300000097009750630503000800000003000  
use time:24.82  
900020030000700000054000800000070080000000100000010000000007050000002040000000000  
use time:6.58  
000000000000140000000000000020000368060900000003000009000005000000000005001000000  
use time:3.11  
000000600009020000000501200000080001000600000090000060000005002020070080607000300  
use time:18.19  
004002000000015000000400070200000007009003000000060200000000000700000100000070080  
use time:1.78  
000000008008000560000900010000790001000008000000004000400000000070000400800607020  
use time:11.85  
000000000008000000000600300024500009090720000000090000009001007000002000601070000  
use time:1.01  
000000200030200000060400000683020050091000600002960000004000060010602000020000008  
use time:2.04  
000000000000000650001002000050004000000000000040000090010200000060103907000060000  
use time:18.34  
006001500080000000000000000000000200230080000000003006060050300000000900000800000  
use time:4.81  
300000000000000000100000020200300080000040100000006003020180000000003000480690300  
use time:1.09  
060000000000000030042560070600000050000600000200000060000000603030001020001000000  
use time:100.00  
000003000000009000000050324083907000000000000090060007000000080602500000030040001  
use time:1.06  
070000000509047000006000000100000036700000002008000700480000020000080000001000080  
use time:1.21  
000300010000000000079050000000004950020005000800290000050608000000000005400500000  
use time:1.26  
008000001000007004000004000000093000000000810010000000800040000001000450500600300  
use time:1.11  
004000000000040000003600200000000009407500600000300000000000504030070000000030000  
use time:26.06  
006040005010000000547000090000800500000000030800000000930000000004000000000000800  
use time:4.07  
500007061000000709000001080400000000000000150003000900010000600000004000000010000  
use time:6.44  
000007000000048000670050000500009000300000000000020000000000300002090000000000021  
use time:22.95  
000000002001000000708000000100006000000070000076105080020400000010000050000750000  
use time:21.74  
105000008000000000000000003700000000500000000300000702000920000007000020200000007  
use time:17.64  
005000600780000000000000000050001000000000004000000500500100020210400000007000050  
use time:1.16  
000408297000920000000000050000080000000000000305000980000206010060000070100050800  
use time:2.01  
300000000005000908100000000000300000600410000000000100000000010009024000001000000  
use time:100.00  
010300000000000000006000200000060800060000000000000900007000400004100000000603000  
use time:100.00  
000046300020000000600000000000000080008020000002000400060004239004000000000000600  
use time:8.04  
000790050000000000001008003000801000000000418018000700040000080000010506700000000  
use time:3.68  
050000000000000000004000590000003000900400000000000004709000800008007060500004000  
use time:1.36  
600070090000002000900000030012000000090000006000000003004000000000420917109080000  
use time:10.46  
003000812080000090000008000000000000000007500430000000000500000041000070070900000  
use time:52.68  
000001000700000096100000000000050000000068003003000060004500000000409005000003000  
use time:13.18  
000000000000001500000070008409005000030400001000000040000090000950002004004000000  
use time:100.00  
082000000001040030306007000000600710035000000000080000000030000400970000000000507  
use time:8.94  
200030040010900000000700500000000059600403000000006300000000900040000000900000000  
use time:1.09  
005000000001000000000009100000001000706534000000800640040100530600002091000300000  
use time:2.44  
000000000000000000020030000007000934039100006200000080002000000000602050000000408  
use time:100.00  
000500100064008305000000800000050200000004010001007900000000000000100009000002051  
use time:2.94  
000001200026300009000000000200000900050100800403000000700000503008000400000080000  
use time:2.13  
000100060000000000600000200000000030012000000003040100000030002000000000000796000  
use time:100.00  
000040050000000807007080100000001200162438000000060000000805400000300600000090000  
use time:6.16  
900000000000000000000001800000005000030800000000003000390520000600009200720000001  
use time:1.26  
071000000000000102240080000600090000004000003002004008180200000060008001300000000  
use time:7.68  
000060030003000000002007000000100000800000000100008000706000500000010200000000010  
use time:9.55  
000035000000090000000000000050000079000000000471009000500000010006900000300000000  
use time:2.93  
050000000670900400000000070080300000000060147000000530000000000700050004001000000  
use time:10.48  
903000002000003000000080003000007350500800720700500900000079030000008007400060000  
use time:2.70  
000200045040000030000006000600000058020005000000800000000052896000007520050060000  
use time:8.66  
000000903000008000000007000910000000500000002000000010000030859800000000050006000  
use time:1.41  
580009300000000000000007000015072003000300400003000100000013000040520010000000000  
use time:1.06  
500967000000400000640000000400009070000000090000580000100000000700000001000003000  
use time:97.22  
000000080007042000000503200400005000000400000000010000000000800080000400000024950  
use time:45.37  
008004600100030000000005140000000000080020700000000000060002005041000070000051064  
use time:6.52  
200000000000002000050069400000000004000400200007000000040100600000900040000000700  
use time:1.15  
700000000000003069000004000070030000046000000080000100600300050000040200001000040  
use time:9.44  
000900853020008900000000001000230005090800300050000000040009000000003000200000000  
use time:2.99  
000000000300001004807900035000000058500000000000208000084100000000020900000070000  
use time:9.71  
000000600000025000510000200000009000090800060007000009000300024000000030470000000  
use time:4.63  
000000000658021009040700000200000000000403021004000000010008000000500000020670000  
use time:1.98  
000000000000005042020000090000900000090000030800050009000009000500700000000506070  
use time:2.42  
002016000000093000000000600000000090000002000670000000000100200000050000980000040  
use time:2.77  
000090000000007600600000370000000000010004000000000000000140002700000004102008900  
use time:1.11  
800910260002000000007000040030000400000002000080000020003000002000270500500100030  
use time:19.03  
006900000103070000000000008000000906080000000950032004000000000000080000009400100  
use time:9.09  
020010983080000200000000000002003000000000800800070004760200000000000500004050000  
use time:100.00  
000080000043009000060030900000600084004000000030000000000800000306100700100000000  
use time:1.77  
000259000000640000025007006000900004000020000000000009000000070104006000000400900  
use time:20.41  
000002080100000029020000000030060000800900000200000090300500000700006000000000000  
use time:43.31  
019400000000060010024007305000790001900000000040030050070000900090000000000300100  
use time:5.05  
006000000028160000000003008900050000003040000000000000042000000007930000010000000  
use time:3.29  
002439000000002004000000000020040600003000490000600507001090078300020040090000000  
use time:1.26  
005090000300000000007020100000000000010003007070840000700405000000000001000000300  
use time:25.99  
900000000060000000050000900000000000000900000070000090009000050045000003021500080  
use time:100.00  
000000000000938000003002000030800000600000000400000600000000050005000100009004380  
use time:4.28  
000403000009008040000000070500000907000000000000000080000000004000820090003000852  
use time:100.00  
000600004800000070200080100000300010600000000000100490000000000000020600700004000  
use time:6.29  
000040008318005000000000009001700000040100060000002005030500600000300001000000000  
use time:1.88  
000700051100008300350016000000005000001240000004800000900000000010000040060004290  
use time:1.10  
090260000000901000000000006000000000800002000000800400000008560001040392005000700  
use time:1.61  
090070000001000009000008100000000060030040800000006052000080600000000090080007040  
use time:14.15  
000060008308040000007001005000010004010090000200300000000002600000000201000000000  
use time:4.40  
080000000050000008600000007000009000068000100000800070005600000000000031009000050  
use time:12.54  
000040870004000000005000000000000060350070200000300000000000000030000000000954100  
use time:1.13  
000000000000001000000006000014000008000000040000802600108003004400000060000000530  
use time:6.42  
000040207000060000940000000006500700000090000080000000050000008020078000010009060  
use time:1.54  
300007000004060000050002004080070000000000000000800003020080300043200007000093080  
use time:1.44  
050010002000000104400073000000100400000000009000000060000286000105000008000030000  
use time:1.84  
000000201251000000000020008060300017007000000000000060090010000070000000000000002  
use time:8.74  
000610000000004005000000906900000360000000020200000090000000004005032080300080000  
use time:32.96  
000059020008003000900000000450000030000007000000000540700000000006000012000700000  
use time:5.93  
000790400000001002000000090102000009800050000500000200651900000020006000300000600  
use time:9.27  
000200000000009000509030004000000000050004600060070000080000040000940005000020000  
use time:6.33  
031000000000000008000008000306009020000000006500000000010002500000090000000005800  
use time:60.46  
000103000000904008800000010008500020000800007070602030000310000080000900050000200  
use time:1.24  
500000007000000960000009000000090000050004090207000180760000009000900000010042000  
use time:6.18  
805000001001000000000010000020000800000000200500000000050000172000000000000120600  
use time:3.36  
000030900000000007000005000000087000000020008702000000507000003000000000000060000  
use time:2439.39  
000000000000000190000600520600050009100000600000060000000000070006000000500006000  
use time:100.01  
700000000830000060400006000000800001185009000000001008003000000000000020008000090  
use time:1.32  
270000830000200000800300001000800190000000003700094080000000300500000400008000000  
use time:57.01  
000000004400700002007000050800000000000200000000000435000000000500000000001000328  
use time:17.92  
000700001500830400040005000020090006000000000000000000700008300090000000000062000  
use time:6.83  
000200000840000005000000000001400006060001000050600000070165000006000050008300620  
use time:2.33  
000000000000406018000078004006004000000002000000000040000000030600840000037000005  
use time:6.29  
008300700900000000000000060704020305000070820090000000000000000000000100007060040  
use time:1.36  
002000300800030400000200000000005090005900000600000002000000003000500000009006004  
use time:1.06  
000000091290060000000008300800000030300000608000500007000000000000000062006050000  
use time:5.86  
008000000902700001000000005000105600000006000003000010006080002005000006000500003  
use time:18936.64  
300000000700000500004000000003000000000080090090000280902000008400237900000040000  
use time:2.78  
000000000000000006308041000400006100003010400501000900040000000000400005000000090  
use time:4.08  
040007050000002400020050000080006100000004700004000060000700501000000900500020070  
use time:1.97  
001000009500000000000100002000060000000807003000010008000703016600000000000001400  
use time:17.52  
000001000000435000000000000070098000000050800090060000900000000008040000002010049  
use time:950.91  
040100003080030000900000000000003006090040000000580001370690000009000000000020900  
use time:5.96  
009000006000000308010000040007004010000000000000070080000208070000000004000100800  
use time:12.10  
030400000000800050000000000000904010000003800000000700000000000020000065060000000  
use time:100.00  
080000090300000000000030020000073000006040000000080004000000000740000000010027006  
use time:100.00  
000200000003000000062007008000000400010000090000030100006900080108423060000800000  
use time:2.11  
000900200000000000300000000800000000000000020205000000020600000070380010000000007  
use time:100.00  
000000000090040000001705600000970800008500060000006000000000008600000000000000400  
use time:6.53  
001700000097050000000001000000000003100624000509000000010060000900000030000000010  
use time:2.64  
000100000700800000000407005000010006800050000000006000006000002001600000000500001  
use time:1.27  
000085000310000057000000200680004000200000003000800001800009105400000000000020000  
use time:8.52  
500000070000005000030000900090048000210007000640302000400020300006500002000003007  
use time:1.10  
802006000000100000560800490900000540000400900004000300000000050100200000009000020  
use time:9.74  
000000000000090000000231649001000000000007000000100500000002960000008000008000005  
use time:6.77  
000100000073000006540900000000032005000000040000400630000006001010000060009081004  
use time:1.32  
700000080009000000000700000000000600000000500000057002000030007000040350000070000  
use time:2.68  
000500000901086000000000003007060000000032078803000000052000000000003000010000000  
use time:3.74  
000075600000000005300000070000006500403800700000000003008501060030000000000000000  
use time:51.07  
001000000060520800000006000020005080000000002000800300000104030000000100502090700  
use time:1.36  
000000000000002070900000801000000700080400000370006004003048007140073000000500000  
use time:1.15  
001020000000000000003100000000741600000002000507000940000000000050000030100300020  
use time:2.13  
060008000070050000009600000040000500000000200090000000050000000910000600000710400  
use time:10.58  
600400000030010700500003060000140000000380020100000000000030000056000003000000208  
use time:1.01  
000000006200060400806000000109630008007040000000000010500901007000000190000000600  
use time:2.03  
000205090000930000000000001079006000000000007000000600200050000000002000500007900  
use time:15.17  
000008600000700090040000000001005040020000000057030000000000030003000000080400107  
use time:4.11  
000800040001004000000000006087000030006005000410000702094000000000200000000000600  
use time:100.00  
800000009900600070600000000000000050000010000000006000098000000000004000000380600  
use time:100.00  
000000080000008000920000300000009020590000000000000000000010004130084000000000108  
use time:2.11  
200900300000000000000050000001483002000000800000709005005008210003000000008000006  
use time:3.33  
000000004000000000006450109000305900005000000700000000000830000050000760000500018  
use time:2.07  
050000000000000007070500000000056000080000000000070050190000700000409380002700060  
use time:1.10  
000000007000002631000007008000000020900005003230000004081000000072068000000000000  
use time:1.88  
037600000006030040000000006000000591900000000500000000000000000004009010000540000  
use time:7.43  
300000000070001000040200090700000500900002003000003000000020000032000000000050020  
use time:1.53  
900000008160000000005090010000607000000000090000000040050004000247060000000029000  
use time:3.27  
042000100000042700000000000000000008000018006700000000023001000570000020001700000  
use time:1.37  
000000600008004520500006000200001400000600002000000080903000000000060000006040000  
use time:53.54  
200000107060000230000000000000000000000902500000001000305009000000050600100000020  
use time:12.38  
000000000010000907090800000000500040100000090080000000200000004008000010071960000  
use time:56.73  
000000730000090060400807000000080000200000001641050000034000080000008000900100050  
use time:1.59  
000000629006000000000000000000000104001000000000140200460000000000060008000020000  
use time:1.64  
009302000000000609060000000000000008620109000050000090000080000000000000001000006  
use time:100.00  
800030097910000000000900010000009008070053009100000300000000000001000000000010000  
use time:3.45  
000000000000010000000004008600000009900062000300000200004800000057300002000070000  
use time:3.16  
002040700005200300000000000300060000000007000009000030750000004000600000090000075  
use time:4.50  
000000000000870002080000100000000000001530469000009237400050000000090700000000008  
use time:17.37  
000030470030020000009001000000050200290000050350000840000000000003008064000000000  
use time:1.41  
000070205000091000000400001250030000009500300000010500601080000000000600700150000  
use time:2.01  
000009000001000000960040000209000500000004806000000000090000064002000050000400300  
use time:1.84  
002000100000000000000000090003000000000190400001006000070000001018470000500080060  
use time:51.58  
000000600000800910000600004509000000000902000000000000000060090240000000070400000  
use time:1.19  
107000000500000000000000000000200010003000000406000702000005000000000291000420006  
use time:1.05  
000050000000040126000000500000000603080000000000000000040800000006001000001005864  
use time:3.48  
000000003000000000800000000000000300000270000780000020008000106000004000020901030  
use time:5.26  
090000008000006000000300620000000000000000000000200190000900000030005002900000080  
use time:96.90  
000040006007000000000000000009300000060400003004900000306700058000000000000000000  
use time:5.20  
600000000000010000002400600100050006000206000000100502006040020208000300005020000  
use time:1.70  
280709000000000000007006000050060400000900000000341000000000500001003000000000000  
use time:1.75  
090270000000901002000000001000005000020000030300000140000000000004000200530600900  
use time:1.75  
000000020000400500650000400000010300026300005000000040500000090000000000000927000  
use time:4.25  
000000009070000045000000000010084020005000000004603000003009100000000000000150300  
use time:2.49  
001000020000070100000130040010005004000000000000000800300000060200013005060000003  
use time:28.89  
007000000194000000300000064002000000000006400000030007000000020000085340503760000  
use time:1.01  
300000000060078250000400000000003000000000000608005010000030508000000140040002090  
use time:5.69  
120000040000000003030000000000006000000005006000900000005000000002090100090200400  
use time:56.11  
000000801020009000400706000000960005060200000051000000000000000000045000000000008  
use time:1.06  
000700000000080002010000050700000003000300000060092040071250600000000730050008000  
use time:1.65  
008002000160700030000038000000205000000000009005009000000007000080401500000000000  
use time:1.27  
000000003000010400400020000000000079003700506000300000601005000000400000008000000  
use time:3.70  
000000900000070000300029740000400008000060109700500400000000000002080004008000007  
use time:2.87  
000000900000100000020000000000052000001000240070000006009008030007000000000000059  
use time:100.00  
000000050000006780200000000700004000000080000000000047000040000061030000000005090  
use time:3.43  
000000001030000670200010050710900400000000020000400000040020000002005000000040006  
use time:100.00  
008040000640000700000650000300072084001060000900000600000006000000000079000100000  
use time:3.66  
000000003000003000005000000000040600003000000457008100702030900009020085000000360  
use time:1.96  
000006070000000000000010090000531007050000000000000500006090000000000006049060700  
use time:100.00  
006000000000964000000000036000000700000400000050600300064000500800000020003001000  
use time:1.10  
600000000070600000020030900000050090050003008062000003000000001010060000004000700  
use time:3.76  
000000000000005200000004090035007100020006000000050030001009000000008006000000901  
use time:1.27  
200000007700050000050008000000280006800000000007000500000000004000000903000096080  
use time:17.66  
000070008080000060000000000018000002009000001300001056054008000200010087000000000  
use time:4.66  
000000000000000000050000020002000000900000008504120070010200000000000090097000005  
use time:13.66  
000070000048030000000000009590040000020000400000002908010005000002060000000000090  
use time:11.55  
005203000000906000900007000206001490040600100500000000027000800100000000004009000  
use time:1.97  
600700102000000000000000000000000020000067900000005700006403200080600000005000000  
use time:12.18  
003000000061052070000008000000000820378000000200000000030004090000000040080000000  
use time:956.93  
100300500005070620000000003000000150010500000650007200500010000090000000000200000  
use time:2.00  
007090503000046000000017000030000000005000000000000090000709060050004000000085009  
use time:2.58  
004003000700200100000000090040090600020000080000020007410080060006070001000600900  
use time:4.28  
000000602000000800000800000060003000000000400030007560020309000310040000590000040  
use time:5.85  
000900000701000000000701000004000000000460000300000000089003000003109006000000000  
use time:1.23  
920000000003005000050000070000076000030108000780000406000060000000000600600040008  
use time:1.57  
000800000003000008040900006700508001300000090004000005000006003020000009000081000  
use time:3.28  
006004050020600000000000000010000802900070600002000000000360000000047003700800020  
use time:2.34  
600092000080000500001350000000031020010400000000000030003008071000900000000000006  
use time:4.30  
000000100000000006000006070090000005000000000800701020009000080700920500600000390  
use time:8.68  
000040000000000007060015000000000060009001080000000000016000000005000020300500406  
use time:100.00  
000400000004001906007090400000680004600000000000000000002300600000006010980000500  
use time:4.10  
040000000000000020006000400000000048000090510001040063000000000719000000000700102  
use time:1.44  
000020000080000100200000900000900000000000500007810000700600000100000007030004600  
use time:2.19  
460000005002000000030000000007064020020800090900000000746300001003000009000000000  
use time:3.58  
400000005000006000500000300000000002000300000600400130000091008000000000050000200  
use time:8.91  
500800900002010000000000000000700000700000000000400000070000092000080000060020008  
use time:34.88  
000406050000080000008500000000050000000000000001008600000000540020005000000604002  
use time:4.62  
300000700200000000070040000000256000603000000405030000000007030802400000007000142  
use time:1.59  
009500000000810050500020810000000009900000074000090001030050100000002005000080000  
use time:1.20  
300000002800400000000070000900000000020030050000020000200053904004000000000000003  
use time:100.00  
000700005000200000007006000000000000000000760000070009000627004800050000600000000  
use time:100.00  
900000000000000000001000092200000004040000260000010000408200900000090026000004000  
use time:3.48  
000000008000000063000908007040000000000000000010050700006000040000100600090000001  
use time:3.33  
700000020000000000500000000000000001800000000020000080000800097070000010000200008  
use time:2.36  
000060000000000005060000790000600020030000000600300000000000000000007100006500900  
use time:40.46  
010003000030000000000008000050000080000109026000000000005700000400000050700002030  
use time:4.68  
000000200000502080000006000000000002092000640000008150000000500004060003500000400  
use time:7.21  
000500000000108003000002000003000000000050080029000600000040500007080000400000300  
use time:5.07  
008000000000090070000000000870310020000200400000800000000000000080000000000730080  
use time:100.00  
500600030000000040004005000600100000000000700090004008000890005008000000200001000  
use time:1.36  
300000060000000500000000030400000700000000000106700040000000070000001000067003100  
use time:4.82  
000000000040100070070000000000025000036000000000038000000000001527091000000000208  
use time:23.82  
000000000080000703000150000090831240020005006000000009000000000070200000000080070  
use time:72.15  
200031000060000010034000000003000000090000001000089000000148000400005806000000005  
use time:1.88  
100000000060500901000000000800000000000100000000009008010000040000004000030002800  
use time:2.90  
900706000000040000004000000040000003000001070003007001030070000008050000100060000  
use time:46.50  
000905048000000000800000000002000080070000001968140030000200010230090400000000000  
use time:1.64  
040100060600000050500600000000000500000000000308000040000801000050030000000000003  
use time:31.06  
017000000000006100300450000000000000000000000600000809032007006000000012060085000  
use time:1.28  
000080006009020000500060100000001039000040000000700000000000900000300000930000020  
use time:12.23  
000080000200015007001000000000000000010008300007002900800700000000050600103000700  
use time:1.92  
670000400000900001000000700007002003000600000000300000000005070100700600060049000  
use time:2.22  
000900500200000000900000002000000000000060000000002000000000000450600000000870000  
use time:100.00  
000400900009200008000000000300000005804000213760000000000506000000000502000000306  
use time:6.25  
000009060035000829000000040000908000080010906070460000000000000024000030000000000  
use time:1.66  
000000900005000100010009600206000090090004000000001000600400200000020000020700400  
use time:2.54  
800000000000400000200000009000070000006003700000010050900040000007000100000097320  
use time:1.09  
002000800000000003040100000080700960020000000000000200900002308000000042270000005  
use time:2.19  
002000090000200030000700080005000006000000040000000000000187309200000070000300800  
use time:12.56  
410000000000107500000000000000700000000000000000014800070261090000000010000500000  
use time:1.06  
000060000002071300603000000006700004000100000007000000400000000000004000020000010  
use time:10.08  
050067840000005000000000067000650000500000000006090005000020700000070020090800000  
use time:3.11  
000020608000005000008060003000950000000400060000000890000040907400000201002008040  
use time:1.24  
000009000300004002000005000000090007020801000069200000030008000700000000040000000  
use time:78.03  
000000000000000000000900300200090008430706000000500000500630200063000000010000400  
use time:56.98  
000240007027000000000600020000000009000006050450000000000000006000400070000000000  
use time:100.00  
000700000001600987000000001100400000682003070000000000000900005500000198000001700  
use time:3.26  
600209000070005030009300000500001000001000790007600000000000650000008000005700000  
use time:2.24  
000000005500006900096000000200810007000600008000740006025080004000000000000002000  
use time:1.00  
300000000050300002007000040000090000008000000700000900000700000976405000000800000  
use time:100.00  
000000000650837020700000000010060090270500000080000000000020400007000500060100209  
use time:1.06  
000058000000000000000000000200000000000700000900460000000000008712030000000002000  
use time:100.00  
700006000009100000000008400000030009900000030054000000040000800000400006100000004  
use time:5.46  
000000000000520006790103000006000000000050020000000063007400000000000801084000300  
use time:2.83  
900006500000040016006000040000100000504000003060030000000001007000000400001300000  
use time:4.45  
800437000000020080304001906040000000000000108080005000001000000000002000000300610  
use time:1.26  
001000000060001500000000620000010005030000000659800000000000030010709002025008000  
use time:3.38  
008002000000000800000000700083060000670003000004000003060400100341006050000010064  
use time:2.53  
096020103000050200702000000000070030030040000000000040007000000100063000000000300  
use time:37.84  
520000008000000041006000000407080000000000000000190005040500000600000000000060490  
use time:1.59  
060000000700090000100060000000000076000000001400000020240006000000400000000070002  
use time:2.02  
090806000000000000000000829005600000700205040000003060900070000000000200040000000  
use time:1.05  
500004000000002507000500000102000009300200000090071000007300400004000300000080900  
use time:2.08  
000060030501003000003000000004000020000309000100400000410000900000090000350600002  
use time:3.92  
010053000240006000000007000100004002024000100000000005001460000406000500500008004  
use time:2367.52  
070000300000300000000420000000560004900000006086003000000004080451080000000050000  
use time:9.16  
080060000260500000009000060000103000050000081000056000000300040010000070000600310  
use time:64.04  
000070000300090050000302800007000003000700005000003002000000000003080000125000300  
use time:5.98  
890000004000000060465083079000000000080307000000000000000006010010030650620000007  
use time:1.16  
009000000508006000000000800000030000000000000000640753000000005080015000000000000  
use time:100.01  
000000000004000000502040809000000003000000090800030000900002408000000030003000000  
use time:3600.28  
200000000000001004000007030000000300600000000007000000020004050000000000090203007  
use time:3643.81  
300008000200000000000000003000100050000007000700005400000000704080010000000570000  
use time:100.00  
690000000000009001400000000700400005000203804000000009100607000000000090006000102  
use time:56.53  
030470000000000004000000001500006400000000000072100000200000700400700000080000000  
use time:32.16  
000400000150000000000000000000000000004000030002000090000008460480060000000020080  
use time:13.90  
000000000067004000500000081070000000000000008006000000000008400004000000690000800  
use time:8.50  
090000004400080060050000008070600000012000080000030007000000701003000000001000000  
use time:44.18  
000050008500000000000000700000700000000009005000200004000080007001090480089004200  
use time:25.33  
000400900090001000600030000006000705900000300000004000860000230000090000000300000  
use time:15.13  
000080000105006000000000003500000800000000400002040000009000000004000001000400050  
use time:52.77  
000000060040900002600000000009200000000000530000080090000000608000008000200070000  
use time:10.49  
030000000080560000000000800003000024200000050000050000000090008000008000000000000  
use time:100.00  
200008000000000000000520003600000380050003210000072060102090000000030076300000000  
use time:2.40  
000700010010000005900000008005300007040081000009400000000000000070800000000007090  
use time:19.73  
000060000100000790000050000002006000010037000009000200020003000000800600064000000  
use time:9.62  
400000000079000000620000030000609020000000600090000008050000002000056010000000000  
use time:1.57  
000060070800400126000000000080000600600000002000000001008000000090600000000800067  
use time:12.33  
000130000100090700800000100007000000000500020002000400740050260080000000000010000  
use time:15.61

easytest.py

import sudoku  
file = open("difficult_sudoku.txt","r")

i = 0  
for line in file:  
    if i % 2 == 1:
        print("用时间%f"%(sudoku.sudokutest(line,sudoku.playSudoku_easy)))
    i += 1

file.close()  

测试结果(部分):

用时间0.026514
用时间100.001352
用时间0.007269
用时间0.047377
用时间0.046706
用时间0.010347
用时间0.005284
用时间100.001018
用时间0.011672
用时间3.536470
用时间0.045223
用时间100.001417
用时间0.006271
用时间0.008595
用时间0.014227
用时间1.407873
用时间0.053190
用时间23.669871
用时间0.022319
用时间0.178111
用时间0.024872
用时间0.045397
用时间0.047018
用时间0.165640
用时间0.007430
用时间28.528286
用时间0.025661
用时间1.570115
用时间5.961911
用时间54.336893
用时间100.001868
用时间0.013382
用时间0.142416
用时间0.118540
用时间0.022790

2prime

继续阅读此作者的更多文章