SCXML-Sudoku

Ausführen des Beispiels

Zum Ausführen des Beispiels von Qt Creatorauszuführen, öffnen Sie den Modus Welcome und wählen Sie das Beispiel aus Examples aus. Weitere Informationen finden Sie unter Erstellen und Ausführen eines Beispiels.

Sudoku-Funktionen

Unser Sudoku enthält die folgenden Funktionen:

• Zu Beginn und nach Beendigung des Spiels wechselt das Sudoku in den Zustand idle. In diesem Zustand können die Spieler sehen, ob ihr letztes Spiel erfolgreich beendet wurde oder nicht. Der Zustandsautomat befindet sich dann in einem von zwei Unterzuständen des Zustands idle: solved bzw. unsolved. Im Zustand idle können die Spieler auch das Sudoku-Gitter auswählen, das sie lösen möchten. Das Gitter ist deaktiviert und die Benutzerinteraktion wird ignoriert.
• Nachdem die Spieler auf die Schaltfläche Start geklickt haben, geht das Sudoku in den Zustand playing über und ist bereit für die Benutzerinteraktion auf dem Spielbrett.
• Wenn sich das Spiel im Zustand playing befindet und die Spieler auf die Schaltfläche Stop klicken, endet das Spiel und geht in den Zustand unsolved über, der dem Zustand idle untergeordnet ist. Wenn die Spieler das aktuelle Rätsel erfolgreich gelöst haben, endet das Spiel automatisch und geht in den solved Unterzustand des idle Zustands über, der den Erfolg anzeigt.
• Das Spielbrett besteht aus 81 Knöpfen, die in einem 9x9-Gitter angeordnet sind. Die Schaltflächen mit den angegebenen Anfangswerten bleiben während des Spiels deaktiviert. Die Spieler können nur mit Schaltflächen interagieren, die anfangs leer sind. Jeder Klick auf eine Schaltfläche erhöht ihren Wert um eins.
• Während des Spiels steht den Spielern die Schaltfläche Undo zur Verfügung.

SCXML-Teil: Interne Logik Beschreibung

Die Datei sudoku.scxml beschreibt die interne Struktur der Zustände, die das Sudoku-Spiel einnehmen kann, definiert die Übergänge zwischen den Zuständen und löst die entsprechenden Skriptfunktionen aus, wenn die Übergänge stattfinden. Sie kommuniziert auch mit dem GUI-Teil, indem sie Ereignisse sendet und auf die anstehenden Ereignisse hört und auf sie reagiert.

Wir verwenden das ECMAScript-Datenmodell:

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

Wir deklarieren die folgenden Variablen:

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

Die obigen Variablen werden gemeinsam mit den Skript-Hilfsfunktionen verwendet, die in der Datei sudoku.js definiert sind:

    <script src="sudoku.js"/>

Wir rufen einige der dort definierten Funktionen bei Übergängen oder als Reaktion auf die von der GUI gesendeten Ereignisse auf.

Alle zuvor erwähnten möglichen Zustände sind in einem Stammzustand game definiert.

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

Wenn das Sudoku-Beispiel gestartet wird, tritt der Zustandsautomat in den Zustand game ein und bleibt in diesem Zustand, bis die Anwendung beendet wird. Beim Eintritt in diesen Zustand wird intern das Ereignis restart ausgelöst. Dieses Ereignis wird auch ausgelöst, wenn die Spieler das aktuelle Sudoku-Gitter ändern oder wenn sie das Spiel durch Drücken der Schaltfläche Start starten. Wir wollen es nicht senden, wenn sie das aktuelle Spiel beendet haben, weil wir immer noch das gefüllte Raster des letzten Spiels anzeigen wollen. Dieses Ereignis wird also von drei verschiedenen Kontexten ausgelöst und intern einmal in einem ziellosen Übergang des Zustands game erfasst:

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

Wenn wir das Ereignis restart abfangen, rufen wir eine Hilfsskriptmethode restart() auf, die in der Datei sudoku.js definiert ist, und lösen intern ein weiteres Ereignis update aus.

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

Die Funktion restart() weist die Variable initState der Variable currentState zu und löscht die Variable undoStack.

