Tag Archives: board game

A Crossword Puzzle In Scala

Data structure for the crossword board

First, it would help make the implementation more readable by coming up with a couple of inter-related classes to represent the crossword board’s layout:

Class Board represents the crossword board which can be constructed with the following parameters:

sz: Size of the square-shaped board with dimension sz x sz
bgCh: Background character representing a single cell of the board which can be identified with its XY-coordinates (default ‘.’)
spCh: Space character representing a single empty cell of a word slot (default ‘*’)
slots: A set of word slots, each of which is represented as an instance of class Slot
arr: The “hidden” character array of dimension sz x sz that stores the content (bgCh, spCh (in empty slots) and words)

Class Slot represents an individual word slot with these parameters:

start: The XY-coordinates of the starting character of the word slot
horiz: A boolean indicator whether a word slot is horizontal (true) or vertical (false)
len: Length of the word slot
jctIdxs: Indexes of all the junction cells that intersect any other word slots
word: A word that fits the slot in length and matches characters that intersect other word slots at its junctions (default “”)

Thus, we have the skeletal classes:

case class Slot(start: (Int, Int), horiz: Boolean, len: Int, jctIdxs: Set[Int], word: String = "")

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)
}

Next, we expand class Board to include a few methods for recursively filling its word slots with matching words along with a couple of side-effecting methods for displaying board content, error reporting, etc.

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)

  // Print content of a provided array
  def printArr(a: Array[Array[Char]] = arr): Unit

  // Report error messages
  def logError(msg: String, sList: List[Slot], wMap: Map[Int, Array[String]], jMap: Map[(Int, Int), Char]): Unit

  // Fill slots with words of matching lengths & junction characters
  def fillSlotsWithWords(words: Array[String]): Board

  // Update board array from slots
  def updateArrayFromSlots(): Board
}

To separate initialization tasks from the core crossword solving logic, we add an companion object to class Board.

object Board {
  // Initialize a board's array from provided background char, slot space char & slots
  def apply(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()): Board

  // Convert an index of a slot into coordinates
  def idxToCoords(start: (Int, Int), horiz: Boolean, idx: Int): (Int, Int)

  // Initialize a board and create slots from board array with ONLY layout
  def initBoardLayout(layout: Array[Array[Char]], bg: Char = '.', sp: Char = '*'): Board
    def findSlot(i: Int, j: Int): Option[Slot]
    def createSlots(i: Int, j: Int, slots: Set[Slot], mkCh: Char): Set[Slot]
}

Creating a crossword puzzle

There are a couple of ways to construct a properly initialized Board object:

From a set of pre-defined word slots, or,
From a sz x sz array of the board layout with pre-populated cells of background and empty world slot

object Board {
  // Initialize a board's array from provided background char, slot space char & slots
  def apply(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()): Board = {
    val board = new Board(sz, bgCh, spCh, slots)
    val slotCoords = slots.toList.flatMap{ slot =>
      val (i, j) = idxToCoords(slot.start, slot.horiz, slot.len - 1)
      List(i, j)
    }
    require(slots.isEmpty || slots.nonEmpty && slotCoords.max < sz, s"ERROR: $slots cannot be contained in ${board.arr}!")
    for (i <- 0 until sz; j <- 0 until sz) {
      board.arr(i)(j) = bgCh
    }
    slots.foreach{ slot =>
      val (i, j) = (slot.start._1, slot.start._2)
      (0 until slot.len).foreach{ k =>
        val (i, j) = idxToCoords(slot.start, slot.horiz, k)
        board.arr(i)(j) = if (slot.word.isEmpty) spCh else slot.word(k)
      }
    }
    board
  }

  ...
}

Method Board.apply() constructs a Board object by populating the private array field with the provided character bgCh to represent the background cells. Once initialized, empty slots represented by the other provided character spCh can be “carved out” in accordance with a set of pre-defined word Slot objects.

Example:

val emptySlots = Set(
  Slot((6, 8), false, 4, Set(2), ""),
  Slot((3, 1), true, 6, Set(2, 5), ""),
  Slot((3, 6), false, 7, Set(0, 5), ""),
  Slot((1, 9), false, 5, Set(0), ""),
  Slot((1, 3), false, 5, Set(0, 2, 4), ""),
  Slot((8, 1), true, 8, Set(5, 7), ""),
  Slot((1, 2), true, 8, Set(1, 7), ""),
  Slot((5, 0), true, 4, Set(3), "")
)

