Sudoku SCXML

Exécution de l'exemple

Vous pouvez exécuter l'exemple à partir de :

• Qt Creator

  Ouvrez le mode « Welcome » et sélectionnez l'exemple dans « Examples ». Pour plus d'informations, consultez Qt Creator: Tutoriel : Compiler et exécuter.

• Qt Extension for Visual Studio Code

  Exécutez la commande « Qt: Open Qt examples » à partir de Command Palette, puis sélectionnez l'exemple dans la liste. Pour plus d'informations, consultez Qt Extension for Visual Studio Code: Tutoriel : Compiler et exécuter.

Fonctionnalités du Sudoku

Notre sudoku présente les fonctionnalités suivantes :

• Au démarrage et à la fin de la partie, le sudoku passe à l'état « idle ». Dans cet état, les joueurs peuvent voir si leur dernière partie s'est terminée avec succès ou non. La machine à états se trouve alors dans l'un des deux états enfants de l'état « idle » : « solved » ou « unsolved », respectivement. Dans l'état « idle », les joueurs peuvent également choisir la grille de sudoku qu'ils souhaitent résoudre. La grille est désactivée et les interactions de l’utilisateur sont ignorées.
• Une fois que les joueurs ont cliqué sur le bouton « Start », le sudoku passe à l’état « playing » et est prêt à recevoir les interactions de l’utilisateur sur le plateau.
• Lorsque le jeu est dans l’état « playing » et que les joueurs cliquent sur le bouton « Stop », le jeu se termine et passe à l’état enfant « unsolved » de l’état « idle ». Si les joueurs ont résolu le puzzle en cours avec succès, le jeu se termine automatiquement et passe à l’état enfant « solved » de l’état « idle », indiquant la réussite.
• Le plateau se compose de 81 boutons, disposés en une grille de 9x9. Les boutons dont les valeurs initiales sont indiquées restent désactivés pendant la partie. Les joueurs ne peuvent interagir qu’avec les boutons initialement vides. Chaque clic sur un bouton augmente sa valeur d’un.
• Pendant la partie, le bouton « Undo » est disponible pour faciliter la tâche des joueurs.

Partie SCXML : description de la logique interne

Le fichier sudoku.scxml décrit la structure interne des états dans lesquels le jeu de sudoku peut se trouver, définit les transitions entre ces états et déclenche les fonctions de script appropriées lorsque ces transitions ont lieu. Il communique également avec la partie interface graphique en envoyant des événements, en écoutant les événements à venir et en y réagissant.

Nous utilisons le modèle de données ECMAScript :

<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0"
       name="Sudoku" datamodel="ecmascript">

Nous déclarons les variables suivantes :

    <datamodel>
        <data id="initState"/>
        <data id="currentState" expr="[[]]"/>
        <data id="undoStack"/>
    </datamodel>

Les variables ci-dessus sont partagées avec les fonctions d'aide du script définies dans le fichier « sudoku.js » :

    <script src="sudoku.js"/>

Nous appelons certaines des fonctions qui y sont définies lors des transitions ou en réponse aux événements envoyés par l'interface graphique.

Tous les états possibles mentionnés précédemment sont définis dans un état racine game.

    <state id="game">
        <onentry>
            <raise event="restart"/>
        </onentry>
        <state id="idle">
            ...
            <state id="unsolved"/>
            <state id="solved"/>
        </state>
        <state id="playing">
            ...
        </state>
        ...
    </state>

Lorsque l’exemple de sudoku est lancé, la machine à états entre dans l’état « game » et y reste jusqu’à la fermeture de l’application. À l’entrée dans cet état, nous déclenchons en interne l’événement « restart ». Cet événement est également déclenché chaque fois que les joueurs modifient la grille de sudoku actuelle ou lorsqu’ils lancent la partie en cliquant sur le bouton « Start ». Nous ne souhaitons pas le déclencher lorsqu’ils ont terminé la partie en cours, car nous voulons continuer à afficher la grille complétée de la dernière partie. Ainsi, cet événement est déclenché à partir de trois contextes différents et est capturé en interne une fois lors d’une transition sans cible de l’état « game » :

        <transition event="restart">
            <script>
                restart();
            </script>
            <raise event="update"/>
        </transition>

