How to store results from recursive function with unknown depth?

Question

I recently came across a game that generates a NxN (2x2, 4x4...) board with numbered tiles (1, 2, 3...), where each number determines the allowed moves. Goal is to empty the whole board, if possible, while every tile can be used only once.

A small board could look like this:

| 1 1 |  
| 1 1 |

larger board:

| 1 2 2 3 |  
| 2 1 1 1 |  
| 3 2 1 3 |  
| 2 2 3 1 |

Since I often stumbled across the situation where a solution was not possible, I tried to write a short script that checks if a solution can be found or not before the board is used.

While this worked partially, checking every possible combination and storing all results separately became more complicated and I'm not even sure if this is possible at all.

Here's the simplified example:

$tiles[1][1] = 'p1';
$tiles[2][1] = 'p1';
$tiles[1][2] = 'p1';
$tiles[2][2] = 'p1';

$moves = array(
                array('x' => -1, 'y' => -1),
                array('x' =>  0, 'y' => -1),
                array('x' =>  1, 'y' => -1),
                array('x' => -1, 'y' =>  0),
                array('x' =>  1, 'y' =>  0),
                array('x' => -1, 'y' =>  1),
                array('x' =>  0, 'y' =>  1),
                array('x' =>  1, 'y' =>  1)
            );

function nextMove($x, $y, &$visited)
{
    global $moves;

    $max_loops = count($moves);
    $visited[] = $x. ', ' .$y;

    for ($j = 0; $j < $max_loops; $j++)
    {
        $new_x = $x + $moves[$j]['x'];
        $new_y = $y + $moves[$j]['y'];

        if (($new_x >= 1) && ($new_x <= 2) && ($new_y >= 1) && ($new_y <= 2))
        {
            $new_pos = $new_x. ', ' .$new_y;

            if (!in_array($new_pos, $visited))
            {
                $j = $max_loops - 1;

                nextMove($new_x, $new_y, $visited);
            }
        }
    }
}

nextMove(1, 1, $visited, $moves_done);
var_dump($visited);

So, what happens here is rather simple:

The function gets called with the initial coordinates, counts the maximum amount of moves (for that tile) and adds the current position to the $visited array.

After that, the for loop iteartes through the array of possible moves, generates new coordinates and checks if they are on the board or if that tile has been 'visited' before. If a valid move was found, the function gets called again with the new coordinates.

(As you can see $j = $max_loops - 1; ends the loop here to avoid wrong values added to $visited, if no valid move was found later)

This is what happens right now:

array(4) {
  [0]=>
  string(4) "1, 1"
  [1]=>
  string(4) "1, 2"
  [2]=>
  string(4) "2, 1"
  [3]=>
  string(4) "2, 2"
}

So far the script is working, but as soon as there's no possible move, the script ends and doesn't check further combinations (with $j = $max_loops - 1;) or adds wrong coordinates to $visited. To avoid this I either have to store the results separately or change the function and this is where I got stuck.

One big problem is the unknown amount of possible moves, because sometimes the game ends after 2 moves, sometimes the board can be cleared.

