15 puzzle solver: Difference between revisions

{{trans|Nim}}

 

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]

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

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program puzzle15solvex64.s */

=={{header|Ada}}==

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

 

procedure Puzzle_15 is

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

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program puzzle15solver.s */

=={{header|C}}==

===IDA*===

/**@file HybridIDA.c

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

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

 

====The Task====

int main (){

fifteenSolver start(8,0xfe169b4c0a73d852);

 

====Extra Credit====

int main (){

fifteenSolver start(0,0x0c9dfbae37254861);

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

=={{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|]

</syntaxhighlight>

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

 

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

#! /usr/bin/gforth

 

(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

 

===Source===

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

DOUBLE PRECISION S !A copy I can mess with.

=={{header|Go}}==

{{trans|C++}}

 

import "fmt"

=={{header|Julia}}==

{{trans|C++}}

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

 

=={{header|Lua}}==

===Original===

#!/usr/bin/lua

--[[

 

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

----------

-- SOLVER

{{trans|C++}}

====The solver====

# 15 puzzle.

 

 

====The task====

let start = getTime()

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

</pre>

====Extra credit====

let start = getTime()

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

=={{header|Pascal}}==

===The Solver===

unit FifteenSolverT;

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

end.

</syntaxhighlight>

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

program testFifteenSolver;

 

=={{header|Picat}}==

 

main =>

=={{header|Perl}}==

{{trans|Raku}}

no warnings;

 

 

=={{header|Phix}}==

<span style="color: #000080;font-style:italic;">-- demo\rosetta\Solve15puzzle.exw</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">STM</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- single-tile metrics.</span>

<!--</syntaxhighlight>-->

 

<span style="color: #008080;">function</span> <span style="color: #000000;">iddfs<span style="color: #0000FF;">(<span style="color: #004080;">integer</span> <span style="color: #000000;">step<span style="color: #0000FF;">,</span> <span style="color: #000000;">lim<span style="color: #0000FF;">,</span> <span style="color: #000000;">space<span style="color: #0000FF;">,</span> <span style="color: #000000;">prevmv<span style="color: #0000FF;">)</span>

<span style="color: #008080;">if</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>

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

 

<span style="color: #000080;font-style:italic;">-- demo/rosetta/Solve15puzzle_simple.exw</span>

<span style="color: #008080;">enum</span> <span style="color: #000000;">left<span style="color: #0000FF;">,</span> <span style="color: #000000;">down<span style="color: #0000FF;">,</span> <span style="color: #000000;">up<span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span> <span style="color: #000080;font-style:italic;">-- (nb 5-move flips it, as in down===5-up, etc)</span>

Works with PowerBASIC 6 Console Compiler

{{trans|Go}}

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

Modified to run this task's 52 move problem.

 

import random

 

===A* with good heuristic===

;File - astar.py

"""

 

;File - testone.py

 

"""

 

</pre>

=={{header|Racket}}==

#lang racket

 

=={{header|Raku}}==

{{trans|C++}}

 

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

=={{header|Rust}}==

{{trans|C++}}

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

 

 

=== alternative ===

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

 

 

===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) = {

{{libheader|Wren-long}}

This works but is very slow (132 seconds).

 

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