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:
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.