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();
            if (hist.back().options.size() == 0)
            {
                hist.pop_back();
                continue;
            }
            backtracking = false;
            int choiceNr = rand() % hist.back().options.size(); // choose a random number;
            repaint();                                         // draw cells again
            delay(delayTime);
            hist.back().cell->collapse(hist.back().options[choiceNr]); // collapse cell with chosen number;
            std::vector<int>::iterator it;
            it = hist.back().options.begin() + choiceNr;
            hist.back().options.erase(it);
        }
        else
        {
            std::vector<Cell *> b; // vector of cells with least entropy
            int minEtropy = 10;
            for (int x = 0; x < 9; x++) // loop through all cells and fill list b --> this could be optimzed
            {
                for (int y = 0; y < 9; y++)
                {
                    if (grid[x + y * 9].collapsed)
                        continue;
                    else if (grid[x + y * 9].possibleStates < minEtropy)
                    {
                        minEtropy = grid[x + y * 9].possibleStates;
                        b.clear();
                        b.push_back(&grid[x + y * 9]);
                    }
                    else if (grid[x + y * 9].possibleStates == minEtropy)
                    {
                        b.push_back(&grid[x + y * 9]);
                    }
                }
            }
            if (b.size() == 0) // if b is empty -> solved
            {
                qInfo("Solved!!");
                return;
            }
            else if (minEtropy == 0)
            {
                qInfo("backtracking");
                backtracking = true;
                continue;
            }

            int choiceCell = rand() % b.size();                  // choose a random cell
            int choiceNr = rand() % b[choiceCell]->options.size(); // choose a random number;
            hist.push_back(History(b[choiceCell], b[choiceCell]->options, choiceNr));
            b[choiceCell]->collapse(b[choiceCell]->options[choiceNr]); // 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;
}