Solving a 3x3 frog puzzle with python

Question

This is a puzzle where your goal is to pair frog heads with bodys on the inner edges. The included picture shows the solved puzzle.

I have thought about how to solve this puzzle in Python. My idea was to represent the tiles as an array of 2x2 numpy matrices like [["RB", "GB"], ["BB", "GH"]] for example, and then just looping through all the permutations and checking if the frogs match on the edges. However this approach would not take in to account rotations, which could be done with numpy.rot90() on the individual matrices.

I don't know if this would be a feasible solution or if i have taken the wrong approach to solving this.

Answer 1

You have very interesting task. I implemented my own solution which should be very fast, because it uses Numba which usually boosts Python code 50x-200x times on average.

My algorithm is based on backtracking approach, and is non-recursive (it uses stack).

It finds and prints all possible solutions, not just first one. See end of my answer to see output of results in console. First number of solutions is printed, then all solutions in ASCII-graphical form.

Also my algorithm is generic, meaning that you may provide as many tiles as you have, number of tiles provided can be larger than rectangle to be covered (but not less), rectangle is not limited to 3x3, it can have arbitrary height and width, width and height may be non-equal too. E.g. you can use 20 tiles to cover rectangle of shape 4x3, so that 12 tiles will be used in solutions and 8 unused.

Input data of algorithm is located inside test() function. It calls find(l, h, w) function where a is list of all existing tiles, h and w are height and width (counted in tiles) of rectangle to be covered.

Input tiles are in next format: each tile should have exactly 4 string elements, each string element should exactly 2 chars, first char signifies color, r: red, g: green, b: blue, h: brown; second char is frog side, b: bottom, t: top (e.g. 'bt' means blue top of frog). 4 elements mean 4 sides of tile, first: right, second: top, third: left, fourth: bottom.

In order to run my script you have to install two module one time only through command line python -m pip install numpy numba.

I hope that thanks to back-tracking and Numba my algorithm can solve task for very many number of tiles.

Also forgot to mention, my algorithm can also be run to find not all possible solutions but just any first solution, in order to find only first just pass True as last param of find function, i.e. run find(l, h, w) if you want to find all solutions and run find(l, h, w, True) if you want just very first one.

Try following code online!

import numpy as np, numba

@numba.njit(cache = True)
def nfind(a, h, w, first):
    hw = h * w
    n = a.shape[0]
    taken = np.zeros((n,), dtype = np.bool_)
    rot = np.zeros((h, w), dtype = np.int32)
    idx = np.zeros((h, w), dtype = np.int32)
    stack = np.zeros((hw, 2), dtype = np.int32)
    ans = np.zeros((0, h, w, 2), dtype = np.int32)
    i, r, istack = 0, 0, 0
    while True:
        y, x = istack // w, istack % w
        if i >= n or istack >= hw:
            if istack >= hw:
                cans = np.zeros((1, h, w, 2), dtype = np.int32)
                for i0 in range(h):
                    for i1 in range(w):
                        cans[0, i0, i1] = idx[i0, i1], rot[i0, i1]
                ans = np.concatenate((ans, cans))
                if first:
                    return ans
            istack -= 1
            if istack < 0:
                return ans
            i, r = stack[istack]
            taken[i] = False
            i, r = i + (r + 1) // 4, (r + 1) % 4
        elif (
            not taken[i] and
            (y == 0 or a[idx[y - 1, x], (rot[y - 1, x] + 3) % 4] == a[i, (r + 1) % 4] ^ 1) and
            (x == 0 or a[idx[y, x - 1], (rot[y, x - 1] + 0) % 4] == a[i, (r + 2) % 4] ^ 1)
        ):
            stack[istack] = i, r
            taken[i] = True
            idx[y, x] = i
            rot[y, x] = r
            istack += 1
            i, r = 0, 0
        else:
            i, r = i + (r + 1) // 4, (r + 1) % 4

