Optimizing puzzle game involving sequence numbers
I've dug into the concept a little bit and as a start here are some bits of code and discussion to help out. Obviously, the real meat here is doing the backtracking efficiently but I think starting with simplifying the problem a bit would help.

For starters, it seems that turning the grid into a simple list would make it easier to deal with the relevant code.

// Initialize game parameters
// --------------------------
$game = array();
$game['xlen']    = 4;
$game['ylen']    = 4;
$game['blocked'] = 1;
$game['size']    = $game['xlen'] * $game['ylen'];
$game['playing'] = 0;

// Initialize empty grid
// ---------------------
$grid = array();
for ( $i = 0; $i &lt; $game['size']; $i++ )
  $grid[] = 0;

// Let's take a look
// -----------------
echo "Initialized game grid...&lt;br&gt;&lt;br&gt;\n";
dump_grid($game,$grid,3);


So, here's a grid dumping function that will allow very detailed insight into the behavior of the running program in case it isn't doing exactly what one might expect.

// It's always important to be able to "see" what is happening to get insight
// into what is working and what isn't.
// --------------------------------------------------------------------------
function dump_grid($game,$grid,$indents = 0)
{
  // Build up indent value
  // ---------------------
  $indent = '';
  if ( $indents )
  {
    $indent = str_repeat("&amp;nbsp;",$indents);
    echo $indent;
  }

  // Dump out grid contents
  // ----------------------
  $x = 0;
  foreach ($grid as $value)
  {
    echo "| " . sprintf("%02d",$value) . " ";

    $x++;
    if ( $x &gt;= $game['xlen'] )
    {
      echo "|&lt;br&gt;\n$indent";
      $x=0;
    }
  }
  echo "&lt;br&gt;\n";
}


Using the above I can watch events unfold in the following manner... as I like to iterate code/test efforts by reloading the code in a browser page.




Initialized game grid...

   | 00 | 00 | 00 | 00 |
   | 00 | 00 | 00 | 00 |
   | 00 | 00 | 00 | 00 |
   | 00 | 00 | 00 | 00 |

Sample blocked square...

   | 00 | 00 | 00 | 00 |
   | -1 | 00 | 00 | 00 |
   | 00 | 00 | 00 | 00 |
   | 00 | 00 | 00 | 00 |

Starting position selected...

   | 00 | 00 | 00 | 00 |
   | -1 | 00 | 00 | 00 |
   | 00 | 00 | 00 | 00 |
   | 00 | 00 | 00 | 01 |



Of course, the hard part is left. What I would consider doing at this point is using the "grid" to store game state with respect to blocked squares and moves and maintaining a separate move tree to ensure that random selection doesn't end up trying failed branches over and over.

Using your game objects, or mine, a method of maintaining the known failing moves from a given state will be needed. That could be integrated into a move selection function. I have a rudimentary move selection function used to choose the blocked location and starting point in the above.



// Pick a random grid position. Optional parameter to force game placement
// rules to be applied when picking a position.
// --------------------------------------------------------------------------
function pick_open($game,$grid,$playing = 1)
{
  $open = array();
  for ($i=0; $i &lt; $game['size']; $i++)
    if ( $grid[$i]==0 )
      $open[$i] = $i;

  if ( !count($open) )
    die("Attempting to pick an open spot when none are available!");

  if ( !$playing )
    return array_rand($open,1);

  die("Rules based open spot select not yet implemented!");
}


As I'm trying to help and not create the whole solution I'll have to leave that to you. However, I would strongly suggest making the effects of your code as visible as possible and looking for ways to simplify the problem.

Hint: Perhaps use the game state (the grid being output) as a key to determine if any moves from that state have already proven to be failures.

Note: If you weren't using random move selection you could just iterate through all possible moves and accept the first valid solution. However, a non-random iteration might make a game too predictable.