Задача о путешествии шахматного коня

Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года).

Когда то давно, мы уже рассматривали пример решения задачи рекурсивным образом, на примере задачи по размену денег. Пришло время вспомнить некоторые классические подходы и начать хотелось бы с задачи о путешествии шахматного коня.

Решение приведенное ниже относится к так называемым алгоритмам с возвратом.
Разделяй и властвуй -основная идея рекурсии. Т.е. мы сложную задачу делим на маленькие простые  решаем их по отдельности в цепочке. В случае данной задачи, можно рассмотреть подзадачу, которая состоит в том, чтобы либо выполнить какой-либо очередной ход, либо обнаружить, что дальнейшие ходы невозможны.

Итак, каждый ход мы будем характеризовать 3-мя числами: его порядковым номером i и парой координат x, y. История ходов будет храниться в матрице списков, в соответствующей ячейке записываем порядковый номер хода. Соответственно, если в ячейке 0, значит туда мы еще не ходили.

Важно определиться с вычислением новой координаты. Можно заметить, что у коня есть 8 позиций-кандидатов (u, v) куда может прыгнуть конь.
Будем получать новые координаты прибавляя соответствующие смещения, хранящиеся в 2х списках dx, dy и отслеживать допустимость хода (находимся в пределах доски).

Характерной чертой данного алгоритма является то, что каждый шаг, выполняемый в попытке приблизиться к полному решению, запоминается таким образом, чтобы от него можно было позднее отказаться, если выяснится, что он не может привести к полному решению. Такое действие называется возвратом. А класс алгоритмов, как не трудно догадаться, алгоритмы с возвратом.

Очень советую читать именно алгоритм, тем более Питон в этом сильно помогает. Это даст куда больше толку. чем множество лишних слов!)

#Задача о коняшке
def knightsTour(x0, y0, done, size=5):
    #создаем шахматную доску в виде 2го списка
    h = [[0 for j in xrange(size)] for i in xrange(size)]
    #начальная координата(1го хода)
    h[x0][y0] = 1
    
    #Возможные ходы
    dx = [2, 1, -1, -2, -2, -1, 1, 2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]

    def CanBeDone(u, v, i):
        h[u][v] = i
        done = tryNextMove(u, v, i)
        if not done:
            h[u][v] = 0
        return done
    
    def tryNextMove(x,y, i):
        
        #eos - показывает все ли варианты возможных 8ми ходов мы рассмотрели
        #done - показывает удачна ли данная ветка решения
        #k - порядковый номер рассмотренной попытки из 8 допустимых
        env = {'done': False, 'eos': False, 'u': x, 'v': y, 'k': -1}

        def next():
            x = env['u']
            y = env['v']
            while env['k'] < 8:
                env['k'] +=1;
                if env['k'] < 8:
                    env['u'] = x + dx[env['k']]
                    env['v'] = y + dy[env['k']]
                if (env['u'] >= 0 and env['u']<size) and (env['v']>=0 and env['v']<size) and h[env['u']][env['v']]==0:
                    break
            env['eos'] = (env['k']==8)

        if i < size**2:#если доска не заполнена
            next()
            while not env['eos'] and not CanBeDone(env['u'], env['v'], i+1):
                next()
            done = not env['eos']
        else:
            done = True
        return done

    tryNextMove(x0, y0, 1)
    print h

Привожу пример заполнения шахматной доски.