val board = Board(sz = 10, slots = emptySlots)

board.printArr()
/*
. . . . . . . . . . 
. . * * * * * * * * 
. . . * . . . . . * 
. * * * * * * . . * 
. . . * . . * . . * 
* * * * . . * . . * 
. . . . . . * . * . 
. . . . . . * . * . 
. * * * * * * * * . 
. . . . . . * . * . 
*/

Alternatively, one could construct a Board by providing a pre-populated array of the board layout.

object Board {
  ...

  // Initialize a board and create slots from board array with ONLY layout
  def initBoardLayout(layout: Array[Array[Char]], bg: Char = '.', sp: Char = '*'): Board = {
    val sz = layout.length
    def findSlot(i: Int, j: Int): Option[Slot] = {
      if (j < sz-1 && layout(i)(j+1) == sp) {  // Horizontal
        val ln = Iterator.from(j).takeWhile(k => k < sz && layout(i)(k) == sp).size
        val js = (0 until ln).collect{
          case k if (i>=0+1 && layout(i-1)(j+k)!=bg) || (i<sz-1 && layout(i+1)(j+k)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), true, ln, js))
      }
      else {  // Vertical
        val ln = Iterator.from(i).takeWhile(k => k < sz && layout(k)(j) == sp).size
        val js = (0 until ln).collect{
          case k if (j>=0+1 && layout(i+k)(j-1)!=bg) || (j<sz-1 && layout(i+k)(j+1)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), false, ln, js))
      }
    }
    def createSlots(i: Int, j: Int, slots: Set[Slot], mkCh: Char): Set[Slot] = {
      if (i == sz) slots
      else {
        if (j == sz)
          createSlots(i+1, 0, slots, mkCh)
        else {
          findSlot(i, j) match {
            case Some(slot) =>
              val jctCoords = slot.jctIdxs.map{ idx =>
                Board.idxToCoords(slot.start, slot.horiz, idx)
              }
              (0 until slot.len).foreach { k =>
                val (i, j) = Board.idxToCoords(slot.start, slot.horiz, k)
                if (!jctCoords.contains((i, j)))
                  layout(i)(j) = mkCh
              }
              createSlots(i, j+1, slots + slot, mkCh)
            case None =>
              createSlots(i, j+1, slots, mkCh)
          }
        }
      }
    }
    val mkCh = '\u0000'
    val newBoard = Board(sz, bg, sp).copy(slots = createSlots(0, 0, Set(), mkCh))
    (0 until sz).foreach{ i =>
      newBoard.arr(i) = layout(i).map{ ch => if (ch == mkCh) sp else ch }
    }
    newBoard
  }
}

Method Board.initBoardLayout() kicks off createSlots(), which parses every element of the array to identify the “head” of any word slot and figure out its “tail” and indexes of cells that intersect with other slots. The mkCh character is for temporarily masking off any identified slot cell that is not a intersecting junction during the parsing.

Example:

val arr = Array(
  Array('.', '.', '.', '.', '.', '.', '.', '.', '.', '.'),
  Array('.', '.', '*', '*', '*', '*', '*', '*', '*', '*'),
  Array('.', '.', '.', '*', '.', '.', '.', '.', '.', '*'),
  Array('.', '*', '*', '*', '*', '*', '*', '.', '.', '*'),
  Array('.', '.', '.', '*', '.', '.', '*', '.', '.', '*'),
  Array('*', '*', '*', '*', '.', '.', '*', '.', '.', '*'),
  Array('.', '.', '.', '.', '.', '.', '*', '.', '*', '.'),
  Array('.', '.', '.', '.', '.', '.', '*', '.', '*', '.'),
  Array('.', '*', '*', '*', '*', '*', '*', '*', '*', '.'),
  Array('.', '.', '.', '.', '.', '.', '*', '.', '*', '.')
)

