1
\$\begingroup\$

This is a follow up of Skyscraper Solver for NxN Size Version 3

I know its getting old...

So I still have the same Issue the code is to slow to solve bigger skyscraper puzzles.

Since the last Version I made the following improvements:

-Implement Class ClueHint direktly with Fields

  • I removed unecessary std::optional in ClueHint

-Class Row now uses Class Board reference to access each field on the board

  • Fields implementation uses still bitmasks. But as suggested in the answers to the old code i inverted the logic. I also tried out to use std::bitset for Field but that was alot slower so i stayed with a bitmask here.

I still wonder is backtracking the fastest solution? Anything else we can try to speed it up?

Here is the code:

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace codewarsbacktracking {

using BitmaskType = std::uint32_t;

/*
    Example size = 4

    b0000 0 Impossible
    b0001 1 Skyscraper = 1
    b0010 2 Skyscraper = 2
    b0011 3 Nopes = 3, 4
    b0100 4 Skyscraper = 3
    b0101 5 Nopes = 2, 4
    b0110 6 Nopes = 1, 4
    b0111 7 Nopes = 4
    b1000 8 Skyscraper = 1
    b1001 9 Nopes = 2, 3
    b1010 10 Nopes = 1, 3
    b1011 11 Nopes = 3
    b1100 12 Nopes = 1,2
    b1101 13 Nopes = 2
    b1110 14 Nopes = 1
    b1111 15 Nopes = {}
*/

class Field {
public:
    Field() = default;

    void insertSkyscraper(int skyscraper);
    void insertNope(int nope);
    void insertNopes(const std::vector<int> &nopes);
    void insertNopes(const Field &field);

    int skyscraper(std::size_t size) const;
    std::vector<int> nopes(std::size_t size) const;

    bool hasSkyscraper() const;

    bool containsNope(int value) const;
    bool containsNopes(const std::vector<int> &values) const;

private:
    bool bitIsToggled(BitmaskType bitmask, int bit) const;
    // same as c++20 std::has_single_bit()
    bool hasSingleBit(BitmaskType bitmask) const;

    BitmaskType mBitmask{static_cast<BitmaskType>(-1)};

    friend inline bool operator==(const Field &lhs, const Field &rhs);
    friend inline bool operator!=(const Field &lhs, const Field &rhs);
};

inline bool operator==(const Field &lhs, const Field &rhs)
{
    return lhs.mBitmask == rhs.mBitmask;
}
inline bool operator!=(const Field &lhs, const Field &rhs)
{
    return !(lhs == rhs);
}

void Field::insertSkyscraper(int skyscraper)
{
    mBitmask = 1 << (skyscraper - 1);
}

void Field::insertNope(int nope)
{
    mBitmask &= ~(1 << (nope - 1));
}

void Field::insertNopes(const std::vector<int> &nopes)
{
    for (const auto nope : nopes) {
        insertNope(nope);
    }
}

void Field::insertNopes(const Field &field)
{
    mBitmask &= field.mBitmask;
}

int Field::skyscraper(std::size_t size) const
{
    if (!hasSkyscraper()) {
        return 0;
    }

    for (std::size_t i = 0; i < size; ++i) {
        if (bitIsToggled(mBitmask, i)) {
            return i + 1;
        }
    }
    assert(false);
    return 0;
}

std::vector<int> Field::nopes(std::size_t size) const
{
    std::vector<int> nopes;
    nopes.reserve(size - 1);
    for (std::size_t i = 0; i < size; ++i) {
        if (!bitIsToggled(mBitmask, i)) {
            nopes.emplace_back(i + 1);
        }
    }
    return nopes;
}

bool Field::hasSkyscraper() const
{
    return hasSingleBit(mBitmask);
}

bool Field::containsNope(int value) const
{
    return !bitIsToggled(mBitmask, value - 1);
}

bool Field::containsNopes(const std::vector<int> &values) const
{
    for (const auto &value : values) {
        if (!containsNope(value)) {
            return false;
        }
    }
    return true;
}

bool Field::bitIsToggled(BitmaskType bitmask, int bit) const
{
    return bitmask & (1 << bit);
}

bool Field::hasSingleBit(BitmaskType bitmask) const
{
    return bitmask != 0 && (bitmask & (bitmask - 1)) == 0;
}

struct RowClues {
    RowClues(std::size_t boardSize);
    RowClues() = default;

    void reverse();

    bool isEmpty() const;

    std::vector<Field> fields;
};

RowClues::RowClues(std::size_t boardSize)
    : fields{std::vector<Field>(boardSize, Field{})}
{
}

void RowClues::reverse()
{
    std::reverse(fields.begin(), fields.end());
}

bool RowClues::isEmpty() const
{
    return fields.empty();
}

RowClues getRowClue(int clue, std::size_t boardSize)
{
    if (clue == 0) {
        return RowClues{};
    }

    RowClues rowClues{boardSize};

    if (clue == static_cast<int>(boardSize)) {
        for (std::size_t i = 0; i < boardSize; ++i) {
            rowClues.fields[i].insertSkyscraper(i + 1);
        }
    }
    else if (clue == 1) {
        rowClues.fields[0].insertSkyscraper(boardSize);
    }
    else if (clue == 2) {
        rowClues.fields[0].insertNope(boardSize);
        rowClues.fields[1].insertNope(boardSize - 1);
    }
    else {
        for (std::size_t fieldIdx = 0;
             fieldIdx < static_cast<std::size_t>(clue - 1); ++fieldIdx) {

            for (std::size_t nopeValue = boardSize;
                 nopeValue >= (boardSize - (clue - 2) + fieldIdx);
                 --nopeValue) {
                rowClues.fields[fieldIdx].insertNope(nopeValue);
            }
        }
    }
    return rowClues;
}

RowClues merge(RowClues frontRowClues, RowClues backRowClues)
{
    if (frontRowClues.isEmpty() && backRowClues.isEmpty()) {
        return frontRowClues;
    }
    if (frontRowClues.isEmpty()) {
        backRowClues.reverse();
        return backRowClues;
    }
    if (backRowClues.isEmpty()) {
        return backRowClues;
    }

    assert(frontRowClues.fields.size() == backRowClues.fields.size());

    backRowClues.reverse();

    for (std::size_t i = 0; i < frontRowClues.fields.size(); ++i) {

        if (frontRowClues.fields[i].hasSkyscraper()) {
            continue;
        }
        else if (backRowClues.fields[i].hasSkyscraper()) {
            frontRowClues.fields[i] = backRowClues.fields[i];
        }
        else { // only nopes merge nopes
            frontRowClues.fields[i].insertNopes(backRowClues.fields[i]);
        }
    }
    return frontRowClues;
}

void mergeClueHintsPerRow(std::vector<RowClues> &rowClues)
{
    std::size_t startOffset = rowClues.size() / 4 * 3 - 1;
    std::size_t offset = startOffset;

    for (std::size_t frontIdx = 0; frontIdx < rowClues.size() / 2;
         ++frontIdx, offset -= 2) {

        if (frontIdx == rowClues.size() / 4) {
            offset = startOffset;
        }

        int backIdx = frontIdx + offset;

        rowClues[frontIdx] = merge(rowClues[frontIdx], rowClues[backIdx]);
    }
    rowClues.erase(rowClues.begin() + rowClues.size() / 2, rowClues.end());
}

std::vector<RowClues> getRowClues(const std::vector<int> &clues,
                                  std::size_t boardSize)
{
    std::vector<RowClues> rowClues;
    rowClues.reserve(clues.size());

    for (const auto &clue : clues) {
        rowClues.emplace_back(getRowClue(clue, boardSize));
    }
    mergeClueHintsPerRow(rowClues);
    return rowClues;
}

struct Point {
    int x;
    int y;
};

inline bool operator==(const Point &lhs, const Point &rhs)
{
    return lhs.x == rhs.x && lhs.y == rhs.y;
}
inline bool operator!=(const Point &lhs, const Point &rhs)
{
    return !(lhs == rhs);
}

enum class ReadDirection { topToBottom, rightToLeft };

void nextDirection(ReadDirection &readDirection)
{
    assert(readDirection != ReadDirection::rightToLeft);
    int dir = static_cast<int>(readDirection);
    ++dir;
    readDirection = static_cast<ReadDirection>(dir);
}

void advanceToNextPosition(Point &point, ReadDirection readDirection,
                           int clueIdx)
{
    if (clueIdx == 0) {
        return;
    }
    switch (readDirection) {
    case ReadDirection::topToBottom:
        ++point.x;
        break;
    case ReadDirection::rightToLeft:
        ++point.y;
        break;
    }
}

class BorderIterator {
public:
    BorderIterator(std::size_t boardSize);

    Point point() const;
    ReadDirection readDirection() const;

    BorderIterator &operator++();

private:
    int mIdx = 0;
    std::size_t mBoardSize;
    Point mPoint{0, 0};
    ReadDirection mReadDirection{ReadDirection::topToBottom};
};

BorderIterator::BorderIterator(std::size_t boardSize) : mBoardSize{boardSize}
{
}

Point BorderIterator::point() const
{
    return mPoint;
}

ReadDirection BorderIterator::readDirection() const
{
    return mReadDirection;
}

BorderIterator &BorderIterator::operator++()
{
    ++mIdx;
    if (mIdx == static_cast<int>(2 * mBoardSize)) {
        return *this;
    }
    if (mIdx != 0 && mIdx % mBoardSize == 0) {
        nextDirection(mReadDirection);
    }

    advanceToNextPosition(mPoint, mReadDirection, mIdx % mBoardSize);
    return *this;
}

class Board;

class Row {
public:
    Row(Board &board, const Point &startPoint,
        const ReadDirection &readDirection);

    void addCrossingRows(Row *crossingRow);

    bool hasOnlyOneNopeField() const;
    void addLastMissingSkyscraper();

    void addNopesToAllNopeFields(int nope);

    bool allFieldsContainSkyscraper() const;

    int skyscraperCount() const;
    int nopeCount(int nope) const;

    enum class Direction { front, back };

    bool hasSkyscrapers(const std::vector<int> &skyscrapers,
                        Direction direction) const;
    bool hasNopes(const std::vector<std::vector<int>> &nopes,
                  Direction direction) const;

    void addFieldData(const std::vector<Field> &fieldData, Direction direction);

    const Field &getFieldRef(std::size_t idx) const;
    Field &getFieldRef(std::size_t idx);

private:
    template <typename SkyIterator>
    bool hasSkyscrapers(SkyIterator skyItBegin, SkyIterator skyItEnd) const;

    template <typename NopesIterator>
    bool hasNopes(NopesIterator nopesItBegin, NopesIterator nopesItEnd) const;

    template <typename FieldDataIterator>
    void addFieldData(FieldDataIterator fieldDataItBegin,
                      FieldDataIterator fieldDataItEnd);

    void insertFieldData(std::size_t idx, const Field &fieldData);

    void insertSkyscraperNeighbourHandling(std::size_t idx, int skyscraper);

    void insertNopesNeighbourHandling(std::size_t idx, int nopes,
                                      bool hadSkyscraperBefore);

    bool onlyOneFieldWithoutNope(int nope) const;

    bool nopeExistsAsSkyscraperInFields(int nope) const;

    std::optional<int> nopeValueInAllButOneField() const;

    void insertSkyscraperToFirstFieldWithoutNope(int nope);

    bool hasSkyscraper(int skyscraper) const;

    // Field &getFieldRef(std::size_t idx);

    Board &mBoard;
    Point mStartPoint;
    ReadDirection mReadDirection;
    std::vector<Row *> mCrossingRows;
};

class Board {
public:
    Board(std::size_t size);

    void insert(const std::vector<RowClues> &rowClues);

    void insert(const std::vector<std::vector<int>> &startingSkyscrapers);

    bool isSolved() const;

    std::vector<Field> fields;

    std::vector<Row> mRows;

    std::vector<std::vector<int>> skyscrapers2d() const;

    std::size_t size() const;

private:
    void makeRows();
    void connnectRowsWithCrossingRows();

    std::size_t mSize;
};

template <typename It> int missingNumberInSequence(It begin, It end)
{
    int n = std::distance(begin, end) + 1;
    double projectedSum = (n + 1) * (n / 2.0);
    int actualSum = std::accumulate(begin, end, 0);
    return projectedSum - actualSum;
}

Row::Row(Board &board, const Point &startPoint,
         const ReadDirection &readDirection)
    : mBoard{board}, mStartPoint{startPoint}, mReadDirection{readDirection}
{
}

void Row::addCrossingRows(Row *crossingRow)
{
    assert(crossingRow != nullptr);
    assert(mCrossingRows.size() < mBoard.size());
    mCrossingRows.push_back(crossingRow);
}

bool Row::hasOnlyOneNopeField() const
{
    return skyscraperCount() == static_cast<int>(mBoard.size() - 1);
}

void Row::addLastMissingSkyscraper()
{
    assert(hasOnlyOneNopeField());

    std::vector<int> sequence;
    sequence.reserve(mBoard.size() - 1);

    std::size_t nopeFieldIdx = -1;
    for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
        if (getFieldRef(idx).hasSkyscraper()) {
            sequence.emplace_back((getFieldRef(idx)).skyscraper(mBoard.size()));
        }
        else {
            nopeFieldIdx = idx;
        }
    }

    assert(nopeFieldIdx != -1);
    assert(skyscraperCount() == static_cast<int>(sequence.size()));

    auto missingValue =
        missingNumberInSequence(sequence.begin(), sequence.end());

    assert(missingValue >= 0 &&
           missingValue <= static_cast<int>(mBoard.size()));

    (getFieldRef(nopeFieldIdx)).insertSkyscraper(missingValue);
    insertSkyscraperNeighbourHandling(nopeFieldIdx, missingValue);
}

