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

Published on 12 May 2024 09:40 PM
#Picat

How to resolve the algorithm 15 puzzle solver step by step in the Picat 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 Picat programming language

Source code in the picat programming language

import planner.

main =>
    init(InitS),
    goal(GoalS),
    best_plan((InitS,GoalS),Plan),
    println(Plan).

init(InitS) =>
    M = {{15, 14, 1,  6},
         {9 , 11, 4, 12},
         {0,  10, 7,  3},
         {13,  8, 5,  2}},
    InitS = [(R,C) : T in 0..15, pos(M,T,R,C)].

goal(GoalS) =>
    M = {{1,  2,  3,  4},
         {5,  6,  7,  8},
         {9, 10, 11, 12},
         {13,14, 15,  0}},
    GoalS = [(R,C) : T in 0..15, pos(M,T,R,C)].         

pos(M,T,R,C) =>
    N = len(M),
    between(1,N,R),
    between(1,N,C),
    M[R,C] == T,!.
    
final((S,GoalS)) => S == GoalS.

action((S,GoalS),NextS,Action,Cost) =>
    S = [P0|Tiles],
    P0 = (R0,C0),
    Cost = 1,
    (R1 = R0-1, R1 >= 1, C1 = C0, Action = u;
     R1 = R0+1, R1 =< 4, C1 = C0, Action = d;
     R1 = R0, C1 = C0-1, C1 >= 1, Action = l;
     R1 = R0, C1 = C0+1, C1 =< 4, Action = r),
    P1 = (R1,C1),
    slide(P0,P1,Tiles,Tiles1),
    S1 = [P1|Tiles1],
    NextS = (S1,GoalS).

% slide the tile at P1 to the empty square at P0
slide(P0,P1,[P1|Tiles],Tiles1) =>
    Tiles1 = [P0|Tiles].
slide(P0,P1,[Tile|Tiles],Tiles1) =>
    Tiles1=[Tile|Tiles1R],
    slide(P0,P1,Tiles,Tiles1R).

% called by the planner
heuristic((S,GoalS)) = Dist =>
    S = [_|Tiles],
    GoalS = [_|FTiles],
    Dist = sum([abs(R-FR)+abs(C-FC) : 
                {(R,C),(FR,FC)} in zip(Tiles,FTiles)]).

You may also check:How to resolve the algorithm Anadromes step by step in the AWK programming language
You may also check:How to resolve the algorithm Averages/Median step by step in the Vedit macro language programming language
You may also check:How to resolve the algorithm Mertens function step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Joystick position step by step in the Tcl programming language
You may also check:How to resolve the algorithm Loops/Foreach step by step in the XPL0 programming language