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

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm Solve a Holy Knight's tour step by step in the J 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 J programming language

Source code in the j programming language

9!:21]2^34

unpack=:verb define
  mask=. +./' '~:y
  board=. (255 0 1{a.) {~ {.@:>:@:"."0 mask#"1 y
)

ex1=:unpack ];._2]0 :0
  0 0 0 
  0   0 0 
  0 0 0 0 0 0 0
0 0 0     0   0
0   0     0 0 0
1 0 0 0 0 0 0
    0 0   0
      0 0 0
)

solve=:verb define
  board=.,:y
  for_move.1+i.+/({.a.)=,y do.
    board=. ;move <@knight"2 board
  end.
)

kmoves=: ,/(2 1,:1 2)*"1/_1^#:i.4

knight=:dyad define
  pos=. ($y)#:(,y)i.x{a.
  moves=. <"1(#~ 0&<: */"1@:* ($y)&>"1)pos+"1 kmoves
  moves=. (#~ (0{a.)={&y) moves
  moves y adverb def (':';'y x} m')"0 (x+1){a.
)


   $~.sol
48422 8 8


   (a.i.{.sol){(i.255),__
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
__ 27 12 21 14  9 16 31
23  2 25 __ __ 30 __  8
26 __ 20 __ __ 15 32 17
 1 24  3 34  5 18  7 __
__ __ 36 19 __ 33 __ __
__ __ __  4 35  6 __ __


   (a.i.{:sol){(i.255),__
__  5  8 31 __ __ __ __
__ 32 __  6  9 __ __ __
__  7  4 33 30 23 10 21
 3 34 29 __ __ 20 __ 24
36 __  2 __ __ 11 22 19
 1 28 35 12 15 18 25 __
__ __ 16 27 __ 13 __ __
__ __ __ 14 17 26 __ __
   (a.i.24211{sol){(i.255),__
__ 11 14 33 __ __ __ __
__ 34 __ 10 13 __ __ __
__ 19 12 15 32  9  6 25
35 16 31 __ __ 24 __  8
18 __ 20 __ __  7 26  5
 1 36 17 30 27  4 23 __
__ __  2 21 __ 29 __ __
__ __ __ 28  3 22 __ __


unpack=:verb define
  mask=. +./' '~:y
  board=. __ 0 1 {~ {.@:>:@:"."0 mask#"1 y
)

ex1=:unpack ];._2]0 :0
  0 0 0 
  0   0 0 
  0 0 0 0 0 0 0
0 0 0     0   0
0   0     0 0 0
1 0 0 0 0 0 0
    0 0   0
      0 0 0
)

solve1=:verb define
 (1,+/0=,y) solve1 ,:y
:
  for_block._10 <\ y do.
    board=. ;({.x) <@knight"2 ;block
    if. #board do.
      if. =/x do.
        {.board return.
      else.
        board=. (1 0+x) solve1 board
        if. #board do.
          board return.
        end.
      end.
    end.
  end.
  i.0 0
)

kmoves=: ,/(2 1,:1 2)*"1/_1^#:i.4

knight=:dyad define
  pos=. ($y)#:(,y)i.x
  moves=. <"1(#~ 0&<: */"1@:* ($y)&>"1)pos+"1 kmoves
  moves=. (#~ 0={&y) moves
  moves y adverb def (':';'y x} m')"0 x+1
)


   solve1 ex1
__ 11 28 13 __ __ __ __
__ 22 __ 10 29 __ __ __
__ 27 12 21 14  9 16 31
23  2 25 __ __ 30 __  8
26 __ 20 __ __ 15 32 17
 1 24  3 34  5 18  7 __
__ __ 36 19 __ 33 __ __
__ __ __  4 35  6 __ __


ex2=:unpack ];._2]0 :0
           1   0          
           0   0          
         0 0 0 0 0        
           0 0 0          
     0     0   0     0    
 0 0 0 0 0       0 0 0 0 0
     0 0           0 0    
 0 0 0 0 0       0 0 0 0 0
     0     0   0     0    
           0 0 0          
         0 0 0 0 0        
           0   0          
           0   0          
)


   solve1 ex2
__ __ __ __ __  1 __  5 __ __ __ __ __
__ __ __ __ __  6 __ 46 __ __ __ __ __
__ __ __ __ 48 45  2  7  4 __ __ __ __
__ __ __ __ __  8 47 44 __ __ __ __ __
__ __ 56 __ __ 49 __  3 __ __ 42 __ __
13 52 11 50  9 __ __ __ 43 38 31 36 33
__ __ 14 55 __ __ __ __ __ 41 34 __ __
53 12 51 10 15 __ __ __ 39 30 37 32 35
__ __ 54 __ __ 23 __ 29 __ __ 40 __ __
__ __ __ __ __ 16 19 22 __ __ __ __ __
__ __ __ __ 24 21 26 17 28 __ __ __ __
__ __ __ __ __ 18 __ 20 __ __ __ __ __
__ __ __ __ __ 25 __ 27 __ __ __ __ __

You may also check:How to resolve the algorithm SHA-1 step by step in the Jsish programming language
You may also check:How to resolve the algorithm Run-length encoding step by step in the Wren programming language
You may also check:How to resolve the algorithm Tau number step by step in the Verilog programming language
You may also check:How to resolve the algorithm Count in octal step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm 100 doors step by step in the MATLAB / Octave programming language