Appropriate algorithms, Part 1

The Suko puzzle is a grid of nine squares. The aim of the puzzle is to put a different digit from 1 to 9 in each square so that the four squares around each of the four circles in the board add up to the total in that circle and the digits in the coloured squares add up to the number given below in the circle of the same colour. The idea of this page is to get an idea of the puzzle and how you might solve it. Go to the next page to see it solved by an algorithm.

Without the algorithm, this puzzle can be in Edit mode or Play mode. It starts in Edit mode. This allows you to set up a particular puzzle - for instance one from a newspaper by clicking in the various circles and entering the totals.

When you have selected one of the coloured circles (indicated by a heavier outline) you can also set the colours of the squares by clicking in them. Clicking again will clear the square colour to white. Published Suko puzzles have all their squares coloured, but that is not enforced here.

Alternatively, you can click the Generate button to get a random puzzle. Unlike published puzzles, it may have more than one solution. You can modify the generated puzzle by changing any of the totals and any of the colours of the square; after your changes, of course, there may be no solution.

Click the Play button to change to Play mode. In this mode you can key digits into the squares.

Whenever you leave one of the input fields - by clicking elsewhere - the JavaScript checks all the fields and shows any that are definitely wrong in red (italics) - up to you to work out why. Blue indicates totals whose contributing squares are not all filled in with valid digits and black (not italics) indicates values that are valid, though not necessarily part of a solution. When all the nine digits and seven totals show in black you have a solution.

From Play mode you can go back into Edit mode by clicking the now relabelled button. In Edit mode you can modify the puzzle without changing the digits you have already entered in the squares.

The Reset button puts the puzzle back into its initial state. When the puzzle is in Play mode, you can clear all the digits from the squares by clicking the Clear Solution button.

The purpose of this page is to let you get an idea of the puzzle and how you might solve it. Go to the next page to add an algorithm to solve it.

Here is the same puzzle as on the previous page, but with a solver algorithm added.

You can still edit the puzzle and play it as before, but now you can also call an algorithm to solve it. Once you have set up the puzzle - by using the Generate button or by editing it yourself - you can click the Solve button to see the algorithm solve the puzzle and change the mode to Solved. If the algorithm cannot find a solution (either there is none or there is an error in my coding) then it changes the mode to Failed.

Use the second row of buttons to see my basic algorithm in action.

• Solve - runs the algorithm
• Solve in steps - runs the algorithm displaying each step taken
• Show/Hide details - toggles the display of the algorithm's elapsed time and step count, and gives you a control to make the step‑by‑step solution go faster or slower.

If you go into Play mode and edit some of the squares before clicking Solve, the digits in those squares will be fixed - the algorithm will not change them. In Play mode, the Clear Solution button still works the same as before, but in other modes it leaves those digits you fixed in Play mode and clears only the digits the algorithm filled in.

Clicking the Solve in steps button runs the same algorithm but coded differently so that each step in its search for a solution is displayed. This can take hours unless you use the Show details button and increase the speed. You can vary the speed while it is running. You can also stop it (ie put it in Paused mode) and start it up again from the same point.

Go to the next page to find out about this algorithm, but first consider whether the algorithm as it is looks acceptable in this context and why. Looking at the execution speed, I see it solve one of these puzzles sometimes in 5ms or less, mostly in less than 50ms and only occasionally more - it hardly ever takes over 100ms. On my computer the solution appears without a perceptible delay. Watching the algorithm go step‑by‑step you can see that it looks excruciatingly inefficient. Does that matter? why?

I think that most people who have solved a few Suko puzzles find some rules to help them. For example:

• If one of the totals covers three of the four squares around one of the white circles, then the digit in the fourth square is the difference between that total and the one in the white circle.
• If four squares add up to 11 then their values must be 1, 2, 3, 5.

In creating a solver algorithm, it is tempting to start with rules like this, but that approach runs into the difficult problem of finding a complete set of rules that will always solve the puzzle. Such a set must exist, but is likely to be very large, or to contain complex rules, or both. An algorithm that contains a set of rules that is not complete in this sense will still need some general method to complete the solution after its rules have done their best. (If you have a set of rules that is reasonably small and simple and solves any Suko puzzle, then I am wrong and I would like to know about it.)

What I have done here, and the approach I recommend, is to start with that general method, which I have structured in such a way that rules can be added later. Every rule added will (we hope) make the algorithm run faster on average, though maybe not always, and will have cost extra effort in writing and testing the code.

