Solving Loop Puzzles


A quick puzzle from Daily Programmer:

∞ Loop is a mobile game that consists of n*m tiles, placed in a n*m grid. There are 16 different tiles: ┃, ━, ┏, ┓, ┛, ┗, ┣, ┳, ┫, ┻, ╋, ╹, ╺, ╻, ╸, ' '. The objective is to create a closed loop: every pipe must have another tile facing it in the adjacent tile for example if some tile has a pipe going right, its adjacent tile to the right must have a pipe going left.

The most straightforward solution is a hybrid combination of constraints and backtracking, similar to what I did when solving Takuzu and tile puzzles.

First, we'll create two classes, one for individual characters and one for puzzles. Think what you may about object oriented programming, but I think it fits fairly well with this problem.

First, characters. We want something that will be able to represent characters with with their character form (the box drawing characters above) or as a collection of edges (if the top / right / bottom / left pipe is included). This could be represented as a 4-bit integer, but instead I'll use a 4-tuple of bools. It's just a bit easier to read by default.

On top of that, we want functions that can rotate pieces, test if two characters are actually the same, and to test if two neighboring pieces can border each other or not. The last is true if they either both have a pipe pointing inwards or neither does.

class Character(object):
    '''A box drawing character or empty space ( ╸╻┓╺━┏┳╹┛┃┫┗┻┣╋).'''

    order = ' ╸╻┓╺━┏┳╹┛┃┫┗┻┣╋'
    sides = {'top': (0, 2), 'right': (1, 3), 'bottom': (2, 0), 'left': (3, 1)}

    def __init__(self, symbol_or_bits):
        '''
        Create a new character from either the symbol (must be a valid symbol)
        or a 4-tuple of booleans representing the sides (top, right, bottom,
        left).
        '''

        if isinstance(symbol_or_bits, str):
            self.symbol = symbol_or_bits

            bits = bin(Character.order.find(symbol_or_bits))[2:]
            bits = '0' * (4 - len(bits)) + bits

            self.bits = tuple(bit == '1' for bit in bits)
        else:
            self.bits = symbol_or_bits
            self.symbol = Character.order[int(''.join('1' if bit else '0' for bit in symbol_or_bits), 2)]

    def rotate(self):
        '''Return the next rotation for this character.'''

        return Character(tuple(self.bits[i] for i in range(-1, 3)))

    def rotations(self):
        '''Generate all four of the rotations this character could have.'''

        c = self
        for i in range(4):
            yield c
            c = c.rotate()

    def can_neighbor(self, other, side):
        '''
        Test if this character can neighbor a given other on a given side.

        Two characters can be neighbors if they either both have a line on that
        side or neither does. If other is not set, that is assumed to be a
        outside of the puzzle and thus not have a line.
        '''

        my_bit, their_bit = Character.sides[side]

        # print(side, self, other, my_bit, their_bit, self.bits, other.bits) # DEBUG

        if other:
            return self.bits[my_bit] == other.bits[their_bit]
        else:
            return not self.bits[my_bit]

    def __hash__(self):
        '''Use the symbol as a hash. This is so we can put characters in sets.'''

        return hash(self.symbol)

    def __eq__(self, other):
        '''Characters are equal if they have the same symbol.'''

        return self.symbol == other.symbol

    def __repr__(self):
        '''Print which character this is.'''

        return self.symbol

After that, the next step will be to create a Puzzle. This is the grid of characters, but we'll actually go a step larger. Each cell in the Puzzle will actually be a set of rotations that are still possible. This means that as long as any cell has more than 1 possibility, it's not solved. If any has managed to reach 0, no solution is possible.

In addition, we'll put the constraining function here. This will loop through every single cell in the puzzle: for each, it will match each rotation remaining against each rotation of all four neighbors. If a given rotation cannot possibly match any one of the neighbors, remove it from the set. Imagine:

┛╸╸
╺┓╻
┗ ┣

The middle character can originally be any of {┏, ┓, ┛, ┗}; however, the bottom center is an empty space, so we should not include any downward facing options. Thus, with a single round of constraint, we've reduced the center tile to {┛, ┗}. Even better, this will further constrain the top center piece. At first it was {╹, ╺, ╻, ╸}, but the center has to have an upward pointing point, forcing the top center to be {╻}. Each round of constraints only sets each tile once and won't work recursively, but it's easy enough to call it more than once. Especially since the function will return True until the puzzle reaches a steady state.

