SCXML-Sudoku

Ausführen des Beispiels

Sie können das Beispiel ausführen unter:

• Qt Creator

  Öffnen Sie den Modus „ Welcome “ und wählen Sie das Beispiel unter „ Examples “ aus. Weitere Informationen finden Sie unter Qt Creator: Tutorial: Erstellen und Ausführen.

• Qt Extension for Visual Studio Code

  Führen Sie den Befehl „ Qt: Open Qt examples “ aus dem Verzeichnis „ Command Palette “ aus und wählen Sie das Beispiel aus der Liste aus. Weitere Informationen finden Sie unter Qt Extension for Visual Studio Code: Tutorial: Erstellen und Ausführen.

Sudoku-Funktionen

Unser Sudoku verfügt über die folgenden Funktionen:

• Zu Beginn und am Ende 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. Die Zustandsmaschine befindet sich dann in einem von zwei untergeordneten Zuständen des Zustands „ idle “: „ solved “ bzw. „ unsolved “. Im Zustand „ idle “ können die Spieler außerdem das Sudoku-Raster auswählen, das sie lösen möchten. Das Raster ist deaktiviert und Benutzerinteraktionen werden ignoriert.
• Nachdem die Spieler auf die Schaltfläche „ Start “ geklickt haben, wechselt das Sudoku in den Zustand „ playing “ und ist bereit für die Benutzerinteraktion auf dem Spielfeld.
• Befindet sich das Spiel im Zustand „ playing “ und klicken die Spieler auf die Schaltfläche „ Stop “, endet das Spiel und wechselt in den Unterzustand „ unsolved “ des Zustands „ idle “. Haben die Spieler das aktuelle Rätsel erfolgreich gelöst, endet das Spiel automatisch und wechselt in den Unterzustand „ solved “ des Zustands „ idle “, was den Erfolg anzeigt.
• Das Spielfeld besteht aus 81 Schaltflächen, die in einem 9×9-Raster angeordnet sind. Die Schaltflächen mit vorgegebenen 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 deren Wert um eins.
• Während des Spiels steht den Spielern die Schaltfläche „ Undo “ zur Verfügung.

SCXML-Teil: Beschreibung der internen Logik

Die Datei „sudoku.scxml“ beschreibt die interne Struktur der Zustände, in denen sich das Sudoku-Spiel befinden kann, definiert die Übergänge zwischen den Zuständen und löst die entsprechenden Skriptfunktionen aus, wenn diese Übergänge stattfinden. Außerdem kommuniziert sie mit dem GUI-Teil, indem sie Ereignisse sendet, auf anstehende Ereignisse achtet und auf diese 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 oben genannten Variablen werden gemeinsam mit den in der Datei „ sudoku.js “ definierten Skript-Hilfsfunktionen genutzt:

    <script src="sudoku.js"/>

Wir rufen einige der dort definierten Funktionen auf, wenn wir Übergänge vornehmen oder auf die von der GUI gesendeten Ereignisse reagieren.

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, wechselt die Zustandsmaschine in den Zustand „ game “ und verbleibt in diesem Zustand, bis die Anwendung beendet wird. Beim Eintritt in diesen Zustand lösen wir intern das Ereignis „ restart “ aus. Dieses Ereignis wird auch immer dann ausgelöst, wenn die Spieler das aktuelle Sudoku-Gitter ändern oder wenn sie das Spiel durch Drücken der Schaltfläche „ Start “ starten. Wir möchten dieses Ereignis nicht auslösen, wenn die Spieler das aktuelle Spiel beendet haben, da wir weiterhin das ausgefüllte Raster aus dem letzten Spiel anzeigen möchten. Somit wird dieses Ereignis aus drei verschiedenen Kontexten ausgelöst und intern einmalig 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 Hilfsmethode des Skripts „ restart() “ auf, die in der Datei „ sudoku.js “ definiert ist, und lösen intern ein zusätzliches „ update “-Ereignis 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 Variablen „ currentState “ zu und löscht die Variable „ undoStack “.

Das Ereignis „ update “ wird intern ausgelöst, wann immer wir die GUI darüber informieren möchten, dass sich der Inhalt des Rasters geändert hat und dass die GUI sich entsprechend den übergebenen Werten aktualisieren soll. Dieses Ereignis wird in einem weiteren zielfreien Ü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 den Elementen „ <param> “ festgelegt sind. Wir übergeben zwei Parameter, auf die extern über die Namen „ currentState “ und „ initState “ zugegriffen werden kann. Die tatsächlich dafür übergebenen Werte entsprechen den Variablen „ currentState “ bzw. „ initState “ des Datenmodells, die durch die Attribute „ expr “ festgelegt sind.

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

Im Zustand „ idle “ reagieren wir auf zwei Ereignisse, die vom GUI-Teil gesendet werden können: „ start “ und „ setup “. Immer wenn wir das Ereignis „ start “ empfangen, wechseln wir einfach in den Zustand „ playing “. Wenn wir das Ereignis „ setup “ empfangen, erwarten wir, dass der GUI-Teil uns das neue Raster zur Lösung gesendet hat. Der neue Anfangszustand des Rasters wird voraussichtlich über das Feld „ initState “ von „ _event.data “ übergeben. Wir weisen den übergebenen Wert der in unserem Datenmodell definierten Variablen „ initState “ zu und initialisieren den Inhalt des Rasters 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>