Lorsque nous interceptons l’événement « restart », nous appelons une méthode de script d’aide « restart() », définie dans le fichier « sudoku.js », et déclenchons en interne un événement « update » supplémentaire.

function restart() {
    for (var i = 0; i < initState.length; i++)
        currentState[i] = initState[i].slice();
    undoStack = [];
}

La fonction ` restart() ` attribue la valeur de ` initState ` à la variable ` currentState ` et efface la variable ` undoStack `.

L’événement « update » est déclenché en interne chaque fois que l’on souhaite signaler à l’interface graphique que le contenu de la grille a été modifié et qu’elle doit se mettre à jour en fonction des valeurs transmises. Cet événement est intercepté lors d’une autre transition sans cible de l’état « game » :

        <transition event="update">
            <send event="updateGUI">
                <param name="currentState" expr="currentState"/>
                <param name="initState" expr="initState"/>
            </send>
        </transition>

Nous envoyons l’événement externe updateGUI, qui est intercepté dans le code C++. L’événement updateGUI est accompagné de données supplémentaires, spécifiées dans les éléments <param>. Nous transmettons deux paramètres, accessibles en externe via les noms currentState et initState. Les valeurs réelles qui leur sont transmises correspondent respectivement aux variables currentState et initState du modèle de données, qui sont spécifiées par les attributs expr.

        <state id="idle">
            <transition event="start" target="playing"/>
            <transition event="setup" target="unsolved">
                <assign location="initState" expr="_event.data.initState"/>
                <raise event="restart"/>
            </transition>
            <state id="unsolved"/>
            <state id="solved"/>
        </state>

Lorsque nous sommes dans l’état « idle », nous réagissons à deux événements pouvant être envoyés par la partie interface graphique : « start » et « setup ». Chaque fois que nous recevons l’événement « start », nous passons simplement à l’état « playing ». Lorsque nous recevons l’événement « setup », nous nous attendons à ce que la partie interface graphique nous ait envoyé la nouvelle grille à résoudre. Le nouvel état initial de la grille doit être transmis via le champ « initState » de _event.data. Nous attribuons la valeur transmise à la variable « initState » définie dans notre modèle de données et réinitialisons le contenu de la grille.

        <state id="playing">
            <onentry>
                <raise event="restart"/>
            </onentry>
            <transition event="tap">
                <if cond="isValidPosition()">
                    <script>
                        calculateCurrentState();
                    </script>
                    <if cond="isSolved()">
                        <raise event="solved"/>
                    </if>
                    <raise event="update"/>
                </if>
            </transition>
            ...
        </state>

Chaque fois que nous entrons dans l’état « playing », nous réinitialisons le contenu de la grille, car nous pourrions encore afficher le contenu de la partie précédente. Dans l’état « playing », nous réagissons aux événements éventuels envoyés par l’interface graphique : tap, undo et stop.

L’événement ` tap ` est envoyé lorsque les joueurs cliquent sur l’une des cases de sudoku activées. Cet événement est censé contenir des données supplémentaires précisant les coordonnées de la case, qui sont transmises via les champs ` x ` et ` y ` de ` _event.data`. Tout d’abord, nous vérifions si les coordonnées transmises sont valides en appelant la fonction de script ` isValidPosition() ` :

function isValidPosition() {
    var x = _event.data.x;
    var y = _event.data.y;
    if (x < 0 || x >= initState.length)
        return false;
    if (y < 0 || y >= initState.length)
        return false;
    if (initState[x][y] !== 0)
        return false;
    return true;
}

Nous nous assurons que les coordonnées ne sont ni négatives ni supérieures aux limites de notre grille. De plus, nous vérifions si les coordonnées désignent une cellule initialement vide, car nous ne pouvons pas modifier les cellules initialement définies par la description de la grille.

Une fois que nous nous sommes assurés que les coordonnées transmises sont correctes, nous appelons la fonction de script « calculateCurrentState() » :

function calculateCurrentState() {
    if (isValidPosition() === false)
        return;
    var x = _event.data.x;
    var y = _event.data.y;
    var currentValue = currentState[x][y];
    if (currentValue === initState.length)
        currentValue = 0;
    else
        currentValue += 1;
    currentState[x][y] = currentValue;
    undoStack.push([x, y]);
}

