有没有办法衡量这个算法解决这个数独谜题所花费的时间？

Question

我有使用回溯算法解决数独谜题的代码。我想知道使用 python 语言，回溯算法在几秒或几毫秒内解决数独谜题需要多长时间。

我的代码是 '''

from tabulate import tabulate
import timeit

# A 9x9 matrix which represents our sudoku solver
sudoku_board = [
    [0,0,0,0,0,0,2,0,0],
    [0,8,0,0,0,7,0,9,0],
    [6,0,2,0,0,0,5,0,0],
    [0,7,0,0,6,0,0,0,0],
    [0,0,0,9,0,1,0,0,0],
    [0,0,0,0,2,0,0,4,0],
    [0,0,5,0,0,0,6,0,3],
    [0,9,0,4,0,0,0,7,0],
    [0,0,6,0,0,0,0,0,0]
]

# Display the board
def display_board(sudoku_board):
    print(tabulate(sudoku_board, tablefmt='fancy_grid'))


#Look for an unassigned cell if it exists return row and col values else return False
def empty_cells_exist():
    for i in range(9):
        for j in range(9):
            if sudoku_board[i][j] == 0:
                return [i, j]
    return False

# Is our choice good or not?
def valid_number_check(num, i, j):
    #Checking vertically
    for row in range(9):
        if sudoku_board[row][j] == num:
            return False

#Checking horizontally
for col in range(9):
    if sudoku_board[i][col] == num:
        return False

#Check in the 3x3 gird / box
grid_row = (i // 3) * 3
grid_col = (j // 3) * 3

for i in range(3):
    for j in range(3):
        if sudoku_board[grid_row + i][grid_col + j] == num:
            return False

# Once all tests are passed return true
return True

# Solver
def solver():
    cells_exist = empty_cells_exist()

if not cells_exist:
    return True

i, j = cells_exist[0], cells_exist[1]
for num in range(1,10):
    if valid_number_check(num, i, j):
        sudoku_board[i][j] = num
       
        #Backtracking (checking the next step)
        if solver():
            return True
        else:
            sudoku_board[i][j] = 0
            
#     False if nothing (1 through 9) yield an "accepted answer"
    return False



    display_board(sudoku_board)

    if solver():
        display_board(sudoku_board)
    else:
        print("no solution available")

    if __name__ == "__main__":
         print(timeit.timeit(solver,number=10000))

,

如您所见，我已尝试对求解器函数进行计时，但它 returns 一个类似于 0.07027392299999846 的数字，它不是所需的格式。我要求它采用清晰可读的格式，以便人们理解。比如分秒格式。

Answer 1

为此我通常使用 datetime.datetime.now:

>>> import datetime
>>> begin = datetime.datetime.now()
>>> begin
datetime.datetime(2021, 3, 15, ..., 40, 14, 560666)
>>> end = datetime.datetime.now()
>>> end - begin
datetime.timedelta(seconds=10, microseconds=530067)
>>> str(_)
'0:00:10.530067' # the nice representation

或者自己构建timedelta object：

>>> datetime.timedelta(seconds=0.07027392299999846)
datetime.timedelta(microseconds=70274)
>>> str(_)
'0:00:00.070274'

因此您的代码可能如下所示：

dt = timeit.timeit(solver,number=10000)
print(datetime.timedelta(seconds=dt))

Answer 2

您可以使用模块时间测量所用时间

import time
time1=time.time()
#code
time2=time.time()
time=time2-time1
print(f"time taken {timne} seconds")

有没有办法衡量这个算法解决这个数独谜题所花费的时间？

Is there a way to measure the time taken this algorithm takes to solve this Soduku Puzzle?

python

algorithm

time

sudoku

backtracking