Bonjour à tous.

Aujourd’hui, nous allons voir comment résoudre un Sudoku en moins d’une minute (en quelques millisecondes en réalité).

Bien évidemment, cette performance n’est pas humainement possible, et il nous faudra donc développer un petit algorithme pour y parvenir.

Cet algorithme sera divisé en deux parties :

• L’élimination “classique” des impossibilités
• La résolution par essais successifs

En ce qui concerne les classes utilisées, elles sont au nombre de quatre :

Les Zones représentent les cases du Sudoku, et sont composées d’une liste de chiffres encore possibles, et de la valeur réellement marquée sur ladite case.

La Grid, comme son nom l’indique, est la grille de jeu. Le Solver résoudra pour nous une Grid, et pour finir le Program récupèrera les entrées / sorties sous format console.

Voyons maintenant plus en détail l’algorithme.

Éliminer les chiffres impossibles dans les zones

Lors d’un Sudoku, nous avons deux états possibles pour une case : soit nous connaissons le chiffre qui se trouve dans la case, auquel cas celui-ci est écrit, soit nous hésitons entre un certain nombre de valeurs. Personnellement, lorsque je suis bloqué, j’ai tendance à écrire les chiffres possibles au crayon à papier dans la case, et les effacer lorsqu’ils deviennent impossibles. Une fois qu’il n’en reste qu’un, je l’écris définitivement. Et c’est exactement ce que nous allons faire.

La Grid possède trois méthodes publiques permettant justement de “nettoyer” les possibilités de chaque zone. On va ainsi vérifier s’il n’y a pas des chiffres déjà présents horizontalement, verticalement, ou dans les zones de 3 cases sur 3 cases qui composent la grille complète.

public bool CleanHorizontal();
public bool CleanVertical();
public bool Clean3X3();

A tout moment, si une case ne dispose plus que d’une seule possibilité, on considère cette case comme étant résolue.

Notre Solver n’a plus qu’à appeler ces méthodes de manière à “nettoyer la grille” :

private bool BasicSolve(Grid grid, bool checkErrors = false)
{
    bool hasAnyChange;
    do
    {
        hasAnyChange = grid.CleanHorizontal() | grid.CleanVertical() | grid.Clean3X3();
        OnBasicSolveStepPassed?.Invoke(grid, EventArgs.Empty);
        if (checkErrors && grid.HasError)
        {
            return false;
        }
    } while (hasAnyChange);
    return true;
}

On remarque la présence d’un évènement OnBasicSolveStepPassed, qui sera utilisé par le Program pour afficher les avancées de notre Solver.

On observe également l’utilisation de grid. HasError. Actuellement, notre grille ne peut pas être en erreur si la grille est réalisable, pour la bonne raison que notre façon d’agir ne nous expose à aucun moment à commettre une erreur.

Ce qui me force à introduire la seconde partie de l’algorithme, celle capable d’en réaliser.

La résolution par essais successifs.

Supposons que nous nous attaquions à la grille suivante :

private const string EmptyGrid = "1   6 2  \n" +
                                 "         \n" +
                                 "         \n" +
                                 "         \n" +
                                 "    4    \n" +
                                 "         \n" +
                                 "         \n" +
                                 "         \n" +
                                 "  7 3   5";

Il semble évident que nous ne disposons pas de suffisamment d’informations pour la résoudre en nous contentant de retirer les chiffres impossibles dans certaines Zones.

Il va donc nous falloir expérimenter un chiffre, voire si cet essai nous permet de gagner la partie, et si ce n’est pas le cas, essayer un autre chiffre. Il faut également que cette action se répète autant de fois que nous hésitons entre diverses valeurs.

C’est donc cette méthode TryMultipleValues qui va nous permettre de tester en profondeur des valeurs lorsque nous ne pouvons plus rien obtenir de nouveau de la grille actuelle.

private void TryMultipleValues(Grid grid)
{
    var newGrid = grid.Copy();
    Zone oldTriedZone = null;
    while (true)
    {
        var triedZone = newGrid.GetFirstNonEmptyZone();
        if (!triedZone.ForceResult())
        {
            if (oldTriedZone != null)
            {
                grid.Zones[oldTriedZone.X, oldTriedZone.Y].Possibilities.Remove(oldTriedZone.Result.Value);
            }
            return;
        }
        oldTriedZone = triedZone;
        if (!BasicSolve(newGrid, true))
        {
            grid.Zones[triedZone.X, triedZone.Y].Possibilities.Remove(triedZone.Result.Value);
            return;
        }
        if (newGrid.IsCompleted)
        {
            Grid = newGrid;
            _solved = true;
            return;
        }
        TryMultipleValues(newGrid);
    }
}

On récupère la 1ère zone disponible qui n’est pas encore résolue. Dans une copie de la grille de départ (en cas d’erreur, il ne faudra surtout pas que nos mauvais essais soient enregistrés sur la véritable grille), on va forcer une des valeurs possible pour cette zone. Si l’on ne peut plus forcer de valeur, cela signifie que tous les essais ont échoués et que nous pouvons donc prévenir la grille du niveau précédent que la valeur que nous cherchions est inaccessible.

Une fois cette valeur forcée, on tente de résoudre le Sudoku avec cette nouvelle valeur.

En cas d’erreur (deux chiffres identiques se retrouvent dans la même ligne, colonne, ou case 3×3 ) , rebelote, on prévient le niveau supérieur que la valeur testée ne convient pas.

Si la grille est terminée, nous avons terminé le jeu, et s’il ne l’est pas et qu’il n’y a pas d’erreur, nous devons effectuer de nouveau des essais multiples sur une nouvelle case.

Voila ! Vous pouvez maintenant impressionner vos amis en résolvant à toute vitesse vos Sudokus difficiles en un temps record, avec un simple regard discret sur votre écran d’ordinateur.

Comme toujours, les sources complètes du projet sont disponibles sur GitHub.