Frog Leap Puzzle with Depth-First Search (DFS)

TL;DR: We solve the classic “frog leap” puzzle with Depth-First Search (DFS) by generating next boards around teh blank and trying jumps before steps. This trick finds the minimal soluton in exactly N^2+2N moves.

The classic frog puzzle looks like this, when 3 frogs from side are used:

The core idea is to try to find a way to map all the frogs around the blank rock (_ in the code) and to run DFS on it. These frogs are maximum 4, thus it is not that tough. In the code, these are b-2, b-1, b+1, b+2 correspondingly:

def neighbours_research(state):
    """
      >*_._*>
      _*<.<*_
      >_._>
      _<._<
    """

    s = list(state)
    b = s.index("_")
    result = []

    # >*_._*>
    if b-2 >= 0 and s[b-2] == ">" and s[b-1] in "<>":
        t = s[:]
        t[b], t[b - 2] = t[b-2], t[b]
        result.append("".join(t))

    # _*<.<*_
    if b+2 < len(s) and s[b+2] == "<" and s[b+1] in "<>":
        t = s[:]
        t[b], t[b+2] = t[b+2], t[b]
        result.append("".join(t))

    # >_._>
    if b-1 >= 0 and s[b-1] == ">":
        t = s[:]
        t[b], t[b-1] = t[b-1], t[b]
        result.append("".join(t))

    # _<._<
    if b+1 < len(s) and s[b+1] == "<":
        t = s[:]
        t[b], t[b+1] = t[b+1], t[b]
        result.append("".join(t))
        
    return result

The 4 results from the starting state look like that:

The magic of the code is that it uses DFS approach, trying each new move first, as a stack (or LIFO). If it is stuck, then the built-in functionality of the stack backtracks and tries the next one. We keep visited set and path. The idea is that the visited is a set, so thus a repetition and endless loop is avoided. The path is the current route from teh start, and with python we append on enter and pop on backtrack.

def solve_frogs_dfs(n):
    start = start_state(n)
    goal = goal_state(n)
    visited = set()
    path = []
        
    def dfs(state: str) -> bool:
        if state in visited:
            return False
        visited.add(state)
        path.append(state)
        if state == goal:
            return True

        for nxt in neighbours_research(state):            
            if dfs(nxt):
                return True
        path.pop()
        return False

    dfs(start)
    return path

In the GitHub example and the YouTube video, I am printing a bit more, but the minimal is the code above. This is a working result from it for 3 frogs per side:

To make the code complete, these are start_state() and goal_state() functions, referred in the dfs() above:

def start_state(n):
    return ">"*n+"_"+"<"*n

def goal_state(n):
    return "<"*n+"_"+">"*n

def print_path(path):
    for row in path:
        print(row)

The complete result with 3 frogs looks like that:

The YT video is here:

The GitHub link is here: https://github.com/Vitosh/Python_personal/tree/master/YouTube/045_Python_Frog_Jump

Enjoy it 🙂