void Row::addNopesToAllNopeFields(int nope)
{
    for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
        if (getFieldRef(idx).hasSkyscraper()) {
            continue;
        }

        bool hasSkyscraperBefore = false;
        getFieldRef(idx).insertNope(nope);
        insertNopesNeighbourHandling(idx, nope, hasSkyscraperBefore);
    }
}

bool Row::allFieldsContainSkyscraper() const
{
    return skyscraperCount() == static_cast<int>(mBoard.size());
}

int Row::skyscraperCount() const
{
    int count = 0;

    for (std::size_t i = 0; i < mBoard.size(); ++i) {
        if (getFieldRef(i).hasSkyscraper()) {
            ++count;
        }
    }
    return count;
}

int Row::nopeCount(int nope) const
{
    int count = 0;
    for (std::size_t i = 0; i < mBoard.size(); ++i) {
        if (getFieldRef(i).hasSkyscraper()) {
            continue;
        }
        if (getFieldRef(i).containsNope(nope)) {
            ++count;
        }
    }
    return count;
}

bool Row::hasSkyscrapers(const std::vector<int> &skyscrapers,
                         Row::Direction direction) const
{
    if (direction == Direction::front) {
        return hasSkyscrapers(skyscrapers.cbegin(), skyscrapers.cend());
    }
    return hasSkyscrapers(skyscrapers.crbegin(), skyscrapers.crend());
}