val board = Board.initBoardLayout(arr)
/*
Board(10, '.', '*', HashSet(
  Slot((6, 8), false, 4, Set(2), ""),
  Slot((3, 1), true, 6, Set(2, 5), ""),
  Slot((3, 6), false, 7, Set(0, 5), ""),
  Slot((1, 9), false, 5, Set(0), ""),
  Slot((1, 3), false, 5, Set(0, 2, 4), ""),
  Slot((8, 1), true, 8, Set(5, 7), ""),
  Slot((1, 2), true, 8, Set(1, 7), ""),
  Slot((5, 0), true, 4, Set(3), "")
))
*/

board.printArr()
/*
. . . . . . . . . . 
. . * * * * * * * * 
. . . * . . . . . * 
. * * * * * * . . * 
. . . * . . * . . * 
* * * * . . * . . * 
. . . . . . * . * . 
. . . . . . * . * . 
. * * * * * * * * . 
. . . . . . * . * . 
*/

Solving the crossword puzzle

The core crossword solving logic is handled by method fillSlotsWithWords() placed within the body of case class Board.

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)

  ...

  // Fill slots with words of matching lengths & junction characters
  def fillSlotsWithWords(words: Array[String]): Board = {
    val wordMap: Map[Int, Array[String]] = words.groupMap(_.length)(identity)
    val wLenProd: Int = wordMap.map{ case (_, ws) => ws.size }.product
    val trials: Int = wLenProd * wLenProd
    // Prioritize slots with `len` of the smallest by-len group and maximal number of `jctIdxs`
    val orderedSlots = slots.groupMap(_.len)(identity).toList.
      flatMap{ case (_, ss) => ss.map((ss.size, _)) }.
      sortBy{ case (k, slot) => (k, -slot.jctIdxs.size) }.
      map{ case (_, slot) => slot }
    val jctMap: Map[(Int, Int), Char] = slots.
      map(slot => slot.jctIdxs.map(Board.idxToCoords(slot.start, slot.horiz, _))).
      reduce(_ union _).map(_->' ').toMap
    def loop(slotList: List[Slot],
             slotSet: Set[Slot],
             wMap: Map[Int, Array[String]],
             jMap: Map[(Int, Int), Char],
             runs: Int): Set[Slot] = {
      if (runs == 0) {  // Done trying!
        logError(s"FAILURE: Tried $trials times ...", slotList, wMap, jMap)
        slotSet
      }
      else {
        slotList match {
          case Nil =>
            slotSet  // Success!
          case slot :: others =>
            val wordsWithLen = wMap.get(slot.len)
            wordsWithLen match {
              case None =>
                logError(s"FAILURE: Missing words of length ${slot.len}!", slotList, wMap, jMap)
                slotSet
              case Some(words) =>
                words.find{ word =>
                  slot.jctIdxs.forall{ idx =>
                    val jCoords = Board.idxToCoords(slot.start, slot.horiz, idx)
                    jMap(jCoords) == ' ' || word(idx) == jMap(jCoords)
                  }
                }
                match {
                  case Some(w) =>
                    val kvs = slot.jctIdxs.map { idx =>
                      Board.idxToCoords(slot.start, slot.horiz, idx) -> w(idx)
                    }
                    loop(others, slotSet - slot + slot.copy(word = w), wMap, jMap ++ kvs, runs-1)
                  case None =>
                    val newWMap = wMap + (slot.len -> (words.tail :+ words.head))
                    // Restart the loop with altered wordMap
                    loop(orderedSlots, slots, newWMap, jctMap, runs-1)
                }
            }
        }
      }
    }
    val newBoard = copy(slots = loop(orderedSlots, Set(), wordMap, jctMap, wLenProd * wLenProd))
    (0 until sz).foreach{ i => newBoard.arr(i) = arr(i) }
    newBoard.updateArrayFromSlots()
  }

  ...
}

Method fillSlotsWithWords() takes an array of words as the parameter. Those words are supposed to fit the slots of a given initialized Board. The method creates an optimally ordered List of the slots and a Map of words grouped by the length of the words with each key associated with a list of words of the same length. In addition, it also assembles a Map of slot junctions as a helper dataset for matching intersecting characters by XY-coordinates.

The method then uses a recursive loop() to fill slotList and shuffle the wordMap as needed. Let me elaborate a little bit:

Optimally ordered slots – Slots are pre-ordered so that those with the most unique slot-length and the most slot junctions will be processed first. The idea is to fill upfront the most slots with certainty (e.g. those with unique length) and lock down the most slot junction characters as subsequent matching criteria for the intersecting slots.
Order shuffling – During the recursive processing, when a slot of a given length can no longer be filled with the remaining list of slots, the list of words of that length will be shuffled and the loop() will be reset to run with the altered wordMap.

