CODEWITHSUNDEEP
phpalgorithmbreadth-first-searchsliding-tile-puzzle
Trsak
Trsak

Reputation: 303

Solving 3x3 puzzle with PHP using Breadth-first search

i am making a 3x3 puzzle solver using php. Zero is the free space, where you can move. For example: 

1 2 3  
4 0 5  
7 8 6

To 

1 2 3  
4 5 0  
7 8 6

To 

1 2 3  
4 5 6  
7 8 0

I already made random generator - 50 random moves are made. But I'm stack, with the solver algorithm.

The output should be all the steps to solve it.

I already got working method to solve one-step puzzle, but i dont know how to use it recursively. 

public function makeMoves($elements)
{
    $pos = $this->findSpace($elements); //returns position of the free space

    $actions = $this->findActions($pos); //returns all actions positions (left, right, top, bottom)

    $possibleActions = $this->findPossibleActions($actions); //return number of possible actions

    for ($i = 1; $i <= $possibleActions; ++$i) { //let's do all possible actions
        $move = $this->selectAction($actions, $i, $pos); //get new position for the space
        $perform = $this->performAction($elements, $pos, $move); //swap the space with the element on that position

        $this->tree[] = new Elements;

        end($this->tree);
        $last_id = key($this->tree);

        $this->tree[$last_id]->setState($perform);
        $this->tree[$last_id]->setAncestor(0);

        $step = [$move, $pos];

        $this->tree[$last_id]->setStep($step);

        if ($perform == $this->elementsDone) { 
            return $this->tree[$last_id];
        }
    }
}

Upvotes: 1

Views: 985

Answers (1)

btilly
btilly

Reputation: 46497

One solution is to use the A* algorithm to find the shortest path to a solution. Each move has cost 2. Each position has a distance from the desired solution of the sum of the distances each piece has to move. (One corner to the other is distance 4.) You are guaranteed to find the shortest solution if there is one.

See http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript for an implementation of that algorithm.

Be warned that half of all random configurations will NOT be solvable. See https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html for a test to tell you which ones to throw away. It also gives hints for how to write an algorithm which takes less memory than the one I suggested and finds inefficient solutions, but will do less work to find those solutions.

Upvotes: 1

Related Questions