How to resolve the algorithm Solve a Holy Knight's tour step by step in the Picat programming language

Published on 12 May 2024 09:40 PM
#Picat

How to resolve the algorithm Solve a Holy Knight's tour step by step in the Picat programming language

Table of Contents

Problem Statement

Chess coaches have been known to inflict a kind of torture on beginners by taking a chess board, placing pennies on some squares and requiring that a Knight's tour be constructed that avoids the squares with pennies. This kind of knight's tour puzzle is similar to   Hidato. The present task is to produce a solution to such problems. At least demonstrate your program by solving the following:

Note that the zeros represent the available squares, not the pennies. Extra credit is available for other interesting examples.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Solve a Holy Knight's tour step by step in the Picat programming language

Source code in the picat programming language

import sat.

main =>
    S = {".000....",
         ".0.00...",
         ".0000000",
         "000..0.0",
         "0.0..000",
         "1000000.",
         "..00.0..",
         "...000.."},
    MaxR = len(S),
    MaxC = len(S[1]),
    M = new_array(MaxR,MaxC),
    StartR = _,    % make StartR and StartC global
    StartC = _,   
    foreach (R in 1..MaxR)
        fill_row(R, S[R], M[R], 1, StartR, StartC)
    end,
    NZeros = len([1 : R in 1..MaxR, C in 1..MaxC, M[R,C] == 0]),
    M :: 0..MaxR*MaxC-NZeros,
    Vs = [{(R,C),1} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0],
    Es = [{(R,C),(R1,C1),_} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0,
                              neibs(M,MaxR,MaxC,R,C,Neibs),
                              (R1,C1) in Neibs, M[R1,C1] !== 0],
    hcp(Vs,Es),
    foreach ({(R,C),(R1,C1),B} in Es)
        B #/\ (R1 #!= StartR #\/ C1 #!= StartC) #=> M[R1,C1] #= M[R,C]+1
    end,
    solve(M),
    foreach (R in 1..MaxR)
        foreach (C in 1..MaxC)
            if M[R,C] == 0 then
                printf("%4c", '.')
            else
                printf("%4d", M[R,C])
            end
        end,
        nl
    end.

neibs(M,MaxR,MaxC,R,C,Neibs) =>
    Connected = [(R+1, C+2),
                 (R+1, C-2),
                 (R-1, C+2),
                 (R-1, C-2),
                 (R+2, C+1),
                 (R+2, C-1),
                 (R-2, C+1),
                 (R-2, C-1)],
    Neibs = [(R1,C1) : (R1,C1) in Connected,
                       R1 >= 1, R1 =< MaxR, C1 >= 1, C1 =< MaxC,
                       M[R1,C1] !== 0].
    

fill_row(_R, [], _Row, _C, _StartR, _StartC) => true.
fill_row(R, ['.'|Str], Row, C, StartR, StartC) =>
    Row[C] = 0,
    fill_row(R,Str, Row, C+1, StartR, StartC).
fill_row(R, ['0'|Str], Row, C, StartR, StartC) =>
    fill_row(R, Str, Row, C+1, StartR, StartC).
fill_row(R, ['1'|Str], Row, C, StartR, StartC) =>
    Row[C] = 1,
    StartR = R,
    StartC = C,
    fill_row(R, Str, Row, C+1, StartR, StartC).

You may also check:How to resolve the algorithm Multiplication tables step by step in the Forth programming language
You may also check:How to resolve the algorithm Peaceful chess queen armies step by step in the zkl programming language
You may also check:How to resolve the algorithm Determine if only one instance is running step by step in the Delphi programming language
You may also check:How to resolve the algorithm Longest increasing subsequence step by step in the Arturo programming language
You may also check:How to resolve the algorithm Delegates step by step in the Logtalk programming language