Question: A bit of history: Since I was a kid, I have been playing a very easy little solitaire game to which I have never found a solution and honestly, I don't know if there is one, but I would like to find it out with the help of my computer. First, let me explain the rules:  First you have to take a grid sheet and draw an area of 10 x 10 squares. Next you have to place the first number at a square of your chioce (I usually use the square at 0,0) Now you have to start counting up numbers from 1 to 100 according to certain jump rules (I'll get into that right now) and annotating the corresponding number inside the square you are jumping to. Jump rules are: leave 2 squares blank horizontally or vertically and leave only one blank diagonally.  The problem: I have written the following (awfully slow) code in Python. Considering that my interpretation is that the possiblities the computer has to explore are 100!, I think the "bruteforcing" method will take a pretty long time. I'm running an 11th gen I7 but my Python code gets only executed on a single core. How could I speed my code up and/or how I could improve the algorithm? Here is the code: class Gametable: def __init__( self ): #This value contains the maximum number reched by the algorithm self.max_reached = 1 def start_at( self, coordX, coordY ): tmpTable = [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ] #We do not need to check the first jump, since the table should be empty. if self.is_valid_move( coordX, coordY, 1, tmpTable ): print("Found a solution!") else: print("Found no solution :(") def print_table( self, table ): print(52*"-") for X in range(10): for Y in range(10): if table[ X ][ Y ] == 0: print("| ", end="") else: print("| {:02d} ".format( table[ X ][ Y ]), end='') print(" |") print(52*"-") print() def is_valid_move( self, X, Y, counter, table): # Check bounds if X < 0: return False elif X > 9: return False elif Y < 0: return False elif Y > 9: return False # Now check next steps if table[ X ][ Y ]==0: table[ X ][ Y ] = counter if self.is_valid_move( X + 3, Y, counter+1, table ) or self.is_valid_move( X - 3, Y, counter+1, table ) or self.is_valid_move( X , Y + 3, counter+1, table ) or self.is_valid_move( X, Y - 3, counter+1, table ) or self.is_valid_move( X + 2, Y + 2, counter+1, table ) or self.is_valid_move( X + 2, Y - 2, counter+1, table ) or self.is_valid_move( X - 2, Y + 2, counter+1, table ) or self.is_valid_move( X - 2, Y - 2, counter+1, table ): return True else: if counter > self.max_reached: print("Max reached "+str(self.max_reached)) self.print_table(table) self.max_reached = counter table[X][Y] = 0 # We'll have to delete the last step if there is no further possibility return False mytable = Gametable() mytable.start_at( 0, 0 )  This is an example of the game: 

Answer: I had a go and implemented Warnsdorff's rule for prioritising moves, and the program immediately found a solution: def print_table(table): print(51*"-") for row in table: for cell in row: print(f"|{cell:>3} " if cell else "| ", end='') print("|\n" + 51*"-") print() def solve(table, x, y): sizey = len(table) sizex = len(table[0]) size = sizey * sizex # Generate move list (nothing special) def moves(x, y): return [(x1, y1) for x1, y1 in ( (x + dx, y + dy) for dx, dy in ( (-3, 0), (-2, 2), (0, 3), ( 2, 2), ( 3, 0), ( 2, -2), (0, -3), (-2, -2) ) ) if 0 <= x1 < sizex and 0 <= y1 < sizey and table[y1][x1] == 0 ] # Heuristic for evaluating a move by the number of followup moves def freedom(x, y): return len(moves(x, y)) # Get move list sorted by heuristic (Warnsdorff's rule) def sortedmoves(x, y): return sorted((freedom(x1, y1), x1, y1) for x1, y1 in moves(x, y)) def dfs(x, y, i): table[y][x] = i # Table completed? if i == size or any(dfs(x1, y1, i + 1) for _, x1, y1 in sortedmoves(x, y)): return True # BINGO! table[y][x] = 0 # backtrack return False return dfs(x, y, 1) table = [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ] if solve(table, 0, 0): print("SOLVED!") print_table(table)  Output: SOLVED! --------------------------------------------------- | 1 | 43 | 67 | 16 | 42 | 75 | 31 | 39 | 74 | 32 | --------------------------------------------------- | 69 | 18 | 3 | 83 | 35 | 4 | 82 | 36 | 5 | 81 | --------------------------------------------------- | 66 | 15 | 41 | 76 | 94 | 40 | 73 | 93 | 30 | 38 | --------------------------------------------------- | 2 | 44 | 68 | 17 | 79 | 86 | 34 | 80 | 87 | 33 | --------------------------------------------------- | 70 | 19 | 95 | 84 | 72 | 96 | 89 | 37 | 6 | 92 | --------------------------------------------------- | 65 | 14 | 57 | 77 | 99 | 56 | 78 |100 | 29 | 60 | --------------------------------------------------- | 23 | 45 | 71 | 26 | 90 | 85 | 27 | 91 | 88 | 10 | --------------------------------------------------- | 54 | 20 | 98 | 55 | 58 | 97 | 50 | 59 | 7 | 49 | --------------------------------------------------- | 64 | 13 | 24 | 63 | 12 | 25 | 62 | 11 | 28 | 61 | --------------------------------------------------- | 22 | 46 | 53 | 21 | 47 | 52 | 8 | 48 | 51 | 9 | ---------------------------------------------------  Other starting squares When I tried other starting squares, it turned out that when starting at (4, 2) the search took too long. So I added a tie-breaker to the heuristic (in case the minimum freedom was shared by multiple moves): I went with the taxicab distance to the closest corner. This turned out to work out well for all starting positions: def print_table(table): print(51*"-") for row in table: for cell in row: print(f"|{cell:>3} " if cell else "| ", end='') print("|\n" + 51*"-") print() def solve(table, x, y): sizey = len(table) sizex = len(table[0]) size = sizey * sizex # Generate move list (nothing special) def moves(x, y): return [(x1, y1) for x1, y1 in ( (x + dx, y + dy) for dx, dy in ( (-3, 0), (-2, 2), (0, 3), ( 2, 2), ( 3, 0), ( 2, -2), (0, -3), (-2, -2) ) ) if 0 <= x1 < sizex and 0 <= y1 < sizey and table[y1][x1] == 0 ] # Heuristic for evaluating a move by the number of followup moves def freedom(x, y): return len(moves(x, y)) # Heuristic for breaking ties: taxicab distance to closest corner def cornerdistance(x, y): return min(x, sizex - 1 - x) + min(y, sizey - 1 - y), # Get move list sorted by heuristic (Warnsdorff's rule) def sortedmoves(x, y): return sorted((freedom(x1, y1), cornerdistance(x1, y1), x1, y1) for x1, y1 in moves(x, y)) def dfs(x, y, i): table[y][x] = i # Table completed? if i == size or any(dfs(x1, y1, i + 1) for _,_, x1, y1 in sortedmoves(x, y)): return True # BINGO! table[y][x] = 0 # backtrack return False return dfs(x, y, 1) # Try any starting square for i in range(10): for j in range(10): table = [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ] print("=====",i,j,"=================") if solve(table, i, j): print("SOLVED!") print_table(table)  All 100 solutions were spit out to the screen in no time.