Talk:15 puzzle solver

From Rosetta Code

Description of the F#/C++ algorithm

Consider the usual depiction of the 15 puzzle game as square with tiles as a weighted graph. Let ℍ be the set of all nodes of the graph each node representing an arrangement of the tiles within the square. Identify one of the nodes as representing the initial arrangement IA, and one of the nodes as representing the required arrangement RA, for the solution.

Two nodes N and G are connected by an edge if one movement of the hole can change the arrangement of tiles at N to the arrangement at G. The edge will have a weight of either 0 or 1. The weight will be 0 if the tile that moves moves closer to its final position, 1 otherwise.

Let the final position be

                                       1  2  3  4
                                       5  6  7  8
                                       9 10 11 12
                                      13 14 15

For a move a single tile moves. At node N where tile 7 moves and is at position 10 then then the weight of an edge from N to G will be 0 if tile 7 is in position 6 or 11 at G. It will be 1 if tile 7 is at 9 or 14 at G.

There is a subset ℚ of ℍ such that for every node in ℚ there exists a path from the node to RA on edges with 0 weight. This path may be characterized as n0(0).

1. Determine if IA є ℚ. If it is then I have found a solution. n the path length of the solution will be n0. n will be what lesser solutions to this task call Manhattan Distance.

2. If IA ∉ ℚ then I have determined that there is not a solution where n=Manhattan Distance at IA. I have identified a subset ℙ of ℍ where each node in ℙ will have a path from IA of the form n1(0)(1).

Now you must convince yourself that the minimum solution distance for each node in ℙ is the Manhattan Distance at IA+2, and that this is realized if ℙ ⋂ ℚ is not the empty set.
Consider N has 7 at position 9 and at G it is at position 14 having followed the path 9->10->14 (01 path length n=2). At N the 7 tile contributes 3 to the Manhattan Distance for n1 moves it decreases by 1 then it increases by 1 for the final move. So the minimum solution distance is 3-n1+1+n≡3-1+1+2=5.
Consider N has 7 at position 9 and at G it is at position 15 having followed the path 9->10->11->15 (001 path length n=3). The minimum solution distance is 3-n1+1+n≡3-2+1+3=5.
Now of course 7 may not be the only tile that moves so the minimum solution distance is the sum of the contributions of all tiles that move and the path length may be much larger than 3. Convince yourself that the result is still Manhattan Distance at IA+2.

3. If ℙ ⋂ ℚ is not the empty set then I have determined that there is a solution where n=Manhattan Distance at IA+2. The solution will be of the form n1(0)(1)n0(0).

4. If ℙ ⋂ ℚ is the empty set then I have determined that there is not a solution where n=Manhattan Distance at IA+2 and I have identified a new subset ℙ of ℍ where each node in ℙ will have a path from IA of the form n1(0)(1)n2(0)(1)

Now you must convince yourself that the minimum solution distance for each node in ℙ is the Manhattan Distance at IA+4, and that this is realized if ℙ ⋂ ℚ is not the empty set.

5. Repeating 3 and 4 until ℙ ⋂ ℚ is not the empty set.

You may wish to look at the [20 Random Puzzles] and confirm that the final solution length is the Manhattan Distance of the starting

position+_n*2.

--Nigel Galloway (talk) 14:21, 28 July 2020 (UTC)

Ah-ha! I think the penny has finally dropped!
 let mc = manhattan_cost(puzzle)
 while (not solveable_in(mc)) mc++
Or, better yet:
 let all moves which do not increase the manhattan cost be regarded as "free".
 let n=0
 while (not solveable_with_at_most_n_non_free_moves(n)) n++
The new Phix solution implements this (albeit aiming for simplicity over spectacular efficiently). --Pete Lomax (talk) 13:18, 29 July 2020 (UTC)

Code obfuscation / reference to implemented algorithm

As of today, 6 out of 14 implementations are translations of a same piece of code that is intentionally obfuscated and comes without any descriptions/explanations. It would be nice to see any proofs the implemented algorithm is correct (that is, detects an optimal solution). Also submitting an obfuscated code clearly contradicts the very idea of the site as a Programming Chrestomathy.

Maybe this will help: https://www.youtube.com/watch?v=mfsYSPCNWCw - SCNR, the more I watched the funnier I found it. --Pete Lomax (talk) 15:09, 25 July 2020 (UTC)

Mathematical meaning of minimum

The meaning of minimum has been discussed see: Minimum. It means 52 not 58, assuming fewest is a synonym for minimum. I think the task description should call for 'minimum solutions to random 15 puzzles' (see below)--Nigel Galloway (talk) 10:28, 6 October 2017 (UTC)