Cette fonction incrémente la valeur de la cellule de la grille passée en paramètre et ajoute le nouveau coup à l'historique de la pile d'annulation.

Dès que la fonction ` calculateCurrentState() ` a terminé son exécution, nous vérifions si la grille est déjà résolue en appelant la fonction de script ` isSolved() ` :

function isOK(numbers) {
    var temp = [];
    for (var i = 0; i < numbers.length; i++) {
        var currentValue = numbers[i];
        if (currentValue === 0)
            return false;
        if (temp.indexOf(currentValue) >= 0)
            return false;
        temp.push(currentValue);
    }
    return true;
}

function isSolved() {
    for (var i = 0; i < currentState.length; i++) {
        if (!isOK(currentState[i]))
            return false;

        var column = [];
        var square = [];
        for (var j = 0; j < currentState[i].length; j++) {
            column.push(currentState[j][i]);
            square.push(currentState[Math.floor(i / 3) * 3 + Math.floor(j / 3)]
                                    [i % 3 * 3 + j % 3]);
        }

        if (!isOK(column))
            return false;
        if (!isOK(square))
            return false;
    }
    return true;
}

La fonction ` isSolved() ` renvoie ` true ` si la grille est correctement résolue. Comme nous devons vérifier chaque ligne, chaque colonne et chaque carré 3x3, nous définissons la fonction auxiliaire ` isOK() `. Cette fonction prend une liste de nombres et renvoie ` true ` si la liste passée contient des nombres uniques et qu’aucun nombre n’est égal à zéro, ce qui signifie qu’il n’y a pas de case vide. La boucle principale de la fonction ` isSolved() ` est appelée neuf fois. À chaque itération, nous construisons trois listes de nombres représentant une ligne, une colonne et un carré de la grille, puis nous appelons la fonction ` isOK() ` pour chacune d’elles. Lorsque les 27 listes sont valides, la grille est correctement résolue et nous renvoyons ` true`.

Pour en revenir à notre fichier SCXML, si la méthode ` isSolved() ` renvoie ` true`, nous déclenchons en interne l’événement ` solved `. La dernière instruction, dans le cas d’un déplacement correct, consiste à déclencher l’événement ` update `, car nous devons signaler à l’interface graphique la modification de la grille.

        <state id="playing">
            ...
            <transition event="undo">
                <script>
                    undo();
                </script>
                <raise event="update"/>
            </transition>
            <transition event="stop" target="idle"/>
            <transition event="solved" target="solved"/>
        </state>

Lorsque nous sommes dans l'état « playing », nous réagissons également à l'événement « undo » envoyé par l'interface graphique. Dans ce cas, nous appelons la fonction de script « undo() » et signalons à l'interface graphique la nécessité d'une mise à jour.

function undo() {
    if (!undoStack.length)
        return;

    var lastMove = undoStack.pop();
    var x = lastMove[0];
    var y = lastMove[1];
    var currentValue = currentState[x][y];
    if (currentValue === 0)
        currentValue = initState.length;
    else
        currentValue -= 1;
    currentState[x][y] = currentValue;
}

La fonction undo() supprime le dernier coup de l’historique, s’il y en a eu un, et décrémente la valeur actuelle de la case décrite par les coordonnées issues de ce coup.

L’état « playing » est également prêt à recevoir l’événement « stop » envoyé par l’interface graphique lorsque les joueurs cliquent sur le bouton « Stop ». Dans ce cas, nous activons simplement l’état « idle ».

De plus, nous interceptons l’événement « solved » envoyé en interne et activons l’état « solved » dans ce cas.

Partie C++ : Construction de l’interface graphique

La partie C++ de l'application se compose d'une classe ` MainWindow ` qui construit l'interface graphique et l'intègre à la partie SCXML. Cette classe est déclarée dans le fichier `mainwindow.h`.

class MainWindow : public QWidget
{
    Q_OBJECT

public:
    explicit MainWindow(QScxmlStateMachine *machine, QWidget *parent = nullptr);

private:
    QScxmlStateMachine *m_machine = nullptr;
    QList<QList<QToolButton *>> m_buttons;
    QToolButton *m_startButton = nullptr;
    QToolButton *m_undoButton = nullptr;
    QLabel *m_label = nullptr;
    QComboBox *m_chooser = nullptr;
};

