Skip to content

Files

Latest commit

1d922d7 · Apr 8, 2021

History

History
18 lines (14 loc) · 1.45 KB

README.md

File metadata and controls

18 lines (14 loc) · 1.45 KB

Unruly-game-solver

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 :)

Brief overview of the game:

  • 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

Strategy

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.

Notes

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.