Solving Sudoku with F#

One of my more recent additions to the life of {Redacted} is a thing we call the Thursday Kata. Every Thursday, I pop a message into our slack channel, with a challenge for the week.  Dev team members noodle over the problem, slack a gist with their solution, and then on Wednesday, during our weekly team meeting, we vote on a submitted solution and have the author present what they did, how they did it, and what they learned.

It’s a lot of fun, and is gaining quite a bit of traction within the development org. Developers are walking around discussing the kata, and strategies for solving it, and it interrupts what can be some of the more mundane day-to-day tasks.

The tasks aren’t meant to take more than an hour or two. A more recent example was a Sudoku solver. Devs were challenged to come up with a solver, in whatever language they wanted to look at.

Unfortunately, as the emcee of this event, my own solutions are off limits for voting… but that’s when I remembered I have readers of this blog (even if it is only myself and my mom. Hi Mom!)  Here’s the gist.

Basically, I had two ideas. First, be able to parse and render a puzzle grid, and second, solve the grid using a simple recursive algorithm.

I started with a few types that would help me with the domain.

1. Sector. A type that represented the 9 blocks (tic-tac-toe blocks) of a Sudoku grid.
2. Position. A type that represented an individual location of a Sudoku grid. The position was made of a Rank and File, which indicated the X and Y coordinate (in similar terms to chess, a game I’m more familiar with.)
3. Grid. A type simply mapping a Position (Rank and File) with integers.

The first thing I did was create a simple set of all available positions, and second I created a Map of positions with a unique set of positions to “check”. For example: the position at Rank.One and File.A (the upper left square), would be mapped to a distinct set of positions that included:

• All positions in Rank.One (A1, B1, C1… I1)
• All positions in File.A (A1, A2, A3… A9)
• All positions in the same TopLeft sector (A1, B1, C1, A2, B2, C2, A3, B2, C3)

The next three functions were some simple rendering / parsing functions, enabling me to quickly test my solver, by entering grids as simple strings.

let easy = parseGrid "5,-,-,-,1,-,-,-,4,2,7,4,-,-,-,6,-,-,-,8,-,9,-,4,-,-,-,8,1,-,4,6,-,3,-,2,-,-,2,-,3,-,1,-,-,7,-,6,-,9,1,-,5,8,-,-,-,5,-,3,-,1,-,-,-,5,-,-,-,9,2,7,1,-,-,-,2,-,-,-,3";;

val easy : Grid option = Some (map [({Rank = One; File = A;}, 5; .... 

let rendered = renderGrid e;;
val rendered : string =
"
 5 - - | - 1 - | - - 4
 2 7 4 | - - - | 6 - -
 - 8 - | 9 - 4 | - - -
 *********************
 8 1 - | 4 6 - | 3 - 2
 - - 2 | - 3 - | 1 - -
 7 - 6 | - 9 1 | - 5 8
 *********************
 - - - | 5 - 3 | - 1 -
 - - 5 | - - - | 9 2 7
 1 - - | - 2 - | - - 3
"

Ah UI code… my favorite 🙂

I created a few helper functions to make some logical tests work as well.

• getAvailableValues : Grid -> position -> (Position * int[])
  This function took a grid and a position, and returned the array of possible number values that were available for the position in question.
• isNotSolvable : (‘a * ‘b []) list -> bool
  This was a simple test to look at a list of things, and if there were any items that came in with an empty array (as the b value).
• isSolved : (‘a * ‘b []) list -> bool
  This simple test ensures that the incoming list, the max length of the b array is 1 value.

All together, this made the solve method easy to write.

Solve : Grid -> Map<Position, int> option.

If solve returned a None value, no solution was found. Otherwise, it would return Some solution (see what I did there.)

In that function, it defined a recursive function called ‘createSolution’, taking a grid g.

That function would first iterate through allGrid positions, and then create a list of Position * int [], mapping over the getAvailableValues function and the grid passed in.  That gave us a list of positions, and all positions potential answers. It caled the isNotSolvable method, to test if ANY of the positions couldn’t be solved (because they had no avialable options in the array.)  If so, the function returned None. Otherwise, it checked if the puzzle was solved, using the isSolved function above, and if so, it created a Grid map, and returned Some with that grid.

Finally, the meat of the function assumed that at least one of the Grid squares had more than one possible answer. It then did a simple query for the square with the smallest number of possible answers, and then simply called ‘createSolution’ recursively with one of those possible answers set for the square in question.

What ends up here is a depth first solution, but one that always returns (eventually.)

Here are some simple results I got. Fire up FSI and see what you get! Have a good puzzle everyone!

// easy (solve time 0.167 seconds)
let easy = Option.get (parseGrid "5,-,-,-,1,-,-,-,4,2,7,4,-,-,-,6,-,-,-,8,-,9,-,4,-,-,-,8,1,-,4,6,-,3,-,2,-,-,2,-,3,-,1,-,-,7,-,6,-,9,1,-,5,8,-,-,-,5,-,3,-,1,-,-,-,5,-,-,-,9,2,7,1,-,-,-,2,-,-,-,3");;
 
// hard (6.401 seconds) (38x easy)
let hard = Option.get (parseGrid "-,-,5,-,-,-,9,-,-,-,-,4,6,9,-,1,-,-,7,9,-,-,-,-,-,-,-,-,1,-,2,-,-,-,-,3,-,7,-,-,-,6,-,8,-,-,-,-,-,1,4,6,-,2,2,3,-,-,-,8,-,-,-,-,-,-,-,5,-,-,-,7,-,-,-,4,-,3,-,1,-");;
 
// extreme (20 minutes, 50.464 seconds) (7,487x easy)
let extreme = Option.get (parseGrid "8,-,-,-,-,-,-,-,-,-,-,3,6,-,-,-,-,-,-,7,-,-,9,-,2,-,-,-,5,-,-,-,7,-,-,-,-,-,-,-,4,5,7,-,-,-,-,-,1,-,-,-,3,-,-,-,1,-,-,-,-,6,8,-,-,8,5,-,-,-,1,-,-,9,-,-,-,-,4,-,-");;