Backtracking, one of the ways to solve some kind of problems is backtracking. A good book ?

Alain De Vos

Alain De Vos

I'm looking for a book who explains backtracking, with exercises. For me it can be in any programming language.
For instance you can use backtracking to play chess or checkers.
 
To illustrate backtracking, I used to sit the student in front of xmaze. Worked a charm.
 
pay any sum greater than 7 with coins of 3 and 5
Bash: 
#!/bin/sh

pay() {
 local stack=$2
 local sum=$1
 local temp
 if [ $sum -eq 0 ]
  then
   echo "DONE $GSUM with $stack"
   done=1
   return
  fi
 
 for i in 1 2
  do
  eval 'ccoin=$COIN'_$i
  temp=$(($sum - $ccoin))
  [ $temp -ge 0 ] && pay $temp "$stack $ccoin"
  [ $done -eq 1 ] && return
 done
}
COIN_1=3
COIN_2=5
done=0
echo PAYING $1 with coins of $COIN_1 and $COIN_2
GSUM=$1
pay $GSUM ""
 
People solve the 8 Queens Problem using backtracking. Here's a good article with example code:

www.interviewbit.com

8 Queens Problem

Table Of Contents show Approach : Bruteforce Efficient Approach: Backtracking Implementation of the Approach C++ Implementation Java Implementation Python Implementation Practice Questions FAQ Given a…
www.interviewbit.com
 
:D needs a terminal with more than 31 lines and 76 columns
Bash: 
#!/bin/sh
# maze generated at https://www.dcode.fr/maze-generator
solve() {
local row
local col
row=$1
col=$2
eval block_${row}_${col}=1
print_at $row $col Y
[ $row -eq $FIN_ROW -a $col -eq $FIN_COL ] && DONE=1 && return
try_at $row $(($col + 1)) $row $col
[ $DONE -eq 1 ] && return
try_at $(($row + 1)) $col $row $col
[ $DONE -eq 1 ] && return
try_at $row $(($col - 1)) $row $col
[ $DONE -eq 1 ] && return
try_at $(($row - 1)) $col $row $col
[ $DONE -eq 1 ] && return
delete_at $row $col
sleep 0.05
#unset block_${row}_${col}
}
try_at() {
#echo try $1 $2
get_at $1 $2
[ $ret = "B" ] && return
bold_at $3 $4 .
sleep 0.05
solve $1 $2
}

print_at() {
tput cm $(($2 - 1)) $(($1 - 1))
echo -n "$3"
}

delete_at() {
 local v
 tput me
 print_at $1 $2 " "
 }

bold_at() {
 tput md
print_at $1 $2 $3
}

get_at() {
local r
local c
ret=B
r=$1
c=$2
eval 'o=$block_'${r}_${c}
[ $r -lt 1 -o $c -lt 1 -o $r -gt 31 -o $c -gt 76 -o "$o" = "1" ] && return
local v
v=maze_${r}_${c}
eval ret=\$$v
}
exec << EOF
...BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
...B........B..B........B..............B..B..B........B..B.....B..B..B.....B
B..B..BBBBBBB..BBBB..B..BBBB..B..BBBBBBB..B..BBBB..B..B..B..B..B..B..B..BBBB
B..B........B........B..B.....B...........B........B.....B..B.....B........B
B..B..BBBB..BBBBBBB..BBBB..BBBB..BBBBBBBBBBBBB..BBBB..BBBB..B..BBBBBBBBBB..B
B.....B...........B...........B..B........B.....B.....B.....B..B...........B
B..BBBB..BBBB..BBBB..BBBBBBB..B..B..BBBBBBB..B..B..BBBB..BBBBBBBBBB..BBBB..B
B..B.....B..B..B.....B..B..B..B..B..B..B.....B..B..B.....B..B..B..B..B.....B
BBBBBBB..B..BBBB..BBBB..B..BBBB..B..B..BBBB..B..B..B..B..B..B..B..BBBB..BBBB
B..............B.....B..B..B..B..............B..B..B..B.....B.....B........B
B..BBBBBBB..B..BBBBBBB..B..B..B..BBBB..BBBBBBB..BBBB..BBBB..BBBB..BBBBBBB..B
B..B..B.....B.....B..B..............B..B...........B.....B.....B..B..B..B..B
B..B..BBBBBBB..B..B..BBBBBBBBBBBBBBBB..BBBBBBBBBBBBB..BBBB..BBBB..B..B..B..B
B.....B........B..B...........B..B..B.....B..B.....B.....B.................B
B..BBBB..B..BBBB..B..BBBB..BBBB..B..BBBB..B..BBBB..BBBB..B..BBBBBBB..B..BBBB
B.....B..B..B.....B.....B........B........B...........B..B........B..B..B..B
BBBB..B..B..BBBBBBBBBBBBBBBB..BBBBBBB..BBBBBBBBBBBBB..BBBB..BBBB..BBBB..B..B
B.....B..B.....B..B..B.................B.....B.....B........B.....B..B.....B
B..BBBBBBB..BBBB..B..BBBB..BBBBBBBBBB..BBBB..BBBB..B..BBBBBBBBBB..B..BBBBBBB
B..B........B........B........B.....B.......................B.....B..B.....B
BBBBBBBBBB..BBBBBBB..B..BBBB..B..B..BBBB..B..B..BBBB..BBBB..BBBBBBB..B..B..B
B........B..............B..B..B..B..B.....B..B..B.....B.....B.....B..B..B..B
B..BBBB..BBBB..BBBBBBB..B..BBBB..BBBBBBB..B..BBBBBBB..B..BBBB..BBBB..B..B..B
B..B........B.....B..B.................B..B..B.....B..B..B.....B........B..B
B..BBBBBBBBBB..B..B..BBBBBBBBBB..B..BBBBBBBBBBBBB..BBBB..B..BBBB..B..BBBB..B
B..B........B..B.....B...........B..B...........B.................B.....B..B
B..B..BBBB..B..B..B..BBBBBBB..BBBB..B..BBBBBBBBBBBBB..B..BBBB..B..B..B..B..B
B.....B.....B..B..B.....B..B..B..B.....B..B.....B.....B.....B..B..B..B..B..B
B..BBBBBBB..BBBB..BBBB..B..BBBB..B..B..B..B..B..BBBB..B..B..BBBBBBBBBB..B..B
B.....B..............B...........B..B........B..B.....B..B.....B........B...
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
EOF
i=1
tput reset cl
while read l
do
echo $l|tr "B." "# "

j=1
while [ "$l" != "" ]
 do
 ll=${l#B}
 if [ "$ll" = "$l" ]
 then
 char="."
 ll=${l#.}
 else char="B"
 fi
 l=$ll
 eval  maze_${i}_${j}='$char'
 j=$(($j+1))
 done
 i=$(($i + 1))
done
FIN_ROW=31
FIN_COL=76
DONE=0
solve 1 1
tput me
echo ""
 
You must log in or register to reply here.
Back
Top