15 puzzle solver: Difference between revisions
New post.
(Fix C#) |
(New post.) |
||
Line 6,305:
<pre>
Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;
public final class Puzzle15Solver {
public static void main(String[] aArgs) {
List<Integer> start = List.of( 15, 14, 1, 6, 9, 11, 4, 12, 0, 10, 7, 3, 13, 8, 5, 2 );
final int zeroIndex = 8;
Puzzle initial = new Puzzle(start, new ArrayList<String>(), zeroIndex, 0);
openSet.add(initial);
System.out.println("Solving the 15 puzzle:");
initial.display();
while ( solution == null ) {
search();
}
System.out.println(solution.moves.stream().collect(Collectors.joining("")));
System.out.println("Number of steps: " + solution.moves.size());
System.out.println("Number of puzzle states checked: " + closedSet.size());
}
private static void search() {
Puzzle current = openSet.poll();
closedSet.add(current);
final int zeroIndex = current.zeroIndex;
final int row = zeroIndex / 4;
final int column = zeroIndex % 4;
if ( column > 0 ) {
makeMove(current, zeroIndex, Move.LEFT);
}
if ( column < 3 ) {
makeMove(current, zeroIndex, Move.RIGHT);
}
if ( row > 0 ) {
makeMove(current, zeroIndex, Move.UP);
}
if ( row < 3 ) {
makeMove(current, zeroIndex, Move.DOWN);
}
}
private static void makeMove(Puzzle aPuzzle, int aIndex, Move aMove) {
Puzzle nextPuzzle = aPuzzle.clone();
Integer temp = nextPuzzle.tiles.get(aIndex + aMove.step);
nextPuzzle.tiles.set(aIndex + aMove.step, 0);
nextPuzzle.tiles.set(aIndex, temp);
nextPuzzle.zeroIndex += aMove.step;
nextPuzzle.moves.add(aMove.symbol);
if ( ! closedSet.contains(nextPuzzle) ) {
openSet.add(nextPuzzle);
if ( nextPuzzle.tiles.equals(Puzzle.GOAL) ) {
solution = nextPuzzle;
}
}
}
private enum Move {
LEFT("L", -1), RIGHT("R", +1), UP("U", -4), DOWN("D", +4);
private Move(String aSymbol, int aStep) {
symbol = aSymbol;
step = aStep;
}
private String symbol;
private int step;
}
private static class Puzzle {
public Puzzle(List<Integer> aTiles, List<String> aMoves, int aZeroIndex, long aSearchDepth) {
tiles = aTiles;
moves = aMoves;
zeroIndex = aZeroIndex;
searchDepth = aSearchDepth;
}
public long heuristic() {
int distance = 0;
for ( int i = 0; i < tiles.size(); i++ ) {
final int tile = tiles.get(i);
if ( tile > 0 ) {
distance += Math.abs( ( i / 4 ) - ( tile - 1 ) / 4 ) + Math.abs( ( i % 4 ) - ( tile - 1 ) % 4 );
}
}
return distance + searchDepth;
}
public Puzzle clone() {
return new Puzzle(new ArrayList<Integer>(tiles), new ArrayList<String>(moves), zeroIndex, searchDepth + 1);
}
public void display() {
for ( int i = 0; i < tiles.size(); i++ ) {
System.out.print(String.format("%s%2d%s",
( i % 4 == 0 ) ? "[" : "", tiles.get(i), ( i % 4 == 3 ) ? "]\n" : " "));
}
System.out.println();
}
@Override
public int hashCode() {
int hash = 3;
hash = 23 * hash + tiles.hashCode();
hash = 23 * hash + zeroIndex;
return hash;
}
@Override
public boolean equals(Object aObject) {
return switch(aObject) {
case Puzzle puzzle -> tiles.equals(puzzle.tiles);
case Object object -> false;
};
}
private List<Integer> tiles;
private List<String> moves;
private int zeroIndex;
private long searchDepth;
private static final List<Integer> GOAL = List.of( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 );
}
private static Queue<Puzzle> openSet =
new PriorityQueue<Puzzle>( (one, two) -> Long.compare(one.heuristic(), two.heuristic()) );
private static Set<Puzzle> closedSet = new HashSet<Puzzle>();
private static Puzzle solution;
}
</syntaxhighlight>
{{ out }}
<pre>
Solving the 15 puzzle:
[15 14 1 6]
[ 9 11 4 12]
[ 0 10 7 3]
[13 8 5 2]
RRRULDLUULDRURDDDLUULURRRDLDDRULDLUURDDLULURRULDRRDD
Number of steps: 52
Number of puzzle states checked: 2276369
</pre>
| |||