def find(l, h, w, first = False):
    a = np.zeros((len(l), 4), dtype = np.uint8)
    col, sid = 'rgbh', 'bt'
    for i, x in enumerate(l):
        assert len(x) == 4, x
        for j, y in enumerate(x):
            assert len(y) == 2, y
            a[i, j] = (col.index(y[0]) << 1) | sid.index(y[1])
    r = nfind(a, h, w, first)
    print('Number of solutions: ', r.shape[0], '\n')
    s = []
    for i in range(r.shape[0]):
        ss = []
        for y in range(h):
            sss = []
            for x in range(w):
                e = []
                for j in range(4):
                    e += [l[r[i, y, x, 0]][(r[i, y, x, 1] + j) % 4]]
                sss += [[
                    f'  {e[1]}  ',
                    f'{e[2]}  {e[0]}',
                    f'  {e[3]}  ',
                ]]
            ss += [sss]
        s += [ss]
    bl = 4
    for i in range(0, len(s), bl):
        lines = [''] * (len(s[0]) * 4 - 1)
        for ie, e in enumerate(s[i : i + bl]):
            for y in range(len(s[0])):
                for x in range(len(s[0][0])):
                    for il, l in enumerate(e[y][x]):
                        lines[y * 4 + il] += l + ('|', ' # ')[x + 1 >= len(s[0][0])]
                    if y + 1 < len(s[0]):
                        lines[y * 4 + 3] += '-' * (7, 6)[x + 1 >= len(s[0][0])]
                        if x + 1 >= len(s[0][0]):
                            lines[y * 4 + 3] += ' # '
        lines += ['#' * (len(lines[0]) - 1)]
        for l in lines:
            print(l)
            
def test():
    find([
        ['gt', 'bt', 'bb', 'rb'], ['bt', 'hb', 'gb', 'rt'], ['bt', 'rb', 'bb', 'ht'],
        ['bb', 'rt', 'gt', 'hb'], ['bb', 'rb', 'bt', 'gt'], ['rb', 'hb', 'bt', 'gt'],
        ['rb', 'ht', 'gt', 'hb'], ['hb', 'gb', 'rt', 'gt'], ['rb', 'gb', 'ht', 'bt'],
    ], 3, 3)

if __name__ == '__main__':
    test()

Console output:

Number of solutions:  8

  bt  |  hb  |  rb   #   gt  |  gb  |  rb   #   bt  |  rb  |  rb   #   gt  |  bt  |  rb   #
bb  gt|gb  bt|bb  bt # bt  rb|rt  hb|ht  hb # rb  ht|hb  gt|gb  bt # hb  rt|rb  ht|hb  gt #
  rb  |  rt  |  ht   #   bb  |  gt  |  gt   #   bb  |  bt  |  ht   #   bb  |  bb  |  bt   #
-------------------- # -------------------- # -------------------- # -------------------- #
  rt  |  rb  |  hb   #   bt  |  gb  |  gb   #   bt  |  bb  |  hb   #   bt  |  bt  |  bb   #
gt  bb|bt  bb|bt  rb # gt  rb|rt  hb|ht  rb # hb  rt|rb  gt|gb  gt # rb  ht|hb  rt|rb  gt #
  hb  |  gt  |  gt   #   bb  |  bt  |  bt   #   gb  |  bt  |  rt   #   gb  |  gb  |  bt   #
-------------------- # -------------------- # -------------------- # -------------------- #
  ht  |  gb  |  gb   #   bt  |  bb  |  bb   #   gt  |  bb  |  rb   #   gt  |  gt  |  bb   #
gt  rb|rt  hb|ht  rb # gt  hb|ht  rb|rt  hb # bt  rb|rt  hb|ht  hb # hb  ht|hb  rt|rb  bt #
  hb  |  gt  |  bt   #   rb  |  bt  |  gt   #   bb  |  gt  |  gt   #   rb  |  gb  |  gt   #