Finally, since it’s possible that the given crossword puzzle slot layout and words might not have a solution, a limit in the number of trials of running the recursive loop() is provided as a safety measure to avoid an infinite loop.

Example:

val words = Array("mandarin", "apple", "nance", "papaya", "avocado", "date", "kiwi", "honeydew")

val filledBoard = board.fillSlotsWithWords(words)
/*
Board(10, '.', '*', HashSet(
  Slot((1, 9), false, 5, Set(0), "nance"),
  Slot((3, 6), false, 7, Set(0, 5), "avocado"),
  Slot((5, 0), true, 4, Set(3), "date"),
  Slot((8, 1), true, 8, Set(5, 7), "honeydew"),
  Slot((6, 8), false, 4, Set(2), "kiwi"),
  Slot((3, 1), true, 6, Set(2, 5), "papaya"),
  Slot((1, 3), false, 5, Set(0, 2, 4), "apple"),
  Slot((1, 2), true, 8, Set(1, 7), "mandarin")
))
*/

filledBoard.printArr()
/*
. . . . . . . . . . 
. . m a n d a r i n 
. . . p . . . . . a 
. p a p a y a . . n 
. . . l . . v . . c 
d a t e . . o . . e 
. . . . . . c . k . 
. . . . . . a . i . 
. h o n e y d e w . 
. . . . . . o . i . 
*/

Final thoughts

Appended is the complete source code of the classes for the crossword puzzle.

Obviously there are many different ways to formulate and solve a puzzle game like this. What’s being illustrated here is a brute-force approach, as the order shuffling routine upon hitting a wall within the slot-filling recursive loop has to reset the recursion process. The good news is that, having tested it with a dozen of random examples (admittedly a small sample), the prioritization strategy (by optimally picking slots to be evaluated) does prove to help a great deal in efficiently solving the sample games.

case class Slot(start: (Int, Int), horiz: Boolean, len: Int, jctIdxs: Set[Int], word: String = "")

object Board {
  // Initialize a board's array from provided background char, slot space char & slots
  def apply(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()): Board = {
    val board = new Board(sz, bgCh, spCh, slots)
    val slotCoords = slots.toList.flatMap{ slot =>
      val (i, j) = idxToCoords(slot.start, slot.horiz, slot.len - 1)
      List(i, j)
    }
    require(slots.isEmpty || slots.nonEmpty && slotCoords.max < sz, s"ERROR: $slots cannot be contained in ${board.arr}!")
    for (i <- 0 until sz; j <- 0 until sz) {
      board.arr(i)(j) = bgCh
    }
    slots.foreach{ slot =>
      val (i, j) = (slot.start._1, slot.start._2)
      (0 until slot.len).foreach{ k =>
        val (i, j) = idxToCoords(slot.start, slot.horiz, k)
        board.arr(i)(j) = if (slot.word.isEmpty) spCh else slot.word(k)
      }
    }
    board
  }

  // Convert an index of a slot into coordinates
  def idxToCoords(start: (Int, Int), horiz: Boolean, idx: Int): (Int, Int) = {
    if (horiz) (start._1, start._2 + idx) else (start._1 + idx, start._2)
  }

