15 puzzle solver: Difference between revisions

Line 39:

<syntaxhighlight 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 131:

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program puzzle15solvex64.s */

Line 1,172:

=={{header|Ada}}==

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

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

<syntaxhighlight lang="ada">with Ada.Text_IO;

procedure Puzzle_15 is

Line 1,369:

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

/* ARM assembly Raspberry PI */

/* program puzzle15solver.s */

Line 2,332:

=={{header|C}}==

===IDA*===

/**@file HybridIDA.c

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

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

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

class fifteenSolver{

Line 2,704:

====The Task====

int main (){

fifteenSolver start(8,0xfe169b4c0a73d852);

Line 2,718:

====Extra Credit====

int main (){

fifteenSolver start(0,0x0c9dfbae37254861);

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.

<syntaxhighlight 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,088:

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

Line 3,113:

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

Line 3,128:

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

#! /usr/bin/gforth

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 <syntaxhighlight 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

Line 3,301:

===Source===

<syntaxhighlight 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 4,571:

=={{header|Go}}==

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 4,821:

=={{header|Julia}}==

<syntaxhighlight 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,050:

=={{header|Lua}}==

===Original===

#!/usr/bin/lua

--[[

Line 5,281:

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

----------

-- SOLVER

Line 5,538:

====The solver====

# 15 puzzle.

Line 5,682:

====The task====

let start = getTime()

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

Line 5,697:

</pre>

====Extra credit====

let start = getTime()

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

Line 5,714:

=={{header|Pascal}}==

===The Solver===

unit FifteenSolverT;

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

Line 5,747:

end.

</syntaxhighlight>

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

program testFifteenSolver;

Line 5,797:

=={{header|Picat}}==

<syntaxhighlight lang=~~Picat~~>import planner.

<syntaxhighlight lang="picat">import planner.

main =>

Line 5,863:

=={{header|Perl}}==

<syntaxhighlight lang=perl>use strict;

<syntaxhighlight lang="perl">use strict;

no warnings;

Line 5,929:

=={{header|Phix}}==

-- demo\rosetta\Solve15puzzle.exw

constant STM = 0 -- single-tile metrics.

Line 6,082:

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

if time()>t1 then

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,383:

Works with PowerBASIC 6 Console Compiler

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

<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,860:

Modified to run this task's 52 move problem.

import random

Line 7,066:

===A* with good heuristic===

;File - astar.py

"""

Line 7,911:

;File - testone.py

"""

Line 7,973:

</pre>

=={{header|Racket}}==

#lang racket

Line 8,298:

=={{header|Raku}}==

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

<syntaxhighlight lang="raku" line># 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,374:

=={{header|Rust}}==

<syntaxhighlight 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,581:

=== alternative ===

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

<syntaxhighlight lang="rust">use keyed_priority_queue::KeyedPriorityQueue;

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

Line 8,769:

===Implementation===

<syntaxhighlight 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,914:

This works but is very slow (132 seconds).

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