Find a continuous path filling whole 3xN grid going through certain points in given order

Question

I've got a grid consisting of squares that is 3 squares high and N squares long. Some of the squares are filled with numbers that are not greater than 3*N. You can move only to squares that are below, above, on right, or left from you. When you move on a square, you fill that square with a number of the amount of moves you have already taken + 1. If square is already filled with a number, you can move onto it, only if the sum steps you've have taken + 1 is equal to the number on the square.

I need to find a continous path that leads through all the squares of the grid only once and output the same grid filled with numbers corresponding to the steps of your path. In other words, a path was previously laid out on the grid and then some numbers have been erased from squares. Now I have to retrace that path.

I should be done in O(N^2), but I will be thankful for any solutions.

Answer 1

Hint: if this is a homework problem that comes up in a chapter on graphs, you might want to consider forming a graph.

A common pattern in applications of graphs is to let each node in the graph represent the "state" of the world at some point in time, and then use that graph somehow.

Suppose you're following some continuous path through this grid, and at some point in time in the middle of your traversal, I yell "freeze!", temporarily pause time, and look at the state of the world at that point in time (ignoring past or future). What information do I need to record, to fully describe the state of the world (where you are) at that point in time? How many different possible states are there? Now create a graph where ..., and..... (you fill in the rest)