python 말 페달 최적화 알고리즘 실현 (탐욕 알고리즘 + 교체)

import time

##    
X = Y = 5

##         
STEP = 8
##         
nextList = [(2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2)]  ##      

##   
startPoint=(2,0)

##     
chess=[[0 for j in range(Y)] for i in range(X)]



##    
def printChess():
    for i in range(X):
        print(chess[i])
    print('over')

##         
def nextOk(point, i):
    nextp = (point[0] + nextList[i][0], point[1] + nextList[i][1])
    if 0 <= nextp[0] < X and 0 <= nextp[1] < Y and chess[nextp[0]][nextp[1]] == 0:
        return True, nextp
    else:
        return False, point

##         
def findNext(point):
    list = []
    for i in range(STEP):
        ok, pointn = nextOk(point, i)
        if ok:
            list.append(pointn)
    return list

##          （    ）
def getBestNext(point, step):
    temp =X+1
    best = (-1, -1)

    list = findNext(point)
    lenp = len(list)
    for i in range(lenp):
        n = len(findNext(list[i]))
        if n < temp:
            if n > 0:
                temp = n
                best = list[i]
            elif n == 0 and step == X * Y:
                best = list[i]
    return best

##         （         ）
def traverse(point, count):
    global sum_count
    if count > X * Y:
        return True
    for i in range(STEP):
        ok, nextp = nextOk(point, i)
        if ok:
            chess[nextp[0]][nextp[1]] = count
            result = traverse(nextp, count + 1)
            if result:
                return True
            else:
                chess[nextp[0]][nextp[1]] = 0
    return False

##         
def traverseFast(point, step):
    chess[point[0]][point[1]] = step
    while 1:
        step += 1
        best = getBestNext(point, step)
        if best[0] == -1:
            return step
        else:
            chess[best[0]][best[1]] = step
            point = best
    return step

##      
def testSlow():
    start = time.clock()
    chess[startPoint[0]][startPoint[1]]=1
    ok = traverse(startPoint,2)
    if ok:
        print('    ')
    else:
        print('    ')
    printChess()
    print('user_time==', time.clock() - start)

##      
def testFast():
    start = time.clock()
    step = traverseFast(startPoint, 1)
    if step - 1 == X * Y:
        print('      ')
    else:
        print('      ')
    printChess()
    print('user_time==', time.clock() - start)

if __name__ == '__main__':

 
  
     testFast()

    chess = [[0 for j in range(Y)] for i in range(X)]
    testSlow()
  
  
10