bool Row::hasNopes(const std::vector<std::vector<int>> &nopes,
                   Direction direction) const
{
    if (direction == Direction::front) {
        return hasNopes(nopes.cbegin(), nopes.cend());
    }
    return hasNopes(nopes.crbegin(), nopes.crend());
}

void Row::addFieldData(const std::vector<Field> &fieldData, Direction direction)
{
    if (direction == Direction::front) {
        addFieldData(fieldData.begin(), fieldData.end());
    }
    else {
        addFieldData(fieldData.rbegin(), fieldData.rend());
    }
}

template <typename SkyIterator>
bool Row::hasSkyscrapers(SkyIterator skyItBegin, SkyIterator skyItEnd) const
{
    for (auto skyIt = skyItBegin; skyIt != skyItEnd; ++skyIt) {
        auto idx = std::distance(skyItBegin, skyIt);
        if (*skyIt == 0 && getFieldRef(idx).hasSkyscraper()) {
            continue;
        }
        if (getFieldRef(idx).skyscraper(mBoard.size()) != *skyIt) {
            return false;
        }
    }
    return true;
}

template <typename NopesIterator>
bool Row::hasNopes(NopesIterator nopesItBegin, NopesIterator nopesItEnd) const
{
    for (auto nopesIt = nopesItBegin; nopesIt != nopesItEnd; ++nopesIt) {
        if (nopesIt->empty()) {
            continue;
        }
        auto idx = std::distance(nopesItBegin, nopesIt);
        if (getFieldRef(idx).hasSkyscraper()) {
            return false;
        }
        if (!getFieldRef(idx).containsNopes(*nopesIt)) {
            return false;
        }
    }
    return true;
}

template <typename FieldDataIterator>
void Row::addFieldData(FieldDataIterator fieldDataItBegin,
                       FieldDataIterator fieldDataItEnd)
{
    for (auto fieldDataIt = fieldDataItBegin; fieldDataIt != fieldDataItEnd;
         ++fieldDataIt) {

        auto idx = std::distance(fieldDataItBegin, fieldDataIt);
        insertFieldData(idx, *fieldDataIt);
    }
}

const Field &Row::getFieldRef(std::size_t idx) const
{
    assert(idx >= 0 && idx < mBoard.size());

    if (mReadDirection == ReadDirection::topToBottom) {
        return mBoard
            .fields[mStartPoint.x + (mStartPoint.y + idx) * mBoard.size()];
    }
    return mBoard.fields[mStartPoint.x - idx + (mStartPoint.y) * mBoard.size()];
}

