Sudoku: Depth and Breadth First Search

2020, Jun 02
Link to project here.

The simplest way to solve a Sudoku puzzle would be to simply search for the answer one cell at a time. The two most basic methods of search are Depth First(DFS) and Breadth First Search(BFS). Both algorithms make use of backtracking once they have explored a branch in their search path sufficiently to go back and expand other paths.

When looking at the pseudocode on Wikipedia for both algorithms, they are extremely similar with only one key difference: DFS uses a stack data structure to store the order of the nodes it will expand, whereas BFS uses a queue. The gist of it is items stored in a stack are retrieved in a "Last In, First Out" order (like a stack of plates), whereas a queue being the opposite of it is a "First In, First Out" order (like a queue to buy movie tickets). We will actually use this to our advantage and make a single function able to use either algorithm via currying. Also, because the Sudoku grid is an acyclic graph where every move we take will lead to a unique board state, we can omit keeping a record of discovered cells that are separate from the queue/stack.

Implementation

When deciding what value to put in each cell, we first have to decide which cell we want to try filling first. Being that these are simple algorithms, they can really just start looking on the very first empty cell in the grid, starting from the top left and moving to the bottom right.

const getEmptyCell = (grid, i=0) => {
  const matrix = grid.get("matrix")
  const j = matrix.get(i).indexOf(" ")
  // if j<0, recurse further into the grid, else return coordinates of (i,j)
  return j<0 ? 
    // If i does not exceed the number of rows, continue, else break
    (i+1<matrix.count() ? fnSearch.getEmptyCell(grid, i+1) : {row:-1, col:-1}) : 
    {row:i, col:j} // If j >= 0, then we found an empty cell
}

Once we have decided on a cell to check out, we have to determine if a value can be added when placed within the cell.

const isValidMove = (grid, row, col, value) => 
  !grid.get("matrix").get(row).some(v => v==value) && // row
  !grid.get("matrix").some(row => row.get(col)==value) && // col
  !fnGrid.getBlock(grid, row, col).some(row => row.some(v => v==value)) // block

The logic is essentially the same as when I wrote the validation function for the grid (check out part 1 of the blog). The difference here is that the function only needs check the row, column and block where a value is intended to be placed.

With isValidMove() in place, it can now be used to filter for a set of valid values for a given cell. First, we find an empty cell, then the set of valid symbols for the grid is filtered for only values that are valid in that position. These values are then inserted into the grid to generate a list of following states that can be added to the stack/queue.

  // Get the next available moves from this grid
const getNext = grid => {
  // Get the position of next empty cell
  const {row, col} = fnSearch.getEmptyCell(grid)
  if (row<0) return Immutable.List()
  else {
    return grid.get("symbols") // For all symbols,
      .filter(v => fnSearch.isValidMove(grid, row, col, v)) // filter for only the ones that are valid
      .map(v => fnGrid.setValue(grid, row, col, v)) // get new grids with the valid symbols added to the position
      .toList() // Convert from Set to List
  }
}

Now it's just a matter of iterating through the stack/queue to find the solution we are looking for. Thus here is the function that runs the BFS/DFS algorithm, or at least the pure functional one.

Functional Solver

const solve2 = isBfs => grid => {
  const _solve = (grid, moves) => {
    if (grid.get("isComplete") || moves.count()<=0) return grid
    else if (fnGrid.validate(grid)) return grid.set("isComplete", true)
    else {
      const newMoves = moves.concat(basicSearch.getNext(grid))
      return _solve(
        isBfs ? newMoves.first() : newMoves.last(), 
        isBfs ? newMoves.shift() : newMoves.pop())
    }
  }
  return _solve(grid, basicSearch.getNext(grid))
}

In essence, this is what is happening:

  1. If the grid is already marked as complete, or there is nothing left in the stack/queue, just return what we currently have.
  2. Check if the grid is complete, if it is, mark it complete and we are done.

  3. If none of the above are true, generate new moves based on the current board state and then,

    • If DFS, add to top of stack and take the move at the top of the stack.
    • If BFS, add to back of queue and take the move at the front of the queue.

Currying is used to determine beforehand which algorithm the function is going to use via the isBfs variable.

Non-Functional Solver

While this implementation works great, I decided to write a non-functional version as well, as it would be simpler to break into steps for visualization. There is also the possibility of stack overflow to consider, most modern browsers seem to let you go pretty deep, but I would rather just stay on the safe side.

const solve= isBfs => data => {
  const step = basicSearch.solveStep(isBfs)
  // Loop until solution found or exhausted all options
  while(!data.getIn(["grid","isComplete"]) && data.get("moves").count()>0) {
    data = step(data)
  }
  return data
}

You'll notice that instead of passing a grid, I'm passing a data variable instead. This is because through tinkering with the visualization, and also with the solver stepping feature, it's more convenient for keeping all the things I need to keep track of together in a single object.

const mkDataMap = grid => Immutable.Map({
  grid: grid,
  moves: basicSearch.getNext(grid),
  steps: 0,
})

As you can see, it is just a simple map object keeping track of the current grid state, the stack/queue and the number of steps that have been taken. With this, I'm able to run a solver step by step rather than having to do it all at once and only show to final product.

const solveStep = isBfs => data => {
  const grid = data.get("grid")
  const moves = data.get("moves")
  // If grid is a valid solution, update its status
  if (fnGrid.validate(grid)) return data.setIn(["grid","isComplete"], true)
  else {
    // Otherwise add the moves from current grid and grab the first one in the stack
    const newMoves = moves.concat(basicSearch.getNext(grid))
    return data
      .set("grid", isBfs ? newMoves.first() : newMoves.last())
      .set("moves", isBfs ? newMoves.shift() : newMoves.pop())
      .set("steps", data.get("steps")+1)
  }
}

This function is essentially the same as the earlier recursive function, just without the recursion. Moving forward I will still attempt to make functional solvers, however I think that I will favour the use of stack safe solvers by default.

Conclusion

While running these algorithms on some test puzzles, I found that DFS does decently well on easy and medium difficulty puzzles, while struggles on the harder ones with very large numbers of steps. BFS works fine on the 4x4 puzzles, but is incredibly slow otherwise because it checks every intermediate possibility all the way to the solution. I would absolutely not recommend BFS for Sudoku.