Solution to the towers puzzle

towers.cpp

/******************************************************************************
 * File:             towers.cpp
 *
 * Author:           Raziman T V
 * Created:          04/09/20
 * Description:      Solving the Towers puzzle
 *****************************************************************************/

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <set>
#include <vector>

typedef std::pair<int, int> viewpair;
typedef std::vector<int> perm;
typedef std::set<int> allowed;

// Given a vector of heights, count how many towers can be seen
// from the two directions
viewpair views(const perm& p) {
  viewpair ret{0, 0}, best{-1, -1};
  const int N = p.size();
  for (int i = 0; i < N; ++i) {
    if (p[i] > best.first) {
      best.first = p[i];
      ret.first++;
    }
    if (p[N - 1 - i] > best.second) {
      best.second = p[N - 1 - i];
      ret.second++;
    }
  }
  return ret;
}

// Read a vector
void readvec(std::vector<int>& v) {
  for (auto& i : v) {
    std::cin >> i;
  }
}

// Remove all bad permutations from a row/column and update the values
// Bad permutation has value val at position pos
void remove(allowed& a, const std::vector<perm>& pvec,
            std::vector<std::vector<int>>& valuecnt, int N, int pos, int val) {
  auto sit = a.begin();
  while (sit != a.end()) {
    if (pvec[*sit][pos] == val) {
      for (int l = 0; l < N; ++l) {
        valuecnt[l][pvec[*sit][l]]--;
      }
      sit = a.erase(sit);
    } else
      ++sit;
  }
}

int main() {
  // Read the size of the vector
  int N;
  std::cin >> N;
  assert(N > 0 and N < 11);

  // Partition the permutations of {1,2,…N} based on towers visible from sides
  perm p(N);  // Identity permutation
  std::iota(p.begin(), p.end(), 0);

  std::vector<perm> pvec;                     // Vector of permutations
  std::map<viewpair, std::vector<int>> pmap;  // Map that partitions by visible
  do {                                        // Loop over permutations
    pmap[views(p)].push_back(pvec.size());
    pvec.push_back(p);
  } while (std::next_permutation(p.begin(), p.end()));

  // Read visibility in order: Up, Down, Left, Right
  std::vector<int> U(N), D(N), L(N), R(N);
  readvec(U);
  readvec(D);
  readvec(L);
  readvec(R);

  // Allowed permutations for each column and row
  std::vector<allowed> colperm(N), rowperm(N);

  // [i][j][v] = Number of allowed permutations for value v in jth cell of ith
  // row or column
  std::vector<std::vector<std::vector<int>>> colval(
      N, std::vector<std::vector<int>>(N, std::vector<int>(N))),
      rowval = colval;

  // Start with only those permutations which satisfy visibility count
  for (int i = 0; i < N; ++i) {
    for (const auto& p : pmap[{U[i], D[i]}]) {
      colperm[i].insert(p);
      for (int j = 0; j < N; ++j) {
        colval[i][j][pvec[p][j]]++;
      }
    }
    for (const auto& p : pmap[{L[i], R[i]}]) {
      rowperm[i].insert(p);
      for (int j = 0; j < N; ++j) {
        rowval[i][j][pvec[p][j]]++;
      }
    }
  }

  // Main part of solver
  // If any cell has a value allowed by some permutation in a row
  //  but not by any permutation of the column or vice versa,
  //  remove the permutation and update all cell is the row
  while (1) {
    bool removed = false;

    // Loop over all the cells
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        // Loop over the values
        for (int v = 0; v < N; ++v) {
          // If v is allowed by a column permutation but not by any row
          if (colval[i][j][v] > 0 and rowval[j][i][v] == 0) {
            removed = true;
            remove(colperm[i], pvec, colval[i], N, j, v);
          } else if (colval[i][j][v] == 0 and rowval[j][i][v] > 0) {
            // If v is allowed by a row permutation but not by any column
            remove(rowperm[j], pvec, rowval[j], N, i, v);
          }
        }
      }
    }

    // If no change happened in this round, we have done as far as we could
    if (!removed) break;
  }

  // If some row/column is empty, there is no solution
  // If it has more than one candidate, the solution is non-unique
  for (int i = 0; i < N; ++i) {
    if (rowperm[i].empty() or colperm[i].empty()) {
      std::cout << "No solution" << std::endl;
      return 0;
    } else if (rowperm[i].size() > 1 or colperm[i].size() > 1) {
      std::cout << "Non-unique solution" << std::endl;
      return 0;
    }
  }

  // Output the unique solution
  for (int i = 0; i < N; ++i) {
    for (auto j : pvec[*rowperm[i].begin()]) {
      std::cout << j + 1 << " ";
    }
    std::cout << "\n";
  }
  return 0;
}