I am surprised that anyone thinks that 52 < 31. Optimal solution improved and now linked from the task description. Pete Lomax (talk) 05:11, 24 October 2017 (UTC)
A fair point, but one that could have been made with less damage to the tasks structure I'm sure. I've clarified that only single moves are allowed in this task and created a draft task for multimoves, which are interesting in their own right but comparing them to single moves is silly--Nigel Galloway (talk) 10:04, 24 October 2017 (UTC)
Which may not be what you want. In the output you have "stm-optimal solution of 38(52) moves found in 1 minute and 54s: r3uldlu2ldrurd3lu2lur3dld2ruldlu2rd2lulur2uldr2d2" which is the second of the acceptable solutions in the task description before you changed it (only written not quite as specified in the task description). So with a little change of emphasis, and without marking other solutions as incorrect this could return.--Nigel Galloway (talk) 10:40, 24 October 2017 (UTC)
Whatever. I can accept a moratorium on incorrect tags, splitting the task feels dishonest. Any clear, elegant solution, optimal or not, should be welcome. Pete Lomax (talk) 14:06, 25 October 2017 (UTC)
Of course it's welcome. The stm-optimal solution is the objective of this task. It is not the objective of this task to find the mtm-optimal solution, but as an extra is not a problem.--Nigel Galloway (talk) 16:01, 25 October 2017 (UTC)

Mathematical meaning of random

Unlike minimum, which I am surprised that anyone thinks means anything other than 'reduced to the least possible amount or degree', random means easy mathematically. There are 16!/2 15 puzzles, a little over 10 trillion, of which the number that are hard to solve is counted in the hundred thousands. Therefore a randomly chosen puzzle is easy. --Nigel Galloway (talk) 10:36, 6 October 2017 (UTC)

see for an analysis of 20 randomly generated 15 puzzles--Nigel Galloway (talk) 13:00, 20 October 2017 (UTC)
that page updated with a multimove solution Pete Lomax (talk) 05:10, 24 October 2017 (UTC)

Extra credit for non-random puzzles

We could offer extra credit for solving hard puzzles:

 2  1  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

and

  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1

--Nigel Galloway (talk) 13:08, 6 October 2017 (UTC)

Multimoves

Prohibition on multimoves removed from task description. The task description should not dissuade such submissions. Pete Lomax (talk) 22:57, 29 November 2017 (UTC)

I'd disagree... This means that some moves are more equal than others. Like, if one was considering distances, a (single-step) move is a constant unit of assessment, as with considering sort routines. A swap of elements i and j is three actions and does not consider the distance between them because the intervening positions are not involved. But, when moving a square multiple positions in the same direction, there are multiple actions, and, like Zeno's Arrow, each position is occupied... Dinosaur (talk) 00:29, 30 November 2017 (UTC)
We have agreed that it is not fair or sensible to compare them. My point is about excluding valid solutions. Pete Lomax (talk) 02:52, 30 November 2017 (UTC)
But comparisons seem possible and reasonable to me. Like, consider the "Optimal solution in 31 multimoves"
u2r2d3ru2ld2ru3ld3l2u3r2d2l2dru3rd3l2u2r3dl3dru2r2d2            As offered.
uurrdddruulddruuuldddlluuurrddlldruuurdddlluurrrdllldruurrdd    Run-length encoding undone: 60 moves.
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd            First solution, of 52 moves.
This to me involves more (single-step) moves than the problem's two given 52 (single-step) move solutions and involves more movement of the squares, even though there are only 31 actions if you count the like of uu as one action. In other words, a minimum action-count problem is not the same as a minimum move-count problem since an action may involve multiple moves. Put another way, one could consider a set of allowable actions (here, udlr, or, udlr, uu ll rr dd, uuu lll rrr etc) and once you start down that path, why not also allow additional actions, such as uld dru; whatever takes your fancy? Then start considering the minimum number of such actions required to transform one string into another... Perhaps not. Dinosaur (talk) 08:39, 30 November 2017 (UTC)
Hi Pete, Solutions which find multimoves also are not prohibited, the task requirement is to find the fewest single moves which the phix solution now does. It is on the page, it is not excluded, it is not required as part of the task. This problem can be solved by extension of the A* algorithm. I didn't understand why you thought my suggestion to split the task was dishonest, it is my honest opinion that solving graphs with co-operative moves requires a different algorithm. That algorithm can also by used to solve this problem, apparently in 5.5hours rather than 29secs.--Nigel Galloway (talk) 12:20, 30 November 2017 (UTC)

Using A* algorithm

I added an extra credit to to A* search algorithm :


Use this algorithm to solve an 8 puzzle. Each node of the input graph will represent an arrangement of the tiles. The nodes will be connected by 4 edges representing swapping the blank tile up, down, left, or right. The cost of each edge is 1. The heuristic will be the sum of the Manhatten distance of each numbered tile from its goal position. An 8 puzzle graph will have 9!/2 (181,440) nodes. The 15 puzzle has over 10 trillion nodes. This algorithm may solve simple 15 puzzles (but there are not many of those).


Using the better heuristic used in the Python A* solution enables the solution of the task problem (using 4GB of memory). 15 puzzle solver/20 Random has 20 random starting positions. Using the Python code starting positions requiring 1sec or more can not be solved on a computer with 8GB of memory. With 8GB it can test up to say 2200000 positions. So these solutions are good for extra credit medal with bar in the A* task but do not indicate that this is the correct algorithm to solve this task--Nigel Galloway (talk) 17:25, 5 February 2019 (UTC)

Edit undone

User Kaviyarasu (their first/only contribution) changed the puzzle in the task description to

5 1  4  8
9 6  3 11
10 2  15  7
13  14  12  0

so I put it back. Obviously I have no problem with additional (/optional) puzzles, but the one all the existing contributions are using should not have been replaced. (Maybe I should have put this on their talk page, tl;dt) --Pete Lomax (talk) 21:06, 1 June 2020 (UTC)