Hlavolam II

... Petr Blahoš, 2. 11. 2018 Python

V minulém díle jsme pomocí OpenCV oskenovali hlavolam a převedli jsme jej do formy, stravitelné pro počítač. Naznačil jsem, že budeme tento hlavolam řešit pomocí počítače. Po rozmyšlení jsem ale došel k závěru, že je to zatím pro to nebohé pachole moc složité (datové struktury, rekurze), takže se věnujeme něčemu jinému, a zde Vám jen předestřu hotové řešení.

Řešení

PUZZLE = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 5, 4, 4, 8, 3, 3, 4, 6, 3, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 4, 5, 1, 1, 1, 4, 5, 1, 7, 1, 3, 5, 0, 0, 0, 0],
    [0, 0, 0, 4, 9, 4, 9, 6, 7, 5, 5, 5, 8, 7, 6, 6, 8, 5, 0, 0, 0],
    [0, 0, 3, 7, 2, 9, 8, 3, 5, 6, 7, 3, 9, 1, 8, 7, 5, 8, 5, 0, 0],
    [0, 0, 1, 4, 7, 8, 4, 2, 9, 2, 7, 1, 1, 8, 2, 2, 7, 8, 3, 0, 0],
    [0, 7, 2, 1, 8, 5, 5, 3, 1, 1, 3, 1, 3, 3, 4, 2, 8, 6, 1, 3, 0],
    [0, 4, 2, 6, 7, 2, 5, 2, 4, 2, 2, 5, 4, 3, 2, 8, 1, 7, 7, 3, 0],
    [0, 4, 1, 6, 5, 1, 1, 1, 9, 1, 4, 3, 4, 4, 3, 1, 9, 8, 2, 7, 0],
    [4, 3, 5, 2, 3, 2, 2, 3, 2, 4, 2, 5, 3, 5, 1, 1, 3, 5, 5, 3, 7],
    [2, 7, 1, 5, 1, 1, 3, 1, 5, 3, 3, 2, 4, 2, 3, 7, 7, 5, 4, 2, 7],
    [2, 5, 2, 2, 6, 1, 2, 4, 4, 6, 3, 4, 1, 2, 1, 2, 6, 5, 1, 8, 8],
    [0, 4, 3, 7, 5, 1, 9, 3, 4, 4, 5, 2, 9, 4, 1, 9, 5, 7, 4, 8, 0],
    [0, 4, 1, 6, 7, 8, 3, 4, 3, 4, 1, 3, 1, 2, 3, 2, 3, 6, 2, 4, 0],
    [0, 7, 3, 2, 6, 1, 5, 3, 9, 2, 3, 2, 1, 5, 7, 5, 8, 9, 5, 4, 0],
    [0, 0, 1, 6, 7, 3, 4, 8, 1, 2, 1, 2, 1, 2, 2, 8, 9, 4, 1, 0, 0],
    [0, 0, 2, 5, 4, 7, 8, 7, 5, 6, 1, 3, 5, 7, 8, 7, 2, 9, 3, 0, 0],
    [0, 0, 0, 6, 5, 6, 4, 6, 7, 2, 5, 2, 2, 6, 3, 4, 7, 4, 0, 0, 0],
    [0, 0, 0, 0, 2, 3, 1, 2, 3, 3, 3, 2, 1, 3, 2, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 7, 4, 4, 5, 7, 3, 4, 4, 7, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]


def widen_puzzle(puzzle):
    """
    Adds 10 empty cells (value 0) on each side of the field.
    """
    sz0 = len(puzzle)
    sz1 = sz0 + 20
    out = [[0] * sz1 for i in range(sz1)]
    for i in range(sz0):
        for j in range(sz0):
            out[i + 10][j + 10] = puzzle[i][j]

    return out


DIRS = [
    (-1, 1), (-1, 0), (-1, -1),
    (0, 1),           (0, -1),
    (1, 1),  (1, 0),  (1, -1),
]


def make_border(puzzle):
    """ changes the value to -1 on the puzzle borders. """
    sz = len(puzzle)
    for i in range(5, sz - 5):
        for j in range(5, sz - 5):
            if puzzle[i][j]:
                continue
            for (dx, dy) in DIRS:
                if puzzle[i + dx][j + dy] > 0:
                    puzzle[i][j] = -1
                    break


def deep_solve(puzzle):
    """ Finds all solutions of the puzzle. """
    puzzle = widen_puzzle(puzzle)
    make_border(puzzle)

    path = [(20, 20), ]
    dirs = []
    visited = set()
    follow_path(puzzle, path, dirs, visited)


def follow_path(puzzle, path, dirs, visited):
    """
    Makes one step in every direction from the last point (path[-1])
    one by one, and recursively calls itself to follow the path.
    """
    if not path:
        return
    for (dx, dy) in DIRS:
        (x, y) = path[-1]
        val = puzzle[x][y]
        (xx, yy) = (x + val * dx, y + val * dy)
        if (xx, yy) in visited:
            continue
        visited.add((xx, yy))
        try:
            path.append((xx, yy))
            dirs.append((dx, dy))

            if 0 == puzzle[xx][yy]:
                continue  # outside
            if -1 == puzzle[xx][yy]:
                if puzzle[xx + dx * -1][yy + dy * -1] > 0:
                    print_path(puzzle, path, dirs)
                continue  # border
            follow_path(puzzle, path, dirs, visited)
        finally:
            del dirs[-1]
            del path[-1]


def print_path(puzzle, path, dirs):
    print("%s, " % (dirs, ))


if "__main__" == __name__:
    deep_solve(PUZZLE)

Pár slov:

  • PUZZLE je to pole, které jsme dostali z algoritmu počítačového vidění v minulém díle.
  • Nejprve jej rozšíříme o 10 prázdných polí z každé strany. Tím pádem nebudeme při skákání muset hlídat, jestli jsme uvnitř pole, nebo ne.
  • Dále na hranici doplníme hodnotu -1. Tím pádem, když skočíme a jsme na hodnotě 0, tak jsme venku. Když jsme na hodnotě -1, tak jsme na hranici, což ovšem ještě není jistě řešení.
  • Když se postavíme na druhé políčko od konce třetího řádku (je tam číslo 3, za ním je 5, tak na tu trojku), a jdeme doleva nahoru, ocitneme se na políčku, které je na hranici, čili vypadá to, že jsme našli řešení. Ale řešení to, jak asi chápete, není.
  • No a pak už jen začneme uprostřed (funkce deep_solve), připravíme pole s dosavadní cestou (path) a s dosavadními směry (dirs) a zavoláme funkci follow_path, která udělá 1 krok (postupně ve všech směrech) a rekurzivně zavolá sama sebe.
  • Cestou si ještě ukládáme navštívená políčka, jinak bychom se mohli zacyklit.
  • Když algoritmus najde řešení, vypíše směry, kterými se postupně má jít. Netvrdím, že ta řešení jsou nejoptimálnější. Vyšla 187 kroků dlouhá.