#! /bin/bash
#
# sudoku.sh : Résolution d'un sudoku 9x9 en bash 
#
# Edouard.Thiel@lif.univ-mrs.fr - 08/12/2005
#
# This program is free software under the terms of the 
# GNU Lesser General Public License (LGPL) version 2.1.


# Affiche la grille à partir du tableau G global

AffiGrille () {
    local x y v
    for ((y = 0; y < 9; y++)); do
        if ((y % 3 == 0)); then
            echo "+---------+---------+---------+"
        else
            echo "|         |         |         |"
        fi
        for ((x = 0; x < 9; x++)); do
            if ((x % 3 == 0)); then
                echo -n "|"
            fi
            v=$((G[y*9+x]))   # ou v="${G[$y*9+$x]}"
            if [ "$v" = 0 ]; then
                 echo -n " . "
            else echo -n " $v "
            fi
        done
        echo "|"
    done
    echo "+---------+---------+---------+"
}


# Réussi si la case en paramètre a une valeur possible dans G

CasePossible () {
    local i="$1" xi yi x y t c=0
    xi=$((i%9)) yi=$((i/9))
    
    for ((t=0; t<9; t++)); do
        if ((G[t*9+xi] == G[i])); then ((c++)); fi
    done
    if ((c > 1)); then return 1; fi
    
    for ((t=0; t<9; t++)); do
        if ((G[yi*9+t] == G[i])); then ((c++)); fi
    done
    if ((c > 2)); then return 1; fi
    
    xi=$(((xi/3)*3)) yi=$(((yi/3)*3))
    for ((y=yi; y<yi+3; y++)); do
        for ((x=xi; x<xi+3; x++)); do
            if ((G[y*9+x] == G[i])); then ((c++)); fi
        done 
    done
    return $((c > 3 ? 1 : 0));
}


# Programme principal

echo
echo "*** Résolution d'un sudoku 9x9 en bash ***"
echo "Edouard.Thiel@lif.univ-mrs.fr - 08/12/2005"
echo
echo "Taper le problème en 1 seule ligne de 81 digits, 0 pour les cases vides."
echo "3 exemples à copier/coller :"
echo "720000040300090060000080003007109680042000900800306005270000010004600290003710006"
echo "907100000405320001000070200000090003008507400500010000006030000100046907000001506"
echo "480000006001006050062500400000004000600098001000100800007039210050000603300000049"

while :; do
    echo "Entrez une ligne :"
    read ligne
    
    if [ ${#ligne} -ne 81 ]; then
        echo "Erreur: longueur ${#ligne} != 81" 1>&2
    else 
        break
    fi
done

# Mémorise la ligne dans les tableaux P et G
for ((i = 0 ; i <= 80; i++)); do
    P[$i]="${ligne:$i:1}"   # Sous-chaine à la position i de longueur 1 
    G[$i]="${P[$i]}"        # Recopie. On peut aussi faire ((G[i]=P[i]))
done

# Affiche la grille pour vérification
echo
echo "Grille du problème:"
AffiGrille

# Recherche d'une solution par backtracking

i=-1
while :; do             # ":" = "true" : boucle infinie
    echo -n -e "\r$i"   # Options de echo : help echo
    
    # Case suivante
    for ((i++; i < 81; i++)); do 
        if ((P[i] == 0)); then break; fi
    done
    
    # Solution trouvée
    if ((i >= 81)); then break; fi
    
    ((G[i]=0))
    while :; do
        # Valeur suivante
        ((G[i]++))
    
        if ((G[i] > 9)); then
            # Case précédente
            for ((i--; i >= 0; i--)); do 
                if ((P[i] == 0)); then break; fi
            done
            
            # Pas de solution
            if ((i < 0)); then break 2; fi
           
            # Va à valeur suivante
            continue;
        fi
    
        # Valeur possible : va à la case suivante
        if CasePossible "$i" ; then break; fi
    done
done
echo -n -e "\r"

# Affichage solution ou échec
if ((i < 0));
then echo "Pas de solution"
else echo "Solution trouvée :"
     AffiGrille
fi

# Fin succès
exit 0