20a.rb

input = Struct.new(:tiles, :dim).new({})
data.split("\n\n").map do |s|
  lines = s.lines.map(&:chomp)
  input.tiles[lines.first[/\d+/].to_i] = lines[1..].map(&:chars)
end
input.dim = input.tiles.length.sqrt.to_i

def coords(input, pos)
  [ pos / input.dim, pos % input.dim ]
end

def solve(input, board, ids, add_id = nil, add_tile = nil)
  # append id & tile to ids/board
  if add_id
    r, c = coords(input, board.length)
    (ids = ids.dup)[[ r, c ]] = add_id
    (board = board.dup)[[ r, c ]] = add_tile
  end

  # check N and W
  if !ids.empty?
    r, c = coords(input, ids.length - 1)
    if n = board[[ r - 1, c ]]
      return if n.last != board[[ r, c ]].first
    end
    if w = board[[ r, c - 1 ]]
      return if w.map(&:last) != board[[ r, c ]].map(&:first)
    end
  end

  # done?
  if board.length == input.tiles.length
    p ids[[ 0, 0 ]] * ids[[ input.dim - 1, 0 ]] * ids[[ 0, input.dim - 1 ]] * ids[[ input.dim - 1, input.dim - 1 ]]
    exit
  end

  # place another tile and try to solve
  (input.tiles.keys - ids.values).each do |id|
    tile = input.tiles[id].dup.map(&:dup)
    2.times do
      # test
      solve(input, board, ids, id, tile)
      # rotate 3 times
      3.times { solve(input, board, ids, id, tile = tile.transpose.map(&:reverse)) }
      # flip
      tile = tile.reverse
    end
  end
end

solve(input, {}, {})