Signpost solver

signpost.cpp

/* Signpost solver
 * Author: Raziman T V
 *
 * (Game can be found at
 * http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/signpost.html)
 *
 * Board is to be input as
 * H W
 * v_i dir_i
 * where v_i is the value of ith cell (0 for unknown)
 * and dir_i is the direction in which cell points
 */

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

using namespace std;

// Map NWSE to directions
map<string, pair<int, int>> dir{
    {"X", {0, 0}},   {"E", {0, 1}},    {"NE", {-1, 1}},
    {"N", {-1, 0}},  {"NW", {-1, -1}}, {"W", {0, -1}},
    {"SW", {1, -1}}, {"S", {1, 0}},    {"SE", {1, 1}}};

class board {  // Game board

  struct cell {      // Cell in the board
    int val;         // value of the cell (0 for unknown)
    int next, prev;  // adjacent nodes in hamiltonian path (-1 if unknown)
    int parent;      // Parent for DSU
    set<int> nextposs, prevposs;  // Candidates for adjacent nodes
  };

  struct undo {  // Struct to store variable changes so they can be undone
    vector<int> next, prev, val, used;    // A vector for each changing variable
    vector<pair<int, int>> poss, parent;  // next and prev poss combined to poss
  };

  int H, W;                 // Dimensions of the grid
  vector<cell> cellmatrix;  // Board matrix
  map<int, int> used;       // Positions of already fixed numbers

  pair<int, int> getlowest();   // Find the node with lowest in/out degree
  bool merge(int, int, undo&);  // Add an edge between two nodes
  void undomerge(undo&);        // Remove an added ege, undoing side effects
  int findparent(int, undo&);   // Find the DSU parent with path compression

 public:
  bool solve();  // Solve the board starting from current state

  friend istream& operator>>(istream&, board&);  // Read state and set up data
  friend ostream& operator<<(ostream&, board&);  // Output state
};

// Find the node with lowest in/out degree
// Break ties by minimising out/in degree
// First element returned is position, second is whether we will fill  next/prev
pair<int, int> board::getlowest() {
  int zeros = 0;
  pair<int, int> best{2 * (H + W), 2 * (H + W)}, ret{-1, -1};

  for (int i = 0; i < H * W; ++i) {
    if (cellmatrix[i].next == -1) {  // If we have not chosen the successor node
      // Outdegree-indegree pair
      pair<int, int> cur{cellmatrix[i].nextposs.size(),
                         cellmatrix[i].prevposs.size()};
      if (cur.first == 0) {
        // Only 2 nodes (start and end) can have zero size of next/prev poss
        // If there is more, this is an unsolvable state
        if (++zeros > 2) return {-1, -1};
      } else if (cur < best) {
        best = cur;
        ret = {i, 0};
      }
    }
    if (cellmatrix[i].prev == -1) {  // Repeat for predecessor node choiec
      pair<int, int> cur{cellmatrix[i].prevposs.size(),
                         cellmatrix[i].nextposs.size()};
      if (cellmatrix[i].prevposs.size() == 0) {
        if (++zeros > 2) return {-1, -1};
      } else if (cur < best) {
        best = cur;
        ret = {i, 1};
      }
    }
  }
  return ret;
}

// Merge two nodes
// Remember to log all operations so that they can be undone later
bool board::merge(int u, int v, undo& U) {
  // If the nodes are in the same DSU component we have a cycle, crash out
  int upar = findparent(u, U), vpar = findparent(v, U);
  if (upar == vpar) return false;

  // Otherwise merge the components
  U.parent.push_back({upar, upar});
  cellmatrix[upar].parent = vpar;

  // Mark the nodes as successor and predecessor of each other
  cell &ucell = cellmatrix[u], &vcell = cellmatrix[v];
  ucell.next = v;
  U.next.push_back(u);
  vcell.prev = u;
  U.prev.push_back(v);

  // Now they should be removed as candidates from every other vertex
  for (int i : ucell.nextposs) {
    cellmatrix[i].prevposs.erase(u);
    U.poss.push_back({u, i});
  }
  for (int i : vcell.prevposs) {
    cellmatrix[i].nextposs.erase(v);
    U.poss.push_back({i, v});
  }
  ucell.nextposs = vcell.prevposs = {};

  // Check for value consistency
  if (ucell.val > 0 and vcell.val > 0 and ucell.val + 1 != vcell.val) {
    // If both have values but are inconsistent, die
    return false;
  } else if (ucell.val > 0 and vcell.val == 0) {
    // If one has value but the other does not,
    // propagate to the latter (and if it has a successor and so on)
    int vv = v, vval = ucell.val + 1;
    while (1) {
      // If we end up with an already used or out-of-bounds value, die
      if (vval > H * W or used.count(vval) > 0) return false;
      U.val.push_back(vv);
      U.used.push_back(vval);
      cellmatrix[vv].val = vval;
      used[vval++] = vv;
      if (cellmatrix[vv].next == -1) break;
      // The vertex has a successor, we should continue
      vv = cellmatrix[vv].next;
    }

    // If the propagation resulted in nodes with consecutive values, merge them
    if (used.count(vval)) {
      if (cellmatrix[vv].nextposs.count(used[vval]) == 0) return false;
      return merge(vv, used[vval], U);
    }
  } else if (ucell.val == 0 and vcell.val > 0) {
    // Same as above in the other direction
    int uu = u, uval = vcell.val - 1;
    while (1) {
      if (uval < 1 or used.count(uval) > 0) return false;
      U.val.push_back(uu);
      U.used.push_back(uval);
      cellmatrix[uu].val = uval;
      used[uval--] = uu;
      if (cellmatrix[uu].prev == -1) break;
      uu = cellmatrix[uu].prev;
    }
    if (used.count(uval)) {
      if (cellmatrix[uu].prevposs.count(used[uval]) == 0) return false;
      return merge(used[uval], uu, U);
    }
  }
  return true;
}

