Optimizing puzzle game involving sequence numbers

Question

I am currently developing a puzzle game that has sequence numbers. The player has to fill the grid with sequence numbers in ascending order. Starting from 1 the player can move horizontally or across and can skip a square in between if it is empty or blocked.

To generate the puzzle automatically, my code is doing the following process:

1. Make some of the squares blocked.
2. Select a random position for 1 and calculate the possible moves for 2.
3. Select a move from possible moves of 2 and store other possible moves in an array so that they can be used for while backtracking if I don't get the solution.
4. Proceed and backtrack if I don't get a solution.

The grid of puzzle can be anywhere between 4x4 and 9x9.

$possibleMoves = getPossibleMoves($rowForOne,$columnForOne,$solution,$value);
$puzzleSolvedFlag = false;


while($value <= $maximumNumberToBeEntered) {
    $randomMove = array_rand($possibleMoves);
    $position = explode(",",$possibleMoves[$randomMove]);
    unset($possibleMoves[$randomMove]);
    array_push($moves,$possibleMoves);
    $solution[$position[0]][$position[1]] = $value;
    $value++;
    $possibleMoves = getPossibleMoves($position[0],$position[1],$solution,$value);
//  echo $value;
    //print_r($possibleMoves);
    while(count($possibleMoves)==0 && $value<=$maximumNumberToBeEntered) {
        $possibleMoves = array_pop($moves);
        //print_r($possibleMoves);
        $value--; 

        foreach ($solution as &$v1) {
            foreach ($v1 as &$v2) {
               if($v2 >= $value) {
                    $v2 = -1;
                }
            }
        }
        if(count($possibleMoves) > 0) {
            break;
        }
    }
    //print_r($possibleMoves);
}

The solution is the array grid. Before the above code I just selected a random move for 1 and the $value will be 2. getPossibleMoves() returns possible moves for 2.

$maximumNumberToBeEntered is the maximum value in the grid (e.g. for a 4x4 grid, if 3 squares are blocked, then the maximum value will be 16-3 = 13).

Can someone help me to optimize the above code? It involves a lot of backtracking.

Answer 1

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 < $game['size']; $i++ )
  $grid[] = 0;

// Let's take a look
// -----------------
echo "Initialized game grid...<br><br>\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(" ",$indents);
    echo $indent;
  }

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

    $x++;
    if ( $x >= $game['xlen'] )
    {
      echo "|<br>\n$indent";
      $x=0;
    }
  }
  echo "<br>\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 < $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.