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:
- Make some of the squares blocked.
- Select a random position for
1
and calculate the possible moves for2
. - 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. - 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.
getPossibleMoves
. Also, an example would be a nice touch (and a corresponding drawind would make this awesome). \$\endgroup\$ – SylvainD Jun 17 '14 at 7:48getPossibleMoves()
? It would greatly help in understanding your question and the mechanics of your puzzle. \$\endgroup\$ – Schism Aug 27 '14 at 14:38