Das Ereignis update wird intern immer dann ausgelöst, wenn wir der GUI mitteilen wollen, dass der Inhalt des Grids geändert wurde und die GUI sich entsprechend der übergebenen Werte aktualisieren soll. Dieses Ereignis wird in einem weiteren ziellosen Übergang des Zustands game abgefangen:

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

Wir senden das externe Ereignis updateGUI, das im C++-Code abgefangen wird. Das Ereignis updateGUI ist mit zusätzlichen Daten ausgestattet, die in <param> Elementen angegeben sind. Wir übergeben zwei Parameter, die von außen über die Namen currentState und initState zugänglich sind. Die tatsächlichen Werte, die für sie übergeben werden, entsprechen den Variablen currentState bzw. initState des Datenmodells, die durch die Attribute expr angegeben werden.

        <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>

Wenn wir uns im Zustand idle befinden, reagieren wir auf zwei Ereignisse, die vom GUI-Teil gesendet werden können: start und setup. Wenn wir das Ereignis start erhalten, gehen wir einfach in den Zustand playing über. Wenn wir das Ereignis setup empfangen, erwarten wir, dass der GUI-Teil uns das neue zu lösende Gitter geschickt hat. Es wird erwartet, dass der neue Anfangszustand des Gitters über das Feld initState von _event.data übergeben wird. Wir weisen den übergebenen Wert der in unserem Datenmodell definierten Variable initState zu und starten den Inhalt des Gitters neu.

        <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>

Jedes Mal, wenn wir den Zustand playing erreichen, setzen wir den Inhalt des Gitters zurück, da wir immer noch den Inhalt des vorherigen Spiels hätten anzeigen können. Im Zustand playing reagieren wir auf mögliche Ereignisse, die von der GUI gesendet werden: tap, undo, und stop.

Das Ereignis tap wird gesendet, wenn die Spieler auf eines der aktivierten Sudoku-Felder drücken. Es wird erwartet, dass dieses Ereignis zusätzliche Daten enthält, die die Koordinaten der Zelle spezifizieren, die über die Felder x und y von _event.data übergeben werden. Zunächst prüfen wir, ob die übergebenen Koordinaten gültig sind, indem wir die Skriptfunktion isValidPosition() aufrufen:

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;
}

Wir stellen sicher, dass die Koordinaten weder negativ noch größer als unser Raster sind. Außerdem prüfen wir, ob die Koordinaten auf eine anfänglich leere Zelle zeigen, da wir die Zellen, die durch die Gitterbeschreibung vorgegeben sind, nicht verändern können.

Wenn wir sichergestellt haben, dass die übergebenen Koordinaten korrekt sind, rufen wir die Skriptfunktion calculateCurrentState() auf:

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]);
}

Diese Funktion erhöht den Wert der Zelle des übergebenen Gitters und fügt den neuen Zug in den Verlauf des Rückgängig-Stapels ein.

Gleich nachdem die Funktion calculateCurrentState() ihre Ausführung beendet hat, überprüfen wir, ob das Gitter bereits gelöst ist, indem wir die Skriptfunktion isSolved() aufrufen:

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;
}

Die Funktion isSolved() gibt true zurück, wenn das Gitter richtig gelöst ist. Da wir jede Zeile, jede Spalte und jedes 3x3-Quadrat überprüfen müssen, definieren wir die Hilfsfunktion isOK(). Diese Funktion nimmt die Liste der Zahlen und gibt true zurück, wenn die übergebene Liste eindeutige Zahlen enthält und keine Zahl gleich Null ist, d.h. keine leere Zelle vorhanden ist. Die Hauptschleife von isSolved() wird neunmal aufgerufen. Bei jeder Iteration werden drei Listen mit Zahlen erstellt, die eine Zeile, eine Spalte und ein Quadrat des Gitters repräsentieren, und isOK() aufgerufen. Wenn alle 27 Listen in Ordnung sind, ist das Gitter richtig gelöst und wir geben true zurück.

Kehren wir zu unserer SCXML-Datei zurück, so lösen wir intern das Ereignis solved aus, wenn isSolved() true zurückgibt. Die letzte Anweisung im Falle einer korrekten Verschiebung ist die Auslösung des Ereignisses update, da wir die GUI über die Änderung des Gitters informieren müssen.

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

