How to build a Sudoku Game

Sudoku is one of my favorite puzzle games. One day I had enough of ads popping up between my Sudoku games on my phone and decided to create a Sudoku app for myself to enjoy, without ads!

Sudoku App

Web site created using create-react-app

GitHub - sngguojie/sudoku

Contribute to sngguojie/sudoku development by creating an account on GitHub.

GitHubsngguojie

Architecture

To build a Sudoku game, we would need a few components:

1. The Solver
2. The Generator

The Solver

We needed to find a possible solution for the sudoku puzzle. The first method that came to mind was to find all valid moves for a puzzle, apply one of the moves, and then try to find the solution again.

However, a puzzle might have more than 1 unique solution. If we want to create a uniquely solvable sudoku puzzle (where every move is deterministic), we need to know if the puzzle has exactly 1 solution.

The last thing we need to consider is performance. Since this is a recursive algorithm, we may potentially recompute the same puzzle over and over again if we apply the same moves in a different order. We also want to make sure we compute the moves that eliminate the greatest subset of next moves first, so that we can get to an answer faster.

With these in mind the `getSolutions` function looks like this:

export const getSolutions = (puzzle: number[][], maxSolutions: number=2, solutionsStore?: { [puzzle: string]: string[] }) => {
  if (solutionsStore !== undefined && solutionsStore[JSON.stringify(puzzle)] !== undefined) {
    return solutionsStore[JSON.stringify(puzzle)]
  }
  const storeSolutions = (solutions: string[]) => {
    if (solutionsStore !== undefined) {
      solutionsStore[JSON.stringify(puzzle)] = solutions
    }
  }
  if (isSolved(puzzle)) {
    let solutions = [JSON.stringify(puzzle)]
    storeSolutions(solutions)
    return solutions
  }
  let { unsolveable, countToSquares, validMoves } = calculateValidMoves(puzzle)
  if (unsolveable) {
    storeSolutions([])
    return []
  }
  let sortedSquares = [...countToSquares].flat()
  let solutions: string[] = []
  let [rowIndex, colIndex] = sortedSquares[0]
  let nextMoves = validMoves[rowIndex][colIndex].map(n => [rowIndex, colIndex, n])
  for (let i in nextMoves) {
    let nextMove = nextMoves[i]
    let nextPuzzleState = applyMove(cloneDeep(puzzle), nextMove)
    let currentSolutions = getSolutions(nextPuzzleState, maxSolutions, solutionsStore)
    currentSolutions.forEach(s => {
      if (!solutions.includes(s)) {
        solutions.push(s)
      }
    })
    if (solutions.length >= maxSolutions) {
      storeSolutions(solutions)
      return solutions
    }
  }
  storeSolutions(solutions)
  return solutions
}

The Generator

Now that we have a solver, we need to generate uniquely solvable puzzles. The basic algorithm is to start with a random solved puzzle, and attempt to remove a random square every iteration and validate that the puzzle is still solvable. If the puzzle becomes unsolvable, or if there becomes more than 1 unique solution, we re-add the number into the square and try a different number or square.

export const generateUnsolvedTruePuzzle = (solvedPuzzle: number[][], maxIterations: number=60) => {
  let puzzle = solvedPuzzle.map(r => [...r])

  let solutionsStore: {[puzzle: string]: string[] } = {}

  let iteration = 0
  while (iteration < maxIterations) {
    iteration ++

    let removed = false
    
    // Moves that can be removed if they lead to multiple solutions
    let undoableMoves = getUndoableMoves(puzzle)
    undoableMoves = shuffle(undoableMoves)

    // iterate through the moves and try remove squares
    for (let i in undoableMoves) {
      let [rowIndex, colIndex, n] = undoableMoves[i]
      
      // Remove square
      puzzle[rowIndex][colIndex] = 0
      
      // if unsolvable after removal, add back square and try next move
      let { unsolveable } = calculateValidMoves(puzzle)
      if (unsolveable) {
        puzzle[rowIndex][colIndex] = n
        continue
      }
      
      // if not unsolvable, get solutions
      let solutions = getSolutions(puzzle, 2, solutionsStore)
      // if there is exactly 1 solution (ie true puzzle) skip rest of the moves
      if (solutions.length === 1) {
        removed = true
        break
      } else {
        // If there is no solution, or multiple solutions, add back square and try next move
        puzzle[rowIndex][colIndex] = n
      }
    }
    // If we go through all the moves and no square can be removed, return the puzzle
    if (!removed) {
      break
    }
  }
  return puzzle
}