"""knightmoves.py Playing around with the classic "Knight's Tour" problem, see for example https://en.wikipedia.org/wiki/Knight's_tour $ time python knightmoves.py 8 closed Making graph of knight's moves on 8 x 8 board. Searching for closed tour ... Done! tour is [(1, 1), (2, 3), (1, 5), (2, 7), (4, 8), (6, 7), (8, 8), (7, 6), (6, 8), (8, 7), (7, 5), (8, 3), (7, 1), (5, 2), (3, 1), (1, 2), (2, 4), (1, 6), (2, 8), (4, 7), (2, 6), (1, 8), (3, 7), (5, 8), (7, 7), (8, 5), (7, 3), (8, 1), (6, 2), (4, 1), (2, 2), (1, 4), (3, 5), (5, 6), (4, 4), (2, 5), (1, 7), (3, 8), (5, 7), (3, 6), (5, 5), (7, 4), (8, 2), (6, 1), (4, 2), (2, 1), (1, 3), (3, 4), (4, 6), (6, 5), (8, 6), (7, 8), (6, 6), (5, 4), (3, 3), (4, 5), (6, 4), (4, 3), (5, 1), (6, 3), (8, 4), (7, 2), (5, 3), (3, 2), (1, 1)] Drawing turtle picture .... Hit return to quit. real 0m34.118s user 0m19.049s sys 0m0.411s There are two optional command line arguments n the board width x height is n x n closed look for a path which returns to its start This is using a recursive depth-first backtracking search, with a few tweaks for this problem. - In addition to keeping a "visited" dictionary, we also keep a list of the nodes visited in order, i.e. the current path that's being worked on. While this has the same information, the hope is that membership tests in the dictionary are faster. - Once we have found a solution, we leave the recursive search without making any more changes to the saved path. - If we need to back up, nodes that we have already looked at are nevertheless removed from the visited dictionary ... since we'll want to look at them again with a different initial path. That means that this full search is a *much* lengthier process than just using depth-first-search to traverse the tree once. This search is looking at all paths (gulp) ... - To improve our chances of finding a solution sooner, we put the neighbors in an order that helps to speed up the search that remains, by taking first those with fewest unvisited neighbors. (There's a blurb about this approach in the wikipedia article) - The "open" version of the search treats any path which has all the nodes as a solution. The "closed" version also requires that the first one be a neighbor of the last. Jim Mahoney | cs.marlboro.college | Feb 20 | MIT License """ import turtle # coordinates # ------------ # # The coordinate system I've chosen is (x,y) with (1,1) # at the bottom left. (This is *not* the matrix row/column aproach.) # # So for board with 4 (rows) x 4 (columns) the (x,y) labeled nodes are # # (4,1) (4,2) (4,3) (4,4) # (3,1) (3,2) (3,3) (3,4) # (2,1) (2,2) (2,3) (2,4) # (1,1) (1,2) (1,3) (1,4) # knight's moves # -------------- # The possible moves from an origin O are # . . x . x . # . x . . . x # . . . o . . # . x . . . x # . . x . x . # # which have these cooresponding offsets : # offsets = [ (-1, 2), ( 1, 2), (-2, 1), ( 2, 1), (-2,-1), ( 2,-1), (-1,-2), ( 1,-2) ] def add(origin, offset): """ vector addition , return destination = origin + offset >>> add((1,1), (1,-1)) (2, 0) """ return (origin[0] + offset[0], origin[1] + offset[1]) def on_board(square, sizes): """ True if this (x,y) square is on a board with this (width,height) """ return 1 <= square[0] <= sizes[0] and 1 <= square[1] <= sizes[1] def neighbors(origin, sizes): """ Given the board sizes = (rows, columns), return [square1, square2, ...] places a knight could move to. >>> neighbors((1,1), (6, 6)) [(2, 3), (3, 2)] >>> neighbors((1,3), (6, 6)) [(2, 5), (3, 4), (3, 2), (2, 1)] """ result = [] for offset in offsets: destination = add(origin, offset) if on_board(destination, sizes): result.append(destination) return result def graph_of_knight_moves(sizes): """ Given the board size = (width, height) return dict of lists = {(x1,y1) : [(x2,y2), ...]} graph representation of the squares on a chess board that are a knight's move apart. """ graph = {} center = ((1+sizes[0])/2, (1+sizes[1])/2) for x in range(1, sizes[0]+1): for y in range(1, sizes[1]+1): graph[(x, y)] = neighbors((x,y), sizes) return graph def line(square1, square2, dots=False, pps=100, dotsize=20): """ Draw a line from (row1,col1) to (row2,col2) """ # pps is "pixels per square" scaling factor border = (pps, pps) (x1,y1) = add((square1[0]*pps, square1[1]*pps), border) (x2,y2) = add((square2[0]*pps, square2[1]*pps), border) turtle.penup() turtle.goto(x1,y1) if dots: turtle.dot(dotsize) turtle.pendown() turtle.goto(x2,y2) if dots: turtle.dot(dotsize) def init_turtle(): """ Customize the turtle settings """ # I don't understand why calling # turtle.hideturtle() # turtle.speed('fast') # here does not set these properties globally. turtle.title("Knight's Tour") turtle.setworldcoordinates( 0, 0, # lower left x,y turtle.window_width(), turtle.window_height()) # upper right x,y def draw_path(path, pencolor='blue', pensize=4): """ Draw a Knight's Tour path with turtle graphics """ turtle.pencolor(pencolor) turtle.pensize(pensize) turtle.hideturtle() turtle.speed('fastest') for i in range(len(path)-1): line(path[i], path[i+1], dots=True) def draw_board(sizes, pencolor='black', pensize=1): """ Draw a sizes=(width,height) board with turtle graphics """ turtle.pencolor(pencolor) turtle.pensize(pensize) turtle.hideturtle() # This works here ... turtle.speed('fastest') # but not in init_turtle() - why? (width, height) = sizes for x in range(1, width+2): line((x-0.5, 0.5), (x-0.5, height+0.5)) for y in range(1, height+2): line((0.5, y-0.5), (width+0.5, y-0.5)) def is_done(graph, path, closed): """ Return true if the path is a valid solution """ # closed : boolean for whether we're looking for a closed path. if closed: return len(graph) == len(path) and path[0] in graph[path[-1]] else: return len(graph) == len(path) def tour_search(graph, node, path=[], visited={}, closed=False): """ search for path through the graph that visits all nodes, each once """ if node in visited or is_done(graph, path, closed): return path else: visited[node] = True path.append(node) if is_done(graph, path, closed): return path else: candidates = graph[node] # # Try looking at those with fewer ways forward first. # This helped a *lot* for the 7x7 and 8x8 searches. # branching = lambda n: 100 if n in visited else len(graph[n]) sorted_candidates = sorted(candidates, key=branching) # for candidate in sorted_candidates: tour_search(graph, candidate, path, visited, closed) if is_done(graph, path, closed): return path path.pop() # No luck though this one, visited.pop(node) # so back track .... return path def main(n, closed, start=(1,1)): sizes = (n, n) print("Making graph of knight's moves on {} x {} board.".format( sizes[0], sizes[1])) graph = graph_of_knight_moves(sizes) print("Searching for {} tour ...".format('closed' if closed else 'open')) tour = tour_search(graph, start, [], {}, closed=closed) if closed: # A closed tour? Well then let's go back to the start after then end. tour.append(tour[0]) print("Done! tour is {}".format(tour)) print("Drawing turtle picture ....") init_turtle() draw_board(sizes) draw_path(tour) wait = input('Hit return to quit.') def get_command_line_args(n=5, closed=False): """ Return values for (n, closed) from defaults or user input """ import sys if len(sys.argv) > 1: try: n = int(sys.argv[1]) except: pass if len(sys.argv) > 2: closed = sys.argv[2] == 'closed' return (n, closed) if __name__ == '__main__': import doctest doctest.testmod() (n, closed) = get_command_line_args() main(n, closed)