Im Zustand playing reagieren wir auch auf das Ereignis undo, das von der GUI gesendet wird. In diesem Fall rufen wir die Skriptfunktion undo() auf und benachrichtigen die grafische Benutzeroberfläche über die Notwendigkeit einer Aktualisierung.

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;
}

Die Funktion undo() entfernt den letzten Zug aus der Historie, falls es einen gab, und verringert den aktuellen Wert für die Zelle, die durch die Koordinaten aus diesem Zug beschrieben wird.

Der Zustand playing ist auch für das Ereignis stop bereit, das von der grafischen Benutzeroberfläche gesendet wird, wenn die Spieler die Schaltfläche Stop drücken. In diesem Fall aktivieren wir einfach den Zustand idle.

Darüber hinaus fangen wir das intern gesendete Ereignis solved ab und aktivieren in diesem Fall den Zustand solved.

C++ Teil: Konstruktion der GUI

Der C++-Teil der Anwendung besteht aus einer Klasse MainWindow, die die grafische Benutzeroberfläche konstruiert und mit dem SCXML-Teil verbindet. Die Klasse wird in mainwindow.h deklariert.

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;
};

Die Klasse MainWindow enthält den Zeiger auf QScxmlStateMachine *m_machine, die von Qt automatisch aus der Datei sudoku.scxml generierte Zustandsautomatenklasse. Sie enthält auch die Zeiger auf einige GUI-Elemente.

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

Der Konstruktor der Klasse MainWindow instanziiert den GUI-Teil der Anwendung und speichert den Zeiger auf den übergebenen Zustandsautomaten. Er initialisiert auch den GUI-Teil und bindet den GUI-Teil an den Zustandsautomaten, indem er ihre Kommunikationsschnittstellen miteinander verbindet.

            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);
            });

Zunächst erstellen wir 81 Schaltflächen und verbinden deren clicked Signal mit einem Lambda-Ausdruck, der das tap Ereignis an den Zustandsautomaten weiterleitet und die Koordinaten der Schaltfläche übergibt.

Später fügen wir dem Gitter einige horizontale und vertikale Linien hinzu, um die Schaltflächen in 3x3 Boxen zu gruppieren.

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

Wir erstellen die Schaltfläche Start / Stop und verbinden ihr Klick-Signal mit einem Lambda-Ausdruck, der das Ereignis stop oder start auslöst, je nachdem, ob sich die Maschine im Zustand playing befindet oder nicht.

Wir erstellen ein Etikett, das angibt, ob das Gitter gelöst ist oder nicht, und eine Schaltfläche Undo, die das Ereignis undo auslöst, wenn sie angeklickt wird.

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

Dann erstellen wir eine Combobox, die mit den Namen der zu lösenden Raster gefüllt wird. Diese Gitter werden aus dem Verzeichnis :/data der in der Anwendung kompilierten Ressourcen gelesen.

    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);

Jedes Mal, wenn die Spieler das Gitter in der Combobox ändern, lesen wir den Inhalt des Gitters und speichern ihn in der Variantenkarte unter dem Schlüssel initValues als Liste von Listen mit int-Varianten, und wir übermitteln das Ereignis setup an die Zustandsmaschine, die den Inhalt des Gitters weitergibt. Zu Beginn lesen wir das erste verfügbare Gitter aus der Liste und übergeben es direkt an den Sudoku-Automaten als Anfangsgitter.

    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) {
        ...
    });

Später stellen wir eine Verbindung zu den Signalen her, die immer dann gesendet werden, wenn der Automat in den Zustand playing oder solved eintritt oder diesen verlässt, und aktualisieren einige Teile der Benutzeroberfläche entsprechend. Außerdem stellen wir eine Verbindung zum Ereignis updateGUI des Zustandsautomaten her und aktualisieren die Werte aller Schaltflächen entsprechend dem Zustand der übergebenen Zellen.

#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();
}

In der Funktion main() in der Datei main.cpp instanziieren wir das Anwendungsobjekt app, den Zustandsautomaten Sudoku und die GUI-Klasse MainWindow. Wir starten den Zustandsautomaten, zeigen das Hauptfenster und führen die Anwendung aus.

Beispielprojekt @ code.qt.io