Sudoku: Making The Game

2020, May 31
Link to project here.

A Sudoku puzzle is typically played on a 9x9 grid, where each cell can be filled with digits 1 to 9. It starts off with some parts of the grid pre-filled with values, and the objective is to fill the remaining cells according to the following constraints:

  1. Each row contains contains all 9 digits.
  2. Each column contains contains all 9 digits.
  3. Each 3x3 block contains contains all 9 digits.
A typical Sudoku puzzle Solution

Images lifted from the Sudoku wikipedia page.

This is the most common form of Sudoku. Some variants include Killer Sudoku, Alphabetical Sudoku, Samurai Sudoku and many more that have modified rule sets.

My Approach

I want to make a simple web app that can visually display a game of Sudoku and then use a selection of algorithms to solve a given puzzle. In addition to the typical 9x9 grid with digits 1-9, I will also endeavour to make the app work with different sized square grids such as 4x4 and 16x16, as well as custom symbols such as alphabets.

Because I want this app to be as simple as possible, I've decided to make it a static webpage that is hosted via GitHub Pages. You can follow the link here to check it out as it progresses. The most straightforward way to make it work then, is for the app to be written directly in Javascript. For the interactive side of things, I've decided to go with the p5js library, because it's great.

I'm starting this project as I learn about the principles of functional programming. So in order to practice, I've set a few rules for myself:

  1. Use pure functions where reasonable.
  2. Avoid "for" and "while" loops, instead use "map", "filter", "reduce" types of operations. Though it's worth noting that in Javascript, these functions are implemented using "while" loops anyway.
  3. Use recursion where reasonable, looping is OK if stack overflow is going to be an issue. Because most browsers do not offer Tail Call Optimization AFAIK, some algorithms can easily exceed their allocated stack depth depending on implementation.

To facilitate not violating rules 1, 2 and 3, I've also decided to use the Immutable library that provides a lot of useful functions and immutable data structures.

This blog is mainly for me to explain things to myself and documenting problems I found along the way. Though if you have any suggestions for how I can improve my writing of blogs, code or both, please don't hesitate to send me a message on social media!

The Grid

In order to play the game, first we need a way to store and represent the puzzle:

const importString = str => {
  const data = str.split("\n")
  const grid = Immutable.Map({
    symbols: Immutable.Set(data[0].split(" ")),
    matrix: Immutable.List(data.slice(1).map(row => Immutable.List(row.split(",")))),
  })
  return grid.set("isComplete", fnGrid.validate(grid))
}

/* Function turns this:
1 2 3 4 
 ,1, ,4
4,2,1, 
 ,3,4,2
2, ,3, 
into this:*/
const output = Immutable.fromJS({
  isComplete: false,
  symbols: Immutable.Set(["1", "2", "3", "4"]),
  matrix: [
    [" ", "1", " ", "4"],
    ["4", "2", "1", " "],
    [" ", "3", "4", "2"],
    ["2", " ", "3", " "],
  ]
})

When supplying the string for import, the top row is a space separated list of symbols that are valid for the given puzzle. The board is represented as a 2D matrix of strings where an empty space is denoted by a space. All values are stored as strings for easy comparisons and allows me to easily support different symbol combinations. Symbols are stored as a set because its only two purposes are for checking if it contains a value and iteration where the order does not matter.

Note: I found that the Immutable.fromJS() function does not convert built-in Javascript sets to Immutable.Set.

Additionally, this exports a given grid to a string. There is no real use for it in the app, but I put it there for completion's sake.

 const exportString = grid => 
  grid
    .get("symbols")
    .join(" ") + "\n" + fnMatrix.toString(grid.get("matrix"))

Now that I can import problems and output solutions, I'll talk about the validate() function next.

Solution Validation

The three constraints for the game listed above are basically directly translated into functions but with symbol checking done separately and first for efficiency (incomplete games will always fail on this step).

