Recursive DFS Problem

Question

I have been struggling with this contest problem for awhile now which is found at this link: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/2009/b.pdf

Short summary of problem: Given an n×m board (3 ≤ n≤6, 5≤m≤50) move a Blenjeel sand worm (of length n) from the left column to the right column, ensuring the worm never simultaneously occupies two squares of the same color.

It's acceptable for the worm to reach the right column in either orientation. The worm can move either from its head or tail, meaning that if the head moves (at any particular time) to a new valid position on the grid, the tail would now be located at the "second to last" square of where the tail was previously located. The same idea occurs if the tail were to be moved instead.

Given an input of ints which represents a board such as:

12324

31312

41431

output the minimum number of moves needed to move the worm from the left column to the right column, or -1 if there is no such solution.

My current train of thought is a recursive DFS that calculates the min path the worm can take from the left column to the right column. This is done by keeping track of the number of moves at each recursive call, as well as making sure we don't have duplicate colors in the worm at anytime, and avoiding cycles by not letting the worm visit a configuration that was already visited (provided the repeated visit happens in the same recursive path). This solution semmed good to me initially but it does not seem to pass some of the test cases.

I have been stumped for awhile now and I was wondering if anyone has any idea on how to correctly approach this problem? Any hints/ideas are appreciated.

Answer 1

You can use BFS to find a shortest path as long as you specify what "vertices" and "edges" are in this graph. One way is the following:

A vertex is an ordered list (call it $L$) of $n$ ordered pairs (representing locations in the grid) such that

1. consecutive pairs are "neighbors",
2. $n$ unique locations are present,
3. $n$ unique colors are present.

But because the worm is reversible, this set of vertices is further subject to the relation that any vertex represented by $L$ can also be represented by $L^{rev}$.

Next we define edges: $v_1$ is joined to vertex $v_2$ if they can be represented by lists $L_1$ and $L_2$ such that the first $n-1$ pairs of $L_2$ equal the last $n-1$ pairs of $L_1$.

During your implementation you might choose canonical (1 of the 2 possible) representatives of each vertex so that you can mark which vertices have been traversed. You might also define a subroutine to generate all neighboring vertices from a given vertex. To sum up, the vertices are all valid "states" that the worm can be in. And the problem becomes finding the distance between the vertex represented by $[(0,0), (1,0), \ldots, (m-1,0)]$ to the vertex represented by $[(0, n-1), (1, n-1), \ldots, (m-1,n-1)]$ .If the latter is not a vertex then you can just return false.