Sudoku Validation

Weekly Challenge IV


I’ve always loved Sudoku, the charming number puzzle game so addicting that British Airways flight attendants are explicitly forbidden from attempting to solve them during take-off. This week, I wrote a program that verifies whether a supplied sudoku solution is satisfactory.

Kindly ignore the watermarks that reveal I stole this image :)

For the unfamiliar, sudoku is a puzzle in which you must fill in a 9x9 grid with the numbers 1–9, in such a way that the following rules are followed:

In this example you are given the black numbers. It’s your job to fill in the rest, represented in red.
  • Each row must contain every number from 1 to 9 exactly once.
  • Each column, similarly, needs one of every number from 1 to 9.
  • Each 3x3 ‘region’ needs to follow the same 1–9 pattern.

Problem Format

This problem comes from CodeWars, and it takes a two-dimensional array as input. The board above looks like this:

[
[5,3,4,6,7,8,9,1,2],
[6,7,2,1,9,5,3,4,8],
[1,9,8,3,4,2,5,6,7],
[8,5,9,7,6,1,4,2,3],
[4,2,6,8,5,3,7,9,1],
[7,1,3,9,2,4,8,5,6],
[9,6,1,5,3,7,2,8,4],
[2,8,7,4,1,9,6,3,5],
[3,4,5,2,8,6,1,7,9]
]

There’s some other nonsense in the problem about returning the strings ‘Finished!’ or ‘Try Again!’ instead of a boolean, but I’m ignoring that :)

Doing it Functionally

For a change of pace, I decided to solve this week’s challenge using functional programming.

A different paradigm from the more-familiar Object-Oriented Programming, functional programming has a few key defining characteristics:

  • Data should be immutable. Never change anything, create new objects instead.
  • Lots of short, to-the-point functions. It’s no coincidence that it’s called functional programming. Functions are first-class (can be passed around as variables) and high-order (functions can take functions as arguments and return functions).
  • Prefer declarative programming (tell it what you want it to do) over imperative programming (tell it how to do it).
  • Perhaps most importantly, no side effects! A function should only depend on what’s inside the function, and given the same input, it should behave the exact same way every time regardless of what’s going on outside. It should not modify any external variables.

Because of these principles, there are a few common trends among functional programming. Iterators like map and reduce are better than for/while loops, because they’re declarative. Recursion is heavily used as well.

The Code

In previous weeks, I would first build out a complete but flawed solution, and then I would tear it down and do it better. This week, though, I just slowly perfected a single approach.

Rather than bore you with the incremental discovery process, I’m just going to share the heavily-annotated result.

And there you have it — my first shot at functional programming. I have to say, I sorta love it. While it may be hard to tell with all my comments, each function is only a few lines long — take a look at the comment-free version.

Each function has exactly 1 job and you can tell exactly what that job is right away. The result is an incredibly easy to read list of tiny tasks that come together to solve a greater problem. I have the feeling I’ll be able to look at this code in a year from now and I’ll understand it within a few seconds.

As always, the code is on GitHub. I added a few tests with Mocha/Chai as well.

I encourage anyone reading this to try to solve a problem functionally. It’s quite a bit of fun =)