5
$\begingroup$

I hope to have your help to solve the problem I am facing. I'm trying to make an 8-puzzle solver but I'm in doubt about how to select the next board, from the one they have already given me. Below I expose my doubt:

uno

In order to get from the initial state to the final state, I have built some functions, which I explain below. The first function is the one that returns the children so they call them from a particular board, in my case the parent board is the initial state, so their children are:

dos

The following function that I have built returns the amount of pieces that are not in place, so in this example, the misplaced tiles of each son respectively are:

tres

I must mention that zero is not taken into account, to calculate the total of pieces out of place. Finally, the function that calculates manhattan distances also implements it, if we use it in each child we can know its manhattan distance, it is important to remember that zero is not taken into account to calculate in this function, so we obtain:

cuatro

My doubt arises when trying to understand which child board should be selected, because if I use Manhattan distance as a criterion, as you can see there is a tie between board B and C, so I could use it as a tiebreaker criterion, tiles out of place, is say, choose the board that has less tiles out of place, which would take me to take the board C, but in some online applet, select the board A, could someone tell me the reason for choosing the board A and not the board C ?. Thanks in advance, any help is welcome.

$\endgroup$
5
$\begingroup$

I'm certain you cannot choose the best move without look-ahead from those metrics alone:

Let's say you are at a position where you have managed to permute the first row somehow, but the rest of the puzzle is solved. Your first move will be to unsolve either 6 or 8, after which both metrics suggest that you should immediately undo your previous move.

Instead you need either an AI (this seems to be a invitingly machine learnable puzzle), a strategy (eg. "how to move a piece from here to there without disturbing other pieces"), or a brute-force search. ("just try everything, until it works")

The latter one seems like a good call, given that there aren't very many (well under a million) possible positions in the puzzle.


EDIT:

In the comments below, OP talks about wanting to implement the A* algorithm. In that case, it doesn't matter if the heuristic guesses wrong from time to time, as long as it helps prune out at least some possibilities. As an answer to the actual question in that case, breaking ties isn't important, since the A* algorithm will just try the other moves if the first one didn't lead to the solved state by greedy, always-heuristic-improving moves. (The algorithm will store all the untried possible moves in a priority queue, so it can always pick the next best attempt if the selected move didn't immediately reach the goal.)

Also, in the comments I claimed that the Manhattan Distance was going to be too low of a lower bound (for estimating the number of remaining moves) to give any advantage over a "dumb" Breadth-first search.

Well, it turns out I was mistaken.

I wrote a small Perl script that tracks the A-star algorithm with Manhattan Distance as the heuristic, and it turns out it's surprisingly effective for this particular puzzle, reducing the searched position space by more than one order of magnitude. (I guess this must mean that there are surprisingly many different positions from which there is a "manhattanly greedy" path to the optimal solution.)

After toying with the solver for some time, it seems that the Manhattan Distance will only need to increase a limited number of times during the search process, and at the end of each path to the optimal solution, there's usually a very long run (typically at least 5 moves, often more) of continuously diminishing Manhattan Distances, which explains much of the efficiency gains.

As a side effect of this exercise, I learned that the puzzle has exactly $\frac{9!}{2}=181440$ reachable positions, and as many unreachable ones.

$\endgroup$
  • $\begingroup$ Thanks for your comment it is very interesting to know the less than one million. I want to tell you that I want to implement the algorithm A star to solve the 8-puzzle for which I am taking as reference this web page algorithmsinsight.wordpress.com/graph-theory-2/…, then I would like to tell me do you think it is necessary to implement the linear conflict function? , to be able to use that algorithm. Maybe you have some suggestions on how to start building the A star algorithm $\endgroup$ – bullitohappy Jul 13 '18 at 4:12
  • $\begingroup$ It seems pretty hard to come up with a decent heuristic that actually estimates progress in the puzzle (maybe something along the lines of "pairs of pieces that are oriented so that they can be solved by moving them around a looping path"?), so maybe just drop the heuristic and do a plain old BFS instead? $\endgroup$ – Bass Jul 13 '18 at 8:25
  • $\begingroup$ thank you very much for your suggestion, I'm still researching more about the algorithm A star to solve this puzzle, I hope very soon to share my progress $\endgroup$ – bullitohappy Jul 15 '18 at 5:20
  • 1
    $\begingroup$ And now I even clicked on the link in your comment. One important thing to notice is that the given A-star example ("Now let’s use Manhattan heuristic on a random 8-Puzzle instance and work it towards the solution.") is fake. It's nowhere near random, but a carefully crafted special position instead: each correct move is designed to coincide with a better manhattan heuristic, which makes the algorithm look halfway magical. In an actually random position, the heuristic will perform much more poorly. $\endgroup$ – Bass Jul 15 '18 at 16:40
  • 1
    $\begingroup$ I've also seen a slight improvement of the Manhattan distance used. If two tiles are in their correct row (or column) but in the wrong order, then you can add 2 to the Manhattan distance because one of the tiles will have to leave and then return to that row (or column). This improvement is probably not worth it for the 8-puzzle, but might help on slightly larger puzzles. By the way, you mean $9!/2$ instead of $10!/2$. $\endgroup$ – Jaap Scherphuis Jul 20 '18 at 6:46

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.