// Undo the operations in the structure
// Apply reverse operation for each variable change in order and clear vector
void board::undomerge(undo& U) {
  for (auto i : U.next) cellmatrix[i].next = -1;
  U.next.clear();
  for (auto i : U.prev) cellmatrix[i].prev = -1;
  U.prev.clear();
  for (auto i : U.val) cellmatrix[i].val = 0;
  U.val.clear();
  for (auto i : U.used) used.erase(i);
  U.used.clear();
  for (auto uv : U.poss) {
    cellmatrix[uv.first].nextposs.insert(uv.second);
    cellmatrix[uv.second].prevposs.insert(uv.first);
  }
  U.poss.clear();

  // Undoing DSU operations is tricky, make sure they are done in stack order
  reverse(U.parent.begin(), U.parent.end());
  for (auto uv : U.parent) {
    cellmatrix[uv.first].parent = uv.second;
  }
  U.poss.clear();
}

// DSU parent finding with path compression
// Usual return (parent[u] == u)?u:parent[u]=findparent(u)
// But we need to log each operation so that it can be undone
int board::findparent(int u, undo& U) {
  if (cellmatrix[u].parent == u) return u;
  int v = findparent(cellmatrix[u].parent, U);
  if (v == cellmatrix[u].parent) return v;

  // Neither u nor its parent is root
  // Log current parent to U before changing the allegiance of u
  U.parent.push_back({u, cellmatrix[u].parent});
  return cellmatrix[u].parent = v;
}

int cnt = 0;  // solve() counter

// Solve the board recursively
// Undo allows to recurse without making copies of the board
bool board::solve() {
  cnt++;

  // If all numbers have been placed, we can die in peace now
  if (used.size() == H * W) return true;

  pair<int, int> lowest;
  undo U, U0;

  // If x and x+2 have been already filled, do a quick check for x+1
  for (auto mit = used.begin(), mit2 = next(mit); mit2 != used.end();
       mit = mit2++) {
    if (mit->first + 2 == mit2->first) {
      vector<int> intersection;
      // x+1 can be in locations which are both next to x and prev to x+2
      set_intersection(cellmatrix[mit->second].nextposs.begin(),
                       cellmatrix[mit->second].nextposs.end(),
                       cellmatrix[mit2->second].prevposs.begin(),
                       cellmatrix[mit2->second].prevposs.end(),
                       back_inserter(intersection));
      // If x+1 can't be placed, die
      // If there is a unique position, place it and die if it does not work
      if (intersection.empty() or
          ((intersection.size() == 1) and
           !merge(mit->second, intersection.back(), U0))) {
        goto BPP;
      }
    }
  }

  // Find the lowest degree vertex to be satisfied or die
  lowest = getlowest();
  if (lowest.first == -1) goto BPP;

  if (lowest.second == 0) {  // We need to choose a successor
    int u = lowest.first;
    vector<pair<int, int>> vposs;

    // Try all successors in decreasing order of predecessor count
    // Why does it reduce the number of solve() calls? MAGIC
    for (auto v : cellmatrix[u].nextposs)
      vposs.push_back({-cellmatrix[v].prevposs.size(), v});
    sort(vposs.begin(), vposs.end());
    for (auto v : vposs) {
      if (merge(u, v.second, U) and solve()) {
        // If assigning the successor solves the board, we are done
        return true;
      }
      // Otherwise remember to undo all the changes we made in this step
      undomerge(U);
    }
  } else {  // We need to choose a predecessor
    int v = lowest.first;
    vector<pair<int, int>> uposs;
    for (auto u : cellmatrix[v].prevposs)
      uposs.push_back({-cellmatrix[u].nextposs.size(), u});
    sort(uposs.begin(), uposs.end());
    for (auto u : uposs) {
      if (merge(u.second, v, U) and solve()) {
        return true;
      }
      undomerge(U);
    }
  }
BPP:  // Bad programming practice
  // Nothing worked. Undo the initial set of operations and return
  undomerge(U0);
  return false;
}

