# Skyscraper Solver for NxN Size

I try to solve a kata on codewars which let you write a skyscraper solver for skyscrapers up to size 11x11.

Basic Example what is a skyscraper puzzle (here with 4by4 but the principle stays the same):

In a grid of 4 by 4 squares you want to place a skyscraper in each square with only some clues:

-The height of the skyscrapers is between 1 and 4

-No two skyscrapers in a row or column may have the same number of floors

-A clue is the number of skyscrapers that you can see in a row or column from the outside

-Higher skyscrapers block the view of lower skyscrapers located behind them

To understand how the puzzle works, this is an example of a row with 2 clues. Seen from the left side there are 4 buildings visible while seen from the right side only 1:

4 1

There is only one way in which the skyscrapers can be placed. From left-to-right all four buildings must be visible and no building may hide behind another building:

4 1 2 3 4 1

Example of a 4 by 4 puzzle with the solution:

0 0 1 2
0 0
0 2
0 0
1 0
0 0 3 0

Which results in:

0 0 1 2
0 2 1 4 3 0
0 3 4 1 2 2
0 4 2 3 1 0
1 1 3 2 4 0
0 0 3 0

The clues are passed as an vector clockwise like so:

0 1 2 3
15 4
14 5
13 6
12 7
11 10 9 8

Also in a skyscraper puzzle there can be already provided solved skyscrapers at start (Interesting for bigger sizes than 4):

0 0 1 2
0 0
0 4 2
0 3 0
1 0
0 0 3 0

To understand the problem it is good idea to solve some skyscrapers.

My code for this works perfectly fine for all my test cases but there is this restriction that the code is run against unit tests on the codewars server. The restriction there is all unit tests have to pass in less than 12 seconds. And that is not happening at the moment.

I already asked with a stripped down code here but I think maybe it is better to show the whole program.

I wonder if my code can be optimized more or my approach is completely wrong in terms of speed.

Here a short rundown of the classes in use to give an overview what the program does:

• Span: Since Codewars only supports C++17 this is a stripped down basic implementation of std::span we use for looking at Permutations from Rows

• Nopes: Represents which buildings are not present on a Field

• BorderIterator: Is used to iterate over the edges of the Board without having to think about x/y coordinates

• Board: Contains skyscrapers and Nopes separated. To supply skyscrapers only easy for the solution.

• Field: View to one Field of the whole Board. Contains skyscrapers and Nopes.

• Row: View to one Row of the Board. Is connected to crossing Rows.

• CluePair: Contains how many buildigns are visible from the front and back of a Row. Clue = 0 means no clue.

• Slice: View to a Row which keeps track of possible Permutations per Row

• Permutations: Generates all Permutations and gives out indexes to valid Permutations depending on CluePairs.

I basically do the following steps to solve the Skyscraper:

1. Create the Board. Fill it with initial skyscrapers if skyscrapers are known.

2. Create the Rows with the Fields.

3. Generate all Permutations for the size of the board. For Example for a board size = 4 we get 1*2*3*4=24 possible Permutations per row. At the same time we determine which Permutations are valid for each Slice.

4. Create the Slices with the permutations indexes.

5. From here on we try to reduce the possible permutation per row which gives us new Nopes and Skyscrapers until the board is solved.

Now I profiled the code and it looks like most of the runtime is wasted in generating the permutations.

Please let men know how I can improve the performance. I already tried to use an alternate approach for  std::next_permutation like Heaps Algorithm but it was even slower.

Is there a way to use maybe threading to increase the performance.

Or am I on the wrong train even generating all permutations?

So please mainly tell me what can be done to increase the speed of the computation.

If you see other bad practices / design issues feel free to also mention them.

Here is the code (It is all in one file because it is a codewars requirement):

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iterator>
#include <map>
#include <numeric>
#include <set>
#include <type_traits>
#include <unordered_set>

#include <chrono>
#include <iomanip>
#include <iostream>

template <typename T> class Span {
public:
using element_type = T;
using value_type = std::remove_cv_t<T>;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using pointer = T *;
using const_pointer = const T *;
using reference = T &;
using const_reference = const T &;
using const_iterator = const_pointer;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

Span(const_pointer ptr, size_type size);

constexpr const_pointer data() const noexcept;

constexpr size_type size() const noexcept;

constexpr const_reference operator[](size_type idx) const;

constexpr const_iterator cbegin() const noexcept;
constexpr const_iterator cend() const noexcept;

constexpr const_reverse_iterator crbegin() const noexcept;
constexpr const_reverse_iterator crend() const noexcept;

private:
const_pointer mPtr;
size_type mSize;
};

template <typename T>
Span<T>::Span(const_pointer ptr, size_type size) : mPtr{ptr}, mSize{size}
{
}

template <typename T>
constexpr typename Span<T>::const_pointer Span<T>::data() const noexcept
{
return mPtr;
}

template <typename T>
constexpr typename Span<T>::size_type Span<T>::size() const noexcept
{
return mSize;
}

