Thought Outflux | Anirudh Sanjeev

Some bloke on slashdot linked to his solution to the knight’s tour problem.

I had a different approach with dynamic programming and a seemingly simpler solution. I used python tuples for coordinates, and the magical “in” keyword (if target in visited: continue

# Knight's tour
def get_legal_moves(coord):
  # Legal move means that the knight won't leave the board.
  # Doesen't take visited into consideration to save memory
  x, y = coord
  legal_moves = []
  for delx, dely in ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)):
    if (x + delx < 0 or x + delx > 7) or (y + dely < 0 or y + dely > 7):
      continue
    legal_moves.append((x+delx,y+dely))
  return legal_moves

def solve_tour(start, visited):
  legal_moves = get_legal_moves(start)
  visited.append(start)
  if(len(visited) == 64):
    print "Finished"
    print visited
  for move in legal_moves:
    if move not in visited:
      solve_tour(move,visited)

for x in xrange(0,7):
  for y in xrange(0,7):
    solve_tour((x,y),[])

This gives almost 15 solutions and is more or less brute force, so I don’t see how it’s worse off than the fancy solution which the slashdotted article proposes.
And does it in 22 lines, compared to the 60 on the slashdot article.

either that or i’m doing something really wrong here.