Is there any way to get the function to iterate through all possible combinations and store/return them separately (might be too much to handle and not neccesary, but could be interesting if only 1-2 tiles can't be used) OR at least check if the whole board can be cleared and return the solution (this is important, because the result should get stored and used later)?

The script should work this way:

array(4) {
  [0]=>
  string(4) "1, 1"
  [1]=>
  string(4) "1, 2"
  [2]=>
  string(4) "2, 1"
  [3]=>
  string(4) "2, 2"
}
array(4) {
  [0]=>
  string(4) "1, 1"
  [1]=>
  string(4) "1, 2"
  [2]=>
  string(4) "2, 2"
  [3]=>
  string(4) "2, 1"
}
array(4) {
  [0]=>
  string(4) "1, 1"
  [1]=>
  string(4) "2, 1"
  [2]=>
  string(4) "1, 2"
  [3]=>
  string(4) "2, 2"
}
array(4) {
  [0]=>
  string(4) "1, 1"
  [1]=>
  string(4) "2, 1"
  [2]=>
  string(4) "2, 2"
  [3]=>
  string(4) "1, 2"
}
array(4) {
  [0]=>
  string(4) "1, 1"
  [1]=>
  string(4) "2, 2"
  [2]=>
  string(4) "2, 1"
  [3]=>
  string(4) "1, 2"
}
array(4) {
  [0]=>
  string(4) "1, 1"
  [1]=>
  string(4) "2, 2"
  [2]=>
  string(4) "1, 2"
  [3]=>
  string(4) "2, 1"
}

[...]

I didn't understand how the game works, could you explain it better? How do you clear the board? — Alvaro Flaño Larrondo
– Alvaro Flaño Larrondo, Commented Nov 7, 2015 at 14:33
I'll try to explain better how it works: You start the game by clicking on any tile on the board. The number determines which tile(s) can be clicked next, either horizontally, vertically oder diagonally. It's a bit like moving the queen on a chess board, I guess, with numbers determining how many squares she has to move. So, if u click on a 3 you have to move 3 tiles, not 1 or 2.. Once you use a tile it gets locked, so you can't use it again (you can still jump over it though). This means, to clear the whole board, you have to find a sequence that contains all tiles IF that's possible. — qlt
– qlt, Commented Nov 8, 2015 at 9:05
You can move only in one direction? So, if you click on a tile with a 3 you can't move 2 tiles left and 1 down.. right? You move 3 tiles vertically, or horizontally or diagonally? — Alvaro Flaño Larrondo
– Alvaro Flaño Larrondo, Commented Nov 8, 2015 at 23:27
Exactly. Just imagine the queen on a chess board, the movement is the same. I actually didn't expect any questions about the game itself, else I would have explained it better in the question. — qlt
– qlt, Commented Nov 9, 2015 at 6:54

Alvaro Flaño Larrondo · Accepted Answer · 2015-11-09 16:01:14Z

1

Ok, here is what I came up with:

<?php

$width = 2;
$height = 2;

$tiles[2][1] = 1;
$tiles[1][2] = 1;
$tiles[1][1] = 1;
$tiles[2][2] = 1;

$directions = array(
                array('x' => -1, 'y' => 0),
                array('x' => -1, 'y' => 1),
                array('x' => 0, 'y' => 1),
                array('x' => 1, 'y' => 1),
                array('x' => 1, 'y' => 0),
                array('x' => 1, 'y' => -1),
                array('x' => 0, 'y' => -1),
                array('x' => -1, 'y' => -1)
            );

$valid_paths = array();

function nextMoves($position, $visited = array()){
    global $directions, $tiles, $valid_paths, $height, $width;

    $visited[] = $position;
    if(count($visited) == $width * $height){
        $valid_paths[] = $visited;
        return;
    }

    $next_moves = array();
    $position = explode(',', $position);
    $x = $position[0];
    $y = $position[1];

    $tile_value = $tiles[$x][$y];

    foreach($directions as $direction){
        $new_x = $x + $direction['x'] * $tile_value;
        $new_y = $y + $direction['y'] * $tile_value;
        $new_pos = "$new_x,$new_y";

        if (($new_x >= 1) && ($new_x <= $width) && ($new_y >= 1) && ($new_y <= $height) && !in_array($new_pos, $visited)){
            $next_moves[] = $new_pos;
        }
    }

    foreach($next_moves as $next_move){
        nextMoves($next_move, $visited);
    }   
}

nextMoves('1,1');

echo "<pre>";
var_dump($valid_paths);
echo "</pre>";

?>

Explanation

The function nextMoves will add to the global variable $valid_paths all the valid paths starting form a given positon.
First it checks if all the tiles have been visited. If that's true it adds the $visited array to the $valid_paths
If not all tiles have been visited it adds the current $position to the $visited array.
Next it iterates over every $directionand if it is possible to move in that direction to a tile that is in the grid and not visited it adds that new tile as a valid next move.
After it has finished calculation all the possible valid next moves it starts over for every new $position with the new $visted ones.

I have improved a little more the code. It can generate valid boards with a set amount of possible answers. I won't post the code here as it is not relevant for thw answer. You can check the improved code in this PHPFiddle.

edited Nov 9, 2015 at 16:01

answered Nov 9, 2015 at 15:00

Alvaro Flaño Larrondo

5,7402 gold badges31 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

qlt Over a year ago

Just had a few minutes and so far the example works. However, I'm not sure if this will still work on larger boards (e.g. 4x4 or even more) without massive performance issues.. and if there's a better way to handle the function/output (e.g. only return the first possible solution and stop the script, return the 'best' solution if it's not possible to clear the board and so on..). Hope I got some time later to take a look at it.

Alvaro Flaño Larrondo Over a year ago

You can take the code above and edit it to return only the first possible solution, or even the better one if there is none. As it is it can handle 4x4 boards and find all the answers befere exceeding PHP's default execution time limit. If you need any more help let me know.

qlt Over a year ago

How would you change the code to return only the first possible / best solution? I have to admit that I didn't use php / recursive functions for a while, so I might overlook even obvious things..

Alvaro Flaño Larrondo Over a year ago

For the first solution you need to add some breakpoints. For the the best solution when there is no solution, you need to keep track of the longest visited array. I created a new PHPFiddle. Take a look at it. It can generate up to 4x4 boards with possible solutions and show the best solution for boards of any size. If you liked my answer please select it as the correct one.

qlt Over a year ago

I did some testing again and so far it's working, except the part where the script should stop after the first result. While your solution works for creating a new board, it won't work for an existing board of course. Most of the time the sequence will just end not even close to the best solution. For this reason, larger boards often hit the execution time limit. Not sure if it's possible to reduce the load here at all, but any advice is highly appreciated!

|

Collectives™ on Stack Overflow

How to store results from recursive function with unknown depth?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related