  // Initialize a board and create slots from board array with ONLY layout
  def initBoardLayout(layout: Array[Array[Char]], bg: Char = '.', sp: Char = '*'): Board = {
    val sz = layout.length
    def findSlot(i: Int, j: Int): Option[Slot] = {
      if (j < sz-1 && layout(i)(j+1) == sp) {  // Horizontal
        val ln = Iterator.from(j).takeWhile(k => k < sz && layout(i)(k) == sp).size
        val js = (0 until ln).collect{
          case k if (i>=0+1 && layout(i-1)(j+k)!=bg) || (i<sz-1 && layout(i+1)(j+k)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), true, ln, js))
      }
      else {  // Vertical
        val ln = Iterator.from(i).takeWhile(k => k < sz && layout(k)(j) == sp).size
        val js = (0 until ln).collect{
          case k if (j>=0+1 && layout(i+k)(j-1)!=bg) || (j<sz-1 && layout(i+k)(j+1)!=bg) => k
        }.toSet
        Option.when(ln > 1)(Slot((i, j), false, ln, js))
      }
    }
    def createSlots(i: Int, j: Int, slots: Set[Slot], mkCh: Char): Set[Slot] = {
      if (i == sz) slots
      else {
        if (j == sz)
          createSlots(i+1, 0, slots, mkCh)
        else {
          findSlot(i, j) match {
            case Some(slot) =>
              val jctCoords = slot.jctIdxs.map{ idx =>
                Board.idxToCoords(slot.start, slot.horiz, idx)
              }
              (0 until slot.len).foreach { k =>
                val (i, j) = Board.idxToCoords(slot.start, slot.horiz, k)
                if (!jctCoords.contains((i, j)))
                  layout(i)(j) = mkCh
              }
              createSlots(i, j+1, slots + slot, mkCh)
            case None =>
              createSlots(i, j+1, slots, mkCh)
          }
        }
      }
    }
    val mkCh = '\u0000'
    val newBoard = Board(sz, bg, sp).copy(slots = createSlots(0, 0, Set(), mkCh))
    (0 until sz).foreach{ i =>
      newBoard.arr(i) = layout(i).map{ ch => if (ch == mkCh) sp else ch }
    }
    newBoard
  }
}

case class Board private(sz: Int, bgCh: Char = '.', spCh: Char = '*', slots: Set[Slot] = Set()) {
  private val arr: Array[Array[Char]] = Array.ofDim(sz, sz)

  // Print content of a provided array
  def printArr(a: Array[Array[Char]] = arr): Unit =
    for (i <- 0 until sz) {
      for (j <- 0 until sz) {
        print(s"${a(i)(j)} ")
        if (a(i)(j) == '\u0000') print(" ")  // Print a filler space for null char
      }
      println()
    }

  // Report error messages
  def logError(msg: String, sList: List[Slot], wMap: Map[Int, Array[String]], jMap: Map[(Int, Int), Char]): Unit = {
    println(msg)
    println(s"Remaining slots: $sList")
    println(s"Latest wordMap: $wMap")
    println(s"Latest jctMap: $jMap")
  }

  // Fill slots with words of matching lengths & junction characters
  def fillSlotsWithWords(words: Array[String]): Board = {
    val wordMap: Map[Int, Array[String]] = words.groupMap(_.length)(identity)
    val wLenProd: Int = wordMap.map{ case (_, ws) => ws.size }.product
    val trials: Int = wLenProd * wLenProd
    // Prioritize slots with `len` of the smallest by-len group and maximal number of `jctIdxs`
    val orderedSlots = slots.groupMap(_.len)(identity).toList.
      flatMap{ case (_, ss) => ss.map((ss.size, _)) }.
      sortBy{ case (k, slot) => (k, -slot.jctIdxs.size) }.
      map{ case (_, slot) => slot }
    val jctMap: Map[(Int, Int), Char] = slots.
      map(slot => slot.jctIdxs.map(Board.idxToCoords(slot.start, slot.horiz, _))).
      reduce(_ union _).map(_->' ').toMap
    def loop(slotList: List[Slot],
             slotSet: Set[Slot],
             wMap: Map[Int, Array[String]],
             jMap: Map[(Int, Int), Char],
             runs: Int): Set[Slot] = {
      if (runs == 0) {  // Done trying!
        logError(s"FAILURE: Tried $trials times ...", slotList, wMap, jMap)
        slotSet
      }
      else {
        slotList match {
          case Nil =>
            slotSet  // Success!
          case slot :: others =>
            val wordsWithLen = wMap.get(slot.len)
            wordsWithLen match {
              case None =>
                logError(s"FAILURE: Missing words of length ${slot.len}!", slotList, wMap, jMap)
                slotSet
              case Some(words) =>
                words.find{ word =>
                  slot.jctIdxs.forall{ idx =>
                    val jCoords = Board.idxToCoords(slot.start, slot.horiz, idx)
                    jMap(jCoords) == ' ' || word(idx) == jMap(jCoords)
                  }
                }
                match {
                  case Some(w) =>
                    val kvs = slot.jctIdxs.map { idx =>
                      Board.idxToCoords(slot.start, slot.horiz, idx) -> w(idx)
                    }
                    loop(others, slotSet - slot + slot.copy(word = w), wMap, jMap ++ kvs, runs-1)
                  case None =>
                    val newWMap = wMap + (slot.len -> (words.tail :+ words.head))
                    // Restart the loop with altered wordMap
                    loop(orderedSlots, slots, newWMap, jctMap, runs-1)
                }
            }
        }
      }
    }
    val newBoard = copy(slots = loop(orderedSlots, Set(), wordMap, jctMap, wLenProd * wLenProd))
    (0 until sz).foreach{ i => newBoard.arr(i) = arr(i) }
    newBoard.updateArrayFromSlots()
  }

  // Update board array from slots
  def updateArrayFromSlots(): Board = {
    slots.foreach{ slot =>
      (0 until slot.len).foreach{ k =>
        val (i, j) = Board.idxToCoords(slot.start, slot.horiz, k)
        arr(i)(j) = if (slot.word.isEmpty) spCh else slot.word(k)
      }
    }
    this
  }
}