void Row::insertFieldData(std::size_t idx, const Field &fieldData)
{
    if (fieldData.hasSkyscraper()) {
        if (getFieldRef(idx).hasSkyscraper()) {
            return;
        }
        getFieldRef(idx) = fieldData;
        insertSkyscraperNeighbourHandling(
            idx, getFieldRef(idx).skyscraper(mBoard.size()));
    }
    else {
        bool hasSkyscraperBefore = getFieldRef(idx).hasSkyscraper();
        getFieldRef(idx).insertNopes(fieldData);

        auto nopes = fieldData.nopes(mBoard.size());

        for (const auto &nope : nopes) {
            insertNopesNeighbourHandling(idx, nope, hasSkyscraperBefore);
        }
    }
}

void Row::insertSkyscraperNeighbourHandling(std::size_t idx, int skyscraper)
{
    if (hasOnlyOneNopeField()) {
        addLastMissingSkyscraper();
    }
    addNopesToAllNopeFields(skyscraper);

    if (mCrossingRows[idx]->hasOnlyOneNopeField()) {
        mCrossingRows[idx]->addLastMissingSkyscraper();
    }

    mCrossingRows[idx]->addNopesToAllNopeFields(skyscraper);
}

void Row::insertNopesNeighbourHandling(std::size_t idx, int nope,
                                       bool hadSkyscraperBefore)
{
    // skyscraper was added so we have to add nopes to the neighbours
    if (!hadSkyscraperBefore && getFieldRef(idx).hasSkyscraper()) {

        insertSkyscraperNeighbourHandling(
            idx, getFieldRef(idx).skyscraper(mBoard.size()));
    }

    if (onlyOneFieldWithoutNope(nope)) {
        insertSkyscraperToFirstFieldWithoutNope(nope);
    }

    if (mCrossingRows[idx]->onlyOneFieldWithoutNope(nope)) {
        mCrossingRows[idx]->insertSkyscraperToFirstFieldWithoutNope(nope);
    }
}

bool Row::onlyOneFieldWithoutNope(int nope) const
{
    if (nopeExistsAsSkyscraperInFields(nope)) {
        return false;
    }
    if (nopeCount(nope) <
        static_cast<int>(mBoard.size()) - skyscraperCount() - 1) {
        return false;
    }
    return true;
}

bool Row::nopeExistsAsSkyscraperInFields(int nope) const
{
    for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
        if (getFieldRef(idx).skyscraper(mBoard.size()) == nope) {
            return true;
        }
    }
    return false;
}

std::optional<int> Row::nopeValueInAllButOneField() const
{
    std::unordered_map<int, int> nopeAndCount;

    for (std::size_t i = 0; i < mBoard.size(); ++i) {
        if (!getFieldRef(i).hasSkyscraper()) {
            auto nopes = getFieldRef(i).nopes(mBoard.size());
            for (const auto &nope : nopes) {
                if (hasSkyscraper(nope)) {
                    continue;
                }
                ++nopeAndCount[nope];
            }
        }
    }

    for (auto cit = nopeAndCount.cbegin(); cit != nopeAndCount.end(); ++cit) {
        if (cit->second ==
            static_cast<int>(mBoard.size()) - skyscraperCount() - 1) {
            return {cit->first};
        }
    }
    return {};
}

void Row::insertSkyscraperToFirstFieldWithoutNope(int nope)
{
    for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
        if ((getFieldRef(idx)).hasSkyscraper()) {
            continue;
        }
        if (!(getFieldRef(idx)).containsNope(nope)) {
            (getFieldRef(idx).insertSkyscraper(nope));
            insertSkyscraperNeighbourHandling(idx, nope);
            return; // there can be max one skyscraper per row;
        }
    }
}

bool Row::hasSkyscraper(int skyscraper) const
{
    for (std::size_t i = 0; i < mBoard.size(); ++i) {
        if (getFieldRef(i).skyscraper(mBoard.size()) == skyscraper) {
            return true;
        }
    }
    return false;
}

Field &Row::getFieldRef(std::size_t idx)
{
    assert(idx >= 0 && idx < mBoard.size());

    if (mReadDirection == ReadDirection::topToBottom) {
        return mBoard
            .fields[mStartPoint.x + (mStartPoint.y + idx) * mBoard.size()];
    }
    return mBoard.fields[mStartPoint.x - idx + (mStartPoint.y) * mBoard.size()];
}

Board::Board(std::size_t size)
    : fields{std::vector<Field>(size * size, Field{})}, mSize{size}
{
    makeRows();
}

void Board::insert(const std::vector<RowClues> &rowClues)
{
    assert(rowClues.size() == mRows.size());

    for (std::size_t i = 0; i < rowClues.size(); ++i) {
        if (rowClues[i].isEmpty()) {
            continue;
        }
        mRows[i].addFieldData(rowClues[i].fields, Row::Direction::front);
    }
}

void Board::insert(const std::vector<std::vector<int>> &startingSkyscrapers)
{
    if (startingSkyscrapers.empty()) {
        return;
    }
    std::size_t boardSize = mRows.size() / 2;
    assert(startingSkyscrapers.size() == boardSize);

    for (std::size_t i = 0; i < startingSkyscrapers.size(); ++i) {

        // ugly glue code probaly better to set skyscrapers directly in the
        // fields
        std::vector<Field> fields(startingSkyscrapers[i].size());

        for (std::size_t fieldIdx = 0; fieldIdx < fields.size(); ++fieldIdx) {
            if (startingSkyscrapers[i][fieldIdx] == 0) {
                continue;
            }
            fields[fieldIdx].insertSkyscraper(startingSkyscrapers[i][fieldIdx]);
        }
        mRows[i + boardSize].addFieldData(fields, Row::Direction::back);
    }
}

bool Board::isSolved() const
{
    std::size_t endVerticalRows = mRows.size() / 2;
    for (std::size_t i = 0; i < endVerticalRows; ++i) {
        if (!mRows[i].allFieldsContainSkyscraper()) {
            return false;
        }
    }
    return true;
}