An appropriate algorithm will represent a balance between the cost of adding those rules and the benefit in shorter run times. My contention is that a good coder will aim at the best balance for the context and not at the fastest practicable algorithm. The example in front of you needs to have an algorithm that runs fast enough not to try the patience of a reasonable user. The actual speed depends on the browser and the computer or device running it; let's assume, for example, that our users may have a browser-device combination that is at most five times slower than mine. On that hypothetical slow system, this algorithm will sometimes keep the user waiting half a second. That isn't much, but it is certainly a perceptible delay so perhaps we should try to do better.

This demonstration algorithm is coded in JavaScript. That is so the file containing it can be distributed as a single unit and displayed, with all its functions intact, by any modern web browser. A compiled version (in C or C++) would typically run around 10 times faster, but what computer would be running it and how many users might it be serving at the same time?

Go to the next page to read about how my basic algorithm works.

The general basic algorithm I have chosen is a search with backtracking. This sort of search is straightforward to code using a recursive routine. Humans are generally not very good at backtracking, and this is a case where modelling your code on the way people approach the problem is not the best idea.

Here is the recursive algorithm as a sequence of actions:

1. Apply any rules to the position

In the basic version the only rule is that when all the squares that contribute to a total have been filled in, they must add up to that total. If not, then the algorithm backtracks - ie exits reporting failure.

