Solve Reddit tile puzzle

puzzle.py

# https://www.reddit.com/r/puzzles/comments/1hjpd63/comment/m38k73k
# Port of my Arc program at https://www.righto.com/2010/12/solving-edge-match-puzzles-with-arc-and.html
# Ken Shirriff righto.com

import math

# Symbols
menorah = 1
dreidel = 2
gift = 3
snack = 4

# Tile edges
top = 0
left = 1
right = 2
bottom = 3



# + is head, -is feet. Each piece is described top, left, right, bottom. The 9 pieces are as shown on Reddit
tiles = [[-dreidel, -snack, menorah, gift], [-snack, -menorah, dreidel, gift], [-menorah, -dreidel, snack, gift],
[-gift, -dreidel, menorah, snack], [-gift, -menorah, dreidel, snack], [menorah, -dreidel, snack, -snack],
[-snack, -dreidel, menorah, gift], [-snack, -menorah, dreidel, gift], [snack, -dreidel, gift, -snack]]

def label(n):
  """ Creates the text label for a tile edge: -4 to +4"""
  sign = ""
  if n < 0:
    sign = "-"
    n = -n
  return (sign + ["", "menorah", "dreidel", "gift ", "snack"][n]).center(8)
  

def prettyprint(tiles):
  """Prints the tiles using ASCII graphics."""
  print()
  for y in range(0, 3):
    for line in range(0, 5):
      for x in range(0, 3):
        if line == 0 or line == 4:
          print("------------------- ", end="")
        elif line == 1:
          print("|     %s    | " % label(tiles[y * 3 + x][top]), end="")
        elif line == 2:
          print("|%s %s| " % (label(tiles[y * 3 + x][left]), label(tiles[y * 3 + x][right])), end="")
        elif line == 3:
          print("|     %s    | " % label(tiles[y * 3 + x][bottom]), end="")
      print("")


def matches(grid, gridedge, gridx, gridy, newedge, newtile, w, h):
  """
  Test one edge of the new tile against the current grid to see if it matches okay.
  grid is the grid of placed tiles as a list of tiles e.g. ((1 3 4 2) none (-1 2 -1 1) ...)
  gridedge is the edge of the grid cell to match (top/bottom/left/right)
  gridx is the x coordinate of the grid tile
  gridy is the y coordinate of the grid tile
  newedge is the edge of the new tile to match (top/bottom/left/right)
  newtile is the new tile e.g. (1 2 -1 -3)
  w is the width of the grid
  h is the height of the grid
  """
  n = gridy * w + gridx
  if gridx < 0 or gridy < 0 or gridx >= w or gridy >= w or n >= len(grid): return True # Nothing to match
  if n >= len(grid) or grid[n] is None: return True # No tile to match
  return grid[n][gridedge] == -newtile[newedge] # Check if opposites

def is_okay(grid, newtile, x, y, w, h):
  """ Test if a tile will fit into a grid of placed tiles successfully
  grid is the grid of tiles
  newtile is the tile to place into the grid
  (x, y) is the position to place the tile"""
  return (matches(grid, right, x-1, y, left, newtile, w, h) and
    matches(grid, left, x+1, y, right, newtile, w, h) and
    matches(grid, top, x, y+1, bottom, newtile, w, h) and
    matches(grid, bottom, x, y-1, top, newtile, w, h))

def try_tile(grid, candidate, candidates, nextpos, w, h):
  """
  Try adding a candidate tile to the grid, and recurse if successful.
  grid is a list of tiles already placed
  candidates is a list of tiles yet to be placed
  nextpos is the next position to place a tile (0 to 8)
  w and h are the dimensions of the puzzle.
  Returns a list of solutions or []
  """
  print("trying grid", grid, "candidate", candidate)
  if is_okay(grid, candidate, nextpos % w, nextpos // w, w, h):
    return solve(grid + [candidate], candidates, nextpos + 1, w, h)
  else:
    return []

def rotate(tile):
  """ Return the tile, rotated clockwise"""
  return [tile[left], tile[bottom], tile[top], tile[right]]

def solve(grid, candidates, nextpos, w, h):
  """ grid is a list of tiles already placed
  candidates is a list of tiles yet to be placed
  nextpos is the next position to place a tile (0 to 8)
  w and h are the dimensions of the puzzle.
  Returns a list of solutions or []
  """
  if not candidates:
    # Success!
    print("success", grid)
    return [grid]
  else:
    results = []
    # Try each tile in the next spot
    for idx in range(0, len(candidates)):
      candidate = candidates[idx]
      newcandidates = candidates[:idx] + candidates[idx+1:] # Remove candidate tile
      # Try all four rotations
      results += try_tile(grid, candidate, newcandidates, nextpos, w, h)
      results += try_tile(grid, rotate(candidate), newcandidates, nextpos, w, h)
      results += try_tile(grid, rotate(rotate(candidate)), newcandidates, nextpos, w, h)
      results += try_tile(grid, rotate(rotate(rotate(candidate))), newcandidates, nextpos, w, h)
      if results:
        print("Results", results)
    return results

def main():
    results = solve([], tiles, 0, 3, 3)
    for result in results:
      print(result)
      prettyprint(result)
      print()


if __name__ == "__main__":
    main()