as an example in the "knight's tour.
hello joe
the description of the functions of the "knight's tour" you have already made. it is to be feared that mine (with the help of google translator) does not come better... i try it in spite of that;
description of the code "knight's tour" (code is below with points: a-f ).
a)
first we need a chessboard cb[] with 8x8 (64) squares. it is an array in which we define 8 rows with eight squares each and fill it up with zeros at the same time.
here we create the lists of possible gaps: dx[] & dy[].
now we need a few loops...
b)
the first loop "k" (can be a "while") does nothing else than count the jumps (from the start field) and enter them (in order) into the cb[[]]. the first entry is the start field which is defined outside the loop. it is reset at the end of the loop each time.
c)
the first "for" loop "i" (the outer one) saves the "kx/ky" field in "nx/ny" and (if the condition of the function "between" is true) sets the value in the var "ctr" to zero. then the inner for loop "j" starts here.
d)
this saves the "nx/ny" field in "ex/ey" and checks all eligible (unvisited) fields for usability, the number of which it manages in the var: "ctr". here, too, the eligible fields are checked by the function "between".
when leaving the loop "i", the values of the two counters (ctr, i) are stored in the list pq[]: pq.push [ctr, i]
applies to both loops ("i & j"):
the number of possible jumps varies in the range from 0 to 7 (so up to eight possibilities) which are controlled by the values (-2 to 2) stored in the lists dx[] and dy[].
e)
after leaving loop "i" we loop in loop "dd" the values stored in pq[] and select the neighbor with the minimum number of entries. in case of equal entries we leave the selection to chance (coin toss).
f)
we sum up the values determined by dx[m] & dy[m] (the selection from the loop "dd") to the starting values "kx" & "ky" - this is the next jump field for the check.
a short, somewhat different but very simple and straightforward explanation in python:
knight's tour warnsdorff algorithm
https://www.geeksforgeeks.org/warnsdorffs-algorithm-knights-tour-problem/
// version: after jstrout help
// knight's tour ( kt-022a-py.txt )
// quell: python with warnsdorf
// extended with coin toss
// datum: 210517 - 22:30
// corrigendum: 21.05.2021 kt-022c-py.txt
n = 8
cbx = n-1 // width and
cby = n-1 // height of the chessboard
cb = [] // make chessboard cb
for j in range(0, n-1) // fill cb with zeros
cb.push([0, 0, 0, 0, 0, 0, 0, 0])
end for
// -------------------------------------------------------------- end of a)
// -------------------------------------------------------------- functions
// show chesboard
prnt = function(cb)
for x in range(0, n-1)
print cb[x]
end for
end function
//between inclusive
between = function( x, mi, mx ) // mi: min mx: max
between = (x >= mi) and (x <= mx);
return between
end function
// -------------------------------------------------------- possible moves
// directions the Knight can move on the chessboard
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]
// start the Knight from field
kx = 1
ky = 1
print "Startfeld: "+ kx +"/"+ ky
k = 0
while k != 64
k = k+1
cb[ky][kx] = k //+ 1
pq = [] // priority queue of available neighbors
// ---------------------------------------------------------- end of b)
for i in range(0, 7) // Check thatone for usability (n=8)
nx = kx + dx[i]
ny = ky + dy[i]
// between-1
if between( nx, 0, cbx ) and between( ny, 0, cby ) then
if cb[ny][nx] == 0 then
// count the available neighbors of the neighbor
ctr = 0
// ---------------------------------------------- end of c)
for j in range(0, 7) // Check thisone for usability
ex = nx + dx[j]
ey = ny + dy[j]
// between-2
if between( ex, 0, cbx ) and between( ey, 0, cby ) then
// increment the counter ctr (pq)
if cb[ey][ex] == 0 then ctr = ctr + 1
end if //between-2
end for //j
pq.push [ctr, i] // counter & loop no.
// ---------------------------------------------- end of d)
end if //cb[ny][nx] == 0
end if // between-1
end for // i
// ----------------------------------------------------- priority queue
// move to the neighbor that has min number of available neighbors
if pq then
minVal = 7
minD = -1
for dd in pq.indexes
p = pq[dd][0]
m = pq[dd][1]
rdm = floor(rnd * 9) // coin toss; random
if p == minVal and rdm < 5 then // take it.. or not ;-)
minVal = p
minD = m
end if
if p < minVal then
minVal = p
minD = m
end if
end for //dd
// ------------------------------------------------------ end of e)
m = minD
kx = kx + dx[m]
ky = ky + dy[m]
// ------------------------------------------------------ end of f)
end if // pq-len
end while
prnt(cb) // show result
// ------------------------------------------------------------- end of pgm
