optimizing Knight's tour on a chess board

Question

my code below

I have a little knight's tour problem I'm trying to solve: find the smallest number of moves from point A to point B on an N*N chess board.

I created a board, and used a simple algorithm:

 1. add point A to candidate list and start loop:
 2. pop first element in candidate list and check it:
 3. if end - return counter
 4. else - add the candidate 's "sons" to end of candidate list
 5. go to step 2 (counter is incremented after all previous level sons are popped)

This algorithm works as I expected (used it on a few test cases), but it was very slow:

The call f = Find_route(20, Tile(4,4), Tile(14,11)) (20 is the board dimensions, Tile(4,4) and Tile(14,11) are the start & end positions, respectively) checked 201590 (!!) tiles before reaching the answer.

I tried optimizing it by sorting the candidates list with sorted(tiles, key = lambda e : abs(e.x - end.x)+abs(e.y - end.y)) where tiles is the candidates list. That works for some of the cases but for some it is kind of useless.

helpful cases:

• f = Find_route(20, Tile(1,4), Tile(1,10)) from 459 to 309 (~33% !!)
• f = Find_route(20, Tile(7,0), Tile(1,11)) from 87738 to 79524 (~10% :( )

unhelpful cases:

• f = Find_route(20, Tile(4,4), Tile(14,11)): from 201891 to 201590
• f = Find_route(20, Tile(1,4), Tile(1,11)) from 2134 to 2111

I want eventually to have a list of near-end cases, from which the algorithm would know exactly what to do, (something like a 5 tiles radius), and I think that could help, but I am more interested in how to improve my optimize_list method. Any tips?

---

Code

class Tile(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        tmp = '({0},{1})'.format(self.x, self.y)
        return tmp

    def __eq__(self, new):
        return self.x == new.x and self.y == new.y

    def get_horse_jumps(self, max_x , max_y):
        l = [(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)]
        return [Tile(self.x + i[0], self.y + i[1]) for i in l if (self.x + i[0]) >= 0 and (self.y + i[1]) >= 0 and (self.x + i[0]) < max_x and (self.y + i[1]) < max_y]          


class Board(object):
    def __init__(self, n):
        self.dimension = n
        self.mat = [Tile(x,y) for y in range(n) for x in range(n)]

    def show_board(self):
        print('-'*20, 'board', '-'*20)
        n = self.dimension
        s = ''
        for i in range(n):
            for j in range(n):
                s += self.mat[i*n + j].__str__()
            s += '\n'
        print(s,end = '')
        print('-'*20, 'board', '-'*20)


class Find_route(Board):
    def __init__(self, n, start, end):
        super(Find_route, self).__init__(n)
        #self.show_board()
        self.start = start
        self.end = end

    def optimize_list(self, tiles, end):
        return sorted(tiles, key = lambda e : abs(e.x - end.x)+abs(e.y - end.y))

    def find_shortest_path(self, optimize = False):
        counter = 0
        sons = [self.start]
        next_lvl = []
        num_of_checked = 0

        while True:
            curr = sons.pop(0)
            num_of_checked += 1
            if curr == self.end:
                print('checked: ', num_of_checked)
                return counter
            else: # check sons
                next_lvl += curr.get_horse_jumps(self.dimension, self.dimension)
                # sons     <- next_lvl (optimize?)
                # next_lvl <- []
                if sons == []:
                    counter += 1
                    if optimize:
                        sons = self.optimize_list(next_lvl, self.end)
                    else:
                        sons = next_lvl
                    next_lvl = []


optimize = True            
f = Find_route(20, Tile(7,0), Tile(1,11))
print(f.find_shortest_path(optimize))
print(f.find_shortest_path())

---

EDIT

I added another optimization level - optimize list at any insertion of new candidate tiles, and it seems to work like a charm, for some cases:

        if optimize == 2:
            if sons == []:
                #counter += 1
                sons = self.optimize_list(next_lvl, self.end)
            else:
                sons = self.optimize_list(sons + next_lvl, self.end)
        else:
            if sons == []:
                counter += 1
                if optimize == 1:
                    sons = self.optimize_list(next_lvl, self.end)
                else:
                    sons = next_lvl
                next_lvl = []

optimize = 2          
f = Find_route(20, Tile(1,4), Tile(8,18)) # from 103761 to 8 ( optimal!!! )
print(f.find_shortest_path(optimize))
print(f.find_shortest_path())

I have a problem with calculating the number-of-jumps because I don't know when to increment the counter (maybe at each check?), but it seems to at least converge faster. Also, for other cases (e.g. f = Find_route(20, Tile(1,4), Tile(8,17))) it does not improve at all (not sure if it stops...)

Answer 1

Don't reinvent the wheel.

• Build a graph with tiles as vertices. Connect tiles with an edge if a knight can get from one tile to another in one step.

• Use a standard path finding algorithm. The breadth-first search looks like the best option in you're looking for a shortest path in an unweighted graph.