const validate = grid => 
  fnGrid.checkSymbols(grid) && fnGrid.checkRowsUnique(grid) && 
  fnGrid.checkColsUnique(grid) && fnGrid.checkBlockUnique(grid),

The checkSymbols() function goes through the grid and checks if every symbol is valid. 

  const checkSymbols = grid => 
    grid.get("matrix")
      .every(row => row.every(v => grid.get("symbols").has(v)))

The most efficient way to implement checkRowsUnique() is probably to recursively check if each cell value had been processed before using a set. However, I want to solve this in one line. This is accomplished by sorting the row before going through it, which mean we only need to check if a cell value is equal to its predecessor.

const checkRowsUnique = grid => 
  grid.get("matrix")
    .every(row => row.sort().every((v, i, list) => i!=0 ? v!=list.get(i-1) : true))

This is actually an example of the subtle difference how certain built-in Javascript methods work when compared to Immutable methods. The Javascript .sort() mutates the original array whereas Immutable.List.sort() does not. For this to work in vanilla Javascript, a copy will have to be made to prevent the original array from being mutated: row.concat().sort()....

checkColsUnique() would require a different approach as unfortunately in this case the columns can't be sorted. Had I gone the efficient route for checkRowsUnique(), I would likely be able to use essentially the same code with a few minor tweaks. Thankfully, a simple solution is to transpose the grid, converting columns to rows, which will allow me to reuse my current implementation of checkRowsUnique().

const checkColsUnique = grid => 
  fnGrid.checkRowsUnique(grid.set("matrix", fnMatrix.transpose(grid.get("matrix"))))

The performance penalties of this method will likely become apparent as the puzzles get larger, but I will let future me handle that.

Unfortunately, I am unable to come up with a satisfying one-liner to implement checkBlockUnique(), so instead I have to settle for a nested for-loop in disguise.

const checkBlockUnique = grid => {
    const _checkBlocksUnique = (row, col, matrix, blockLength) => { 
      // Recurse through blocks in grid
      // if all blocks have been checked, the matrix is valid
      if (row >= matrix.count()) return true
      // if cells in block are invalid, early termination
      else if (
        !_checkCellsUnique(0, 0, 
          fnMatrix.submatrix(matrix, row, col, blockLength, blockLength), 
          Immutable.Set())) return false
      else {
        // If the next col is out of bounds, go to next row
        const nextRow = col+blockLength >= matrix.count() ? row+blockLength : row
        const nextCol = col+blockLength >= matrix.count() ? 0 : col+blockLength
        return _checkBlocksUnique(nextRow, nextCol, matrix, blockLength)
      }
    }
    const _checkCellsUnique = (row, col, block, valueSet) => {  
      // Recurse through cells in grid
      // if all cells have been checked, the block is valid
      if (row >= block.count()) return true
      // if cells in block are invalid, early termination
      const value = block.get(row).get(col)
      if (value==" " || valueSet.has(value)) return false
      else {
        // If the next col is out of bounds, go to next row
        const nextRow = col+1 >= block.count() ? row+1 : row
        const nextCol = col+1 >= block.count() ? 0 : col+1
        return _checkCellsUnique(nextRow, nextCol, block, valueSet.add(value))
      }
    }
    // first and only call in this function
    return _checkBlocksUnique(0, 0, grid.get("matrix"), fnGrid.getBlockLen(grid))
  },

Starting at the top right of the grid, _checkBlocksUnique() copies the section of the block it is interested in and passes it to _checkCellsUnique(). _checkCellsUnique() recurses through the cells in a given block, keeping a set of values that it has seen, and checking new values against it. Once _checkCellsUnique() is done with the block, _checkBlocksUnique() moves on to the next block and repeats the process without overlapping with itself.

Conveniently, the number of rows or columns in a block belonging to a square Sudoku puzzle is always the square root of the number of rows or columns in the puzzle, so it is not necessary to persistently store the length of a block.

Conclusion

We are able to represent, manipulate and validate a Sudoku board. Now we just have to solve it.