user
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:

```
15 14  1  6
 9 11  4 12
 0 10  7  3
13  8  5  2
```

Solution:

```
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

```

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.

Extra credit.

Solve the following problem:

```
  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1

```

Related Task

* 15 puzzle game
* A\* search algorithm
assistant
**Translation of**: C++

```
# 20210623 Raku programming solution vCSMt9hkak0

constant \Nr = <3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3>;
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 is default(0);
my @N3 is default(0);
my @N4 is default(0);
my @N2 is default(0);

sub fY() {
   if @N2[$n] == 0x123456789abcdef0 {
      say "Solution found in ", $n, " moves: ", [~] @N3[1..$n] and exit();
   }
   return @N4[$n] ≤ $m ?? fN() !! False ;
}

sub fN() {
   sub common { ++$n; return True if fY(); --$n }
   if (@N3[$n] ne 'u' && @N0[$n] div 4 < 3) { fI() and common }
   if (@N3[$n] ne 'd' && @N0[$n] div 4 > 0) { fG() and common }
   if (@N3[$n] ne 'l' && @N0[$n]  %  4 < 3) { fE() and common }
   if (@N3[$n] ne 'r' && @N0[$n]  %  4 > 0) { fL() and 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);
   @N3[$n+1]='d';
   @N4[$n+1]=@N4[$n]+(Nr[a+>g] ≤ @N0[$n] div 4 ?? 0 !! 1);
}

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);
   @N3[$n+1]='u';
   @N4[$n+1]=@N4[$n]+(Nr[a+>g] ≥ @N0[$n] div 4 ?? 0 !! 1);
}

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);
   @N3[$n+1]='r';
   @N4[$n+1]=@N4[$n]+(Nc[a+>g] ≤ @N0[$n]%4 ?? 0 !! 1);
}

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);
   @N3[$n+1]='l';
   @N4[$n+1]=@N4[$n]+(Nc[a+>g] ≥ @N0[$n]%4 ?? 0 !! 1);
}

sub fifteenSolver(\n, \g){@N0[0]=n; @N2[0]=g}


fifteenSolver(8,0xfe169b4c0a73d852);
loop { fY() or ++$m }

```

Output:

```
Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd

```