Solution for the "Unruly" game from Simon Tatham's puzzle collection

unruly.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

bool notblocked(const std::string& str, char c) {
  int L = str.size();
  if (L < 2) return true;
  return (str[L - 1] != c) || (str[L - 2] != c);
}

// Generate all valid rows/columns starting with a prefix
void genposs(std::vector<std::string>& poss, int Nw, int Nb,
             std::string prefix) {
  if (Nw == 0 && Nb == 0) {
    poss.push_back(prefix);
    return;
  }
  if (std::max(Nb, Nw) > 2 * std::min(Nb, Nw) + 2) return;

  // Append a character only if its remaining count is > 0 and the last two
  // characters are not the same as it
  if (Nw > 0 && notblocked(prefix, 'W'))
    genposs(poss, Nw - 1, Nb, prefix + 'W');
  if (Nb > 0 && notblocked(prefix, 'B'))
    genposs(poss, Nw, Nb - 1, prefix + 'B');
}

// Filter candidatelist to have only strings which have the right cell value
// And return the possibiliities for all cell values
auto filter_compute_cellpossibilities(std::vector<int>& candidatelist,
                                      const std::vector<std::string>& poss,
                                      int cell, char value) {
  for (int i = 0; i < candidatelist.size(); ++i) {
    // If a candidate string has the wrong cell value, discard it
    int candidate = candidatelist[i];
    if (poss[candidate][cell] != value) {
      candidatelist[i--] = candidatelist.back();
      candidatelist.pop_back();
      continue;
    }
  }

  // Otherwise update ret[] using the candidate values
  std::vector<std::pair<bool, bool>> ret(poss[0].size(), {false, false});
  for (int j = 0; j < ret.size(); ++j) {
    for (int candidate : candidatelist) {
      if (poss[candidate][j] == 'W') {
        ret[j].first = true;
        if(ret[j].second) break;
      } else {
        ret[j].second = true;
        if(ret[j].first) break;
      }
    }
  }
  return ret;
}

// From the possibilities for (row, col), check whether cell can be fixed
// And whether this results in a contradiction. Add cell to BFS queue if needed
bool process_cell(int row, int col, const std::pair<bool, bool>& cellposs,
                  char& cellval, std::queue<std::pair<int, int>>& bfsqueue) {
  if (cellposs.first == false) {
    // If W cannot be admitted, it should be B
    if (cellval == 'W') {
      // But if the cell is already fixed to be W, we have a problem
      return false;
    } else if (cellval != 'B') {
      // And if the cell is not fixed, fix it and add to process list
      cellval = 'B';
      bfsqueue.push({row, col});
    }
  } else if (cellposs.second == false) {
    // Do similarly if B cannot be admitted
    if (cellval == 'B') {
      return false;
    } else if (cellval != 'W') {
      cellval = 'W';
      bfsqueue.push({row, col});
    }
  }
  return true;
}

int main() {
  std::vector<std::string> board;

  // Read the board
  std::string str;
  while (std::cin >> str) {
    board.push_back(str);
  }
  int N = board.size();

  // Basic sanity checking
  // We do not check for inconsistencies at this stage
  if (N & 1) {
    std::cerr << "Invalid board\n";
    return 1;
  }
  for (const auto& row : board) {
    if (row.size() != N) {
      std::cerr << "Invalid board\n";
      return 1;
    }
  }

  // Generate the possibilities
  std::vector<std::string> poss;
  genposs(poss, N / 2, N / 2, "");

  // Initially, allow each row and column to admit all possibilities
  std::vector<int> temp(poss.size());
  std::iota(temp.begin(), temp.end(), 0);
  std::vector<std::vector<int>> rowallowed(N, temp), colallowed(N, temp);

  // Store the cells which are fixed and to be processed
  std::queue<std::pair<int, int>> bfsqueue;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (board[i][j] == 'W' || board[i][j] == 'B') bfsqueue.push({i, j});
    }
  }

  // Process the fixed cells
  while (!bfsqueue.empty()) {
    int row = bfsqueue.front().first, col = bfsqueue.front().second;
    bfsqueue.pop();

    // Check the row first
    // rowcellposs[i] = {can ith cell in row be W, similarly B}
    auto rowcellposs = filter_compute_cellpossibilities(rowallowed[row], poss,
                                                        col, board[row][col]);

    // If some cell does not admit B or W, we have a contradiction
    // and rowallowed[] will be empty
    if (rowallowed[row].empty()) {
      std::cerr << "Inconsistency detected\n";
      return 2;
    }

    // Now check whether some cell value has been fixed as a result
    for (int i = 0; i < N; ++i) {
      if (!process_cell(row, i, rowcellposs[i], board[row][i], bfsqueue)) {
        std::cerr << "Inconsistency detected\n";
        return 2;
      }
    }

    // Do the same thing for columns now
    auto colcellposs = filter_compute_cellpossibilities(colallowed[col], poss,
                                                        row, board[row][col]);
    if (colallowed[col].empty()) {
      std::cerr << "Inconsistency detected\n";
      return 2;
    }
    for (int i = 0; i < N; ++i) {
      if (!process_cell(i, col, colcellposs[i], board[i][col], bfsqueue)) {
        std::cerr << "Inconsistency detected\n";
        return 2;
      }
    }
  }

  // If the board has a unique solution, it will hopefully have been solved now
  // So print the board
  std::copy(board.begin(), board.end(),
            std::ostream_iterator<std::string>(std::cout, "\n"));
  return 0;
}

xboard.in

............W.
W....W...W....
...BB.B.B.....
..BB...W.....W
.W........W...
.....B..W...B.
........W.B...
....W.B...BW..
W.....B......W
..........W..W
....B.W.......
.B..B.....B.B.
.BB...WW......
W......BB..W.W

xboard.out

BWWBWBBWWBWBWB
WBBWBWWBWWBWBB
BBWBBWBWBWWBWW
WWBBWBBWWBBWBW
BWBWBWWBBWWBWB
WBWBWBBWWBWBBW
BWBWBWWBWBBWWB
BWWBWBBWBWBWWB
WBWWBWBBWBWBBW
WBBWWBWWBBWBBW
BWWBBWWBBWBWWB
BBWWBWBBWWBWBW
WBBWWBWWBBWBWB
WWBBWBWBBWBWBW