Sudoku - Brute force done right

Brute force is an extremely powerful tool, but only if it is used correctly

Brute force is, as the name suggests, an approach to solving problems that relies on sheer weight of numbers to solve problems rather than clever algorithms. Computers are capable of phenomenal computational power, so why not just deploy this to keep guessing until you get the right answer?

This approach can be super powerful, however, this is no silver bullet. As the programmers, you still have a job to do identifying and defining constraints that can narrow down state space. I like to think of it like water, without supporting structure it just floats around, but, contain it correctly and it can rip through concrete.

As an example, consider trying to solve arbitrary Sudokus. 9 by 9 grid in which the same number can only appear once in each column, row, and 3x3 sub grids.

Without thinking much, it seems that the brute force solution is:

  • Set every unconstrained cell in the grid to a random int between 1 and 9
  • Test whether meets constraints
  • Repeat until passes

Seems good value until you start to think about how big state space actually is. Each cell can be 9 different values so (ignoring the fact that some cells are preset) is 9 ^ (9 * 9). First order approximated by a lot. To get some sense of this, I tried to get this to work, but gave up after half an hour.

The issue we have is that our force is getting dissipated over a large area that essentially pointless. We’re making no use of our constraints, so we end up chasing down rabbit holes. If the first two numbers I put in are one and one, then everything after that is just a waste of time, I’ve already failed. If we could stop when the constraints are failed, then the size of state space dramatically collapses.

How to do this? We need to use the power of the constraints that we have. We can bake the constraints into our random integer choice. Rather than choosing a random.randint(1,9), we can filter to just those that don’t exist in the row, column and square. If this set is empty, then we throw and start randomly selecting from the start.

This actually works super well and gets a solution in ~1000 iterations.

Consider now extending to solve a killer sudoku. This is where in addition to the normal constraints, there are arbitrarily defined regions that have to sum up to a chosen value. I.e. ((0,0), (0,1)) can have to add up to 6 and so on.

The brainless approach to this is to use our sudoku solver to generate valid sudoku’s and then test whether they meet the extra conditions of killer sudoku. Why this is a bad idea should hopefully be clear at this point, but, to reiterate, your solver will spend almost all of its time doing totally irrelevant work. FYI also couldn’t get enough brute force to get a solution this way in practice.

A better way to play is to again flip the problem and bring the constraints inside the brute force. In our random int choosing section, we now need to incorporate the arbitrary area constrictions. I did this by:

  • Iterate over region
  • For each cell in region:
  • Identify possible values based on sudoku rules
  • If it’s not the last cell choose a random element in the set of possible values filtered to be less than the region’s max value
  • Subtract the chosen value from the region’s total value
  • Repeat - if get too high, throw
  • For the last cell, if the remaining value to meet the requirement exists in possible values take that, else throw

The nice thing about this solution is that the sudoku rules and killer sudoku rules are essentially orthogonal. You can create Killer Sudoku as a wrapper over the top of a Sudoku (which is as things should be).

My slightly hacky code for implementing this can be found here:

https://github.com/JakeColtman/Kill-Sudoku-Solver/tree/master/Sudoku

To conclude: brute force is a mightily powerful tool that can do miracles, however, it’s not some silver bullet, nor is it an excuse to be lazy and not think. The more you can build constraints into the way it explores state space, the more powerful it becomes.