Talk:15 puzzle solver: Difference between revisions
→Description of the F#/C++ algorithm
m (→Using A* algorithm: changed an extremely long line (which used scrolling) to normal formatting, fixed a misspelling.) |
|||
| (4 intermediate revisions by 3 users not shown) | |||
Line 1:
==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
<pre>
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
</pre>
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.
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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). --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:09, 25 July 2020 (UTC)
== Mathematical meaning of minimum ==
The meaning of minimum has been discussed see: [http://www.rosettacode.org/wiki/Talk:Superpermutation_minimisation#Ambiguous 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)--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:28, 6 October 2017 (UTC)
Line 51 ⟶ 102:
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--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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) --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 21:06, 1 June 2020 (UTC)
| |||