IT'S JUST NUMBERS ON A GRID, HOW HARD CAN IT BE
Last post I said I was going to build my own puzzle app because the existing ones drove me up the wall. Cocky. Confident. "It's just numbers on a grid, how hard can it be."
Reader, it tried to kill me.
Here's the bit I genuinely didn't think about: an app that gives you a daily Sudoku needs to make Sudokus. Loads of them. And not just any old grid — a proper Sudoku has to have exactly one right answer. One. If a puzzle has two possible solutions, it's broken, because now the player can't logic their way to the answer — they'd have to guess, and I'd built the whole app specifically so nobody ever has to guess.
So how do you check a puzzle only has one solution? You get the computer to solve it. Every possible way. If it finds more than one, bin it and try again. Simple enough. I wrote a solver. Wrote a generator that leaned on the solver. Hit go.
TEN MINUTES. FOR ONE PUZZLE.
And waited. And waited.
Ten minutes. To make one puzzle. I sat there watching a little spinner, slowly realising that at this rate, generating a week of dailies across all the puzzle types would take roughly until the heat death of the universe. I'd built a machine whose entire job was to make puzzles, and it made them at the pace of a man chiselling them into stone.
I'll be honest, that one stung. Because it worked — it just worked uselessly slowly, which is almost worse than broken. Broken you can see. Slow just quietly mocks you.
So I went digging, and the problem was me, obviously. My solver was doing the dumbest possible thing thousands of times a second. Every time it wanted to know "can a 7 go in this square?", it walked the entire row, the entire column, and the entire box, checking each number one by one, like counting sheep out loud. Then it did that again for the next square. And the next. Multiply that by a backtracking search that explores millions of dead ends, and... ten minutes.
THE FIX, IN PLAIN ENGLISH
The fix was three things, and I'll keep it plain English:
- Stop counting sheep. Instead of scanning a whole row to ask "is there a 7 here?", I gave each row, column and box a little bitmask — basically nine on/off switches. Now "can a 7 go here?" is one instant lookup instead of a lap around the grid. Same question, a thousand times faster.
- Solve the hard squares first. Instead of filling the grid left-to-right like a numpty, I taught it to always jump to the square with the fewest options left (the fancy name is MRV — "minimum remaining values," but it just means "do the forced moves first"). Tackle the tight corners early and the whole search tree collapses.
- Throw out the garbage at the door. A quick sanity check up front so an obviously-invalid grid gets rejected instantly instead of after a long sulk.
Oh — and while I was in there I found a test that had been quietly lying to me for weeks. It was supposed to check the solver rejected wrong answers, but it was looking for blanks in a grid that had none, so it was basically testing nothing. The original ten-minute timeout had been hiding the bug. Classic. You go in to fix one thing and find two more wearing a trenchcoat.
FIFTY-EIGHT MILLISECONDS
Then I hit go again.
58 milliseconds.
Ten minutes to fifty-eight thousandths of a second. I actually laughed out loud at the desk. Same puzzle, same correctness, same one-and-only-one-solution guarantee — it just went from "make a cup of tea and come back" to "faster than you can blink." That's the feeling. That's the whole reason anyone does this. You bang your head off a wall for days, and then one line of "oh, that's why," and suddenly the thing that was impossible is instant.
Every single puzzle GridJoy has ever handed you came out of that generator. Made fresh, checked to have one true answer, in less time than it took the old ad-app to load its first interstitial. I think about that every time. If you want one that came off that very production line, today's Sudoku is right here.
— the fed-up (but slightly faster) dev behind GridJoy 👻