Solver for https://proposals.codidact.com/posts/295850

loop_finder.py

#!/usr/bin/pypy3

"""
Tile representation is as four nibbles for ease of manually writing out the tiles
From most significant to least significant they are top, right, bottom, left edge of the tile.
0 indicates that the space is free; fifteen colours of track are therefore supported in principle.
This is not a complete solver in that it doesn't check that each colour forms a single loop.
"""

def tilestr(tile):
	"""
	Returns a string representation of a tile
	"""
	s = hex(tile)[2:]
	return "0" * (4 - len(s)) + s


def linearised_grid_str(grid):
	return tuple(tilestr(tile) for tile in grid)


def valid_left_right(left, right):
	"""
	Validates that tile `left` can be placed to the left of tile `right`
	"""
	return ((left >> 8) & 0xf) == (right & 0xf)


def valid_top_bottom(top, bottom):
	"""
	Validates that tile `top` can be placed above tile `bottom`
	"""
	return ((top >> 4) & 0xf) == ((bottom >> 12) & 0xf)


def rotate(tile, q):
	"""
	Rotates a tile `g` times 90 degrees anticlockwise
	"""
	return 0xffff & ( (tile << (4*q)) | (tile >> (16 - 4*q)) )


def rotations(tile):
	"""
	Enumerates all distinct rotations of a tile (without taking into account the internal structure
	of a tile which has all four edges equal).
	"""
	return set(rotate(tile, i) for i in range(4))


def canonical_centre(centre_size, seq):
	"""
	Applies symmetries of the square to a linearised centre and picks the lexicographically earliest.
	"""
	def rot_grid(g):
		# 012    258     T      R
		# 345 => 147    L R => T B
		# 678    036     B      L
		return tuple(rotate(g[(centre_size-1-y) + centre_size*x], 1) for y in range(centre_size) for x in range(centre_size))


	def flip_tile(tile):
		return (tile & 0xf0f0) | ((tile & 0x0f00) >> 8) | ((tile & 0x000f) << 8)


	def flipH(g):
		# 012    210	 T		T
		# 345 => 543	L R => R L
		# 678    876	 B		B
		return tuple(flip_tile(g[(centre_size-1-x) + centre_size*y]) for y in range(centre_size) for x in range(centre_size))


	candidates = [seq]
	for _ in range(3):
		candidates.append(rot_grid(candidates[-1]))
	candidates.append(flipH(seq))
	for _ in range(3):
		candidates.append(rot_grid(candidates[-1]))

	return min(candidates)


def build_centres(centre_size, tiles4):
	"""
	Returns a list of candidates for the centre tiles. Note that for these purposes a tile 0 corresponds
	to a space which may be filled later by a tile with only two edges.
	
	centre_size: the side length of the centre (i.e. the full grid side length minus two)
	tiles4: the tiles with all four edges used
	"""
	def inner(prefix, available_tiles):
		if len(available_tiles) == 0:
			yield prefix
			return

		# The coordinates of the tile we're about to place
		y, x = divmod(len(prefix), centre_size)

		prev_tile = None
		for i, tile in enumerate(available_tiles):
			# Skip duplicates
			if tile == prev_tile:
				continue

			prev_tile = tile

			# All rotations
			for rot_tile in rotations(tile):
				# Test for immediate conflicts, bearing in mind that tile 0 is a gap which doesn't conflict
				if x > 0 and not (prefix[-1] == 0 or rot_tile == 0 or valid_left_right(prefix[-1], rot_tile)):
					continue

				if y > 0 and not (prefix[-centre_size] == 0 or rot_tile == 0 or valid_top_bottom(prefix[-centre_size], rot_tile)):
					continue

				# TODO A possible optimisation would be to check whether we've just placed a third edge against an
				# empty space which already has two edges next to it, but for now this is overkill.

				yield from inner(prefix + (rot_tile,), available_tiles[:i] + available_tiles[i+1:])

	# We sort for efficient duplicate-skipping
	ext_tiles = tuple(sorted(tiles4 + (0,) * (centre_size**2 - len(tiles4))))
	return set(canonical_centre(centre_size, centre) for centre in inner(tuple(), ext_tiles))


def complete(grid_size, centre, tiles2):
	"""
	Attempts to extend a centre layout using tiles with four edges to a full grid, filling in the gaps
	and border with two-edge tiles. Returns an iterator over completions.
	"""
	def inner(partial, avail, idxs):
		assert len(avail) == len(idxs)
		if len(idxs) == 0:
			yield partial
			return

		yx = idxs[0]
		y, x = divmod(yx, grid_size)
		prev_tile = None
		for i, tile in enumerate(avail):
			# Skip duplicates
			if tile == prev_tile:
				continue

			prev_tile = tile

			# All rotations
			for rot_tile in rotations(tile):
				# Check adjacent slots
				if y > 0 and (yx-grid_size) not in idxs and not valid_top_bottom(partial[yx-grid_size], rot_tile):
					continue
				if y < grid_size-1 and (yx+grid_size) not in idxs and not valid_top_bottom(rot_tile, partial[yx+grid_size]):
					continue
				if x > 0 and (yx-1) not in idxs and not valid_left_right(partial[yx-1], rot_tile):
					continue
				if x < grid_size-1 and (yx+1) not in idxs and not valid_left_right(rot_tile, partial[yx+1]):
					continue

				# Check boundaries
				if y == 0 and not valid_top_bottom(0, rot_tile):
					continue
				if y == grid_size-1 and not valid_top_bottom(rot_tile, 0):
					continue
				if x == 0 and not valid_left_right(0, rot_tile):
					continue
				if x == grid_size-1 and not valid_left_right(rot_tile, 0):
					continue

				yield from inner(partial[:yx] + (rot_tile,) + partial[yx+1:], avail[:i] + avail[i+1:], idxs[1:])


	# Place the centre in a partial grid
	grid = (0,) * grid_size
	for i in range(grid_size - 2):
		grid += (0,) + centre[i*(grid_size-2):(i+1)*(grid_size-2)] + (0,)
	grid += (0,) * (grid_size)

	# Set up priorities for the order in which to fill: centre first, then work around the edge, deliberately
	# not starting in a corner
	priorities = []
	for y in range(1, grid_size - 1):
		for x in range(1, grid_size - 1):
			if not grid[grid_size*y + x]:
				priorities.append(grid_size*y + x)

	for x in range(1, grid_size):
		priorities.append(x)
	for y in range(1, grid_size):
		priorities.append(grid_size*y + x)
	for x in range(grid_size-2, -1, -1):
		priorities.append(grid_size*(grid_size-1) + x)
	for y in range(grid_size-2, -1, -1):
		priorities.append(grid_size*y)

	# We sort the tiles for efficient duplicate-skipping
	yield from inner(grid, sorted(tiles2 + (0,) * (len(priorities) - len(tiles2))), tuple(priorities))


def solve(grid_size, tiles4, tiles2):
	"""
	Finds all solutions given the grid size, the list of tiles having four edges, and the list of tiles having two edges.
	"""
	centres = build_centres(grid_size - 2, tiles4)
	for centre in centres:
		yield from complete(grid_size, centre, tiles2)


if __name__ == "__main__":
	# trichoplax's problem
	tiles4 = (0x2222, 0x1212, 0x1212, 0x1212, 0x1212, 0x1122, 0x1111, 0x1111)
	tiles2 = (0x0011,)*7 + (0x0022,)*7 + (0x0202,)*2
	for solution in solve(5, tiles4, tiles2):
		print(linearised_grid_str(solution))