As a programming exercise, creating and solving a crossword puzzle is a fun one, requiring some non-trivial but reasonable effort in crafting out the necessary programming logic.
The high-level requirements are simple — Given a square-shaped crossword board with intersecting word slots, and a set of words that are supposed to fit in the slots, solve the crossword and display the resulting word-populated board.
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 szthat 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 szarray 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 alteredwordMap.
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
}
}
