15 puzzle solver: Difference between revisions

Line 39:

<~~lang~~ 11l>-V

<syntaxhighlight lang=11l>-V

nr = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]

nc = [3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2]

Line 122:

0, 10, 7, 3,

13, 8, 5, 2])

solver.run()</~~lang~~>

solver.run()</syntaxhighlight>

Line 131:

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

<~~lang~~ AArch64 Assembly>

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program puzzle15solvex64.s */

Line 1,151:

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

.include "../includeARM64.inc"

</syntaxhighlight>

</lang>

<pre>

File name : casR1.txt

Line 1,172:

=={{header|Ada}}==

{{trans|C++}} Decoding actually...

<~~lang~~ Ada>with Ada.Text_IO;

<syntaxhighlight lang=Ada>with Ada.Text_IO;

procedure Puzzle_15 is

Line 1,363:

(0, 10, 7, 3),

(13, 8, 5, 2)));

end Puzzle_15;</~~lang~~>

end Puzzle_15;</syntaxhighlight>

<pre>Solved in 52 moves: RRRULDDLUUULDRURDDDRULLULURRRDDLDLUURDDLULURRULDRDRD</pre>

Line 1,369:

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

<~~lang~~ ARM Assembly>

/* ARM assembly Raspberry PI */

/* program puzzle15solver.s */

Line 2,311:

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

.include "../affichage.inc"

</syntaxhighlight>

</lang>

<pre>

Nom du fichier : casR1.txt

Line 2,332:

=={{header|C}}==

===IDA*===