Solving The Sweet Spots Board Game

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)

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

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

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;
    }
}

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>

1	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

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

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.
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.
Transpose the board to further randomize the zone-walk result.
Repeat the above steps till the zones of assigned sizes successfully fill the entire board.
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>

1	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

1	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.

An Android Board Game: Sweet Spots

1 Reply

Back in 2013, one of my planned to-do items was to explore the Android programming language. As always, the best way to learn a programming platform is to write code on it. At the time I was hooked on an interesting board game called Alberi (based on some mathematical puzzle designed by Giorgio Dendi), so I decided to develop a board game using the very game logic as a programming exercise. I was going to post it in a blog but was buried in a different project upon finishing the code.

This was the first Android application I’ve ever developed. It turned out to be a little more complex than initially thought as a first programming exercise on a platform unfamiliar to me. Nevertheless, it was fun to develop a game I enjoyed playing. Android is Java-based so to me the learning curve is not that steep, and the Android SDK comes with a lot of sample code that can be borrowed.

The game is pretty simple. For a given game, the square-shaped board is composed of N rows x N columns of square cells. The entire board is also divided into N contiguous colored zones. The goal is to distribute a number of treasure chests over the board with the following rules:

Each row must have 1 treasure chest
Each column must have 1 treasure chest
Each zone must have 1 treasure chest
Treasure chests cannot be adjacent row-wise, column-wise or diagonally to each other
There is also a variant of 2 treasure chests (per row/column/zone) at larger board size

Here’s a screen-shot of the board game (N = 6):

SweetSpots screenshot

Publishing the game app on Google Play

Back then I didn’t publish the game on Google Play. I’ve decided to do it now just to try out the process. To do that, I need to create a signed Android application package (APK) then zip-align it as per Google’s publish requirement. Eclipse and Android SDK along with Android Debug Bridge (adb) for the Android device simulator were used for developing the app back in 2013. Android OS version at the time was Jelly Bean, although the game still plays fine today on my Lollipop Android phone. The Eclipse version used for the development was Juno and Android SDK version was 17.0.0.

Just two years later today, while the game app still runs fine as an unsigned APK on the current Android platform it no longer builds properly on the latest Eclipse (Mars) and Android SDK (v24.0.2), giving the infamous “R cannot be resolved” error. Lots of suggestions out there on how to solve the problem such as fixing the resource XML, modifying build path, etc, but unfortunately none applies.

As Google is ending support for Android Developer Tool (ADT) in Eclipse literally by end of the month, leaving IntelliJ-based Android Studio the de facto IDE for future Android app development, I thought I would give it a shot. Android Studio appears to be a great IDE product and importing the Eclipse project to it was effortless. It even nicely correlates dependencies and organizes multiple related projects into one. But then a stubborn adb connection problem blocked me from moving forward. I decided to move back to Eclipse. Finally, after experimenting and mixing the Android SDK build tools and platform tools with older versions I managed to successfully build the app. Here’s the published game at Google Play.

From Tic-tac-toe to SweetSpots

The Android’s SDK version I used comes with a bunch of sample applications along with working code. Among the applications is a Tic-tac-toe game which I decided would serve well as the codebase for the board game. I gave the game a name called Sweet Spots.