template <typename T>
constexpr typename Span<T>::const_reference
Span<T>::operator[](Span::size_type idx) const
{
assert(idx < mSize);
return *(data() + idx);
}

template <typename T>
constexpr typename Span<T>::const_iterator Span<T>::cbegin() const noexcept
{
return data();
}

template <typename T>
constexpr typename Span<T>::const_iterator Span<T>::cend() const noexcept
{
return data() + size();
}

template <typename T>
constexpr typename Span<T>::const_reverse_iterator
Span<T>::crbegin() const noexcept
{
return reverse_iterator(cend());
}

template <typename T>
constexpr typename Span<T>::const_reverse_iterator
Span<T>::crend() const noexcept
{
return reverse_iterator(cbegin());
}

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

class Nopes {
public:
Nopes(int size);

void insert(int value);
void insert(const std::vector<int> &values);
bool sizeReached() const;
int missingNumberInSequence() const;

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

bool isEmpty() const;
void clear();

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

// for debug print
std::unordered_set<int> values() const;

private:
int mSize;
std::unordered_set<int> mValues;
};

Nopes::Nopes(int size) : mSize{size}
{
assert(size > 0);
}

void Nopes::insert(int value)
{
assert(value >= 1 && value <= mSize + 1);
mValues.insert(value);
}

void Nopes::insert(const std::vector<int> &values)
{
mValues.insert(values.begin(), values.end());
}

bool Nopes::sizeReached() const
{
return mValues.size() == static_cast<std::size_t>(mSize);
}

int Nopes::missingNumberInSequence() const
{
assert(sizeReached());
return ::missingNumberInSequence(mValues.begin(), mValues.end());
}

bool Nopes::contains(int value) const
{
auto it = mValues.find(value);
return it != mValues.end();
}

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

bool Nopes::isEmpty() const
{
return mValues.empty();
}

void Nopes::clear()
{
mValues.clear();
}

std::vector<int> Nopes::containing() const
{
std::vector<int> nopes;
nopes.reserve(mValues.size());
for (const auto &value : mValues) {
nopes.emplace_back(value);
}
return nopes;
}

std::unordered_set<int> Nopes::values() const
{
return mValues;
}

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

{
++dir;
}

int clueIdx)
{
if (clueIdx == 0) {
return;
}
++point.x;
break;
++point.y;
break;
}
}

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

Point point() const;

BorderIterator &operator++();

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

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

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

{
}

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

return *this;
}

struct Board {
Board(int size);

std::vector<std::vector<int>> skyscrapers{};
std::vector<std::vector<Nopes>> nopes;

private:
std::vector<std::vector<int>> makeSkyscrapers(int size);
std::vector<std::vector<Nopes>> makeNopes(int size);
};

Board::Board(int size)
: skyscrapers{makeSkyscrapers(size)}, nopes{makeNopes(size)}
{
}

std::vector<std::vector<int>> Board::makeSkyscrapers(int size)
{
std::vector<int> skyscraperRow(size, 0);
return std::vector<std::vector<int>>(size, skyscraperRow);
}

std::vector<std::vector<Nopes>> Board::makeNopes(int size)
{
std::vector<Nopes> nopesRow(size, Nopes{size - 1});
return std::vector<std::vector<Nopes>>(size, nopesRow);
}

void debug_print(Board &board, const std::string &title = "")
{
std::cout << title << '\n';
for (std::size_t y = 0; y < board.skyscrapers.size(); ++y) {
for (std::size_t x = 0; x < board.skyscrapers[y].size(); ++x) {

if (board.skyscrapers[y][x] != 0) {
std::cout << std::setw(board.skyscrapers.size() * 2);
std::cout << "V" + std::to_string(board.skyscrapers[y][x]);
}
else if (board.skyscrapers[y][x] == 0 &&
!board.nopes[y][x].isEmpty()) {
auto nopes_set = board.nopes[y][x].values();
std::vector<int> nopes(nopes_set.begin(), nopes_set.end());
std::sort(nopes.begin(), nopes.end());

std::string nopesStr;
for (std::size_t i = 0; i < nopes.size(); ++i) {
nopesStr.append(std::to_string(nopes[i]));
if (i != nopes.size() - 1) {
nopesStr.push_back(',');
}
}
std::cout << std::setw(board.skyscrapers.size() * 2);
std::cout << nopesStr;
}
else {
std::cout << ' ';
}
}
std::cout << '\n';
}
std::cout << '\n';
}

class Field {
public:
Field(int &skyscraper, Nopes &nopes);

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

bool fullOfNopes() const;

int skyscraper() const;
Nopes nopes() const;

bool hasSkyscraper() const;

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

private:
int *mSkyscraper;
Nopes *mNopes;
bool mHasSkyscraper = false;
};

Field::Field(int &skyscraper, Nopes &nopes)
: mSkyscraper{&skyscraper}, mNopes{&nopes}
{
}

