8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Please confirm, that you want an optimized algorithm. And not just optimizing execution time, memory usage or best practices on coding. \$\endgroup\$ – DanielaWaranie Jun 14 '14 at 10:00
  • \$\begingroup\$ Well my ultimate goal is to reduce the execution time of this algorithm. \$\endgroup\$ – Sanober Malik Jun 16 '14 at 13:41
  • 5
    \$\begingroup\$ 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). \$\endgroup\$ – SylvainD Jun 17 '14 at 7:48
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Schism Aug 27 '14 at 14:38
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.