Creating the Android board game, Sweet Spots, was a fun programming exercise, although developing an algorithmic program to solve the board game is in fact more fun.

A good portion of developing a board game is about validating the game state based on the game rules, creating game control logics, and visual look-and-feel. Much of the above is just mechanical programming exercise. On the other hand, solving the game is a vastly different exercise, requiring some algorithmic programming effort.

Sweet Spots under the hood

The game solving application was written in Java, with Ant the build tool. There are only two simple Java classes that constitute the hierarchical structure of the board game: Spot and Board. Another Java class, SweetSpots, consists of the core mechanism for game solving. Source code is available at GitHub.

Spot defines the (x,y)-coordinate position of each of the NxN spots (i.e. cells) on the board of size N. It also has an integer value that represents:

• empty (i.e. undecided spot)
• filler (i.e. spot not chosen for treasure chest)
• target (i.e. spot chosen for a treasure chest)

In addition, it consists of an integer zone-id (0, 1, .., N-1) that represents the N individual zones.

Board defines the board size (N). The existing board game was developed with either 1 or 2 targets (i.e. number of treasure chests) per row/column/zone for a given game. For generality, the Board class consists of separate targets-per-row, targets-per-column and targets-per-zone, although they would all be the same (i.e. 1 or 2) when applying to the existing game version. It was initially generalized to allow rectangular board dimension (i.e. MxN instead of NxN), but was later simplified to square board.

Board also consists of a variable, spots, of type Spot[][] that maintains the game state during a game, and a number of methods for game rule validation. Besides the standard constructor that takes board size and target count parameters, it also has a constructor for cloning itself to keep a snapshot of the board state.

Class SweetSpots is the class embedded with game solving logic. It takes a board-zone file along with target counts that defines a game as input and consists of necessary methods to solve the game. The board-zone file is a text file which contains the zone information of a given game in the form of a matrix with coordinates (0,0) representing the top left-most entry. For instance, a 4×4 board-zone file might have the following content:

0 1 1 2
0 0 1 2
2 2 2 2
2 3 3 2

The matrix of integers represent 4 zones, each represented by an integer (0-3):

zone 0: (0,0), (0,1), (1,1)
zone 1: (1,0), (2,0), (2,1)
zone 2: (3,0), (3,1), (0,2), (1,2), (2,2), (3,2), (0,3), (3,3)
zone 3: (1,3), (2,3)

Class SweetSpots consists of a variable boardStack which is a stack of type LinkedList. The stack maintains a dynamic list of Board instance snapshots saved at various stages of the trial-and-error routine. The trial-and-error process is performed using two key methods, boardwalk() and rollback(). Method boardwalk() walks through each of the NxN spots on the board (hence “board walk”) in accordance with the game rules. Upon failing any of the game rule validation, rollback() handles rolling back to the previous game-solving state recorded in boardStack.

Below are pseudo-code logic for methods boardwalk() and rollback().

boardwalk(game, coordX, coordY): return int
    while not every spot on the entire board has been walked
        if current spot is empty
            if every targetCount per row/col/zone < targetCount per row/col/zone
                if no targets adjacent to current spot
                    create a snapshot of the board
                    push the snapshot to boardStack
                    put a target in current spot and fillers in adjacent spots
                else
                    put a filler in current spot
        if any row/col/zone has fewer empty spots to satisfy fulfilling targetCount
            return failure
        else // current cell is not empty
            return success
        go to next spot on the board

rollback(): return Board
    if boardStack is empty
        return null
    else
        pop the last saved board from boardStack
        locate the first empty spot
        if every spot on the board has been walked
            return null
        else
            put a filler in current spot
            return board

Solving a game

Class SolveGame is a simple executable module that uses the SweetSpots class to solve a game with defined zone data.

The main flow logic boils down to the following:

static boolean traceOn;
Board game = new Board(boardSize, targetsPerRow, targetsPerCol, targetsPerZone);
SweetSpots ss = new SweetSpots(traceOn);
...
while (ss.boardwalk(game, 0, 0) != 1) {
    game = ss.rollback();
    if (game == null) {
        break;
    }
}

To solve a game with defined zones, simply navigate to the main subdirectory of the java app and run the following command:

java -cp  com.genuine.game.sweetspots.SolveGame <trace?1:0> <boardZoneFile> <boardSize> <targetsPerRow> <targetsPerCol> <targetsPerZone>

For instance, to solve a game defined in ./gamefiles/game-4-1.txt, simply navigate to the main subdirectory of the java app and run the following command from /path/to/sweetspot/java/:

java -cp build/sweetspots-r1.0.0.jar com.genuine.game.sweetspots.SolveGame 0 ./gamefiles/game-4-1.txt 4 1 1 1

Creating a game

Class CreateGame is an executable module that creates a game by generating random zone data and guaranteeing a solution via repetitive method trials in class SweetSpots.

Creating a game for a given board size (i.e. N) and target count involves:

• generating N random contiguous zones that patition the board, and,
• ensuring there is a solution for the generated zones

Getting slightly more granular, it involves the following steps:

1. Assign individual zones random sizes to fill the entire board: To reduce frequency of having extreme zone size, a simplistic weighted random probability distribution, triangularProbDist(), is used for determining the size for individual zones.
2. For each zone, assign random contiguous spots of the assigned size on the board: Within class CreateGame is a method, zoneWalk(), which essentially “walks” row-wise or column-wise randomly till the assigned zone size is reached. Failure at any point of time to proceed further to cover the entire board with the zones will promptly force a return to step #1.
3. Transpose the board to further randomize the zone-walk result.
4. Repeat the above steps till the zones of assigned sizes successfully fill the entire board.
5. Ensure that there is a solution for the created zones: This is achieved by essentially employing the same game solving logic used in SolveGame.

To create a game that consists of a solution, navigate to the main subdirectory of the java app and execute the following command:

java -cp  com.genuine.game.sweetspots.CreateGame <trace?1:0> <boardZoneFile> <boardSize> <targetsPerRow> <targetsPerCol> <targetsPerZone>

To create a game with 4×4 board size, go to /path/to/sweetspot/java/ and run the following command to generate the game zones in ./gamefiles/:

java -cp build/sweetspots-r1.0.0.jar com.genuine.game.sweetspots.CreateGame 0 ./gamefiles/game-4-1.txt 4 1 1 1

The generated game-zone file should look something like the following:

0 1 1 2
0 0 1 2
2 2 2 2
2 3 3 2

The above Java applications were developed back in Summer of 2013. Though some refactoring effort has been made, there is certainly room for improvement in different areas. In particular, the zone creation piece can be designed to be more robust, ideally enforcing a unique solution for the game. That would be something for a different time perhaps in the near future. Meanwhile, enjoy the board game, which can be downloaded from Google Play.