void Field::insertSkyscraper(int skyscraper)
{
assert(*mSkyscraper == 0 || skyscraper == *mSkyscraper);
if (mHasSkyscraper) {
return;
}
*mSkyscraper = skyscraper;
mHasSkyscraper = true;
// potentially performance problem ???
mNopes->clear();
}
void Field::insertNope(int nope)
{
if (mHasSkyscraper) {
return;
}
mNopes->insert(nope);
}
void Field::insertNopes(const std::vector<int> &nopes)
{
if (mHasSkyscraper) {
return;
}
mNopes->insert(nopes);
}

bool Field::fullOfNopes() const
{
return mNopes->sizeReached();
}

int Field::skyscraper() const
{
return *mSkyscraper;
}
Nopes Field::nopes() const
{
return *mNopes;
}

bool Field::hasSkyscraper() const
{
return mHasSkyscraper;
}

std::optional<int> Field::lastMissingNope() const
{
if (!mNopes->sizeReached()) {
return {};
}
return mNopes->missingNumberInSequence();
}

Point calcPosition(std::size_t idx, const Point &startPoint,
{
Point point = startPoint;
if (idx == 0) {
return startPoint;
}
point.y += idx;
break;
point.x -= idx;
break;
}
return point;
}

std::vector<std::vector<Field>> makeFields(Board &board)
{
std::vector<std::vector<Field>> fields(board.skyscrapers.size());
for (auto &row : fields) {
row.reserve(fields.size());
}
for (std::size_t y = 0; y < board.skyscrapers.size(); ++y) {
for (std::size_t x = 0; x < board.skyscrapers[y].size(); ++x) {
fields[y].emplace_back(
Field{board.skyscrapers[y][x], board.nopes[y][x]});
}
}
return fields;
}

class Row {
public:
Row(std::vector<std::vector<Field>> &fields, const Point &startPoint,

void insertSkyscraper(int pos, int skyscraper);

std::size_t size() const;

bool hasOnlyOneNopeField() const;

bool allFieldsContainSkyscraper() const;

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

void guessSkyscraperOutOfNeighbourNopes();

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;

Direction direction);
Direction direction);

std::vector<Field *> getFields() const;

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

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

template <typename SkyIterator, typename FieldIterator>
FieldIterator fieldItBegin, FieldIterator fieldItEnd);

template <typename NopesIterator, typename FieldIterator>
FieldIterator fieldItBegin, FieldIterator fieldItEnd);

template <typename IteratorType>
void insertSkyscraper(IteratorType it, int skyscraper);

template <typename IteratorType> void insertNope(IteratorType it, int nope);

template <typename IteratorType>
void insertNopes(IteratorType it, const std::vector<int> &nopes);

int getIdx(std::vector<Field *>::const_iterator cit) const;
int getIdx(std::vector<Field *>::const_reverse_iterator crit) const;

std::vector<std::vector<Field>> &fields,
const Point &startPoint);

bool onlyOneFieldWithoutNope(int nope) const;
std::optional<int> nopeValueInAllButOneField() const;

void insertSkyscraperToFirstFieldWithoutNope(int nope);

bool hasSkyscraper(int skyscraper) const;

std::vector<Row *> mCrossingRows;
std::vector<Field *> mRowFields;
};

Row::Row(std::vector<std::vector<Field>> &fields, const Point &startPoint,
{
}

void Row::insertSkyscraper(int pos, int skyscraper)
{
assert(pos >= 0 && pos < static_cast<int>(mRowFields.size()));
assert(skyscraper > 0 && skyscraper <= static_cast<int>(mRowFields.size()));
auto it = mRowFields.begin() + pos;
insertSkyscraper(it, skyscraper);
}

std::size_t Row::size() const
{
return mRowFields.size();
}

{
assert(crossingRow != nullptr);
assert(mCrossingRows.size() < size());
mCrossingRows.push_back(crossingRow);
}

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

{
assert(hasOnlyOneNopeField());

auto nopeFieldIt = mRowFields.end();
std::vector<int> sequence;
sequence.reserve(size() - 1);

for (auto it = mRowFields.begin(); it != mRowFields.end(); ++it) {
if ((*it)->hasSkyscraper()) {
sequence.emplace_back((*it)->skyscraper());
}
else {
nopeFieldIt = it;
}
}
assert(nopeFieldIt != mRowFields.end());
assert(skyscraperCount() == static_cast<int>(sequence.size()));
auto missingValue =
missingNumberInSequence(sequence.begin(), sequence.end());
assert(missingValue >= 0 && missingValue <= static_cast<int>(size()));
insertSkyscraper(nopeFieldIt, missingValue);
}

{
for (auto it = mRowFields.begin(); it != mRowFields.end(); ++it) {
if ((*it)->hasSkyscraper()) {
continue;
}
insertNope(it, nope);
}
}

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

int Row::skyscraperCount() const
{
int count = 0;
for (auto cit = mRowFields.cbegin(); cit != mRowFields.cend(); ++cit) {
if ((*cit)->hasSkyscraper()) {
++count;
}
}
return count;
}

int Row::nopeCount(int nope) const
{
int count = 0;
for (auto cit = mRowFields.cbegin(); cit != mRowFields.cend(); ++cit) {
if ((*cit)->nopes().contains(nope)) {
++count;
}
}
return count;
}

void Row::guessSkyscraperOutOfNeighbourNopes()
{
for (;;) {
auto optNope = nopeValueInAllButOneField();
if (!optNope) {
break;
}
insertSkyscraperToFirstFieldWithoutNope(*optNope);
}
}

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

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

Direction direction)
{
if (direction == Direction::front) {
mRowFields.begin(), mRowFields.end());
}
else {
mRowFields.rbegin(), mRowFields.rend());
}
}
Direction direction)
{
if (direction == Direction::front) {
mRowFields.end());
}
else {
mRowFields.rend());
}
}