La classe ` MainWindow ` contient le pointeur vers ` QScxmlStateMachine *m_machine`, qui est la classe de machine à états générée automatiquement par Qt à partir du fichier ` sudoku.scxml `. Elle contient également les pointeurs vers certains éléments de l'interface graphique.

MainWindow::MainWindow(QScxmlStateMachine *machine, QWidget *parent) :
    QWidget(parent),
    m_machine(machine)
{

Le constructeur de la classe ` MainWindow ` instancie la partie interface graphique de l'application et stocke le pointeur vers la machine à états transmise. Il initialise également la partie interface graphique et relie celle-ci à la machine à états en connectant leurs interfaces de communication entre elles.

            connect(button, &QToolButton::clicked, this, [this, i, j]() {
                QVariantMap data;
                data.insert(u"x"_s, i);
                data.insert(u"y"_s, j);
                m_machine->submitEvent("tap", data);
            });

Tout d’abord, nous créons 81 boutons et connectons leur signal « clicked » à une expression lambda qui envoie l’événement « tap » à la machine à états en lui transmettant les coordonnées du bouton.

Par la suite, nous ajoutons des lignes horizontales et verticales à la grille afin de regrouper les boutons dans des cases de 3x3.

    connect(m_startButton, &QAbstractButton::clicked, this, [this]() {
        if (m_machine->isActive("playing"))
            m_machine->submitEvent("stop");
        else
            m_machine->submitEvent("start");
    });

Nous créons le bouton « Start / Stop » et connectons son signal « clicked » à une expression lambda qui déclenche l’événement « stop » ou « start », selon que la machine se trouve ou non dans l’état « playing », respectivement.

Nous créons une étiquette indiquant si la grille est résolue ou non, ainsi qu’un bouton « Undo », qui déclenche l’événement « undo » à chaque fois qu’on clique dessus.

    connect(m_undoButton, &QAbstractButton::clicked, this, [this]() {
        m_machine->submitEvent("undo");
    });

Nous créons ensuite une liste déroulante contenant les noms des grilles à résoudre. Ces grilles sont lues à partir du répertoire « :/data » des ressources intégrées à l'application.

    connect(m_chooser, &QComboBox::currentIndexChanged, this, [this](int index) {
        const QString sudokuFile = m_chooser->itemData(index).toString();
        const QVariantMap initValues = readSudoku(sudokuFile);
        m_machine->submitEvent("setup", initValues);
    });

    const QVariantMap initValues = readSudoku(
                m_chooser->itemData(0).toString());
    m_machine->setInitialValues(initValues);

Chaque fois que les joueurs modifient la grille dans la liste déroulante, nous lisons le contenu de la grille et le stockons dans la carte « variant » sous la clé « initValues » sous la forme d’une liste de listes de variants de type int, puis nous déclenchons l’événement « setup » vers la machine à états en lui transmettant le contenu de la grille. Au départ, nous lisons la première grille disponible dans la liste et la transmettons directement à la machine à états de sudoku en tant que grille initiale.

    m_machine->connectToState("playing", [this] (bool playing) {
        ...
    });

    m_machine->connectToState("solved", [this](bool solved) {
        if (solved)
            m_label->setText(tr("SOLVED !!!"));
        else
            m_label->setText(tr("unsolved"));
    });

    m_machine->connectToEvent("updateGUI", [this](const QScxmlEvent &event) {
        ...
    });

Par la suite, nous nous connectons aux signaux émis chaque fois que la machine entre ou sort des états « playing » ou « solved », et nous mettons à jour certaines parties de l’interface graphique en conséquence. Nous nous connectons également à l’événement « updateGUI » de la machine à états et mettons à jour les valeurs de tous les boutons en fonction des états des cases transmises.

#include "mainwindow.h"
#include "sudoku.h"

#include <QtWidgets/qapplication.h>

int main(int argc, char **argv)
{
    QApplication app(argc, argv);

    Sudoku machine;
    MainWindow mainWindow(&machine);

    machine.start();
    mainWindow.show();
    return app.exec();
}

Dans la fonction main() du fichier main.cpp, nous instancions l’objet d’application app, la machine à états Sudoku et la classe d’interface graphique MainWindow. Nous démarrons la machine à états, affichons la fenêtre principale et exécutons l’application.

Exemple de projet sur code.qt.io