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   #
###########################################################################################