/**@file HybridIDA.c

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

Line 2,619:

}

</syntaxhighlight>

</lang>

<pre>

Line 2,659:

[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====

<~~lang~~ cpp>

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

class fifteenSolver{

Line 2,701:

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

};

</syntaxhighlight>

</lang>

====The Task====

<~~lang~~ cpp>

int main (){

fifteenSolver start(8,0xfe169b4c0a73d852);

start.Solve();

}

</syntaxhighlight>

</lang>

<pre>

Line 2,718:

====Extra Credit====

<~~lang~~ cpp>

int main (){

fifteenSolver start(0,0x0c9dfbae37254861);

start.Solve();

}

</syntaxhighlight>

</lang>

<pre>

Line 2,737:

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.

<~~lang~~ lisp>;;; Using a priority queue for the A* search

<syntaxhighlight lang=lisp>;;; Using a priority queue for the A* search

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

(ql:quickload "pileup"))

Line 3,068:

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

(print-state goal-state))

</syntaxhighlight>

</lang>

Line 3,088:

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

===The Function===

<~~lang~~ fsharp>

// 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|]

Line 3,111:

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

let n = Seq.collect fN n

</syntaxhighlight>

</lang>

===The Task===

<~~lang~~ fsharp>

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

</syntaxhighlight>

</lang>

<pre>

Line 3,128:

The code tested with gforth 0.7.2. It required a 64-bit system.

<~~lang~~ forth>

#! /usr/bin/gforth

Line 3,194:

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

bye

</syntaxhighlight>

</lang>

Line 3,289:

(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.

Granted a flexible pre-processor scheme (as in pl/i, say) one could imagine a menu of tricks being selected from according to the board shape specified, but without such a facility, the constants are merely named rather than literal. Any change, such as to a 3x4 board, can be made by adjusting the appropriate PARAMETER and many usages will adjust accordingly. Others will require adjustment by the diligent programmer for good results. In the absence of a pre-processor one could present the various possible code sequences surrounded by tests as in <~~lang~~ Fortran>IF (NR.EQ.4) THEN

Granted a flexible pre-processor scheme (as in pl/i, say) one could imagine a menu of tricks being selected from according to the board shape specified, but without such a facility, the constants are merely named rather than literal. Any change, such as to a 3x4 board, can be made by adjusting the appropriate PARAMETER and many usages will adjust accordingly. Others will require adjustment by the diligent programmer for good results. In the absence of a pre-processor one could present the various possible code sequences surrounded by tests as in <syntaxhighlight lang=Fortran>IF (NR.EQ.4) THEN

code specialised for NR = 4

ELSE IF (NR.EQ.3) THEN

code specialised for NR = 3

END IF</~~lang~~>

END IF</syntaxhighlight>

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).

Line 3,301:

===Source===

<~~lang~~ Fortran> SUBROUTINE PROUST(T) !Remembrance of time passed.

<syntaxhighlight lang=Fortran> SUBROUTINE PROUST(T) !Remembrance of time passed.

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

DOUBLE PRECISION S !A copy I can mess with.

Line 3,829:

CALL PURPLE HAZE(FNAME(1:14))

END</~~lang~~>

END</syntaxhighlight>

===The Results===

Line 4,571:

=={{header|Go}}==

<~~lang~~ go>package main

<syntaxhighlight lang=go>package main

import "fmt"

Line 4,812:

fifteenSolver(8, 0xfe169b4c0a73d852)

solve()

}</~~lang~~>

}</syntaxhighlight>

Line 4,821:

=={{header|Julia}}==

<~~lang~~ julia>const Nr = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]

<syntaxhighlight lang=julia>const Nr = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]

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

Line 5,035:

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

run()

</~~lang~~>

</syntaxhighlight>

{{output}} <pre>

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

Line 5,050:

=={{header|Lua}}==

===Original===

<~~lang~~ Lua>

#!/usr/bin/lua

--[[

Line 5,275:

print_tiles(Goal)

solve(Tiles);

</syntaxhighlight>

</lang>

{{output}} <pre>

FOUND SOLUTION of length 52 rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

Line 5,281:

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

<~~lang~~ Lua>

----------

-- SOLVER

Line 5,485:

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

end

</syntaxhighlight>

</lang>

<pre>

Line 5,538:

====The solver====

<~~lang~~ Nim>

# 15 puzzle.

Line 5,679:

ms = ms mod d

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

</syntaxhighlight>

</lang>

====The task====

<~~lang~~ Nim>

let start = getTime()

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

Line 5,690:

solver.run()

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

</syntaxhighlight>

</lang>

<pre>

Line 5,697:

</pre>

====Extra credit====

<~~lang~~ Nim>

let start = getTime()

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

Line 5,705:

solver.run()

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

</syntaxhighlight>

</lang>

<pre>

Line 5,714:

=={{header|Pascal}}==

===The Solver===

<~~lang~~ pascal>

unit FifteenSolverT;

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

Line 5,746:

end;

end.

</syntaxhighlight>

</lang>

<~~lang~~ pascal>

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

program testFifteenSolver;

Line 5,779:

end;

end.

</syntaxhighlight>

</lang>

===The Task===

Line 5,797:

=={{header|Picat}}==

<~~lang~~ Picat>import planner.

<syntaxhighlight lang=Picat>import planner.

main =>

Line 5,854:

{(R,C),(FR,FC)} in zip(Tiles,FTiles)]).

</syntaxhighlight>

</lang>

Line 5,863:

=={{header|Perl}}==

<~~lang~~ perl>use strict;

<syntaxhighlight lang=perl>use strict;

no warnings;

Line 5,924:

($N0[0], $N2[0]) = (8, 0xfe169b4c0a73d852); # initial state

while () { fY() or ++$m }</~~lang~~>

while () { fY() or ++$m }</syntaxhighlight>

<pre>Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd</pre>

=={{header|Phix}}==

-- demo\rosetta\Solve15puzzle.exw

constant STM = 0 -- single-tile metrics.

Line 6,080:

{1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0}, -- down

{1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0}} -- right

function iddfs(integer step, lim, space, prevmv)

if time()>t1 then

Line 6,223:

end procedure

main()

<pre>

Line 6,240:

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

-- demo/rosetta/Solve15puzzle_simple.exw

enum left, down, up, right -- (nb 5-move flips it, as in down===5-up, etc)

Line 6,368:

printf(1,"solution of %d moves found in %s: %s\n",

{length(moves),elapsed(time()-t0),moves})

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

Line 6,383:

Works with PowerBASIC 6 Console Compiler

<~~lang~~ PowerBASIC>' The program solve fe169b4c0a73d852 in 4-5 seconds (on Intel Core i7-3770 3.40 GHz, 16 GB RAM, Windows 10 Pro).

<syntaxhighlight lang=PowerBASIC>' The program solve fe169b4c0a73d852 in 4-5 seconds (on Intel Core i7-3770 3.40 GHz, 16 GB RAM, Windows 10 Pro).

' Test not completed with 0c9dfbae37254861 (still running after about 4 hours).

' Most of initialization is done in procedure fifteenSolver(), so it's possible to call it many times from the main function.

Line 6,850:

'call fifteenSolver(&h0c9dfbae37254861, 1000)

end function

</syntaxhighlight>

</lang>

=={{header|Python}}==

Line 6,860:

Modified to run this task's 52 move problem.

<~~lang~~ Python>

import random

Line 7,047:

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

print(cost, num_eval)

</syntaxhighlight>

</lang>

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

Line 7,066:

===A* with good heuristic===

;File - astar.py

<~~lang~~ Python>

"""

Line 7,907:

return strpath

</syntaxhighlight>

</lang>

;File - testone.py

<~~lang~~ Python>

"""

Line 7,950:

print(" ")

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

</syntaxhighlight>

</lang>

Output:

Line 7,973:

</pre>

=={{header|Racket}}==

<~~lang~~ Racket>

#lang racket

Line 8,294:

(module+ main

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

</syntaxhighlight>

</lang>

=={{header|Raku}}==

<~~lang~~ perl6># 20210623 Raku programming solution vCSMt9hkak0

<syntaxhighlight lang=perl6># 20210623 Raku programming solution vCSMt9hkak0

constant \Nr = <3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3>;

Line 8,366:

fifteenSolver(8,0xfe169b4c0a73d852);

loop { fY() or ++$m }

</syntaxhighlight>

</lang>

<pre>

Line 8,374:

=={{header|Rust}}==

<~~lang~~ Rust>const NR: [i32; 16] = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3];

<syntaxhighlight lang=Rust>const NR: [i32; 16] = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3];

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

Line 8,575:

fn main() {

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

}</~~lang~~>

}</syntaxhighlight>

Line 8,581:

=== alternative ===

<~~lang~~ Rust>use keyed_priority_queue::KeyedPriorityQueue;

<syntaxhighlight lang=Rust>use keyed_priority_queue::KeyedPriorityQueue;

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

Line 8,746:

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

}

}</~~lang~~>

}</syntaxhighlight>

Line 8,769:

===Implementation===

<~~lang~~ Scala>import scala.collection.mutable

<syntaxhighlight lang=Scala>import scala.collection.mutable

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

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

Line 8,866:

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)

}

</syntaxhighlight>

</lang>

===Results===

Line 8,914:

This works but is very slow (132 seconds).

<~~lang~~ ecmascript>import "/long" for ULong

<syntaxhighlight lang=ecmascript>import "/long" for ULong

var Nr = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]

Line 9,088:

fifteenSolver.call(8, ULong.fromBaseString("fe169b4c0a73d852", 16))

solve.call()</~~lang~~>

solve.call()</syntaxhighlight>