Sudoku: Greedy Search (Binary Heap)

2020, Jun 03
Link to project here.

If you've tried out Depth (DFS) and Breadth First Search (BFS) on the app, you'd have noticed that they both always start from the top left corner. That's totally fine on smaller and easier puzzles, but then as the difficulty ramps up, or even just having most of the initial values concentrated in the bottom right, both can take forever to run.

This is because when there are many possible values in the first few cells used, it can dramatically increase the number of permutations that have to be evaluated by the program. For example, if given a puzzle such as below:

This puzzle requires 58 moves in order to arrive at the solution. A DFS will start in the top left corner, and here's how the number of nodes along each search path will change:

  1. A1, 7 possible values. Total nodes 7.
  2. A2, 7 possible values. Total nodes 7 + 7 * 7 = 56.
  3. A3, 5 possible values. Total nodes 56 + 56 * 5 = 336.

Even by just the third cell, there are already over 300 possibilities to consider, and as we continue to explore, the number of nodes will continue to multiply by their average branching factor.

Fortunately, there is a commonsense way to fix this problem that most people playing Sudoku will naturally gravitate toward: just start from the cells with the least possible values. So how would starting from the cells with least possibilities in this puzzle affect the number of nodes in the beginning? Lets have a look:

  1. B3, 2 possible values. Total 2 nodes.
  2. B2, 2 possible values. Total 2 + 2 * 2 = 6 nodes.
  3. B1, 1 possible value. Total 6 + 6 * 1 = 12 nodes.

Just by changing the order of evaluation for nodes, we've already managed to achieve a reduction in the number of nodes by a factor of 33. Keep in mind as well that as the board fills up, the number of possibilities for each cell naturally shrinks, thus by the time we get back to cells A1, A2 or A3, it is likely that their possible values would have shrunk significantly.

The type of search that I will be discussing today is called a greedy search. Where at each step in the process, decisions are made based on what is optimal from that given position, without worrying about the big picture. It is particularly useful here because there is only one possible solution for any given puzzle.

Implementation

At its core, my implementation is basically a DFS. It's so similar that instead of rewriting it in a different module, I just modified my existing module to take an extra argument which decides whether the function uses the original getNext() or getGreedyNext() instead. In all cases, the decision is made by this ternary expression:

isGreedy ? basicSearch.getGreedyNext(grid) : basicSearch.getNext(grid)

In order for getGreedyNext() to function correctly, it needs to be able scan the whole grid and find the cell with the least number of possible values. Now, I could very well have just held on to just the smallest move list until the very end, but for educational purposes I decided to throw a binary heap in there instead since both Javascript and Immutable don't provide implementations of this data structure.

Binary Heap

A heap is essentially a priority queue, where elements that are added to the queue are organized based on certain criteria. Just like how in an emergency room, the patients with the most urgent issues are always seen first regardless of when they arrived. A binary heap is just a specific implementation of the heap using a complete binary tree. My particular implementation follows the most common approach of using an array-like structure rather than an actual tree-like structure.

push()

For this particular application I need three operations, push(), pop() and peek(). The push() operation lets us add an element to the heap. However, rather than placing an element directly into where it should it in the heap, it is instead placed at the end of the heap and then the bubbleUp() operation puts it into place.

heap.push = function(v) { 
  return Heap(this.bubbleUp(this.data.push(v), this.data.count()), this.compare)
}

heap.bubbleUp = function(A, i) {
  if (i>0) {
    const parent = Math.floor((i-1)/2)
    if (this.compare(A.get(i), A.get(parent))) {
      return this.bubbleUp(A.set(i, A.get(parent)).set(parent, A.get(i)), parent)
    }
  }
  return A
}

Starting from the very bottom of the tree, the function compares the current element with its parent. Assuming we are using a min heap, if the current element is smaller than its parent they swap places and the element "bubbles up" the binary tree until it finds a parent that is smaller than it. This is pretty much the same behavior you would find in a bubble sort. Once the bubble operation is complete, a copy of the Heap object is returned with the changes made. Keeping in line with the theme if immutable data structures and functional programming.

