15 puzzle solver: Difference between revisions

* [[A* search algorithm]]

<br><br>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program puzzle15solvex64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

<pre>

File name : casR1.txt

RRRULDDLUUULDRURDDDRULLULURRRDDLDLUURDDLULURRULDRDRD

</pre>

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program puzzle15solver.s */

/***************************************************/

.include "../affichage.inc"

<pre>

Nom du fichier : casR1.txt

=={{header|C}}==

===IDA*===

/**@file HybridIDA.c

* @brief solve 4x4 sliding puzzle with IDA* algorithm

}

 

{{out}}

<pre>

13 14 15 0

 

</pre>

 

[http://www.rosettacode.org/wiki/15_puzzle_solver/20_Random see] for an analysis of 20 randomly generated 15 puzzles solved with this solver.

====The Solver====

// Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017

class fifteenSolver{

void Solve(){for(;not fY();++_n);}

};

 

====The Task====

int main (){

fifteenSolver start(8,0xfe169b4c0a73d852);

start.Solve();

}

{{out}}

<pre>

 

====Extra Credit====

int main (){

fifteenSolver start(0,0x0c9dfbae37254861);

start.Solve();

}

{{out}}

<pre>

Using an A* search algorithm which is good enough for the first task. I increased SBCL's dynamic memory to 2GB for the code to run smoothly.

 

(eval-when (:load-toplevel :compile-toplevel :execute)

(ql:quickload "pileup"))

(format t "Found the shortest path in ~D steps and ~3,2F seconds~%" result time))

(print-state goal-state))

 

{{out}}

=={{header|F_Sharp|F#}}==

===The Function===

// A Naive 15 puzzle solver using no memory. Nigel Galloway: October 6th., 2017

let Nr,Nc = [|3;0;0;0;0;1;1;1;1;2;2;2;2;3;3;3|],[|3;0;1;2;3;0;1;2;3;0;1;2;3;0;1;2|]

solve {i=n;g=[L];e=g;l=0}

let n = Seq.collect fN n

===The Task===

let test n g=match [1..15]|>Seq.tryPick(solve n g) with

Some n->n|>List.rev|>List.iter(fun n->printf "%c" (match n with N->'d'|I->'u'|G->'r'|E->'l'|L->'\u0000'));printfn " (%n moves)" (List.length n)

|_ ->printfn "No solution found"

test 0xfe169b4c0a73d852UL 8

{{out}}

<pre>

The idea is taken from C++ or F# version above.

 

#! /usr/bin/gforth

 

4 0 do dup i valid? if i step u-turn <> if i advance recurse rollback then then loop ;

 

: solve 1 limit ! begin search deeper again ;

 

\ -1 0 hex 123456789afbde0c decimal 14 solve \ some trivial case, 3 moves

bye

 

{{out}}

(The source below has the ABS outside the MOD: I don't care [[Talk:Carmichael_3_strong_pseudoprimes|what sort of mod]] is used here, just that negative numbers be as scrambled as positive) In both cases the array indexing is checkable by the compiler at compile time so that there need be no run-time checking on that. Such bound checking may be not as strict as might be expected when EQUIVALENCE tricks are involved. In tests with a variant board size of 3x4, the board position array was declared BOARD(N) where N = 12, but was still equivalenced to BORED(4) and so still allowed room for sixteen elements in BOARD. Subroutine UNPACK was not written to deal with anything other than a 4x4 board and so accessed elements 13, 14, 15, and 16 of BOARD that were outside its declared upper bound of 12, but no run-time objection was made. Similarly with a 3x3 board.

 

code specialised for NR = 4

ELSE IF (NR.EQ.3) THEN

code specialised for NR = 3

and hope that the compiler would carry forward the actual value of <code>NR</code> into the IF-statement's conditional expression, recognise that the result is also constant (for the current compilation with a particular value of <code>NR</code>) and so generate code only for the case that the expression came out as ''true'', without any test to select this being employed in the compiled code. This soon becomes a tangle of combinations, and has not been attempted. And there could be difficulties too. One wonders if, say, with NR = 3, the specialised code for the NR = 4 case could contain a mention of element 4 of an array which is actually of size NR. Would the compiler regard this as an error, given that it will be discarding this code anyway? Even if one used NR rather than a literal such as 4 there could still be problems, such as code calling for a division by (NR - 3).

 

 

===Source===

DOUBLE PRECISION T !The time, in seconds. Positive only, please.

DOUBLE PRECISION S !A copy I can mess with.

CALL PURPLE HAZE(FNAME(1:14))

 

 

===The Results===

=={{header|Go}}==

{{trans|C++}}

 

import "fmt"

fifteenSolver(8, 0xfe169b4c0a73d852)

solve()

 

{{out}}

<pre>

Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

</pre>

 

=={{header|Julia}}==

{{trans|C++}}

const Nc = [3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2]

 

run() = (N0[1] = 8; _n[1] = 1; N2[1] = 0xfe169b4c0a73d852; solve(0))

run()

{{output}} <pre>

next iteration, _n[1] will be 2...

=={{header|Lua}}==

===Original===

#!/usr/bin/lua

--[[

print_tiles(Goal)

solve(Tiles);

{{output}} <pre>

FOUND SOLUTION of length 52 rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

 

===Alternate (with extra credit)===

----------

-- SOLVER

print("ELAPSED: " .. (os.clock()-sclock) .. "s")

end

{{out}}

<pre>

{{trans|C++}}

====The solver====

# 15 puzzle.

 

ms = ms mod d

if ms > 0: result.add(' ')

 

====The task====

let start = getTime()

var solver = initSolver([Value 15, 14, 1, 6,

solver.run()

echo fmt"Execution time: {(getTime() - start).toString}."

{{out}}

<pre>

</pre>

====Extra credit====

let start = getTime()

var solver = initSolver([Value 0, 12, 9, 13,

solver.run()

echo fmt"Execution time: {(getTime() - start).toString}."

{{out}}

<pre>

=={{header|Pascal}}==

===The Solver===

unit FifteenSolverT;

\\ Solve 15 Puzzle. Nigel Galloway; February 1st., 2019.

end;

end.

// Threaded use of 15 solver Unit. Nigel Galloway; February 1st., 2019.

program testFifteenSolver;

end;

end.

===The Task===

{{out}}

</pre>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

{{out}}

<pre>

while (not solveable_with_at_most_n_non_free_moves(n)) n++

-- (clearly optimal by exhaustively disproving all lesser n)

 

{{out}}

uppercase indicates the non-free moves (in manhattan cost terms).

Extrapolating from 0.5s/4hrs of C++, as-is this would probably take at least 3 days to solve the extra credit...<br>

You could probably make solve() iterative rather than recursive, and then go all full-on-inline-assembly on it...

 

=={{header|Python}}==

Modified to run this task's 52 move problem.

 

import random

 

print(", ".join({-1: "Left", 1: "Right", -4: "Up", 4: "Down"}[move[1]] for move in moves))

print(cost, num_eval)

 

Output - this solution of the problem for this task is the same as the second solution:

===A* with good heuristic===

;File - astar.py

"""

 

return strpath

 

;File - testone.py

 

"""

 

print(" ")

print("Run time in seconds: "+str(after - before))

Output:

 

Run time in seconds: 56.601139201

</pre>

=={{header|Racket}}==

#lang racket

 

(module+ main

(print-path (A* initial-state)))

 

=={{header|Rust}}==

{{trans|C++}}

const NC: [i32; 16] = [3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2];

 

fn main() {

FifteenSolver::new(8, 0xfe169b4c0a73d852).solve();

 

{{out}}

 

=== alternative ===

use std::cmp::{Ord, Ordering, PartialOrd, Reverse};

 

closed_states.push(parent_order, Reverse(parent_state));

}

 

{{out}}

 

===Implementation===

case class Board(table: Array[Int], r: Int, c: Int, parent: List[String] = List()) {

def cloneSwap(r: Int, c: Int, rr: Int, cc: Int) = {

val startHard = Board(Array(Array(0, 12, 9, 13), Array(15, 11, 10, 14), Array(3, 7, 2, 5), Array(4, 8, 6, 1)).flatten, 0, 0)

}

 

===Results===

ddrruldrdlururddluuuldlddrruulldrrruuldlldrrruuldldrrululdlurddlurdrrdllluruurrddldllurdrrulldrurd

Total time: 117.666 seconds