mirror of https://github.com/tLDP/LDP
611 lines
17 KiB
Bash
611 lines
17 KiB
Bash
#!/bin/bash
|
|
# ktour.sh
|
|
|
|
# author: mendel cooper
|
|
# reldate: 12 Jan 2009
|
|
# license: public domain
|
|
# (Not much sense GPLing something that's pretty much in the common
|
|
#+ domain anyhow.)
|
|
|
|
###################################################################
|
|
# The Knight's Tour, a classic problem. #
|
|
# ===================================== #
|
|
# The knight must move onto every square of the chess board, #
|
|
# but cannot revisit any square he has already visited. #
|
|
# #
|
|
# And just why is Sir Knight unwelcome for a return visit? #
|
|
# Could it be that he has a habit of partying into the wee hours #
|
|
#+ of the morning? #
|
|
# Possibly he leaves pizza crusts in the bed, empty beer bottles #
|
|
#+ all over the floor, and clogs the plumbing. . . . #
|
|
# #
|
|
# ------------------------------------------------------------- #
|
|
# #
|
|
# Usage: ktour.sh [start-square] [stupid] #
|
|
# #
|
|
# Note that start-square can be a square number #
|
|
#+ in the range 0 - 63 ... or #
|
|
# a square designator in conventional chess notation, #
|
|
# such as a1, f5, h3, etc. #
|
|
# #
|
|
# If start-square-number not supplied, #
|
|
#+ then starts on a random square somewhere on the board. #
|
|
# #
|
|
# "stupid" as second parameter sets the stupid strategy. #
|
|
# #
|
|
# Examples: #
|
|
# ktour.sh 23 starts on square #23 (h3) #
|
|
# ktour.sh g6 stupid starts on square #46, #
|
|
# using "stupid" (non-Warnsdorff) strategy. #
|
|
###################################################################
|
|
|
|
DEBUG= # Set this to echo debugging info to stdout.
|
|
SUCCESS=0
|
|
FAIL=99
|
|
BADMOVE=-999
|
|
FAILURE=1
|
|
LINELEN=21 # How many moves to display per line.
|
|
# ---------------------------------------- #
|
|
# Board array params
|
|
ROWS=8 # 8 x 8 board.
|
|
COLS=8
|
|
let "SQUARES = $ROWS * $COLS"
|
|
let "MAX = $SQUARES - 1"
|
|
MIN=0
|
|
# 64 squares on board, indexed from 0 to 63.
|
|
|
|
VISITED=1
|
|
UNVISITED=-1
|
|
UNVSYM="##"
|
|
# ---------------------------------------- #
|
|
# Global variables.
|
|
startpos= # Starting position (square #, 0 - 63).
|
|
currpos= # Current position.
|
|
movenum= # Move number.
|
|
CRITPOS=37 # Have to patch for f5 starting position!
|
|
|
|
declare -i board
|
|
# Use a one-dimensional array to simulate a two-dimensional one.
|
|
# This can make life difficult and result in ugly kludges; see below.
|
|
declare -i moves # Offsets from current knight position.
|
|
|
|
|
|
initialize_board ()
|
|
{
|
|
local idx
|
|
|
|
for idx in {0..63}
|
|
do
|
|
board[$idx]=$UNVISITED
|
|
done
|
|
}
|
|
|
|
|
|
|
|
print_board ()
|
|
{
|
|
local idx
|
|
|
|
echo " _____________________________________"
|
|
for row in {7..0} # Reverse order of rows ...
|
|
do #+ so it prints in chessboard order.
|
|
let "rownum = $row + 1" # Start numbering rows at 1.
|
|
echo -n "$rownum |" # Mark board edge with border and
|
|
for column in {0..7} #+ "algebraic notation."
|
|
do
|
|
let "idx = $ROWS*$row + $column"
|
|
if [ ${board[idx]} -eq $UNVISITED ]
|
|
then
|
|
echo -n "$UNVSYM " ##
|
|
else # Mark square with move number.
|
|
printf "%02d " "${board[idx]}"; echo -n " "
|
|
fi
|
|
done
|
|
echo -e -n "\b\b\b|" # \b is a backspace.
|
|
echo # -e enables echoing escaped chars.
|
|
done
|
|
|
|
echo " -------------------------------------"
|
|
echo " a b c d e f g h"
|
|
}
|
|
|
|
|
|
|
|
failure()
|
|
{ # Whine, then bail out.
|
|
echo
|
|
print_board
|
|
echo
|
|
echo " Waah!!! Ran out of squares to move to!"
|
|
echo -n " Knight's Tour attempt ended"
|
|
echo " on $(to_algebraic $currpos) [square #$currpos]"
|
|
echo " after just $movenum moves!"
|
|
echo
|
|
exit $FAIL
|
|
}
|
|
|
|
|
|
|
|
xlat_coords () # Translate x/y coordinates to board position
|
|
{ #+ (board-array element #).
|
|
# For user input of starting board position as x/y coords.
|
|
# This function not used in initial release of ktour.sh.
|
|
# May be used in an updated version, for compatibility with
|
|
#+ standard implementation of the Knight's Tour in C, Python, etc.
|
|
if [ -z "$1" -o -z "$2" ]
|
|
then
|
|
return $FAIL
|
|
fi
|
|
|
|
local xc=$1
|
|
local yc=$2
|
|
|
|
let "board_index = $xc * $ROWS + yc"
|
|
|
|
if [ $board_index -lt $MIN -o $board_index -gt $MAX ]
|
|
then
|
|
return $FAIL # Strayed off the board!
|
|
else
|
|
return $board_index
|
|
fi
|
|
}
|
|
|
|
|
|
|
|
to_algebraic () # Translate board position (board-array element #)
|
|
{ #+ to standard algebraic notation used by chess players.
|
|
if [ -z "$1" ]
|
|
then
|
|
return $FAIL
|
|
fi
|
|
|
|
local element_no=$1 # Numerical board position.
|
|
local col_arr=( a b c d e f g h )
|
|
local row_arr=( 1 2 3 4 5 6 7 8 )
|
|
|
|
let "row_no = $element_no / $ROWS"
|
|
let "col_no = $element_no % $ROWS"
|
|
t1=${col_arr[col_no]}; t2=${row_arr[row_no]}
|
|
local apos=$t1$t2 # Concatenate.
|
|
echo $apos
|
|
}
|
|
|
|
|
|
|
|
from_algebraic () # Translate standard algebraic chess notation
|
|
{ #+ to numerical board position (board-array element #).
|
|
# Or recognize numerical input & return it unchanged.
|
|
if [ -z "$1" ]
|
|
then
|
|
return $FAIL
|
|
fi # If no command-line arg, then will default to random start pos.
|
|
|
|
local ix
|
|
local ix_count=0
|
|
local b_index # Board index [0-63]
|
|
local alpos="$1"
|
|
|
|
arow=${alpos:0:1} # position = 0, length = 1
|
|
acol=${alpos:1:1}
|
|
|
|
if [[ $arow =~ [[:digit:]] ]] # Numerical input?
|
|
then # POSIX char class
|
|
if [[ $acol =~ [[:alpha:]] ]] # Number followed by a letter? Illegal!
|
|
then return $FAIL
|
|
else if [ $alpos -gt $MAX ] # Off board?
|
|
then return $FAIL
|
|
else return $alpos # Return digit(s) unchanged . . .
|
|
fi #+ if within range.
|
|
fi
|
|
fi
|
|
|
|
if [[ $acol -eq $MIN || $acol -gt $ROWS ]]
|
|
then # Outside of range 1 - 8?
|
|
return $FAIL
|
|
fi
|
|
|
|
for ix in a b c d e f g h
|
|
do # Convert column letter to column number.
|
|
if [ "$arow" = "$ix" ]
|
|
then
|
|
break
|
|
fi
|
|
((ix_count++)) # Find index count.
|
|
done
|
|
|
|
((acol--)) # Decrementing converts to zero-based array.
|
|
let "b_index = $ix_count + $acol * $ROWS"
|
|
|
|
if [ $b_index -gt $MAX ] # Off board?
|
|
then
|
|
return $FAIL
|
|
fi
|
|
|
|
return $b_index
|
|
|
|
}
|
|
|
|
|
|
generate_moves () # Calculate all valid knight moves,
|
|
{ #+ relative to current position ($1),
|
|
#+ and store in ${moves} array.
|
|
local kt_hop=1 # One square :: short leg of knight move.
|
|
local kt_skip=2 # Two squares :: long leg of knight move.
|
|
local valmov=0 # Valid moves.
|
|
local row_pos; let "row_pos = $1 % $COLS"
|
|
|
|
|
|
let "move1 = -$kt_skip + $ROWS" # 2 sideways to-the-left, 1 up
|
|
if [[ `expr $row_pos - $kt_skip` -lt $MIN ]] # An ugly, ugly kludge!
|
|
then # Can't move off board.
|
|
move1=$BADMOVE # Not even temporarily.
|
|
else
|
|
((valmov++))
|
|
fi
|
|
let "move2 = -$kt_hop + $kt_skip * $ROWS" # 1 sideways to-the-left, 2 up
|
|
if [[ `expr $row_pos - $kt_hop` -lt $MIN ]] # Kludge continued ...
|
|
then
|
|
move2=$BADMOVE
|
|
else
|
|
((valmov++))
|
|
fi
|
|
let "move3 = $kt_hop + $kt_skip * $ROWS" # 1 sideways to-the-right, 2 up
|
|
if [[ `expr $row_pos + $kt_hop` -ge $COLS ]]
|
|
then
|
|
move3=$BADMOVE
|
|
else
|
|
((valmov++))
|
|
fi
|
|
let "move4 = $kt_skip + $ROWS" # 2 sideways to-the-right, 1 up
|
|
if [[ `expr $row_pos + $kt_skip` -ge $COLS ]]
|
|
then
|
|
move4=$BADMOVE
|
|
else
|
|
((valmov++))
|
|
fi
|
|
let "move5 = $kt_skip - $ROWS" # 2 sideways to-the-right, 1 dn
|
|
if [[ `expr $row_pos + $kt_skip` -ge $COLS ]]
|
|
then
|
|
move5=$BADMOVE
|
|
else
|
|
((valmov++))
|
|
fi
|
|
let "move6 = $kt_hop - $kt_skip * $ROWS" # 1 sideways to-the-right, 2 dn
|
|
if [[ `expr $row_pos + $kt_hop` -ge $COLS ]]
|
|
then
|
|
move6=$BADMOVE
|
|
else
|
|
((valmov++))
|
|
fi
|
|
let "move7 = -$kt_hop - $kt_skip * $ROWS" # 1 sideways to-the-left, 2 dn
|
|
if [[ `expr $row_pos - $kt_hop` -lt $MIN ]]
|
|
then
|
|
move7=$BADMOVE
|
|
else
|
|
((valmov++))
|
|
fi
|
|
let "move8 = -$kt_skip - $ROWS" # 2 sideways to-the-left, 1 dn
|
|
if [[ `expr $row_pos - $kt_skip` -lt $MIN ]]
|
|
then
|
|
move8=$BADMOVE
|
|
else
|
|
((valmov++))
|
|
fi # There must be a better way to do this.
|
|
|
|
local m=( $valmov $move1 $move2 $move3 $move4 $move5 $move6 $move7 $move8 )
|
|
# ${moves[0]} = number of valid moves.
|
|
# ${moves[1]} ... ${moves[8]} = possible moves.
|
|
echo "${m[*]}" # Elements of array to stdout for capture in a var.
|
|
|
|
}
|
|
|
|
|
|
|
|
is_on_board () # Is position actually on the board?
|
|
{
|
|
if [[ "$1" -lt "$MIN" || "$1" -gt "$MAX" ]]
|
|
then
|
|
return $FAILURE
|
|
else
|
|
return $SUCCESS
|
|
fi
|
|
}
|
|
|
|
|
|
|
|
do_move () # Move the knight!
|
|
{
|
|
local valid_moves=0
|
|
local aapos
|
|
currposl="$1"
|
|
lmin=$ROWS
|
|
iex=0
|
|
squarel=
|
|
mpm=
|
|
mov=
|
|
declare -a p_moves
|
|
|
|
########################## DECIDE-MOVE #############################
|
|
if [ $startpos -ne $CRITPOS ]
|
|
then # CRITPOS = square #37
|
|
decide_move
|
|
else # Needs a special patch for startpos=37 !!!
|
|
decide_move_patched # Why this particular move and no other ???
|
|
fi
|
|
####################################################################
|
|
|
|
(( ++movenum )) # Increment move count.
|
|
let "square = $currposl + ${moves[iex]}"
|
|
|
|
################## DEBUG ###############
|
|
if [ "$DEBUG" ]
|
|
then debug # Echo debugging information.
|
|
fi
|
|
##############################################
|
|
|
|
if [[ "$square" -gt $MAX || "$square" -lt $MIN ||
|
|
${board[square]} -ne $UNVISITED ]]
|
|
then
|
|
(( --movenum )) # Decrement move count,
|
|
echo "RAN OUT OF SQUARES!!!" #+ since previous one was invalid.
|
|
return $FAIL
|
|
fi
|
|
|
|
board[square]=$movenum
|
|
currpos=$square # Update current position.
|
|
((valid_moves++)); # moves[0]=$valid_moves
|
|
aapos=$(to_algebraic $square)
|
|
echo -n "$aapos "
|
|
test $(( $Moves % $LINELEN )) -eq 0 && echo
|
|
# Print LINELEN=21 moves per line. A valid tour shows 3 complete lines.
|
|
return $valid_moves # Found a square to move to!
|
|
}
|
|
|
|
|
|
|
|
do_move_stupid() # Dingbat algorithm,
|
|
{ #+ courtesy of script author, *not* Warnsdorff.
|
|
local valid_moves=0
|
|
local movloc
|
|
local squareloc
|
|
local aapos
|
|
local cposloc="$1"
|
|
|
|
for movloc in {1..8}
|
|
do # Move to first-found unvisited square.
|
|
let "squareloc = $cposloc + ${moves[movloc]}"
|
|
is_on_board $squareloc
|
|
if [ $? -eq $SUCCESS ] && [ ${board[squareloc]} -eq $UNVISITED ]
|
|
then # Add conditions to above if-test to improve algorithm.
|
|
(( ++movenum ))
|
|
board[squareloc]=$movenum
|
|
currpos=$squareloc # Update current position.
|
|
((valid_moves++)); # moves[0]=$valid_moves
|
|
aapos=$(to_algebraic $squareloc)
|
|
echo -n "$aapos "
|
|
test $(( $Moves % $LINELEN )) -eq 0 && echo # Print 21 moves/line.
|
|
return $valid_moves # Found a square to move to!
|
|
fi
|
|
done
|
|
|
|
return $FAIL
|
|
# If no square found in all 8 loop iterations,
|
|
#+ then Knight's Tour attempt ends in failure.
|
|
|
|
# Dingbat algorithm will typically fail after about 30 - 40 moves,
|
|
#+ but executes _much_ faster than Warnsdorff's in do_move() function.
|
|
}
|
|
|
|
|
|
|
|
decide_move () # Which move will we make?
|
|
{ # But, fails on startpos=37 !!!
|
|
for mov in {1..8}
|
|
do
|
|
let "squarel = $currposl + ${moves[mov]}"
|
|
is_on_board $squarel
|
|
if [[ $? -eq $SUCCESS && ${board[squarel]} -eq $UNVISITED ]]
|
|
then # Find accessible square with least possible future moves.
|
|
# This is Warnsdorff's algorithm.
|
|
# What happens is that the knight wanders toward the outer edge
|
|
#+ of the board, then pretty much spirals inward.
|
|
# Given two or more possible moves with same value of
|
|
#+ least-possible-future-moves, this implementation chooses
|
|
#+ the _first_ of those moves.
|
|
# This means that there is not necessarily a unique solution
|
|
#+ for any given starting position.
|
|
|
|
possible_moves $squarel
|
|
mpm=$?
|
|
p_moves[mov]=$mpm
|
|
|
|
if [ $mpm -lt $lmin ] # If less than previous minimum ...
|
|
then # ^^
|
|
lmin=$mpm # Update minimum.
|
|
iex=$mov # Save index.
|
|
fi
|
|
|
|
fi
|
|
done
|
|
}
|
|
|
|
|
|
|
|
decide_move_patched () # Decide which move to make,
|
|
{ # ^^^^^^^ #+ but only if startpos=37 !!!
|
|
for mov in {1..8}
|
|
do
|
|
let "squarel = $currposl + ${moves[mov]}"
|
|
is_on_board $squarel
|
|
if [[ $? -eq $SUCCESS && ${board[squarel]} -eq $UNVISITED ]]
|
|
then
|
|
possible_moves $squarel
|
|
mpm=$?
|
|
p_moves[mov]=$mpm
|
|
|
|
if [ $mpm -le $lmin ] # If less-than-or equal to prev. minimum!
|
|
then # ^^
|
|
lmin=$mpm
|
|
iex=$mov
|
|
fi
|
|
|
|
fi
|
|
done # There has to be a better way to do this.
|
|
}
|
|
|
|
|
|
|
|
possible_moves () # Calculate number of possible moves,
|
|
{ #+ given the current position.
|
|
|
|
if [ -z "$1" ]
|
|
then
|
|
return $FAIL
|
|
fi
|
|
|
|
local curr_pos=$1
|
|
local valid_movl=0
|
|
local icx=0
|
|
local movl
|
|
local sq
|
|
declare -a movesloc
|
|
|
|
movesloc=( $(generate_moves $curr_pos) )
|
|
|
|
for movl in {1..8}
|
|
do
|
|
let "sq = $curr_pos + ${movesloc[movl]}"
|
|
is_on_board $sq
|
|
if [ $? -eq $SUCCESS ] && [ ${board[sq]} -eq $UNVISITED ]
|
|
then
|
|
((valid_movl++));
|
|
fi
|
|
done
|
|
|
|
return $valid_movl # Found a square to move to!
|
|
}
|
|
|
|
|
|
strategy ()
|
|
{
|
|
echo
|
|
|
|
if [ -n "$STUPID" ]
|
|
then
|
|
for Moves in {1..63}
|
|
do
|
|
cposl=$1
|
|
moves=( $(generate_moves $currpos) )
|
|
do_move_stupid "$currpos"
|
|
if [ $? -eq $FAIL ]
|
|
then
|
|
failure
|
|
fi
|
|
done
|
|
fi
|
|
|
|
# Don't need an "else" clause here,
|
|
#+ because Stupid Strategy will always fail and exit!
|
|
for Moves in {1..63}
|
|
do
|
|
cposl=$1
|
|
moves=( $(generate_moves $currpos) )
|
|
do_move "$currpos"
|
|
if [ $? -eq $FAIL ]
|
|
then
|
|
failure
|
|
fi
|
|
|
|
done
|
|
# Could have condensed above two do-loops into a single one,
|
|
echo #+ but this would have slowed execution.
|
|
|
|
print_board
|
|
echo
|
|
echo "Knight's Tour ends on $(to_algebraic $currpos) [square #$currpos]."
|
|
return $SUCCESS
|
|
}
|
|
|
|
debug ()
|
|
{ # Enable this by setting DEBUG=1 near beginning of script.
|
|
local n
|
|
|
|
echo "================================="
|
|
echo " At move number $movenum:"
|
|
echo " *** possible moves = $mpm ***"
|
|
# echo "### square = $square ###"
|
|
echo "lmin = $lmin"
|
|
echo "${moves[@]}"
|
|
|
|
for n in {1..8}
|
|
do
|
|
echo -n "($n):${p_moves[n]} "
|
|
done
|
|
|
|
echo
|
|
echo "iex = $iex :: moves[iex] = ${moves[iex]}"
|
|
echo "square = $square"
|
|
echo "================================="
|
|
echo
|
|
} # Gives pretty complete status after ea. move.
|
|
|
|
|
|
|
|
# =============================================================== #
|
|
# int main () {
|
|
from_algebraic "$1"
|
|
startpos=$?
|
|
if [ "$startpos" -eq "$FAIL" ] # Okay even if no $1.
|
|
then # ^^^^^^^^^^^ Okay even if input -lt 0.
|
|
echo "No starting square specified (or illegal input)."
|
|
let "startpos = $RANDOM % $SQUARES" # 0 - 63 permissable range.
|
|
fi
|
|
|
|
|
|
if [ "$2" = "stupid" ]
|
|
then
|
|
STUPID=1
|
|
echo -n " ### Stupid Strategy ###"
|
|
else
|
|
STUPID=''
|
|
echo -n " *** Warnsdorff's Algorithm ***"
|
|
fi
|
|
|
|
|
|
initialize_board
|
|
|
|
movenum=0
|
|
board[startpos]=$movenum # Mark each board square with move number.
|
|
currpos=$startpos
|
|
algpos=$(to_algebraic $startpos)
|
|
|
|
echo; echo "Starting from $algpos [square #$startpos] ..."; echo
|
|
echo -n "Moves:"
|
|
|
|
strategy "$currpos"
|
|
|
|
echo
|
|
|
|
exit 0 # return 0;
|
|
|
|
# } # End of main() pseudo-function.
|
|
# =============================================================== #
|
|
|
|
|
|
# Exercises:
|
|
# ---------
|
|
#
|
|
# 1) Extend this example to a 10 x 10 board or larger.
|
|
# 2) Improve the "stupid strategy" by modifying the
|
|
# do_move_stupid function.
|
|
# Hint: Prevent straying into corner squares in early moves
|
|
# (the exact opposite of Warnsdorff's algorithm!).
|
|
# 3) This script could stand considerable improvement and
|
|
# streamlining, especially in the poorly-written
|
|
# generate_moves() function
|
|
# and in the DECIDE-MOVE patch in the do_move() function.
|
|
# Must figure out why standard algorithm fails for startpos=37 ...
|
|
#+ but _not_ on any other, including symmetrical startpos=26.
|
|
# Possibly, when calculating possible moves, counts the move back
|
|
#+ to the originating square. If so, it might be a relatively easy fix.
|