Python:

HW #3 Jumping frogs puzzle https://primefactorisation.com/frogpuzzle/ X 8 X 9 X US Rules: Send all frogs X's to the right hand side of the pond, and all Y's to the left. Frogs move (forward only) by hopping over a frog or sliding onto the empty spot (lily pad). * Solution: Generate all possible senarios to move frogs and pick up the solutions. * For example, assume we have two frogs z's and two frogs A's on each side of the empty lily pad. First, define "state" as the positions of frogs with a string of z's, A's and "-" denoting the empty lipy pad. * Starting from the initial state (ZZ-AA) * Enumerate all unique states from each state at current step. * Repeat the above step until the target state (AA-ZZ) is reached. * Use the backgtrace technique to find all sequences of moves from the start state to the final state. o: ok Initial state -- New states reached in 1 step 1: -XXYY X-XYY XXY-Y XXYY- 2: KYK-Y, X-YXY