std::vector<Field *> Row::getFields() const
{
return mRowFields;
}

template <typename SkyIterator, typename FieldIterator>
bool Row::hasSkyscrapers(SkyIterator skyItBegin, SkyIterator skyItEnd,
FieldIterator fieldItBegin,
FieldIterator fieldItEnd) const
{
auto skyIt = skyItBegin;
for (auto fieldIt = fieldItBegin;
fieldIt != fieldItEnd && skyIt != skyItEnd; ++fieldIt, ++skyIt) {
if (*skyIt == 0 && (*fieldIt)->hasSkyscraper()) {
continue;
}
if ((*fieldIt)->skyscraper() != *skyIt) {
return false;
}
}
return true;
}

template <typename NopesIterator, typename FieldIterator>
bool Row::hasNopes(NopesIterator nopesItBegin, NopesIterator nopesItEnd,
FieldIterator fieldItBegin, FieldIterator fieldItEnd) const
{
auto nopesIt = nopesItBegin;
for (auto fieldIt = fieldItBegin;
fieldIt != fieldItEnd && nopesIt != nopesItEnd; ++fieldIt, ++nopesIt) {

if (nopesIt->empty()) {
continue;
}
if ((*fieldIt)->hasSkyscraper()) {
return false;
}
if (!(*fieldIt)->nopes().contains(*nopesIt)) {
return false;
}
}
return true;
}

template <typename SkyIterator, typename FieldIterator>
FieldIterator fieldItBegin, FieldIterator fieldItEnd)
{
auto skyIt = skyItBegin;
for (auto fieldIt = fieldItBegin;
fieldIt != fieldItEnd && skyIt != skyItEnd; ++fieldIt, ++skyIt) {
if (*skyIt == 0) {
continue;
}
insertSkyscraper(fieldIt, *skyIt);
}
}

template <typename NopesIterator, typename FieldIterator>
FieldIterator fieldItBegin, FieldIterator fieldItEnd)
{
auto nopesIt = nopesItBegin;
for (auto fieldIt = fieldItBegin;
fieldIt != fieldItEnd && nopesIt != nopesItEnd; ++fieldIt, ++nopesIt) {
if (nopesIt->empty()) {
continue;
}
insertNopes(fieldIt, *nopesIt);
}
}

template <typename FieldIterator>
void Row::insertSkyscraper(FieldIterator fieldIt, int skyscraper)
{
assert(mCrossingRows.size() == size());

if ((*fieldIt)->hasSkyscraper()) {
return;
}
(*fieldIt)->insertSkyscraper(skyscraper);

if (hasOnlyOneNopeField()) {
}

int idx = getIdx(fieldIt);

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

}

template <typename FieldIterator>
void Row::insertNope(FieldIterator fieldIt, int nope)
{
if ((*fieldIt)->hasSkyscraper()) {
return;
}
if ((*fieldIt)->nopes().contains(nope)) {
return;
}
(*fieldIt)->insertNope(nope);

auto optlastMissingNope = (*fieldIt)->lastMissingNope();
if (optlastMissingNope) {
insertSkyscraper(fieldIt, *optlastMissingNope);
}

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

int idx = getIdx(fieldIt);

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

template <typename IteratorType>
void Row::insertNopes(IteratorType it, const std::vector<int> &nopes)
{
for (const auto &nope : nopes) {
insertNope(it, nope);
}
}

int Row::getIdx(std::vector<Field *>::const_iterator cit) const
{
return std::distance(mRowFields.cbegin(), cit);
}

int Row::getIdx(std::vector<Field *>::const_reverse_iterator crit) const
{
return size() - std::distance(mRowFields.crbegin(), crit) - 1;
}

std::vector<Field *>
std::vector<std::vector<Field>> &boardFields,
const Point &startPoint)
{
std::vector<Field *> fields;
fields.reserve(boardFields.size());
std::size_t x = startPoint.x;
std::size_t y = startPoint.y;
for (std::size_t i = 0; i < boardFields.size(); ++i) {
fields.emplace_back(&boardFields[y][x]);

++y;
}
else {
--x;
}
}
return fields;
}