std::vector<std::vector<int>> Board::skyscrapers2d() const
{
    std::vector<std::vector<int>> skyscrapers2d(mSize, std::vector<int>());

    std::size_t j = 0;
    skyscrapers2d[j].reserve(mSize);
    for (std::size_t i = 0; i < fields.size(); ++i) {
        if (i != 0 && i % mSize == 0) {
            ++j;
            skyscrapers2d[j].reserve(mSize);
        }
        skyscrapers2d[j].emplace_back(fields[i].skyscraper(mSize));
    }
    return skyscrapers2d;
}

std::size_t Board::size() const
{
    return mSize;
}

void Board::makeRows()
{
    BorderIterator borderIterator{mSize};

    std::size_t rowSize = mSize * 2;
    mRows.reserve(rowSize);

    for (std::size_t i = 0; i < rowSize; ++i, ++borderIterator) {
        mRows.emplace_back(
            Row{*this, borderIterator.point(), borderIterator.readDirection()});
    }
    connnectRowsWithCrossingRows();
}

void Board::connnectRowsWithCrossingRows()
{
    std::size_t boardSize = mRows.size() / 2;

    std::vector<int> targetRowsIdx(boardSize);
    std::iota(targetRowsIdx.begin(), targetRowsIdx.end(), boardSize);

    for (std::size_t i = 0; i < mRows.size(); ++i) {
        if (i == mRows.size() / 2) {
            std::iota(targetRowsIdx.begin(), targetRowsIdx.end(), 0);
            std::reverse(targetRowsIdx.begin(), targetRowsIdx.end());
        }

        for (const auto &targetRowIdx : targetRowsIdx) {
            mRows[i].addCrossingRows(&mRows[targetRowIdx]);
        }
    }
}

void debug_print(Board &board, const std::string &title)
{
    std::cout << title << '\n';

    for (std::size_t i = 0; i < board.fields.size(); ++i) {

        if (i % board.size() == 0 && i != 0) {
            std::cout << '\n';
        }

        auto elementSize = board.size() * 2;
        std::string element;
        element.reserve(elementSize);
        if (board.fields[i].skyscraper(board.size()) != 0) {
            element =
                "V" + std::to_string(board.fields[i].skyscraper(board.size()));
        }
        else if (board.fields[i].skyscraper(board.size()) == 0 &&
                 !board.fields[i].nopes(board.size()).empty()) {
            auto nopes_set = board.fields[i].nopes(board.size());
            std::vector<int> nopes(nopes_set.begin(), nopes_set.end());
            std::sort(nopes.begin(), nopes.end());

            for (std::size_t i = 0; i < nopes.size(); ++i) {
                element.append(std::to_string(nopes[i]));
                if (i != nopes.size() - 1) {
                    element.push_back(',');
                }
            }
        }
        element.resize(elementSize, ' ');
        std::cout << element;
    }
    std::cout << '\n';
}

bool rowsAreValid(const std::vector<Field> &fields, std::size_t index,
                  std::size_t rowSize)
{
    std::size_t row = index / rowSize;
    for (std::size_t currIndex = row * rowSize; currIndex < (row + 1) * rowSize;
         ++currIndex) {
        if (currIndex == index) {
            continue;
        }
        if (fields[currIndex].skyscraper(rowSize) ==
            fields[index].skyscraper(rowSize)) {
            return false;
        }
    }
    return true;
}

bool columnsAreValid(const std::vector<Field> &fields, std::size_t index,
                     std::size_t rowSize)
{
    std::size_t column = index % rowSize;

    for (std::size_t i = 0; i < rowSize; ++i) {
        std::size_t currIndex = column + i * rowSize;
        if (currIndex == index) {
            continue;
        }
        if (fields[currIndex].skyscraper(rowSize) ==
            fields[index].skyscraper(rowSize)) {
            return false;
        }
    }
    return true;
}

template <typename FieldIterator>
int visibleBuildings(FieldIterator begin, FieldIterator end,
                     std::size_t rowSize)
{
    int visibleBuildingsCount = 0;
    int highestSeen = 0;
    for (auto it = begin; it != end; ++it) {
        if (it->skyscraper(rowSize) != 0 &&
            it->skyscraper(rowSize) > highestSeen) {
            ++visibleBuildingsCount;
            highestSeen = it->skyscraper(rowSize);
        }
    }
    return visibleBuildingsCount;
}

std::tuple<int, int> getCluesInRow(const std::vector<int> &clues,
                                   std::size_t row, std::size_t rowSize)
{
    int frontClue = clues[clues.size() - 1 - row];
    int backClue = clues[rowSize + row];
    return {frontClue, backClue};
}

bool cluesInRowAreValid(const std::vector<Field> &fields,
                        const std::vector<int> &clues, std::size_t index,
                        std::size_t rowSize)
{
    std::size_t row = index / rowSize;

    auto [frontClue, backClue] = getCluesInRow(clues, row, rowSize);

    if (frontClue == 0 && backClue == 0) {
        return true;
    }

    std::size_t rowIndexBegin = row * rowSize;
    std::size_t rowIndexEnd = (row + 1) * rowSize;

    auto citBegin = fields.cbegin() + rowIndexBegin;
    auto citEnd = fields.cbegin() + rowIndexEnd;

    bool rowIsFull = std::find_if(citBegin, citEnd, [](const Field &field) {
                         return !field.hasSkyscraper();
                     }) == citEnd;

    if (!rowIsFull) {
        return true;
    }

    if (frontClue != 0) {
        auto frontVisible = visibleBuildings(citBegin, citEnd, rowSize);

        if (frontClue != frontVisible) {
            return false;
        }
    }

    auto critBegin = std::make_reverse_iterator(citEnd);
    auto critEnd = std::make_reverse_iterator(citBegin);

    if (backClue != 0) {
        auto backVisible = visibleBuildings(critBegin, critEnd, rowSize);

        if (backClue != backVisible) {
            return false;
        }
    }
    return true;
}

std::tuple<int, int> getCluesInColumn(const std::vector<int> &clues,
                                      std::size_t column, std::size_t rowSize)
{
    int frontClue = clues[column];
    int backClue = clues[rowSize * 3 - 1 - column];
    return {frontClue, backClue};
}

