Sudoku Part 0: Introduction

• Sudoku Part 0: Introduction
• Sudoku Part 1: Defining The Solver Behavior
• Sudoku Part 2: Implementing A Solver
• Sudoku Part 3: Defining The Generator Behavior
• Sudoku Part 4: Implementing A Generator

It's been a while since my last post here. Part of the reason it has been so long is the fact that I traveled for the holidays, making it more difficult to make time to update this blog.

While traveling I break out sudoku (and other similar puzzle games) to help the time go by on the way to my destination. As a programmer I tend to take any problem I'm solving and analyze it as if I was developing a program to solve the problem for me. This isn't generally something I follow through on, but rather just a mental exercise where I wonder about the what ifs.

While working on a Sudoku puzzle I thought, as fun as solving this puzzle is, writing an algorithm that solved it in the same manner that I do would be even more enjoyable. Better yet, there may be many ways to build a sudoku solving algorithm. I also thought that in order to make an enjoyable sudoku solving algorithm I would also need to create a sudoku generating algorithm. Again, I thought there may be potential for many algorithms.

This time it got me thinking. Sudoku is fun, maybe this would be a good platform to introduce some topics. I have spent some time reading about Behavior-Driven Development (BDD), and would like to introduce an example of it on my blog. This seems like a good candidate. Most people are familiar with the puzzles. Secondly, I would also like to use this as an example for how to use a Dependency Injection framework. The fact that I hope to be able to generate multiple algorithms would seem to enforce the use of such a tool here.

I plan to make this a multi-part series as there are too many topics to cover to justify a single blog post. I am currently investigating this program now, so don't blame me if it takes a while to write the entire series.

Initial Thoughts

When I was first thinking about these problems on the Plane I thought a sudoku generator would be relatively simple. Well I can now say with confidence that it is not. The algorithm I formed in my head went something like the following:

1. Divide the board in to rows, columns and regions, matching the general rules for the game.
2. For each row, column and region create a set of Sudoku values (1-9) which are valid to be used for that grouping.
3. Loop over all pieces of the board
4. For each piece take the intersection of the valid values from this pieces row, column and region
5. Randomly select a value from the remaining values, assign it's value to the piece and then remove it from the list of valid values for the pieces row, column and region.
6. Once a valid board is created, randomly select a piece on the board to clear the value from
7. Continue randomly removing values until the puzzle is no longer uniquely solvable, and re-add the last removed value.

This seemed like a reasonable algorithm to me. It seemed that there would always be a choice for valid values seeing as all previous pieces used valid values. I guess I just assumed that while placing pieces there would always be remaining valid pieces until you finished the puzzle. To my initial surprise, this algorithm failed on step 5 every time. The generator kept kitting situations where there were no valid values which could be placed on the current piece.

See the below example of the result of my algorithm. Note that there is no valid value which can be placed in the next box, even though all previous entries were entirely valid. According to the row of the piece the value should be 4. Yet 4 is invalid for that piece's column and region. So clearly 4 will not work there. Any value besides 4 will cause an issue for the row. This algorithm clearly doesn't work.


With that experiment I'm pretty much back to the drawing board. I do have a few ideas on algorithms that should work, but my goal with this is to have at least two working sudoku generation algorithms. So far I'm at least enjoying the hunt for a working algorithm. I would like to create at least one solution on my own, but at some point I may have to break down and look for some assistance.

--John Chapman