bool Row::onlyOneFieldWithoutNope(int nope) const
{
auto cit = std::find_if(
mRowFields.cbegin(), mRowFields.cend(),
[nope](const auto &field) { return field->skyscraper() == nope; });
if (cit != mRowFields.cend()) {
return false;
}
if (nopeCount(nope) < static_cast<int>(size()) - skyscraperCount() - 1) {
return false;
}
return true;
}

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

for (auto cit = mRowFields.cbegin(); cit != mRowFields.cend(); ++cit) {
if (!(*cit)->hasSkyscraper()) {
auto nopes = (*cit)->nopes().containing();
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>(size()) - skyscraperCount() - 1) {
return {cit->first};
}
}
return {};
}

void Row::insertSkyscraperToFirstFieldWithoutNope(int nope)
{
for (auto it = mRowFields.begin(); it != mRowFields.end(); ++it) {
if ((*it)->hasSkyscraper()) {
continue;
}
if (!(*it)->nopes().contains(nope)) {
insertSkyscraper(it, nope);
return; // there can be max one skyscraper per row;
}
}
}

bool Row::hasSkyscraper(int skyscraper) const
{
for (const auto &field : mRowFields) {
if (field->skyscraper() == skyscraper) {
return true;
}
}
return false;
}

class CluePair {
public:
CluePair(int front, int back);

int front() const;
int back() const;

bool frontIsEmpty() const;
bool backIsEmpty() const;
bool isEmpty() const;

bool operator<(const CluePair &other) const
{
return front() < other.front() ||
(front() == other.front() && back() < other.back());
}

private:
int mFront;
int mBack;
bool mFrontIsEmpty;
bool mBackIsEmpty;
bool mIsEmpty;
};

CluePair::CluePair(int front, int back)
: mFront{front}, mBack{back}, mFrontIsEmpty{mFront == 0},
mBackIsEmpty{mBack == 0}, mIsEmpty{mFrontIsEmpty && mBackIsEmpty}
{
}

int CluePair::front() const
{
return mFront;
}

int CluePair::back() const
{
return mBack;
}

bool CluePair::frontIsEmpty() const
{
return mFrontIsEmpty;
}

bool CluePair::backIsEmpty() const
{
return mBackIsEmpty;
}

bool CluePair::isEmpty() const
{
return mIsEmpty;
}

struct FieldElements {
std::vector<int> skyscrapers{};
std::vector<std::vector<int>> nopes{};
};

std::vector<CluePair> makeCluePairs(const std::vector<int> &clues)
{
std::vector<CluePair> cluePairs;
cluePairs.reserve(clues.size() / 2);

std::size_t startOffset = clues.size() / 4 * 3 - 1;
std::size_t offset = startOffset;

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

if (i == clues.size() / 4) {
offset = startOffset;
}

int backClueIdx = i + offset;
cluePairs.emplace_back(CluePair{clues[i], clues[backClueIdx]});
}
return cluePairs;
}

bool isValidPermutation(const Span<int> &permutation,
const std::vector<Field *> fields)
{
auto permIt = permutation.cbegin();
for (auto fieldIt = fields.cbegin();
fieldIt != fields.cend() && permIt != permutation.cend();
++fieldIt, ++permIt) {

if ((*fieldIt)->hasSkyscraper()) {
if ((*fieldIt)->skyscraper() != *permIt) {
return false;
}
}
else if (!(*fieldIt)->nopes().isEmpty()) {
if ((*fieldIt)->nopes().contains(*permIt)) {
return false;
}
}
}
return true;
}

bool fieldsIdentical(const std::vector<Field> &lastFields,
const std::vector<Field *> &currFields)
{
if (lastFields.size() != currFields.size()) {
return false;
}

auto lastIt = lastFields.begin();
auto currPtrIt = currFields.begin();

for (; lastIt != lastFields.end(); ++lastIt, ++currPtrIt) {
if (lastIt->skyscraper() != (*currPtrIt)->skyscraper()) {
return false;
}
if (lastIt->nopes().values() != (*currPtrIt)->nopes().values()) {
return false;
}
}
return true;
}

std::vector<Field> copyField(const std::vector<Field *> &currFields)
{
std::vector<Field> result;
result.reserve(currFields.size());

for (const auto &currField : currFields) {
result.emplace_back(Field{*currField});
}
return result;
}

