# Optimizing puzzle game involving sequence numbers

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. • Please confirm, that you want an optimized algorithm. And not just optimizing execution time, memory usage or best practices on coding. Commented Jun 14, 2014 at 10:00 • Well my ultimate goal is to reduce the execution time of this algorithm. Commented Jun 16, 2014 at 13:41 • 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). Commented Jun 17, 2014 at 7:48 • 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. Commented Aug 27, 2014 at 14:38 ## 1 Answer 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("&nbsp;",$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.