###########################################################################################
  gt  |  gt  |  bt   #   gt  |  gt  |  bb   #   hb  |  rb  |  hb   #   bt  |  gt  |  hb   #
rb  bt|bb  bt|bb  gt # hb  ht|hb  rt|rb  bt # rb  gt|gb  bt|bb  gt # rb  ht|hb  rt|rb  gt #
  hb  |  rb  |  rb   #   rb  |  bb  |  gt   #   ht  |  ht  |  rt   #   gb  |  gb  |  ht   #
-------------------- # -------------------- # -------------------- # -------------------- #
  ht  |  rt  |  rt   #   rt  |  bt  |  gb   #   hb  |  hb  |  rb   #   gt  |  gt  |  hb   #
bt  bb|bt  gb|gt  gb # gt  gb|gt  rb|rt  hb # gb  gt|gb  bt|bb  bt # rb  bt|bb  bt|bb  gt #
  rb  |  hb  |  hb   #   hb  |  bb  |  bt   #   rt  |  rt  |  ht   #   hb  |  rb  |  rt   #
-------------------- # -------------------- # -------------------- # -------------------- #
  rt  |  ht  |  ht   #   ht  |  bt  |  bb   #   rb  |  rb  |  hb   #   ht  |  rt  |  rb   #
gt  bb|bt  gb|gt  rb # bt  gb|gt  hb|ht  rb # gt  bb|bt  bb|bt  rb # bt  bb|bt  gb|gt  bb #
  hb  |  rb  |  hb   #   rb  |  rb  |  bt   #   bt  |  gt  |  gt   #   rb  |  hb  |  bt   #
###########################################################################################

Answer 2

As John Coleman said, brute forcing it is not a good strategy. I had a little go at it. This will hopefully get you started with an iterative approach, constructing the solution step by step.

It would be easier to represent tiles as two-element tuples:

• tile color: 'G' for green, 'P' for purple - more like blue, 'R' for red, and 'B' for brown.
• tile direction: 0 frog looking outwards, and 1 frog looking inwards (towards the center of the tile).

As an example, your encoding 'RB' translates to ('R', 0).

So here are the first two rows:

tiles = [
    [('P', 0), ('P', 1), ('G', 1), ('R', 0)],
    [('G', 0), ('B', 0), ('P', 1), ('R', 1)],
    [('P', 0), ('R', 0), ('P', 1), ('B', 1)],
    [('G', 1), ('R', 1), ('P', 0), ('B', 0)],
    [('P', 1), ('R', 0), ('P', 0), ('G', 1)],
    [('P', 1), ('B', 0), ('R', 0), ('G', 1)],
]

The board would be represented as a 2D array:

np.zeros((2, 3), dtype='object')`

We will iterate over the board and for each position (left to right, top to bottom), search for a suitable tile by iterating over the available tiles. When placing a new tile, there are two constraints (i) horizontal: with tile on the left side and (ii) with tile above. If there is no tile on the left and/or above then the constraint is ignored. Two adjacent frogs must match colors and have opposite directions.

Here is a possible implementation:

for (i, j), _ in np.ndenumerate(board):
    above = None if i == 0 else board[i-1, j][3] # vertical constraint
    left = None if j == 0 else board[i, j-1][2] # horizontal constraint

    for t, tile in enumerate(tiles):
        (c_left, dir_left), (c_up, dir_up), *_ = tile

        if ((not left or (left[0] == c_left and left[1] != dir_left)) and 
            (not above or (above[0] == c_up and above[1] != dir_up))):
            board[i, j] = tile
            tiles.pop(t)

Note: If you run this with a random tiles list it will most likely fail. You should improve this code in order to backtrack to a previous solution whenever it fails to find the next tile (i.e. it reaches the end of the inner loop). Also, this will not account for tile rotations, but you can easily add this feature in the inner loop!