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.

• DanielaWaranie: Please confirm, that you want an optimized algorithm. And not just optimizing execution time, memory usage or best practices on coding.
• Sanober Malik: Well my ultimate goal is to reduce the execution time of this algorithm.
• SylvainD: Hi, would you be able to provide other pieces of code such as getPossibleMoves. Also, an example would be a nice touch (and a corresponding drawind would make this awesome).
• Schism: Is there a specific reason as to why you're selecting a random move rather than just iterating through the possible moves? Also, I second Josay's request; could you please provide the code for getPossibleMoves()? It would greatly help in understanding your question and the mechanics of your puzzle.

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.