How to resolve the algorithm 15 puzzle solver step by step in the Perl programming language

Published on 12 May 2024 09:40 PM
#Perl

How to resolve the algorithm 15 puzzle solver step by step in the Perl programming language

Table of Contents

Problem Statement

Your task is to write a program that finds a solution in the fewest moves possible single moves to a random Fifteen Puzzle Game. For this task you will be using the following puzzle:

The output must show the moves' directions, like so: left, left, left, down, right... and so on. There are two solutions, of fifty-two moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd see: Pretty Print of Optimal Solution Finding either one, or both is an acceptable result. Solve the following problem:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm 15 puzzle solver step by step in the Perl programming language

Source code in the perl programming language

use strict;
no warnings;

use enum qw(False True);
use constant Nr => <3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3>;
use constant Nc => <3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2>;

my ($n, $m) = (0, 0);
my(@N0, @N2, @N3, @N4);

sub fY {
   printf "Solution found in $n moves: %s\n", join('', @N3) and exit if $N2[$n] == 0x123456789abcdef0;
   $N4[$n] <= $m ? fN() : False;
}

sub fN {
   sub common { ++$n; return True if fY(); --$n }
   if ($N3[$n] ne 'u' and int($N0[$n] / 4) < 3) { fI(); common() }
   if ($N3[$n] ne 'd' and int($N0[$n] / 4) > 0) { fG(); common() }
   if ($N3[$n] ne 'l' and    ($N0[$n] % 4) < 3) { fE(); common() }
   if ($N3[$n] ne 'r' and    ($N0[$n] % 4) > 0) { fL(); common() }
   return False;
}

sub fI {
   my $g = (11-$N0[$n])*4;
   my $a = $N2[$n] & (15 << $g);
   $N0[$n+1] = $N0[$n]+4;
   $N2[$n+1] = $N2[$n]-$a+($a<<16);
   $N4[$n+1] = $N4[$n]+((Nr)[$a>>$g] <= int($N0[$n] / 4) ? 0 : 1);
   $N3[$n+1] = 'd';
}

sub fG {
   my $g = (19-$N0[$n])*4;
   my $a = $N2[$n] & (15 << $g);
   $N0[$n+1] = $N0[$n]-4;
   $N2[$n+1] = $N2[$n]-$a+($a>>16);
   $N4[$n+1] = $N4[$n]+((Nr)[$a>>$g] >= int($N0[$n] / 4) ? 0 : 1);
   $N3[$n+1] = 'u';
}

sub fE {
   my $g = (14-$N0[$n])*4;
   my $a = $N2[$n] & (15 << $g);
   $N0[$n+1] = $N0[$n]+1;
   $N2[$n+1] = $N2[$n]-$a+($a<<4);
   $N4[$n+1] = $N4[$n]+((Nc)[$a>>$g] <= $N0[$n]%4 ? 0 : 1);
   $N3[$n+1] = 'r';
}

sub fL {
   my $g = (16-$N0[$n])*4;
   my $a = $N2[$n] & (15 << $g);
   $N0[$n+1] = $N0[$n]-1;
   $N2[$n+1] = $N2[$n]-$a+($a>>4);
   $N4[$n+1] = $N4[$n]+((Nc)[$a>>$g] >= $N0[$n]%4 ? 0 : 1);
   $N3[$n+1] = 'l';
}

($N0[0], $N2[0]) = (8, 0xfe169b4c0a73d852); # initial state
while () { fY() or ++$m }

You may also check:How to resolve the algorithm Sorting algorithms/Cocktail sort step by step in the Haskell programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the ReScript programming language
You may also check:How to resolve the algorithm Test a function step by step in the Phix programming language
You may also check:How to resolve the algorithm Jensen's Device step by step in the Ring programming language
You may also check:How to resolve the algorithm Proper divisors step by step in the zkl programming language