If you major in Computer Science, you must know the 8-queens problem, which is a classical Artificial Intelligent problem that can be solved using back tracing. Previous posts can be found here and here.
I have just digged into my hard drive and found out that I wrote this 10 years ago (in 2004). It is a BASH shell script that solves the n-queen problem using back tracing algorithm.
The back tracing algorithm will go down the search tree to find solutions as far as it can go. If it reaches the maximum depth or a boundary is met (impossible solution), then it goes to the next possible move on the right, and it rewinds one level up if the possibilities in the current level are enumerated. Back tracing can be implemented by recursive or iterative methods. The following BASH uses non-recursive (iterative approach), which is more efficient than the recursive approach. The recursive back tracing is easier to code (and to understand) and more straightforward.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #!/bin/bash # variable declaration typeset -i BoardSize=8 typeset -i p=0 typeset -i total=0 typeset -i board # initialization function init { for (( i=0;i<$BoardSize;i++ )) do (( board[$i]=-1 )) done } # check if queen can be placed function place { typeset -i flag=1 for (( i=0;i<$1;i++ )) do if [[ (${board[$i]}-${board[$1]} -eq ${i}-${1}) || (${board[$i]}-${board[$1]} -eq ${1}-${i}) || (${board[$i]} -eq ${board[$1]}) ]] then (( flag=0 )) fi done [[ $flag -eq 0 ]] return $? } # print the result function out { printf "Problem of queen %d:%d\n" $BoardSize $total } # free the variables function depose { unset p unset total unset board unset BoardSize } # back tracing function work { while [[ $p -gt -1 ]] do (( board[$p]++ )) if [[ ${board[$p]} -ge ${BoardSize} ]] then # back tracing (( p-- )) else # try next position place $p if [[ $? -eq 1 ]] then (( p++ )) if [[ $p -ge ${BoardSize} ]] then (( total++ )) (( p-- )) else (( board[$p]=-1 )) fi fi fi done } # entry init work out depose |
#!/bin/bash
# variable declaration
typeset -i BoardSize=8
typeset -i p=0
typeset -i total=0
typeset -i board
# initialization
function init
{
for (( i=0;i<$BoardSize;i++ ))
do
(( board[$i]=-1 ))
done
}
# check if queen can be placed
function place
{
typeset -i flag=1
for (( i=0;i<$1;i++ ))
do
if [[ (${board[$i]}-${board[$1]} -eq ${i}-${1}) || (${board[$i]}-${board[$1]} -eq ${1}-${i}) || (${board[$i]} -eq ${board[$1]}) ]]
then
(( flag=0 ))
fi
done
[[ $flag -eq 0 ]]
return $?
}
# print the result
function out
{
printf "Problem of queen %d:%d\n" $BoardSize $total
}
# free the variables
function depose
{
unset p
unset total
unset board
unset BoardSize
}
# back tracing
function work
{
while [[ $p -gt -1 ]]
do
(( board[$p]++ ))
if [[ ${board[$p]} -ge ${BoardSize} ]]
then # back tracing
(( p-- ))
else # try next position
place $p
if [[ $? -eq 1 ]]
then
(( p++ ))
if [[ $p -ge ${BoardSize} ]]
then
(( total++ ))
(( p-- ))
else
(( board[$p]=-1 ))
fi
fi
fi
done
}
# entry
init
work
out
deposeMake sure you chmod +x queen.sh (assumed the filename is queen.sh) and run it under the shell.
1 2 | root@uploadbeta:/tmp/bash# ./queen.sh Problem of queen 8:92 |
root@uploadbeta:/tmp/bash# ./queen.sh Problem of queen 8:92
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Change All Filenames to Lowercase Under BASH for Files under Directories and Sub-Directories
Next Post: BASH Shell Script to Compute the Integer Factorial