Because the algorithm removes a square that is filled in from sets (see Action #4 below), the rule is coded equivalently to check that every empty set has a zero total and removes such empty sets from its list.

2. Choose the square to try next; if no square is left then the algorithm has succeeded; exit reporting success.

In the basic version the square chosen is just the lowest numbered square with no digit assigned to it.

3. List in order the digit values to try for the chosen square

In the basic version this is just the remaining digits in numerical order.

4. Try each digit value in the list in turn in a new copy of the puzzle.

That is, make a copy of the current puzzle state and within that, assign that digit value to the square, remove that square from each set to which it belongs and reduce the total for that set by the value of the digit.

5. After that, call this routine recursively using the new puzzle state.

If that succeeds then the algorithm has finished, just exit reporting success. If the recursive call fails, then try the next digit in the list.

If all the digit values in the list have been tried, then exit reporting failure.

If the first call of this recursive algorithm exits reporting failure, then the algorithm cannot find a solution. Unless there is an error in the code that means that this puzzle has no solution.

Notice that when the recursive routine exits reporting failure, the copy of the puzzle state it was working with is automatically discarded in favour of the previous one and that does the backtracking.

Solving in steps is done by a transform of that algorithm where the recursion is implemented differently so that each JavaScript function call carries out just a single step and then exits so that the display can be updated.

I have provided five candidate improvements that you can now see by selecting Show details.

The first two are rules applied in action #1 "apply rules". The first is, I think self-explanatory, the second generalises the rule I mentioned on a previous page where one of the sets covers three of the four squares of another. It now applies whenever a set of squares with a known total is entirely contained within another. The larger set is reduced by subtracting the smaller. Note that action #1 applies its rules repeatedly until none of their conditions is met. Repeated application of these first two rules can result in seveal squares being filled in before the next search step.

The third improves action #2 "choose the square to try" by a heuristic - for each blank square it sums the squares of the reciprocals of the number of blank squares in all the sets to which it belongs and then selects the blank square with the highest total.

The fourth improves action #3 "list digit values to try" by excluding digit values that are too large or small for one or more of the sets that include the selected square. For example, a set with four members and total 11 cannot contain digits larger than 5; one with three members and a total of 21 cannot contain digits smaller than 4. (It is a little fancier than that because it takes account of which digits have already been assigned - if the digit 9 has already been used, then a set of three with a total of 21 must have no digit smaller than 6 rather than 4. It is not fancy enough to stop the search trying the digit value 4 in a set of four that sums to 11.)

The fifth adds the "diagonal" rules for action #1. I often find these useful when solving Suko puzzles with pencil and paper. In a solved puzzle, look at the totals in the top left and bottom right white circles. If you add those two totals, subtract the value in the central square and add the values in the top right and bottom left squares you will always get the answer 45 (obvious once you see it). If any two squares have been filled in along a diagonal, then its diagonal rule gives the third. Moreover, if only the central square has been filled in, the total of the two corner squares of that diagonal is known and a new set containing them can be added to the puzzle.

You can try these improvements individually or in combination by selecting the check boxes. You can change the selection during a step‑by‑step run. (This doesn't always appear to have an immediate effect because choices that have already been made are not reconsidered.)

Turning on any one of these improvements should make the search take fewer steps to find a solution (or to determine that there isn't one), but will make each step slower to execute. The third improvement - to pick an "influential" square is a heuristic so its effect is less predictable. The interaction between two or more of these improvements is also very variable.

It is also worth considering something simpler even than this search with no improvements - click for the next page.

On a modern computer, the basic recursive search provides a reasonable interactive Suko Solver and might be preferred over the improved versions because of its simplicity.

But you can make it even simpler. I am grateful to Jim Darby (@MathsWithJim) for providing an example of a brute force search. This simply runs through each possible allocation of the digits 1 to 9 to the 9 squares and checks whether it is a solution. You can try that here by showing the algorithm details and selecting the brute force radio button.

To a coder of a certain age the basic recursive search looks aggressively inefficient, and this brute force method looks ridiculously so. But modern computers are so fast that intuition fails. Give it a try.

Because it searches through the 9 factorial possible digit allocations and stops when it finds a solution, this brute force algorithm must take from 1 to 362,880 steps (each number equally likely) when there is a solution and always the maximum when there is not. But the code for this algorithm naturally takes the form of a tight loop with no recursion and no backtracking to an earlier state of the search. That makes the execution much simpler and faster. On my machine it gets through the steps at more than 30 times the rate of the simplest recursive search and that goers a long way towards compensating for its apparent inefficiency. On my machine it also gives the solution apparently instantaneously.

With no improvements I find the recursive search usually takes a few thousand steps, sometimes a few hundred and often between ten and twenty thousand. On the computer I am using the corresponding times range from a few milliseconds to less than a tenth of a second.

Turning on the first four improvements often reduces the search to fewer than ten steps and almost always to under 50. The elapsed time is reduced to a millisecond or less - too short for my simple measurement to give an accurate reading. Turning on just the first two improvements gives similar results, though hardly ever quite as good in any particular case.

Looking at the numbers of search steps one might reasonably conclude that the basic algorithm is grossly inefficient and that the "improvements" do indeed improve it. But if the context of the algorithm is with a computer like mine used for solving puzzles one at a time for a single user, then my main point is that this is conclusion is not that obvious. If I hide the details display then all the solutions appear instant and although the "improvements" make the algorithm faster, there is no practical difference. The long-respected KISS principle of IT design (Keep It Simple Stupid) implies that it is the basic algorithm that is better for this context.

In practice I think it reasonable to cater for this code to be used on devices or computers that run five times slower or even more. (I have run it on a much older Mac and that took around three times longer.) I think that including the first two "improvements" to the recursive algorithm is justified in order to keep it looking fast on a slower machine. The other improvements were fun to code but turn out to have been gilding the lily. In particular the "diagonal rules" that I find so helpful when solving these puzzles myself turn out to fail the test - they often give no significant improvement and seldom a worthwhile one and are the most complicated to code.

Your conclusion, of course, may be different. That's fair enough, particularly if you are looking at this on a slower machine - or even a much faster one.

Comparison with the brute force algorithm is instructive. That one is very straightforward and may be thought fast enough. If you do not allow the user to start playing the puzzle and fix some of the values, then it is even simpler (though not a lot faster). The JavaScript here includes an algorithm to generate all the permutations of the digits to be tried. In practice you might copy one that someone else has written or invoke one from a library. (Python has a suitable function in one of its libraries; in JavaScript I found other people's code that I could copy, but none that came with a good enough explanation of why it worked to make me want to take responsibility for using a copy. There are various published algorithms; I chose one devised by Edsger Dijkstra.)

If the primary purpose of this coding exercise had been to deliver a solver for use on a reasonable range of machines and browsers, then I ought to have started with a firm idea of how fast it needed to be and stopped "improving" it when that was achieved. (Of course, I wouldn't have needed to make the improvements switchable or, except for testing, to time the execution or count the steps.)

Watch out for Part 2 of this discussion of Appropriate Algorithms. In that I intend to discuss what I call "industrial strength" algorithms. These are not all the same, but making them appropriate requires significantly different and, I suspect, less frequently taught approaches. Sad to say, a lot of algorithms that you might reasonably expect would be required to be of "industrial strength" simply are not. I like to hope that this quality deficit may be reduced as more people become aware of it and as the industry matures after the youthful exuberance of the dot com boom - two decades and counting, how long can it take.

Greg Gomberg April 2021