Sudoku

The interesting part of a Sudoku program is not the grid. It is the question each blank square asks: given everything on the board, what could I legally be?

The answer comes from treating the board as twenty-seven overlapping regions — nine rows, nine columns and nine three-by-three cells. Every square belongs to exactly three of them. The values still available to a square are what you get by taking the union of what those three regions already contain, and subtracting it from one through nine.

That is the whole of it, and it is why the code is organised around a RCC type — Row, Column or Cell — rather than around the grid. A region knows its top-left and bottom-right corners and can report which values it already holds. The board knows which three regions any square belongs to. Everything else follows.

The hints shown under each empty square are that calculation, run live as you play. Turn them off if you would rather do the work yourself.

Watching it solve

Press Solve it and the board plays out a backtracking search: take the next empty square, try its first legal value, move on, and when a square runs out of options, unwind and try the next branch. The speed control runs from a couple of moves a second up to fast enough to finish before you have let go of the slider.

Anything you have entered yourself counts as fixed, exactly like the puzzle’s own numbers. So if you have put a value in the wrong place, the search exhausts and tells you — rather than quietly correcting you, which would be a worse answer to the question you asked.

Two ways to choose the next square

The naive search takes the next empty square in reading order. The smart solver takes the most constrained square instead: whichever has the fewest legal values left. That one change is the largest lever in Sudoku search, and the difference is not subtle.

Puzzle	Givens	Next empty square	Fewest candidates
Gentle	36	285	45
Original	26	45,749	55
Brutal	22	671,215	2,481

Reading it. The two right-hand columns are the two strategies, and both hold the same thing: how much work it took to solve that puzzle completely.

• Givens — how many numbers the puzzle starts with, printed on the board.
• Next empty square — steps the naive strategy took to finish, going square by square in reading order.
• Fewest candidates — steps the smart strategy took to finish the same puzzle, always choosing the most constrained square instead.

A step is one value going onto the board or coming back off it. Every number the solver tries is a step, and so is every number it takes back when the branch fails — which is why the counts run so far above the eighty-one squares a finished board has. Gentle’s 285 is not 285 choices available; it is 285 placements and retractions, to fill the forty-five squares that were blank.

So the Brutal row says one puzzle, solved two ways: 671,215 steps the first way and 2,481 the second. On the Original that is an eight-hundred-fold reduction, and on Brutal it is the difference between tractable and not.

There is a detail worth pausing on. Gentle has 45 blank squares and the smart solver takes 45 steps; the Original has 55 blanks and takes 55. Those numbers are equal because the solver never took a value back — it filled every blank once, correctly, and never backtracked at all. Brutal is the one that defeats it: 59 blanks and 2,481 steps, about forty steps for every blank square where the other two needed one.

It is tempting to read that table as “fewer givens, harder puzzle”. It is not that. An empty board — the fewest givens possible — takes 701 steps to brute force. That is a thousandth of Brutal’s total, from a board with twenty-two fewer numbers on it. With nothing already placed there is nothing to contradict, so the first path the search tries very nearly works.

What makes the Brutal puzzle brutal is where its twenty-two numbers are, not how few of them there are. They are placed so that a left-to-right search can commit a long way down a wrong branch before anything reveals the contradiction, and then has to unwind all of it. That is precisely the weakness the most-constrained-square rule removes: it goes looking for the contradiction first.

Ties are broken by my own idea: when several squares are equally constrained, prefer the one whose row — then column, then box, cycling between the three — has the fewest blanks left. Against simply taking the first tied square, that cut the Brutal puzzle from 8,013 steps to 2,481. Random tie-breaking does slightly better on average, 1,713 steps across two hundred seeds, but swings between 665 and 4,875. The rotating rule is deterministic, which matters for something you intend to watch twice.

Why the control sets a duration, not a speed

Because a rate cannot serve both. The smart solver finishes most of these puzzles in about fifty steps; at any rate slow enough to watch the naive one, the smart one is over before you have noticed it started.

So the control sets how long the whole search should take, and the solver paces itself to fit — a minimum of ten seconds, whichever strategy is running. What you compare is not how long you wait but how much thrashing you see: the same ten seconds either shows a tidy walk down the grid, or 671,215 placements and retractions going past in a blur.

Stop holds the search where it is, and Resume picks it up from the same step. The board shows wherever it had got to; every step keeps it legal, so it is a real position rather than a wreck. The values on it are guesses the search had not yet disproved, which is why they stay marked as its own rather than becoming yours. Reset abandons it and restores the puzzle.

Editing while a search is held abandons it too. A held search keeps its own copy of the position, and resuming into a board someone has changed underneath it would replay moves that no longer make sense.

Hitting a target duration means knowing the length of the search before starting it, so the solver runs once at full speed to count, then replays. Both strategies are deterministic, so the replay takes the same route. The counting pass costs about 250ms on the worst puzzle here.

The 2013 Java original did the naive version first; this is that algorithm rewritten, with somewhere to compare it to.

What is original and what is not

This began as a Java desktop application in 2013, became a React rewrite, and has now been lifted into this site. It is worth being exact about which parts are which.

The game logic is the original code, unchanged. The region model above — Board, RCC, Point and a handful of array helpers — is lifted straight across. It moved into an entirely different codebase and worked first time, which is the nicest thing you can say about a piece of code. I wrote twenty-five tests against it during the move and found no defects in it.

The React is not original, and that is deliberate. The version on GitHub was my first React application, and it shows: an async function used as a component, effects keyed on the whole props object, a class component half-migrated to hooks. I would write it very differently today — and in this port I did. What you are playing is a new presentation layer over the old logic.

I have not gone back and modernised the original, because the point of keeping it is that it is the original. It is still on GitHub as it was, first React app and all.

The conflict detection and the completion check are genuinely new. The original had neither, which made it a slightly unsatisfying game — you could fill the grid in wrongly and nothing would say so.