std::vector<Row> makeRows(std::vector<std::vector<Field>> &fields)
{
BorderIterator borderIterator{fields.size()};

std::size_t size = fields.size() * 2;
std::vector<Row> rows;
rows.reserve(size);

for (std::size_t i = 0; i < size; ++i, ++borderIterator) {
rows.emplace_back(Row{fields, borderIterator.point(),
}
return rows;
}

void connectRowsWithCrossingRows(std::vector<Row> &rows)
{
std::size_t boardSize = rows.size() / 2;

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

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

for (const auto &targetRowIdx : targetRowsIdx) {
}
}
}

void insertExistingSkyscrapersFromStartingGrid(
std::vector<Row> &rows, const std::vector<std::vector<int>> startingGrid)
{
assert(startingGrid.size() == rows.size() / 2);
assert(startingGrid[0].size() == rows.size() / 2);

std::size_t verticalRowsSize = rows.size() / 2;
for (std::size_t x = 0; x < verticalRowsSize; ++x) {
for (std::size_t y = 0; y < verticalRowsSize; ++y) {
if (startingGrid[y][x] == 0) {
continue;
}
rows[x].insertSkyscraper(static_cast<int>(y), startingGrid[y][x]);
}
}
}

int factorial(int n)
{
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}

template <typename BuildingIt>
int buildingsVisible(BuildingIt begin, BuildingIt end)
{
int visibleBuildingsCount = 0;
int highestSeen = 0;

for (auto it = begin; it != end; ++it) {
if (*it > highestSeen) {
++visibleBuildingsCount;
highestSeen = *it;
}
}
return visibleBuildingsCount;
}

bool existingSkyscrapersInPermutation(const std::vector<Field *> &fields,
const std::vector<int> &permutation)
{
assert(fields.size() == permutation.size());

auto fieldIt = fields.cbegin();
auto permutationIt = permutation.cbegin();

for (; fieldIt != fields.cend() && permutationIt != permutation.cend();
++fieldIt, ++permutationIt) {
if (!(*fieldIt)->hasSkyscraper()) {
continue;
}
if ((*fieldIt)->skyscraper() != *permutationIt) {
return false;
}
}
return true;
}

class Permutations {
public:
Permutations(std::size_t size, Span<CluePair> cluePairs, Span<Row> rows);

Span<int> operator[](std::size_t permutationIndex) const;

std::vector<std::size_t> permutationIndexs(std::size_t cluePairIndex) const;

private:
int currIndex);

bool permutationFitsCluePair(const CluePair &cluePair, int front, int back);

Span<CluePair> mCluePairs;
Span<Row> mRows;

std::size_t mSize;
std::size_t mPermutationCount;
std::vector<std::vector<std::size_t>> mCluePairsPermutationIndexes;

std::vector<int> mPermutations;
};

Permutations::Permutations(std::size_t size, Span<CluePair> cluePairs,
Span<Row> rows)
: mCluePairs(cluePairs), mRows{rows}, mSize{size},
mCluePairsPermutationIndexes(cluePairs.size())
{
assert(cluePairs.size() == rows.size());
std::vector<int> sequence(mSize);
std::iota(sequence.begin(), sequence.end(), 1);
mPermutationCount = factorial(sequence.size());

mPermutations.reserve(mPermutationCount * mSize);
int *p = &mPermutations[0];

for (auto &cluePairPermutationIndexes : mCluePairsPermutationIndexes) {
cluePairPermutationIndexes.reserve(mPermutationCount);
}

std::size_t currIndex = 0;
do {
std::copy(sequence.begin(), sequence.end(), p);
p += mSize;
++currIndex;
} while (std::next_permutation(sequence.begin(), sequence.end()));
};

Span<int> Permutations::operator[](std::size_t elem) const
{
auto ptr = &mPermutations[elem * mSize];
return Span{ptr, mSize};
}

std::vector<std::size_t>
Permutations::permutationIndexs(std::size_t cluePairIndex) const
{
return mCluePairsPermutationIndexes[cluePairIndex];
}

int currIndex)
{
auto front = buildingsVisible(sequence.cbegin(), sequence.cend());
auto back = buildingsVisible(sequence.crbegin(), sequence.crend());

for (std::size_t i = 0; i < mCluePairs.size(); ++i) {
if (!permutationFitsCluePair(mCluePairs[i], front, back)) {
continue;
}
auto fields = mRows[i].getFields();

if (!existingSkyscrapersInPermutation(fields, sequence)) {
continue;
}
mCluePairsPermutationIndexes[i].emplace_back(currIndex);
}
}

bool Permutations::permutationFitsCluePair(const CluePair &cluePair, int front,
int back)
{
if (cluePair.isEmpty()) {
return false;
}
if (!cluePair.frontIsEmpty() && cluePair.front() != front) {
return false;
}
if (!cluePair.backIsEmpty() && cluePair.back() != back) {
return false;
}
return true;
}

class Slice {
public:
Slice(Permutations &permutations,
const std::vector<std::size_t> &permutationIndexes, Row &row);

void guessSkyscraperOutOfNeighbourNopes();

bool isSolved() const;

void solveFromPossiblePermutations();

bool reducePossiblePermutations();

private:
std::vector<std::set<int>> getPossibleBuildings() const;

FieldElements
getFieldElements(const std::vector<std::set<int>> &possibleBuildings);

Permutations *mPermutations;
std::vector<std::size_t> mPermutationIndexes;
Row *mRow;
};

Slice::Slice(Permutations &permutations,
const std::vector<std::size_t> &permutationIndexes, Row &row)
: mPermutations{&permutations},
mPermutationIndexes{permutationIndexes}, mRow{&row}
{
if (permutationIndexes.empty()) {
return;
}

auto possibleBuildings = getPossibleBuildings();
auto fieldElements = getFieldElements(possibleBuildings);

}