// Read the board state and set up all variables
// If something is inconsistent, die immediately
istream& operator>>(istream& in, board& B) {
  in >> B.H >> B.W;
  assert(B.H > 0 and B.W > 0);

  B.cellmatrix = vector<board::cell>(B.H * B.W);
  B.used = {};

  for (int i = 0; i < B.H; ++i) {
    for (int j = 0; j < B.W; ++j) {
      int cur = i * B.W + j;
      B.cellmatrix[cur].parent = cur;  // DSU initialisation

      int& val = B.cellmatrix[cur].val;
      in >> val;
      assert(val >= 0 and val <= B.H * B.W);  // Ensure values are in range
      if (val > 0) {
        assert(B.used.count(val) == 0);  // Values cannot repeat
        B.used[val] = cur;
      }

      B.cellmatrix[cur].prev = B.cellmatrix[cur].next = -1;

      string d;
      in >> d;
      assert(dir.count(d));
      if (d == "X") continue;
      int di = dir[d].first, dj = dir[d].second;

      // Move till we leave the board, to add next/prev candidates
      for (int ii = i + di, jj = j + dj;
           ii >= 0 and ii < B.H and jj >= 0 and jj < B.W; ii += di, jj += dj) {
        int next = ii * B.W + jj;
        B.cellmatrix[cur].nextposs.insert(next);
        B.cellmatrix[next].prevposs.insert(cur);
      }
    }
  }

  // If an endpoint is missing, weird things can happen
  assert(B.used.count(1) and B.used.count(B.H * B.W));

  // 1 cannot be any node's successor, do the cleanup
  int pos1 = B.used[1];
  for (auto i : B.cellmatrix[pos1].prevposs) {
    B.cellmatrix[i].nextposs.erase(pos1);
  }
  B.cellmatrix[pos1].prevposs = {};

  // Process if x and x+1 are in the board initially
  board::undo temp;
  for (auto mit = B.used.begin(), mit2 = next(mit); mit2 != B.used.end();
       mit = mit2++) {
    if (mit->first + 1 == mit2->first) {
      // Add an edge from x to x+1 or die
      assert(B.cellmatrix[mit->second].nextposs.count(mit2->second));
      assert(B.merge(mit->second, mit2->second, temp));
    }
  }
  return in;
}

// Output board state
ostream& operator<<(ostream& out, board& B) {
  for (int i = 0; i < B.H; ++i) {
    for (int j = 0; j < B.W; ++j) {
      out.width(3);
      out << B.cellmatrix[i * B.W + j].val << " ";
    }
    out << "\n";
  }
  out << "\n";
  return out;
}

int main() {
  board B;
  cin >> B;
  if (B.solve()) cout << B;
  cerr << cnt << "\n";
  return 0;
}

Sample board:

15 15
0 SE 76 E 0 W 0 E 80 S 0 SE 113 SE 0 S 0 S 0 W 0 S 55 SW 221 SW 220 W 0 SW
184 S 0 S 0 S 139 E 140 S 0 S 119 S 53 S 96 SW 29 W 215 S 95 W 175 SW 0 S 0 W
0 S 0 S 88 S 68 SW 0 NW 210 S 208 NW 0 S 0 S 207 W 0 NE 46 SE 100 NW 87 W 154 S
0 SE 6 E 0 S 0 S 66 SE 211 E 97 S 225 X 0 S 7 NW 0 NW 224 W 65 W 0 S 0 NW
145 E 0 S 92 E 48 S 0 E 0 S 0 E 0 NE 161 N 203 E 204 S 202 W 0 NW 0 W 0 NW
105 E 165 SE 106 E 49 SE 0 S 218 SE 0 N 0 NE 0 W 78 SE 0 S 134 SW 189 SW 0 W 156 NW
0 E 0 E 83 SE 0 E 0 SE 0 SE 0 E 90 NW 0 NE 64 NE 34 SE 0 E 0 E 0 SW 155 N
0 E 200 NE 191 SE 62 N 0 E 0 W 0 NE 0 SW 0 NE 149 SE 0 W 0 E 0 S 36 SW 0 W
0 SE 70 SE 198 SE 14 E 141 E 0 N 142 NW 15 E 0 NW 0 NW 16 N 170 S 0 W 129 SW 0 SW
0 N 60 SE 82 N 0 S 81 W 0 N 120 E 0 S 39 W 0 N 0 N 38 W 0 N 35 N 0 W
144 N 0 E 0 E 111 N 197 NW 0 SW 33 NE 72 N 0 E 182 SE 0 NE 116 SE 115 W 126 N 79 NW
131 E 0 N 89 NE 61 N 0 E 0 NW 173 NE 132 NE 0 SW 0 NW 0 W 0 SW 58 NE 172 W 4 W
0 E 0 E 74 NW 0 N 108 W 0 NE 177 E 1 S 163 N 0 SW 0 NE 178 N 0 NW 0 NW 0 W
0 E 0 W 0 N 0 N 0 S 124 NE 0 NE 51 N 0 E 0 W 0 NW 0 NE 183 NW 219 N 0 N
0 N 0 E 0 N 0 NE 23 N 10 E 0 W 0 NW 0 W 0 NW 102 E 42 N 188 N 0 N 0 W