Sentient Sudoku Solver

I recently heard about a new language created by Chris Patuzzo, a former colleague from right here at a Which? So naturally I decided to check it out, and, well, it’s actually pretty interesting.

The reason I find it interesting is that it’s a fundamentally different way of solving problems than the programming I’m used to as a Ruby dev. What I mean by that is that instead of the developer telling a machine how to solve a problem the dev simply describes the desired result. The computer calculates the requested number of possible solution. So if you can specify the requirements of your solution clearly you can get solutions to problems in a very intuitive way.

The language is called “Sentient” and despite its name it’s not any kind of artificial intelligence. If you want to know how it works and where it came from checkout this podcast  for the full story. There are lots of good examples of what can be achieved on the Sentient website. It also has some good docs on there to help if you want to play around with it and try it for yourself. Which, being an ever curious dev, I did.

I started, as is often the case, with a problem. A Sudoku problem. I was fairly sure this would be a good choice as the website claimed Sentient could easily solve such a problem, and, having read what I had, I believed it.

So, first things first, I needed a data structure to represent a Sudoku board. The Sudoku board is basically a 3×3 grid of 3×3 grids. The smaller 3×3 grids, that make up the larger one, I call boxes. Columns and rows are as you’d expect.

In this case I would normally build an object but I decided to follow the patterns shown in the examples from the website and use a primitive. So what primitive did I opt for? An array, of course. My first pass at this was to build a very multi-dimensional array.

array3<array3> grid;

The aim was to have an easy way to get the 3×3 boxes in the Sudoku grid. I soon realised though that while the boxes were more easily accessible I had only made the rows and columns harder to reference. So I simplified it to a more sensible structure.

array9 grid;

The nice thing about this was that I could get the rows from the grid by simply calling “grid.each”, and the columns weren’t much more challenging “grid.transpose.each”. The cost though, was that now it was a little bit trickier to reference the boxes. We’ll come back to that in a moment though.

With the grid defined and the rows and columns accessible I moved onto the invariants. These are basically a way of setting rules that can’t be broken by the computer when it’s trying to come up with a solution to the problem. So, in Sudoku, rows and columns need to contain only unique values between 1-9, and therefore it needed to be specified as such in the code. I checked the website to find the code I needed and was happy to see it could be implemented in a very concise way.

invariant row.uniq?;

invariant row.all?(function (value) {
    value.between?(1,9)
  };
);

The next step was more tricky so bear with me. I needed a way to reference the specific elements of the grid that constituted each box. So, with as little thought as I could get away with (or less), and after a couple of botched and retrospectively stupid attempts I came up with this.

boxes = [0, 3, 6].map(function^ (num) {
  return [0, 3, 6].map(function^ (num2) {
    return [
      grid[num2][num], grid[num2][num+1], grid[num2][num+2],
      grid[num2+1][num], grid[num2+1][num+1], grid[num2+1][num+2],
      grid[num2+2][num], grid[num2+2][num+1], grid[num2+2][num+2]
    ];
  });
});

This is a little ugly and is by far the most complex part of the code. I feel like it could be improved upon but I was far too eager to get back into the Sentient proof of concept. Feel free to leave a comment with a better implementation if you have one though. I’m always happy to get constructive critique.

Once I had access to these boxes I just set the same invariants on them. And, then, with a sprinkle of refactoring on the invariants code to dry things up, and hey presto, a Sudoku solver in just over 30 lines of code!!

array9 grid;

boxes = [0, 3, 6].map(function^ (num) {
  return [0, 3, 6].map(function^ (num2) {
    return [
      grid[num2][num], grid[num2][num+1], grid[num2][num+2],
      grid[num2+1][num], grid[num2+1][num+1], grid[num2+1][num+2],
      grid[num2+2][num], grid[num2+2][num+1], grid[num2+2][num+2]
    ];
  });
});

function validCollection?(collection) {
  invariant collection.uniq?;
  invariant collection.all?(*valueValid?);
};

function valueValid?(value) {
  return value.between?(1,9);
};

grid.each(*validCollection?);
grid.transpose.each(*validCollection?);

boxes.each(function (boxRow) {
  boxRow.each(function (box) {
    validCollection?(box);
  });
});

expose grid;

But wait, how does it work? Well I chose to run it from the command line and passing it a file representing the Sudoku puzzle.

sentient --run sudokuSolver.min.json --assign-file sudokuInput.json

My sudokuInput.json file sets up the grid with the known values in it. Sentient handles the assignment of the values to the grid variable inside the application. The file looks like this

{
  grid: [
    [undefined,3,7,9,undefined,4,6,undefined,8],
    [undefined,undefined,undefined,undefined,3,undefined,undefined,undefined,undefined],
    [undefined,8,undefined,undefined,undefined,undefined,1,undefined,2],
    [5,undefined,6,2,undefined,undefined,3,undefined,undefined],
    [undefined,undefined,9,7,1,3,4,undefined,undefined],
    [undefined,undefined,3,undefined,undefined,6,2,undefined,9],
    [6,undefined,8,undefined,undefined,undefined,undefined,7,undefined],
    [undefined,undefined,undefined,undefined,9,undefined,undefined,undefined,undefined],
    [3,undefined,2,8,undefined,1,5,4,undefined]
  ]
}

The corresponding Sudoku board would look like this

We use undefined in positions we want Sentient to fill in the answers according to the rules we’ve set up in the app. Putting nil instead of undefined will assign the value nil to that position in the grid which wouldn’t work.

When we run that command the output that we get is the completed puzzle, Yay! In unformatted json, Boo! With a little fiddling it looks something like this..

{
  "grid": [
    [1,3,7,   9,2,4,   6,5,8],
    [2,6,5,   1,3,8,   7,9,4],
    [9,8,4,   5,6,7,   1,3,2],

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

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

So there we have it. A complete working Sudoku solver written in under an hour in just 32 lines of code. Something I would have said was impossible just a few days ago.

I thought about writing the equivalent code in Ruby for a comparison, then I shuddered, and decided that this example makes it clear enough in isolation. Clearly it wouldn’t work for every challenge we face as developers but it’s certainly a new way to do things that would otherwise be quite a lot more effort. I look forward to seeing how Sentient evolves over time and I’m happy to add it to my tool belt.