window.cpp

#include "window.h"
#include <QApplication>
#include <QDebug>
#include <QPushButton>
#include <QSlider>
#include <QGridLayout>
#include <QHBoxLayout>
#include <QVBoxLayout>
#include <QSpacerItem>
#include <QTimer>

Window::Window(QWidget *parent)
    : QWidget{parent}
{
    solveButton = new QPushButton("solve", this);
    connect(solveButton, SIGNAL(clicked()), this, SLOT(solveButtonClicked()));
    clearButton = new QPushButton("Clear", this);
    connect(clearButton, SIGNAL(clicked()), this, SLOT(clearButtonClicked()));

    slider = new QSlider(this);
    slider->setRange(0, 1000);
    slider->setOrientation(Qt::Horizontal);
    slider->setValue(delayTime);
    connect(slider, SIGNAL(valueChanged(int)), this, SLOT(setValue(int)));

    horizontalLayout = new QHBoxLayout(this);
    verticalLayout = new QVBoxLayout();
    layout = new QGridLayout();

    spacer[0] = new QSpacerItem(4, 4, QSizePolicy::Minimum, QSizePolicy::Fixed);
    spacer[1] = new QSpacerItem(4, 4, QSizePolicy::Minimum, QSizePolicy::Fixed);
    spacer[2] = new QSpacerItem(8, 8, QSizePolicy::Minimum, QSizePolicy::Expanding);
    verticalLayout->addItem(spacer[2]);

    verticalLayout->addWidget(solveButton);
    verticalLayout->addWidget(slider);
    verticalLayout->addWidget(clearButton);
    horizontalLayout->addLayout(layout, 5);
    horizontalLayout->addLayout(verticalLayout, 1);

    layout->addItem(spacer[0], 3, 3);
    layout->addItem(spacer[1], 7, 7);
    layout->setSpacing(0);

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            grid[x + y * 9].setParent(this);
            layout->addWidget(&grid[x + y * 9], y + y / 3, x + x / 3);
            // connecting signals & slots
            for (int d = 0; d < 9; d++) // rows and columns
            {
                connect(&grid[x + y * 9], SIGNAL(update(int)), &grid[x + d * 9], SLOT(removeOption(int)));
                connect(&grid[x + y * 9], SIGNAL(undo(int)), &grid[x + d * 9], SLOT(addOption(int)));
                if (&grid[x + y * 9] != &grid[d + y * 9])
                {
                    connect(&grid[x + y * 9], SIGNAL(update(int)), &grid[d + y * 9], SLOT(removeOption(int)));
                    connect(&grid[x + y * 9], SIGNAL(undo(int)), &grid[d + y * 9], SLOT(addOption(int)));
                }
            }
            int a = x / 3 * 3;
            int b = y / 3 * 3;
            for (int x1 = a; x1 < a + 3; x1++) // square
            {
                for (int y1 = b; y1 < b + 3; y1++)
                {
                    if (x1 == x || y1 == y)
                        continue;
                    connect(&grid[x + y * 9], SIGNAL(update(int)), &grid[x1 + y1 * 9], SLOT(removeOption(int)));

                    connect(&grid[x + y * 9], SIGNAL(undo(int)), &grid[x1 + y1 * 9], SLOT(addOption(int)));
                }
            }
        }
    }
}

void Window::solveButtonClicked()
{
    std::list<History> hist;
    bool backtracking = false;
    srand(time(NULL)); // random seed
    while (1)
    {
        repaint(); // draw cells again
        delay(delayTime);
        if (backtracking)
        {
            hist.back().cell->collapsedCellClicked();
            std::vector<int> validNrs;
            for (int i = 0; i < 9; i++)
                if (!hist.back().blocked[i])
                    validNrs.push_back(i);
            if (validNrs.size() == 0)
            {
                hist.pop_back();
                continue;
            }
            backtracking = false;
            int rndNr = rand() % validNrs.size(); // choose a random number;
            repaint();                            // draw cells again
            delay(delayTime);
            hist.back().cell->collapse(validNrs[rndNr]); // collapse cell with chosen number;
            hist.back().blocked[validNrs[rndNr]]++;
        }
        else
        {
            std::vector<Cell *> b; // vector of cells with least entropy
            int minEtropy = 10;
            for (auto &cell : grid)
            {
                if (cell.collapsed)
                    continue;
                else if (cell.possibleStates < minEtropy)
                {
                    minEtropy = cell.possibleStates;
                    b.clear();
                    b.push_back(&cell);
                }
                else if (cell.possibleStates == minEtropy)
                {
                    b.push_back(&cell);
                }
            }
            if (b.size() == 0) // if b is empty -> solved
                return;

            else if (minEtropy == 0)
            {
                // qInfo("backtracking");
                backtracking = true;
                continue;
            }

            int rndCell = rand() % b.size(); // choose a random cell
            std::vector<int> validNrs;
            for (int i = 0; i < 9; i++)
            {
                if (!b[rndCell]->blocked[i])
                    validNrs.push_back(i);
            }
            int rndNr = rand() % validNrs.size(); // choose a random number;
            hist.push_back(History(b[rndCell], b[rndCell]->blocked, validNrs[rndNr]));
            b[rndCell]->collapse(validNrs[rndNr]); // collapse that random cell with chosen number;
        }
    }
}
inline void Window::delay(int millisecondsWait)
{
    QEventLoop loop;
    QTimer t;
    t.connect(&t, &QTimer::timeout, &loop, &QEventLoop::quit);
    t.start(millisecondsWait);
    loop.exec();
}
void Window::clearButtonClicked()
{
    for (auto &x : grid)
    {
        if (x.collapsed)
            x.collapsedCellClicked();
    }
    return;
}
void Window::setValue(int s)
{
    delayTime = s;
    return;
}