Note: The Heap object is created using a factory function. I found that using the arrow notation actually prevents the this keyword from functioning properly. Thus the use of function(){} notation is necessary when defining instance methods.

pop()

The pop() operation lets us remove the value at the top of the heap (the root). But considering this is a tree structure, which remaining element is the now removed root replaced with? In fact it is the element at the very end of the tree, after which the tree is reorganized using the bubbleDown() operation.

heap.pop = function() {
  return Heap(this.bubbleDown(this.data.set(0, this.data.last()).pop(), 0), this.compare)
}

// Check if the value at i is smaller/larger than its children, if it is, move it down the heap
heap.bubbleDown = function(A, i) {
  const left = 2*i + 1
  const right = left + 1

  if (left < A.count() && this.compare(A.get(left), A.get(i)) && this.compare(A.get(left), A.get(right))) {
    // if left child exists and left is smaller than i, swap places with left and continue bubbling
    return this.bubbleDown(A.set(i, A.get(left)).set(left, A.get(i)), left)
  } else if (right < A.count() && this.compare(A.get(right), A.get(i))) {
      // if right child exists and right is smaller than i, swap places with right and continue bubbling
      // Don't need to check if right is smaller than left because:
      // 1) if it is smaller than left, it still has to be smaller than i anyway
      // 2) if it is larger than left and i is smaller than left, right is also going to be larger than i.
    return this.bubbleDown(A.set(i, A.get(right)).set(right, A.get(i)), right)
  } else {
    return A
  }
}

Starting from the root of the tree, the function compares the current element i with its children. Assuming we are using a min heap, if i is smaller than its child they swap places and the element "bubbles down" the binary tree until it reaches a point where both children are larger than it. At the end of the operation, the smallest element will be the root of the tree. Similar to push(), pop() returns a copy of the heap with the changes made.

peek()

Literally just a getter for the element at the top of the heap.

heap.peek = function() { 
  return this.data.first()
}

getGreedyNext()

Now that we have access to a Heap object, we can just scan through the grid, adding the moves for each empty cell to the heap.

const getGreedyNext = grid => {
  const symbols = grid.get("symbols")
  const matrix = grid.get("matrix")
  const getMoves = (i, j, heap) => {
    if(i>=matrix.count()) return heap
    const cell = matrix.getIn([i,j])
    const iNew = j+1 < matrix.count() ? i : i+1
    const jNew = j+1 < matrix.count() ? j+1 : 0

    if (cell==" ") {
      const validMoves = symbols.filter(v => fnSearch.isValidMove(grid, i, j, v))
      // *Important* If there are no valid moves in an empty cell, then all moves stemming from
      // this particular grid will be invalid anyway, so just return an empty heap
      if(validMoves.count()<=0) return Heap()
      else {
        const newGrids = validMoves.map(v => fnGrid.setValue(grid, i, j, v)).toList()
        return getMoves(iNew, jNew, heap.push(newGrids))
      }
    } else return getMoves(iNew, jNew, heap)
  }
  // A heap is actually not necessary, I just wanted to try to code one.
  // For max efficiency, just pass along the list of moves with the smallest size instead.
  const sorted = getMoves(0, 0, Heap([], (a, b) => a.count()<b.count()))
  return sorted.count()>0 ? sorted.peek() : Immutable.List()
}

getGreedyNext() is basically the same as getNext() from the perspective of each cell, but it scans the whole grid for the best cell to use instead of just using the first one. Here is what is happening:

  1. If i exceeds the number of rows in the grid, iteration has been completed.

  2. If the cell is empty (" "),

    • If there are no valid moves, this entire grid is invalid and we can exit early.
    • Otherwise, generate a list of grids resulting from the valid moves and push to heap.
  3. If cell already has a value, skip.
  4. Now that we have the heap of moves, return the shortest list (root of heap).

The list is then passed on to the DFS algorithm to work its magic.

Conclusion

This algorithm runs significantly and consistently better than DFS (not even considering BFS). There were many cases where DFS took thousands of steps but Greedy took less than a hundred. However, if a solution just happened to be in the on the last branch at each level, it would still take tens of thousands of steps to finish. This is however, just the worst case scenario. In most cases, this is definitely recommended as a simple and efficient option.