Following the code structure of the Tic-tac-toe sample application, there are two inter-dependent projects for Sweet Spots: SweetSpotsMain and SweetSpotsLib, each with its own manifest file (AndroidManifest.xml). The file system structure of the source code and resource files is simple:

/path-to-app/SweetSpotsMain/
    AndroidManifest.xml
    res/
        drawable/
            icon.png
        layout/
            main.xml
        layout-land/
            main.xml
        values/
            strings.xml
    src/
        com/
            genuine/
                android/
                    sweetspots/
                        MainActivity.java

/path-to-app/SweetSpotsMain/

AndroidManifest.xml

res/

drawable/

icon.png

layout/

main.xml

layout-land/

main.xml

values/

strings.xml

src/

com/

genuine/

android/

sweetspots/

MainActivity.java

/path-to-app/SweetSpotsLib/
    AndroidManifest.xml
    res/
        drawable/
            (board content images)
        layout/
            lib_game.xml
        layout-land/
            lib_game.xml
        values/
            strings.xml
    src/
        com/
            genuine/
                android/
                    sweetspots/
                        library/
                            GameActivity.java
                            GameView.java

/path-to-app/SweetSpotsLib/

AndroidManifest.xml

res/

drawable/

(board content images)

layout/

lib_game.xml

layout-land/

lib_game.xml

values/

strings.xml

src/

com/

genuine/

android/

sweetspots/

library/

GameActivity.java

GameView.java

MainActivity (extends Activity)

The main Java class in SweetSpotsMain is MainActivity, which defines method onCreate() that consists of buttons for games of various board sizes. In the original code repurposed from the Tic-tac-toe app, each of the game buttons uses its own onClickListener that defines onClick(), which in turn calls startGame() to launch GameActivity using startActivity() by means of an Intent object with the GameActivity class. It has been refactored to have the activity class implement onClickListener and override onCreate() with setOnClickListener(this) and onClick() with specific actions for individual buttons.

View source code of MainActivity.java in a separate browser tab.

GameActivity (extends Activity)

One of the main Java classes in SweetSpotsLib is GameActivity. It defines a few standard activities including onCreate(), onPause() and onResume(). GameActivity also implements a number of onClickListener’s for operational buttons such as Save, Restore and Confirm. The Save and Restore buttons are for temporarily saving the current game state to be restored, say, after trying a few tentative moves. Clicking on the Confirm button will initiate validation of the game rules.

View source code of GameActivity.java in a separate browser tab.

GameView (extends View)

The other main Java class in SweetSpotsLib is GameView, which defines and maintains the view of the board game in accordance with the activities. It defines many of the game-logic methods within standard method calls including onDraw(), onMeasure(), onSizeChanged(), onTouchEvent(), onSaveInstanceState() and onRestoreInstanceState().

GameView also consists of interface ICellListener with the abstract method onCellSelected() that is implemented in GameActivity. The method does nothing in GameActivity but could be added with control logic if wanted.

View source code of GameView.java in a separate browser tab.

Resource files

Images and layout (portrait/landscape) are stored under the res/ subdirectory. Much of the key parametric data (e.g. board size) is also stored there in res/values/strings.xml. Since this was primarily a programming exercise on a mobile platform, visual design/UI wasn’t given much effort. Images used in the board game were assembled using Gimp from public domain sources.

Complete source code for the Android board game is at: https://github.com/oel/sweetspots

How were the games created?

These games were created using a separate Java application that, for each game, automatically generates random zones on the board and validate the game via trial-and-error for a solution. I’ll talk about the application in a separate blog post when I find time. One caveat about the automatic game solution creation is that the solution is generally not unique. A game with unique solution would allow some interesting game-playing logic to be more effective in solving the game. One way to create a unique solution would be to manually re-shape the zones in the generated solution.

Genuine Blog

A Tech Blog by Leo Cheung

Tag Archives: board game

A Crossword Puzzle In Scala

Data structure for the crossword board

Creating a crossword puzzle

Solving the crossword puzzle

Final thoughts

Solving The Sweet Spots Board Game

Sweet Spots under the hood

Solving a game

Creating a game

An Android Board Game: Sweet Spots

Publishing the game app on Google Play

From Tic-tac-toe to SweetSpots

MainActivity (extends Activity)

GameActivity (extends Activity)

GameView (extends View)

Resource files

How were the games created?