void Slice::guessSkyscraperOutOfNeighbourNopes()
{
mRow->guessSkyscraperOutOfNeighbourNopes();
}

bool Slice::isSolved() const
{
return mRow->allFieldsContainSkyscraper();
}

void Slice::solveFromPossiblePermutations()
{
if (mPermutationIndexes.empty()) {
return;
}

while (reducePossiblePermutations()) {

auto lastFields = copyField(mRow->getFields());

auto possibleBuildings = getPossibleBuildings();
auto fieldElements = getFieldElements(possibleBuildings);

if (fieldsIdentical(lastFields, mRow->getFields())) {
break;
}
}
}

bool Slice::reducePossiblePermutations()
{
auto startSize = mPermutationIndexes.size();
auto it = mPermutationIndexes.begin();

auto fields = mRow->getFields();

while (it != mPermutationIndexes.end()) {

if (!isValidPermutation(mPermutations->operator[](*it), fields)) {
it = mPermutationIndexes.erase(it);
}
else {
++it;
}
}

return startSize > mPermutationIndexes.size();
}

std::vector<std::set<int>> Slice::getPossibleBuildings() const
{
std::vector<std::set<int>> possibleBuildingsOnFields(mRow->size());

for (const auto &permutationIndex : mPermutationIndexes) {

auto permutation = mPermutations->operator[](permutationIndex);
for (std::size_t i = 0; i < permutation.size(); ++i) {
possibleBuildingsOnFields[i].insert(permutation[i]);
}
}
return possibleBuildingsOnFields;
}

FieldElements
Slice::getFieldElements(const std::vector<std::set<int>> &possibleBuildings)
{
FieldElements fieldElements;
fieldElements.skyscrapers.reserve(possibleBuildings.size());
fieldElements.nopes.reserve(possibleBuildings.size());

for (std::size_t i = 0; i < possibleBuildings.size(); ++i) {
if (possibleBuildings[i].size() == 1) {
fieldElements.skyscrapers.emplace_back(
*possibleBuildings[i].begin());
fieldElements.nopes.emplace_back(std::vector<int>{});
}
else {
std::vector<int> nopes;
nopes.reserve(possibleBuildings.size());
for (std::size_t j = 0; j < possibleBuildings.size(); ++j) {
auto it = possibleBuildings[i].find(j + 1);
if (it == possibleBuildings[i].end()) {
nopes.emplace_back(j + 1);
}
}
fieldElements.skyscrapers.emplace_back(0);
fieldElements.nopes.emplace_back(nopes);
}
}
return fieldElements;
}

std::vector<Slice> makeSlices(Permutations &permutations,
std::vector<Row> &rows,
const std::vector<CluePair> &cluePairs)
{
std::vector<Slice> slices;
slices.reserve(rows.size());

for (std::size_t i = 0; i < cluePairs.size(); ++i) {
slices.emplace_back(
Slice{permutations, permutations.permutationIndexs(i), rows[i]});
}

return slices;
}

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

auto cluePairs = makeCluePairs(clues);

int boardSize = clues.size() / 4;
Board board{boardSize};

auto fields = makeFields(board);

auto rows = makeRows(fields);

connectRowsWithCrossingRows(rows);

if (!startingGrid.empty()) {
insertExistingSkyscrapersFromStartingGrid(rows, startingGrid);
}

//    auto t1 = std::chrono::high_resolution_clock::now();

Permutations permutations(boardSize, Span{&cluePairs[0], cluePairs.size()},
Span{&rows[0], rows.size()});

//    auto t2 = std::chrono::high_resolution_clock::now();
//    std::cout << "generate permutations:"
//              << std::chrono::duration_cast<std::chrono::milliseconds>(t2
//              - t1)
//                     .count()
//              << '\n';

//    auto t3 = std::chrono::high_resolution_clock::now();

std::vector<Slice> slices = makeSlices(permutations, rows, cluePairs);

//    auto t4 = std::chrono::high_resolution_clock::now();
//    std::cout << "make slices:"
//              << std::chrono::duration_cast<std::chrono::milliseconds>(t4
//              - t3)
//                     .count()
//              << '\n';

//    auto t5 = std::chrono::high_resolution_clock::now();

int count = 0;
for (;;) {
++count;

if (count > 1000) {
debug_print(board);
break;
}
bool allFull = true;
for (std::size_t i = 0; i < slices.size(); ++i) {
if (slices[i].isSolved()) {
continue;
}
slices[i].solveFromPossiblePermutations();
slices[i].guessSkyscraperOutOfNeighbourNopes();

if (!slices[i].isSolved()) {
allFull = false;
}
}

if (allFull) {
break;
}
}

//    auto t6 = std::chrono::high_resolution_clock::now();
//    std::cout << "solving loop:"
//              << std::chrono::duration_cast<std::chrono::milliseconds>(t6
//              - t5)
//                     .count()
//              << '\n';

return board.skyscrapers;
}

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


The full project with unit tests (which I cannot post because of the post char limit) can be found on github here.

EDIT:

As mentioned in the comments currently I once generate all permutations of one row. For n=11 this is 11! which is about ~80 million permutations.

I can reduce these permutations while generating them depending on the clues and existing scrapers but I still have to go through all of them at least once (or not?).

Any way to overcome this approach?

• I provided an easy example with an easy small 4by4 Skyscraper. Many more boards can be found in the unit tests for sizes 4by4 up tp 11by11 with pre existing skyscrapers and without. Let me know If you have more questions. Mar 2 '21 at 16:51
• Thank you - that makes a better question now! Mar 2 '21 at 16:52
• I would use a backtracking approach with some implication rules. So concretely, for any partial placement of skyscrapers, check first whether there are rows or columns with 3 skyscrapers, and put the remaining one in that square. I am sure you can think of a few more implications like this. Repeat these rules until nothing can be found. Then go to the next square and make a guess. Then do the rules again, and make sure to label which guess implies their placements. Check validity and repeat. If it is not valid, undo the latest guess and its implications and try the next guess. Mar 3 '21 at 17:56
• If you do not mind using functions you have not written yourself, you could formulate it as a SAT instance and use a SAT solver like minisat. Mar 3 '21 at 17:58
• Off topic: For those who'd like to implement the algorithm in their brain instead of a computer program and test it, this is a Towers puzzle from the Simon Tatham's Portable Puzzle Collection chiark.greenend.org.uk/~sgtatham/puzzles Mar 3 '21 at 21:39

# Don't generate all possible permutations

Generating all possible permutations will be horribly slow. If you treat the $$\N \times N\$$ board as a sequence of $$\N^2\$$ values, where the values are $$\1\dots N\$$ with every value having equal probability, then the number of permutations is $$\\frac{N^2!}{N!^N}\$$. If you generate all permutations for a single row, and repeat that for every row, then you still generate $$\N\cdot N!\$$ permutations. Try to calculate this for a few board sizes and you will quickly see the issue with this. Note that it doesn't matter that you filter out the impossible permutations; this might speed up the rest of the algorithm, but for large boards your runtime will be dominated by the algorithmic complexity of permutation generation.

# Other ways to solve the game

Consider that humans solving these puzzles don't generate all permutations, but solve this puzzle in a very different way. Similar to Sudoku, the main trick is to note down for each grid cell what the possible values are. You start by allowing all $$\N\$$ values, and based on the hints and grid cells for which you have already solved the height of the skyscraper, you remove values from the set that are not possible. You quickly narrow down the possibilities you have to check this way.

So then the question is, how do we actually narrow down the possibilities? There are several heuristics that can be used, including:

## Edge clues

Some clues at the edge will immediately tell us what the height is of towers in their row or column. For example, if an edge clue is 1 in an $$\N \times N\$$ game, then you know that the height of the skyscraper right next to the clue should be $$\N\$$. Similarly, if the edge clue is $$\N\$$ then you know that in that row or column, the skyscapers are in sorted order from 1 to $$\N\$$.

Other edge clues might also provide information, but typically they don't immediately reveal the height of skyscrapers, but rather limit the possibilities of their heights in certain positions.

## Elimination

Once clues restrict the possible heights at a given position so much that only one possibility is left, you can fill in the height at that locations. At the same time, this means that that height value is no longer a valid option for any of the other positions in the same row and column. This eliminates more possibilities, and can reveal even more positions.

## Trial and error

Once the above heuristics no longer eliminate possibilities or reveal heights, most humans will just start tying to guess a height at a certain position, and then try to see what they can then eliminate based on that, and so on, until either they solve the remainder of the puzzle, or hit a dead end. When you hit a dead end, you know that the choices you made up to that point were bad. This should also give you information.

A typical way to do this programmatically is to use a backtracking algorithm

• I wonder how to prevent generate all. Currently I check all generated ones already if they can be valid ones on the board. How can I not generate some at all depending on the clues and present skyscrapers. I guess I really need some starting code. But the number of Permutations I generate is only N! already. Mar 1 '21 at 20:11
• So currently I generate all permutations for a row which is N!. Then I sort them in as possible permutations in the row depending on the clues and present scrapers. So I dont generate all for the whole board. Mar 1 '21 at 20:13
• There are plenty of examples to be found if you search on the Internet for "backtracking algorithm". One of the top search results is geeksforgeeks.org/backtracking-algorithms, have a look at that. You can also search for "backtracking algorithm" here on Code Review; there are plenty of questions where people want their implementations of backtracking algorithms reviewed, so you can learn from those as well. Mar 4 '21 at 7:37
• I think I get it now Fill in skyscrapers and nopes from the clues and also nopes from existing skyscrapers. And only after then no solution is found use backtracking. That should narrow the possibilities already down quite a lot. Mar 4 '21 at 8:29
• I implemented the program with backtracking and wow is it fast. I think I will post that solution for annother code review because one unit test is extremly slow for n=7. All the other ones are blazing fast. Maybe there can be some more optimization in reducing the traverse paths. Mar 12 '21 at 16:52