Immer wenn wir in den Zustand „ playing “ wechseln, setzen wir den Inhalt des Rasters zurück, da wir möglicherweise noch den Inhalt aus dem vorherigen Spielverlauf anzeigen würden. 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 eine der aktivierten Sudoku-Zellen klicken. Dieses Ereignis enthält voraussichtlich zusätzliche Daten, die die Koordinaten der Zelle angeben und über die Felder „ x “ und „ y “ der Klasse „ _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 sind noch über die Grenzen unseres Rasters hinausreichen. Außerdem prüfen wir, ob die Koordinaten auf eine zunächst leere Zelle verweisen, da wir die ursprünglich durch die Rasterbeschreibung vorgegebenen Zellen nicht ändern können.

Nachdem 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 Rasters und fügt den neuen Zug zum Rückgängig-Stapel hinzu.

Unmittelbar nachdem die Funktion „ calculateCurrentState() “ ihre Ausführung beendet hat, prüfen wir, ob das Raster 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 Rätsel korrekt 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 mit Zahlen entgegen und gibt ` true ` zurück, wenn die übergebene Liste eindeutige Zahlen enthält und keine Zahl gleich Null ist, was bedeutet, dass es keine leere Zelle gibt. Die Hauptschleife von „ isSolved() “ wird neunmal aufgerufen. In jeder Iteration erstellen wir drei Zahlenlisten, die jeweils eine Zeile, eine Spalte und ein Quadrat des Rasters darstellen, und rufen für diese die Funktion „ isOK() “ auf. Wenn alle 27 Listen in Ordnung sind, ist das Raster korrekt gelöst und wir geben „ true “ zurück.

Zurück zu unserer SCXML-Datei: Falls „ isSolved() “ den Wert „ true “ zurückgibt, lösen wir intern das Ereignis „ solved “ aus. Die letzte Anweisung im Falle eines korrekten Zuges besteht darin, das Ereignis „ update “ auszulösen, da wir die GUI über die Änderung des Rasters 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 ebenfalls auf das von der GUI gesendete Ereignis „ undo “. In diesem Fall rufen wir die Skriptfunktion „ undo() “ auf und benachrichtigen die GUI ü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 dem Verlauf, sofern vorhanden, und verringert den aktuellen Wert für die Zelle, die durch die aus diesem Zug entnommenen Koordinaten beschrieben wird.

Der Zustand „ playing “ ist auch bereit für das von der GUI gesendete Ereignis „ stop “, das ausgelöst wird, wenn die Spieler die Schaltfläche „ Stop “ betätigen. In diesem Fall aktivieren wir einfach den Zustand „ idle “.

Zudem fangen wir das intern gesendete Ereignis „ solved “ ab und aktivieren in diesem Fall den Zustand „ solved “.

C++-Teil: Aufbau der Benutzeroberfläche

Der C++-Teil der Anwendung besteht aus einer Klasse „ MainWindow “, die die GUI aufbaut und sie mit dem SCXML-Teil verknüpft. Die Klasse ist 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 “, bei der es sich um die Zustandsmaschinenklasse handelt, die von Qt automatisch aus der Datei „ sudoku.scxml “ generiert wird. Außerdem enthält sie 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 die übergebene Zustandsmaschine. Außerdem initialisiert er den GUI-Teil und verbindet diesen mit der Zustandsmaschine, indem er deren Kommunikationsschnittstellen miteinander verknüpft.

            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 Signal „ clicked “ mit einem Lambda-Ausdruck, der das Ereignis „ tap “ an die Zustandsmaschine übergibt und dabei die Koordinaten der Schaltfläche übergibt.

Anschließend fügen wir dem Raster einige horizontale und vertikale Linien hinzu, um die Schaltflächen in 3×3-Feldern 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 „clicked“-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 Label, das anzeigt, ob das Raster gelöst ist oder nicht, sowie eine Schaltfläche „ Undo “, die bei jedem Klick das Ereignis „ undo “ auslöst.

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

Anschließend erstellen wir ein Kombinationsfeld, das mit den Namen der zu lösenden Rätsel gefüllt ist. Diese Rätsel werden aus dem Verzeichnis „ :/data “ der in die 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);

Immer wenn die Spieler das Rätsel in der Combobox ändern, lesen wir den Inhalt des Rätsels ein und speichern ihn in der Varianten-Map unter dem Schlüssel „ initValues “ als Liste von Listen mit int-Varianten. Anschließend lösen wir das Ereignis „ setup “ an die Zustandsmaschine aus und übergeben dabei den Inhalt des Rätsels. Zunächst lesen wir das erste verfügbare Raster aus der Liste aus und übergeben es direkt an die Sudoku-Zustandsmaschine als Startraster.

    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 verbinden wir uns mit den Signalen, die gesendet werden, wenn die Maschine in den Zustand „ playing “ eintritt oder diesen verlässt, sowie mit dem Zustand „ solved “, und aktualisieren einige GUI-Elemente entsprechend. Außerdem verbinden wir uns mit dem Ereignis „ updateGUI “ der Zustandsmaschine und aktualisieren die Werte aller Schaltflächen entsprechend den übergebenen Zellzuständen.

#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 “, die Zustandsmaschine „ Sudoku “ und die GUI-Klasse „ MainWindow “. Wir starten die Zustandsmaschine, zeigen das Hauptfenster an und führen die Anwendung aus.

Beispielprojekt @ code.qt.io