class Puzzle(object):
    '''Represent a grid of possible characters.'''

    border = {Character(' ')}

    def __init__(self, data):
        '''Initialize from a string containing characters.'''

        self.data = [
            [set(Character(c).rotations()) for c in line]
            for line in data.strip().split('\n')
        ]
        self.rows = len(self.data)
        self.cols = len(self.data[0])

    def possibilities(self):
        '''
        Return the number of possibilities in the form (unsolved squares, total
        possibilities). A solved puzzle will return (0, rows * cols).
        '''

        return (
            sum(0 if len(el) == 1 else 1 for row in self.data for el in row),
            sum(len(el) for row in self.data for el in row)
        )

    def is_solvable(self):
        '''Test if the puzzle is still solvable (no empty possibilities.)'''

        return not any(
            len(el) == 0
            for row in self.data
            for el in row
        )

    def is_solved(self):
        '''Test if this puzzle is currently solved.'''

        return all(
            len(el) == 1
            for row in self.data
            for el in row
        )

    def constrain(self):
        '''
        Constrain this puzzle by removing any rotations that could not possibly
        be used (there's no possibility in the neighbor to match them).

        Only make one pass, call this function multiple times in case one
        constraint cascades.

        Return if anything changed.
        '''

        logging.debug('Applying constraints, possiblities: {}'.format(self.possibilities()))

        offsets = [
            ('top', -1, 0),
            ('right', 0, 1),
            ('bottom', 1, 0),
            ('left', 0, -1),
        ]

        something_changed = False

        for row in range(self.rows):
            for col in range(self.cols):
                invalid = set()
                for first_point in self[row, col]:
                    if not all(
                        any(
                            first_point.can_neighbor(second_point, direction)
                            for second_point in self[row + row_offset, col + col_offset]
                        ) for direction, row_offset, col_offset in offsets
                    ):
                        invalid.add(first_point)

                for impossibility in invalid:
                    something_changed = True
                    self[row, col].remove(impossibility)

        return something_changed

    def __getitem__(self, pt):
        '''
        Fetch the current possibility set from a given row and column.

        If the index is out of bounds, instead return a 'border character' with
        no edges to help guarantee that no pieces point outwards.
        '''

        row, col = pt
        if 0 <= row < self.rows and 0 <= col < self.cols:
            return self.data[row][col]
        else:
            return Puzzle.border

    def __repr__(self):
        '''If solved, print the puzzle; if not, print remaining possibilities.'''

        if self.is_solved():
            return '\n'.join(
                ''.join(str(list(el)[0]) for el in row)
                for row in self.data
            )

        else:
            def pad_set(el):
                return ''.join(str(each) for each in el) + ' ' * (4 - len(el))

            line_seperator = '\n' + ('┈' * (7 * self.cols - 3)) + '\n'

            return line_seperator.join(
                ' ┆ '.join(pad_set(el) for el in row)
                for row in self.data
            )
            return repr(self.data)

That's actually enough by itself to solve some puzzles. But sometimes, particularly in larger puzzles, you'll reach states where two arrangements are still possible. In those cases, we want to take a backtracking step: choose each of the possible states in turn and assume it is correct, switching back to the constraint solver until the next block. If a solution is found in that branch, just return. If not, try the next branch from that position.

def solve(puzzle):
    '''
    Use a hybrid constraint / backtracking solver to solve the puzzle.

    while not solved:
        apply constraint solver until it doesn't work any more
        find the first mismatched point and try each possibility
    '''

    queue = [puzzle]
    while queue:
        puzzle = queue.pop()
        logging.info('Running backtracker, states: {}, possiblities in current state: {}'.format(len(queue), puzzle.possibilities()))
        logging.debug(puzzle)

        # Apply constraint until the constrain function returns false
        while puzzle.constrain(): pass
        logging.debug(puzzle)

        if not puzzle.is_solvable():
            logging.info('Unsolveable state found, removing it')
            continue

        if puzzle.is_solved():
            logging.info('Solved state found, returning it')
            return puzzle

        # Split to backtracking
        def first_unclear_point():
            for row in range(puzzle.rows):
                for col in range(puzzle.cols):
                    if len(puzzle[row, col]) > 1:
                        return row, col, puzzle[row, col]

        row, col, possibilities = first_unclear_point()
        for possibility in possibilities:
            copied_puzzle = copy.deepcopy(puzzle)
            copied_puzzle[row, col].clear()
            copied_puzzle[row, col].add(possibility)

            queue.append(copied_puzzle)

    # If we made it out of the loop, there is no solution to the puzzle
    return None

And that's it. We can solve puzzles from stdin:

import sys
puzzle = Puzzle(sys.stdin.read())
solution = solve(puzzle)
print(solution)

Example running:

$ cat 10x10.loops

┗┣┃┃┗┏┳┓┛┏
┗┛┛━┳┫┃┃━━
┛┛━┓┳╋┫━┣┏
┫╋┻┛┛┻━┳╋┗
┛┳┃┳┃╋┫┃┳┗
┓━┓━┏╋┏┻╋┓
┛┛━┃┻┗┓┓┳┓
┏╋╋┏┏┳┣┗┗┗
┣╋╋┏┏┻┓┓┏┫
┏┏┗┫┣┳┳━┫┗

$ cat 10x10.loops | python3 loop-solver.py

┏┳━━┓┏┳┓┏┓
┗┛┏━┻┫┃┃┃┃
┏┓┃┏┳╋┫┃┣┛
┣╋┻┛┗┫┃┣╋┓
┗┻━┳━╋┫┃┣┛
┏━┓┃┏╋┛┣╋┓
┗┓┃┃┣┛┏┛┣┛
┏╋╋┛┗┳┻┓┗┓
┣╋╋┓┏┫┏┛┏┫
┗┛┗┻┻┻┻━┻┛

Cool. Looking at this and several other puzzles, it seems like it would be a good generic framework to work out. Given a definition for a puzzle with an is_valid function (can_neighbor here), a constrain function, and the backtracking code above, it should be able to solve a large class of puzzles. Sudoku, for example, or Hashi. Both puzzles I've been working on solvers for. Even better, once you have a solver you can use it to generate puzzles with a difficulty gradient. Just solve each puzzle, keeping track of how many times you had to backtrack and how many were solved with the constraints.

And that's it. A fun little puzzle.

    comments powered by Disqus