bool cluesInColumnAreValid(const std::vector<Field> &fields,
                           const std::vector<int> &clues, std::size_t index,
                           std::size_t rowSize)
{
    std::size_t column = index % rowSize;

    auto [frontClue, backClue] = getCluesInColumn(clues, column, rowSize);

    if (frontClue == 0 && backClue == 0) {
        return true;
    }

    std::vector<Field> verticalFields;
    verticalFields.reserve(rowSize);

    for (std::size_t i = 0; i < rowSize; ++i) {
        verticalFields.emplace_back(fields[column + i * rowSize]);
    }

    bool columnIsFull =
        std::find_if(verticalFields.cbegin(), verticalFields.cend(),
                     [](const Field &field) {
                         return !field.hasSkyscraper();
                     }) == verticalFields.cend();

    if (!columnIsFull) {
        return true;
    }

    if (frontClue != 0) {
        auto frontVisible = visibleBuildings(verticalFields.cbegin(),
                                             verticalFields.cend(), rowSize);
        if (frontClue != frontVisible) {
            return false;
        }
    }
    if (backClue != 0) {
        auto backVisible = visibleBuildings(verticalFields.crbegin(),
                                            verticalFields.crend(), rowSize);

        if (backClue != backVisible) {
            return false;
        }
    }
    return true;
}

bool skyscrapersAreValidPositioned(const std::vector<Field> &fields,
                                   const std::vector<int> &clues,
                                   std::size_t index, std::size_t rowSize)
{
    if (!rowsAreValid(fields, index, rowSize)) {
        return false;
    }
    if (!columnsAreValid(fields, index, rowSize)) {
        return false;
    }
    if (!cluesInRowAreValid(fields, clues, index, rowSize)) {
        return false;
    }
    if (!cluesInColumnAreValid(fields, clues, index, rowSize)) {
        return false;
    }
    return true;
}

bool guessSkyscrapers(Board &board, const std::vector<int> &clues,
                      std::size_t index, std::size_t countOfElements,
                      std::size_t rowSize)
{
    if (index == countOfElements) {
        return true;
    }

    if (board.fields[index].hasSkyscraper()) {
        if (!skyscrapersAreValidPositioned(board.fields, clues, index,
                                           rowSize)) {
            return false;
        }
        if (guessSkyscrapers(board, clues, index + 1, countOfElements,
                             rowSize)) {
            return true;
        }
        return false;
    }

    auto oldField = board.fields[index];
    for (int trySkyscraper = 1; trySkyscraper <= static_cast<int>(rowSize);
         ++trySkyscraper) {

        if (board.fields[index].containsNope(trySkyscraper)) {
            continue;
        }
        board.fields[index].insertSkyscraper(trySkyscraper);
        if (!skyscrapersAreValidPositioned(board.fields, clues, index,
                                           rowSize)) {
            board.fields[index] = oldField;
            continue;
        }
        if (guessSkyscrapers(board, clues, index + 1, countOfElements,
                             rowSize)) {
            return true;
        }
        board.fields[index] = oldField;
    }
    board.fields[index] = oldField;
    return false;
}

void solveBoard(Board &board, const std::vector<int> &clues)
{
    guessSkyscrapers(board, clues, 0, board.fields.size(), board.size());
}

std::vector<std::vector<int>>
SolvePuzzle(const std::vector<int> &clues,
            std::vector<std::vector<int>> startingGrid, int)
{
    assert(clues.size() % 4 == 0);

    std::size_t boardSize = clues.size() / 4;

    auto rowClues = getRowClues(clues, boardSize);

    Board board{boardSize};

    board.insert(rowClues);
    board.insert(startingGrid);

    if (board.isSolved()) {
        return board.skyscrapers2d();
    }

    solveBoard(board, clues);

    return board.skyscrapers2d();
}

std::vector<std::vector<int>> SolvePuzzle(const std::vector<int> &clues)
{
    return SolvePuzzle(clues, std::vector<std::vector<int>>{}, 0);
}

} // namespace codewarsbacktracking

I also like to include some unit tests. Here I list all the unit tests which are currently to slow. With the start clues these boards are not very filled out. Because of that the backtracking needs to insert many many times to come an solution. Is it even possible to get this faster?

#include <gmock/gmock-matchers.h>
#include <gtest/gtest.h>


#include "../Skyscrapers/codewarsbacktracking.h"

#include <vector>

using namespace testing;

struct TestSkyscraperProvider {
    std::vector<int> clues;
    std::vector<std::vector<int>> result;
};

TestSkyscraperProvider sky6_medium{
    {0, 0, 0, 2, 2, 0, 0, 0, 0, 6, 3, 0, 0, 4, 0, 0, 0, 0, 4, 4, 0, 3, 0, 0},
    {{{5, 6, 1, 4, 3, 2},
      {4, 1, 3, 2, 6, 5},
      {2, 3, 6, 1, 5, 4},
      {6, 5, 4, 3, 2, 1},
      {1, 2, 5, 6, 4, 3},
      {3, 4, 2, 5, 1, 6}}}};

TestSkyscraperProvider sky6_hard{
    {0, 3, 0, 5, 3, 4, 0, 0, 0, 0, 0, 1, 0, 3, 0, 3, 2, 3, 3, 2, 0, 3, 1, 0},
    {{{5, 2, 6, 1, 4, 3},
      {6, 4, 3, 2, 5, 1},
      {3, 1, 5, 4, 6, 2},
      {2, 6, 1, 5, 3, 4},
      {4, 3, 2, 6, 1, 5},
      {1, 5, 4, 3, 2, 6}}}};

TestSkyscraperProvider sky6_random_2{
    {4, 1, 0, 0, 3, 0, 0, 2, 1, 0, 6, 0, 2, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0},
    {{{2, 6, 1, 5, 3, 4},
      {3, 4, 6, 2, 1, 5},
      {4, 2, 3, 1, 5, 6},
      {1, 3, 5, 6, 4, 2},
      {6, 5, 4, 3, 2, 1},
      {5, 1, 2, 4, 6, 3}}}};

