One of my good friends introduced me to a puzzle-solving app for Android called simply Puzzles. This is my attempt to create a time-efficient solver for one of the games Unruly, without resorting to brute-force. It's also a good chance to play around with some C++17 features like std::optional :)
- You are given a square board with an even number of rows/columns
- The board is partially filled with black and white tiles
- You must fill the board according to the following rules:
- No three tiles of a given color may exist subsequently in a horizontal or vertical line
- Every row and column must have the same number of black and white tiles
Two methods are implemented: directInference() and speculativeInference()
- directInference() uses the idea that every square must be either black, or white. If a move is illegal, the move of the opposite color can be inferred.
- speculativeInference() tries valid moves speculatively, and then plays out the game using direct inference. If a move leads to the game being unwinnable or in an invalid state, the move of the opposite color can be inferred.
Originally, it was planned to extend speculativeInference recursively, but the solver in its current state is already able to solve test games of size 14, the max generated by my puzzle app. Termination is guaranteed, but there may exist some configurations which cannot be resolved to a solution.