TestSkyscraperProvider sky7_medium{{7, 0, 0, 0, 2, 2, 3, 0, 0, 3, 0, 0, 0, 0,
                                    3, 0, 3, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 4},
                                   {{{1, 5, 6, 7, 4, 3, 2},
                                     {2, 7, 4, 5, 3, 1, 6},
                                     {3, 4, 5, 6, 7, 2, 1},
                                     {4, 6, 3, 1, 2, 7, 5},
                                     {5, 3, 1, 2, 6, 4, 7},
                                     {6, 2, 7, 3, 1, 5, 4},
                                     {7, 1, 2, 4, 5, 6, 3}}}};

TestSkyscraperProvider sky7_very_hard{{0, 0, 5, 0, 0, 0, 6, 4, 0, 0,
                                       2, 0, 2, 0, 0, 5, 2, 0, 0, 0,
                                       5, 0, 3, 0, 5, 0, 0, 3},
                                      {{{3, 4, 1, 7, 6, 5, 2},
                                        {7, 1, 2, 5, 4, 6, 3},
                                        {6, 3, 5, 2, 1, 7, 4},
                                        {1, 2, 3, 6, 7, 4, 5},
                                        {5, 7, 6, 4, 2, 3, 1},
                                        {4, 5, 7, 1, 3, 2, 6},
                                        {2, 6, 4, 3, 5, 1, 7}}}};

TestSkyscraperProvider sky7_random{{0, 5, 0, 5, 0, 2, 0, 0, 0, 0, 4, 0, 0, 3,
                                    6, 4, 0, 2, 0, 0, 3, 0, 3, 3, 3, 0, 0, 4},
                                   {{{2, 3, 6, 1, 4, 5, 7},
                                     {7, 1, 5, 2, 3, 4, 6},
                                     {6, 4, 2, 3, 1, 7, 5},
                                     {4, 5, 7, 6, 2, 3, 1},
                                     {3, 2, 1, 5, 7, 6, 4},
                                     {1, 6, 4, 7, 5, 2, 3},
                                     {5, 7, 3, 4, 6, 1, 2}}}};

struct TestDataPartialProvider {
    std::vector<int> clues;
    std::vector<std::vector<int>> result;
    std::vector<std::vector<int>> board{};
};

TestDataPartialProvider sky8_hard_partial{{3, 0, 4, 3, 3, 0, 3, 2, 0, 0, 2,
                                           4, 0, 4, 1, 5, 0, 4, 0, 3, 0, 0,
                                           4, 3, 0, 0, 0, 3, 3, 4, 0, 3},
                                          {{1, 6, 2, 4, 3, 8, 5, 7},
                                           {6, 8, 5, 2, 4, 1, 7, 3},
                                           {2, 3, 7, 5, 8, 4, 1, 6},
                                           {3, 1, 6, 8, 7, 5, 2, 4},
                                           {4, 7, 1, 6, 5, 3, 8, 2},
                                           {8, 2, 4, 3, 1, 7, 6, 5},
                                           {7, 5, 3, 1, 2, 6, 4, 8},
                                           {5, 4, 8, 7, 6, 2, 3, 1}},
                                          {{0, 0, 0, 0, 0, 0, 0, 0},
                                           {0, 0, 5, 0, 0, 0, 0, 0},
                                           {0, 0, 0, 0, 0, 0, 0, 0},
                                           {0, 1, 0, 0, 0, 0, 0, 4},
                                           {0, 0, 1, 6, 5, 0, 0, 0},
                                           {0, 0, 0, 0, 0, 0, 0, 0},
                                           {0, 0, 3, 0, 0, 0, 0, 0},
                                           {0, 0, 0, 0, 0, 0, 0, 1}}};


TestDataPartialProvider sky11_medium_partial{
    {3, 2, 2, 3, 1, 4, 4, 3, 5, 2, 6, 5, 2, 3, 3, 2, 2, 1, 4, 3, 3, 5,
     4, 4, 3, 2, 1, 5, 3, 4, 3, 3, 2, 2, 4, 3, 3, 5, 3, 3, 2, 1, 3, 4},
    {{6, 8, 10, 5, 11, 3, 7, 9, 4, 2, 1},
     {9, 5, 6, 10, 7, 2, 1, 4, 8, 11, 3},
     {11, 2, 7, 8, 1, 4, 6, 3, 9, 10, 5},
     {3, 11, 2, 4, 5, 6, 9, 7, 10, 1, 8},
     {8, 10, 3, 7, 9, 11, 4, 1, 2, 5, 6},
     {5, 4, 9, 2, 8, 1, 3, 6, 11, 7, 10},
     {2, 7, 1, 9, 4, 10, 8, 5, 3, 6, 11},
     {4, 1, 5, 11, 3, 9, 10, 2, 6, 8, 7},
     {1, 3, 11, 6, 2, 8, 5, 10, 7, 4, 9},
     {7, 6, 8, 3, 10, 5, 2, 11, 1, 9, 4},
     {10, 9, 4, 1, 6, 7, 11, 8, 5, 3, 2}},
    {{0, 8, 0, 0, 0, 3, 0, 0, 0, 2, 0},
     {0, 0, 0, 0, 7, 2, 0, 0, 0, 0, 3},
     {0, 0, 7, 0, 0, 0, 6, 0, 0, 10, 0},
     {0, 11, 0, 4, 0, 0, 0, 0, 10, 1, 8},
     {8, 0, 0, 7, 0, 0, 0, 1, 2, 0, 6},
     {0, 4, 0, 0, 8, 1, 0, 0, 0, 7, 0},
     {2, 0, 0, 0, 4, 0, 8, 5, 3, 0, 0},
     {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
     {1, 3, 11, 0, 2, 0, 0, 10, 0, 4, 0},
     {0, 0, 0, 3, 10, 5, 0, 11, 0, 0, 0},
     {0, 0, 4, 0, 0, 0, 0, 0, 0, 3, 0}}};

TestDataPartialProvider sky11_medium_partial_2{
    {1, 2, 2, 5, 3, 2, 5, 3, 5, 4, 3, 4, 2, 3, 1, 2, 3, 2, 4, 3, 4, 4,
     3, 4, 3, 2, 3, 5, 3, 1, 2, 3, 3, 3, 3, 2, 3, 5, 2, 5, 3, 4, 2, 1},
    {{11, 9, 10, 5, 8, 6, 2, 4, 1, 3, 7},
     {9, 1, 3, 8, 7, 11, 6, 5, 2, 4, 10},
     {6, 2, 1, 7, 3, 9, 8, 11, 5, 10, 4},
     {7, 6, 4, 2, 10, 8, 1, 3, 9, 5, 11},
     {2, 7, 6, 9, 4, 10, 3, 8, 11, 1, 5},
     {4, 11, 2, 6, 9, 5, 10, 1, 3, 7, 8},
     {1, 4, 7, 10, 2, 3, 5, 6, 8, 11, 9},
     {3, 8, 5, 4, 11, 7, 9, 2, 10, 6, 1},
     {10, 5, 8, 1, 6, 2, 11, 7, 4, 9, 3},
     {5, 10, 11, 3, 1, 4, 7, 9, 6, 8, 2},
     {8, 3, 9, 11, 5, 1, 4, 10, 7, 2, 6}},
    {{0, 0, 10, 0, 8, 0, 2, 0, 1, 0, 0},
     {0, 0, 0, 0, 7, 11, 0, 5, 0, 0, 0},
     {0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 4},
     {0, 0, 0, 0, 0, 0, 1, 3, 9, 0, 0},
     {0, 0, 6, 0, 4, 0, 3, 0, 11, 1, 0},
     {0, 0, 0, 6, 9, 0, 0, 1, 3, 0, 8},
     {0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 9},
     {0, 0, 0, 4, 11, 0, 0, 0, 0, 0, 1},
     {10, 0, 8, 1, 0, 2, 11, 7, 4, 0, 0},
     {5, 10, 0, 0, 0, 0, 0, 0, 0, 8, 0},
     {0, 0, 9, 0, 5, 0, 0, 0, 7, 0, 6}}};

 TEST(CodewarsBacktracking, sky6_medium)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky6_medium.clues),
              sky6_medium.result);
}

 TEST(CodewarsBacktracking, sky6_hard)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky6_hard.clues),
              sky6_hard.result);
}

 TEST(CodewarsBacktracking, sky6_random_2)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky6_random_2.clues),
              sky6_random_2.result);
}

 TEST(CodewarsBacktracking, sky7_medium)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky7_medium.clues),
              sky7_medium.result);
}

 TEST(CodewarsBacktracking, sky7_very_hard)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky7_very_hard.clues),
              sky7_very_hard.result);
}

 TEST(CodewarsBacktracking, sky7_random)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky7_random.clues),
              sky7_random.result);
}


 TEST(CodewarsBacktracking, sky8_hard_partial)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky8_hard_partial.clues,
                                                sky8_hard_partial.board,
                                                sky8_hard_partial.board.size()),
              sky8_hard_partial.result);
}


TEST(CodewarsBacktracking, sky11_medium_partial)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(
                  sky11_medium_partial.clues, sky11_medium_partial.board,
                  sky11_medium_partial.board.size()),
              sky11_medium_partial.result);
}

TEST(CodewarsBacktracking, sky11_medium_partial_2)
{
    EXPECT_EQ(codewarsbacktracking::SolvePuzzle(
                  sky11_medium_partial_2.clues, sky11_medium_partial_2.board,
                  sky11_medium_partial_2.board.size()),
              sky11_medium_partial_2.result);
}


int main(int argc, char *argv[])
{
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

Edit:

Please let me know if there is a faster way to solve the issue than with backtracking. There was already another method mentioned in the comments but no real explanation how it could work.

So the question is do I need another algorithm to solve the puzzle faster or just optimize more on the backtracking implementation?

\$\endgroup\$
6
  • \$\begingroup\$ I didn't read very carefully what the problem is, but it appears to be some kind of a puzzle (like Sudoku or something similar). You could borrow ideas for solving constraint satisfaction (CSP) problems or SAT (= Boolean satisfiability) to find faster methods than (naive) backtracking. For instance, when modeling Sudoku as a CSP, there are very effective heuristics such as minimum remaining values and least-constraining value etc. along with consistency enforcing methods (like AC-3). \$\endgroup\$
    – Juho
    Commented Apr 3, 2021 at 13:56
  • \$\begingroup\$ Sounds all interesting but I would lile some explanation what I can do regarding the skyscraper problem. Currently with backtracking I run through all the possible combinations left from the initial clues I get \$\endgroup\$
    – Sandro4912
    Commented Apr 4, 2021 at 16:32
  • \$\begingroup\$ I read on the sudoku CSP in this article: medium.com/my-udacity-ai-nanodegree-notes/… So if I understand correctly backtracking is the right way but I should select were to start trying out the numbers? At the moment I just insert all the numbers beginning on Point 0,0 and traverse linear all the field. So maybe there has to be a better way? \$\endgroup\$
    – Sandro4912
    Commented Apr 7, 2021 at 14:58
  • \$\begingroup\$ Well, I'm not saying "backtracking is the right way", but I am saying that you can presumably speed up backtracking considerably by considering the order in which you try values. This part is exactly as you observed. These heuristics usually follow the principle of "fail fast", or "in order to succeed, you must fail quickly". It's also easy to imagine what would happen if you had a perfect oracle for telling you in which order to try values: you would solve the instance in an instant. \$\endgroup\$
    – Juho
    Commented Apr 7, 2021 at 15:11
  • \$\begingroup\$ So I could sort the fields by the fields with the less remaining possible options and traverse them first in the backtracking. very interesting idea. I think the algorithm for that should be almost the same as in sudoku. \$\endgroup\$
    – Sandro4912
    Commented Apr 7, 2021 at 18:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.