GODRICH
#css-animation#button#loader#transition#scroll#dashboard#ui#design-trends

Sudoku: 9 Scenes, Candidates to Unique Boards

· Godrich · 9 items · 23 min read

gameVanilla JSSCSSAutoplayGames & playHero section

Sudoku is not guessing. 01 strikes candidates one bit per cell, 03 backtracks from the fewest-candidate cell, and 04 counts solutions after every hole it digs

Sudoku Is Not a Game of Trying Digits in Blanks but a Calculation Where You Strike the Numbers Already Seen in the Row, Column and 3x3 Box and Solve From the Candidates That Remain: Building a Sudoku Game Starts by Choosing What Value Holds the Candidates

A Candidate Elimination Map Striking Bits per Cell01 sd-candidate-bitmask-map A Chain Where Filling a Single Candidate Unlocks the Next02 sd-single-fill-cascade A Backtrack Starting From the Fewest-Candidate Cell03 sd-fewest-first-backtrack Making a Board by Digging While Counting Solutions04 sd-unique-dig-count A Conflict Marker for Repeated Digits in a Line or Box05 sd-conflict-peer-mark A Hint That Shows Why: Which Line Struck the Candidates06 sd-hint-reason-trace A Keypad Whose Rings Shrink With Digits Left07 sd-digit-left-ring A Completion Wave Spreading With a Delay per Cell08 sd-solved-wave-flourish A Difficulty Score Bar Measured by Techniques Needed09 sd-difficulty-score-bar

Auto-plays · click a tile to jump to its section · all nine in one zip

The nine scenes run on one board model, and each scene reads a different value off it. Candidates are not stored per cell but computed from the board array on demand, so the moment a digit changes, the candidates change with it. If you want a sudoku solver you can read in one sitting, this is its shape: an 81-number array, one candidate rule and a canvas.

A candidate is one nine-bit number

The board is an 81-number array where 0 is a blank, and digit d is written as bit d minus 1. The full set ALL is 511, so a candidate set is a single integer and popcount, which counts the lit bits, gives how many candidates remain.

The same board comes back without random numbers

Boards are dug out of a finished grid shuffled by an integer hash hash2(a, b), so one seed gives one board. Time is one scene clock divided into fixed 1/60 second steps.

    const ALL = 511;
    function bit(d) { return 1 << (d - 1); }
    function popcount(m) {
        let c = 0;
        let v = m;
        while (v) {
            v &= v - 1;
            c += 1;
        }
        return c;
    }

Sudoku in JavaScript: 9 Scenes — a Candidate Elimination Map, a Chain of Single-Candidate Fills, a Fewest-First Backtrack, a Dig That Keeps One Solution, a Duplicate Marker, a Hint That Shows Its Reason, a Remaining Count per Digit, a Completion Wave and a Difficulty Score

Area, frames and intensity from the latest render

The table lists each scene's cumulative area, its moving frames out of 23 and its mean intensity from the latest render.

Scene Area Moving frames Intensity
01 Candidate map 21.3% 23/23 46.1
02 Single-candidate chain 24.6% 23/23 40.3
03 Fewest-first backtrack 12.4% 21/23 96.7
04 Dig for one solution 20.9% 21/23 29.7
05 Duplicate marker 17.1% 14/23 42.8
06 Hint with reasons 8.2% 9/23 58.9
07 Remaining-count rings 20.8% 18/23 53.9
08 Completion wave 31.9% 17/23 92.5
09 Difficulty score 20.4% 21/23 123.8

Scene 08 covers the widest area at 31.9% and 06 the narrowest at 8.2%. Moving frames reach 23 of 23 in 01 and 02 and fall to 9 in 06, and mean intensity is highest in 09 at 123.8 and lowest in 04 at 29.7.

01A Candidate Elimination Map Striking Bits per Cell

Each cell holds 1 to 9 as one nine-bit value, and the bits of digits already placed in its row, column and box are ORed together and struck from it, which suits filling and clearing pencil notes automatically. A cell is mint with one candidate and takes the background shade with seven or more.

A Candidate Elimination Map Striking Bits per Cell
Open in a new tab

01 · A Candidate Elimination Map Striking Bits per Cell — Measured area 21.349% · moving frames 23/23Original by GODRICH · SCSS and React ship in the zip · See the password

candMaskPEERSpopcount
    // OR of the bits of digits already used by the other cells in the kind unit that holds cell i
    function usedMask(b, i, kind) {
        const u = UNITS[unitIndex(kind, i)];
        let m = 0;
        for (let k = 0; k < 9; k += 1) {
            if (u[k] !== i && b[u[k]] !== 0) {
                m |= bit(b[u[k]]);
            }
        }
        return m;
    }
    // candidates = all nine bits minus the bits used by the three units; a filled cell has 0
    function candMask(b, i) {
        if (b[i] !== 0) {
            return 0;
        }
        return ALL & ~(usedMask(b, i, 0) | usedMask(b, i, 1) | usedMask(b, i, 2));
    }

A node run of these functions matched all 188 blank cells on four boards against candidates counted as sets with no mismatch, and on the first board placing the 8 cells the demo fills takes the blanks from 47 to 39 and the average candidates per blank from 3.15 to 2.28.

02A Chain Where Filling a Single Candidate Unlocks the Next

A cell left with exactly one candidate is filled and the candidates are counted again, which suits pointing a stuck player to the next cell.

A Chain Where Filling a Single Candidate Unlocks the Next
Open in a new tab

02 · A Chain Where Filling a Single Candidate Unlocks the Next — Measured area 24.627% · moving frames 23/23Original by GODRICH · SCSS and React ship in the zip · See the password

singlesFillorderisStuck
    function singlesFill(start) {
        const b = start.slice();
        const order = [];
        const digits = [];
        const avail = [];
        for (;;) {
            let first = -1;
            let n = 0;
            for (let i = 0; i < 81; i += 1) {
                if (b[i] === 0 && popcount(candMask(b, i)) === 1) {
                    if (first < 0) {
                        first = i;
                    }
                    n += 1;
                }
            }
            if (first < 0) {
                break;
            }
            const d = lowDigit(candMask(b, first));
            b[first] = d;
            order.push(first);
            digits.push(d);
            avail.push(n);
        }

On four boards with 32 clues the chain filled 27, 20, 19 and 17 cells, all equal to the answer, yet every board stopped short of a full solve and the fewest-candidate cell gets a pulsing rose ring once the chain stalls.

03A Backtrack Starting From the Fewest-Candidate Cell

When single candidates run out, the search commits a digit in the cell with the fewest candidates and backs out when stuck, which suits solving a hard board whose route is not visible. Committed digits are counted and cut off at NODE_CAP 400.

A Backtrack Starting From the Fewest-Candidate Cell
Open in a new tab

03 · A Backtrack Starting From the Fewest-Candidate Cell — Measured area 12.417% · moving frames 21/23Original by GODRICH · SCSS and React ship in the zip · See the password

NODE_CAPsearchdead
            let mm = bm;
            while (mm) {
                const lo = mm & -mm;
                mm ^= lo;
                const d = 32 - Math.clz32(lo);
                r.nodes += 1;
                if (r.nodes > cap) {
                    r.capHit = true;
                    return;
                }
                b[best] = d;
                rm[rowOf(best)] |= lo;
                cm[colOf(best)] |= lo;
                xm[boxOf(best)] |= lo;
                if (wantTrace) {
                    r.trace.push((best << 4) | d);
                }
                rec();

A node run on four boards with 24 to 25 clues solved them in 150, 167, 173 and 244 nodes by fewest-first order, while the plain blank order hit the 20,000 cap on all four and stopped at 20,001 nodes.

04Making a Board by Digging While Counting Solutions

The dig empties one cell at a time from a finished board and counts solutions only up to 2, keeping the blank on one and putting the digit back on two, which suits producing new boards that have one solution.

Making a Board by Digging While Counting Solutions
Open in a new tab

04 · Making a Board by Digging While Counting Solutions — Measured area 20.873% · moving frames 21/23Original by GODRICH · SCSS and React ship in the zip · See the password

CLUESdigBoardsearch
    function digBoard(sol, seed, target, singlesOnly) {
        const puz = sol.slice();
        const order = perm(81, seed * 31 + 5);
        const steps = [];
        let clues = 81;
        for (let k = 0; k < 81; k += 1) {
            if (clues <= target) {
                break;
            }
            const c = order[k];
            const d = puz[c];
            puz[c] = 0;
            const s = search(puz, 2, 6000, false, false);
            const cnt = s.capHit ? 2 : Math.min(2, s.count);
            const ok = cnt === 1 && (!singlesOnly || singlesFill(puz).solved);
            steps.push({ cell: c, cnt: cnt, ok: ok, nodes: s.nodes });
            if (ok) {
                clues -= 1;
            }
            else {
                puz[c] = d;
            }
        }
        return { puz: puz, steps: steps, clues: clues };
    }

With CLUES 36 the four boards took 47, 46, 45 and 45 tries and restored 2, 1, 0 and 0 cells, and all four ended with 36 clues and a solution count of 1.

05A Conflict Marker for Repeated Digits in a Line or Box

When a placed digit already exists in its row, column or box, the two cells are tinted rose and joined by a line, which points out a wrong entry right away. Only rule breaks are marked, and the 03 search decides separately whether a board is unsolvable.

A Conflict Marker for Repeated Digits in a Line or Box
Open in a new tab

05 · A Conflict Marker for Repeated Digits in a Line or Box — Measured area 17.101% · moving frames 14/23Original by GODRICH · SCSS and React ship in the zip · See the password

conflictssharedKindtintUnit
    // pairs of placed digits that repeat: [cell, cell, unit kind]
    function conflicts(b) {
        const out = [];
        for (let i = 0; i < 81; i += 1) {
            if (b[i] === 0) {
                continue;
            }
            for (let k = 0; k < 20; k += 1) {
                const p = PEERS[i][k];
                if (p > i && b[p] === b[i]) {
                    out.push([i, p, sharedKind(i, p)]);
                }
            }
        }
        return out;
    }

On all three boards 4 of the 8 entries break the rules, and a wrong entry is erased 0.42 s later.

06A Hint That Shows Why: Which Line Struck the Candidates

A hint gives not just the answer digit but lights the row, column and box that struck each candidate in turn, which suits a teaching view that explains why a digit goes there.

A Hint That Shows Why: Which Line Struck the Candidates
Open in a new tab

06 · A Hint That Shows Why: Which Line Struck the Candidates — Measured area 8.234% · moving frames 9/23Original by GODRICH · SCSS and React ship in the zip · See the password

computeHintwhysleftMask
    function computeHint(c) {
        hintCell = c;
        whys = [];
        if (g[c] !== 0) {
            leftMask = 0;
            hintCell = -1;
            return;
        }
        const cand = candMask(g, c);
        leftMask = cand;
        let n = 0;
        for (let d = 1; d <= 9; d += 1) {
            if ((cand & bit(d)) !== 0) {
                continue;
            }
            const srcs = [-1, -1, -1];
            for (let kind = 0; kind < 3; kind += 1) {
                const u = UNITS[unitIndex(kind, c)];
                for (let k = 0; k < 9; k += 1) {
                    if (u[k] !== c && g[u[k]] === d) {
                        srcs[kind] = u[k];
                    }
                }
            }
            let pick = -1;

On four boards the target cells are 59, 41, 20 and 48 with 8 struck digits each, all three unit kinds appear among the reasons, and one bit is left at the end so that digit shows in the cell.

07A Keypad Whose Rings Shrink With Digits Left

Each key 1 to 9 draws the count not yet placed as a ring arc, and the key dims once all nine are in, which suits an input panel that shows how many of each digit remain.

A Keypad Whose Rings Shrink With Digits Left
Open in a new tab

07 · A Keypad Whose Rings Shrink With Digits Left — Measured area 20.815% · moving frames 18/23Original by GODRICH · SCSS and React ship in the zip · See the password

leftOfselDigitARC_RATE
    function leftOf(d) {
        let c = 0;
        for (let i = 0; i < 81; i += 1) {
            if (g[i] === d) {
                c += 1;
            }
        }
        return 9 - c;
    }

The arc follows its target at ARC_RATE 9 instead of dropping in one jump, and the first board starts with [1,4,2,5,4,7,5,5,4] left, a sum of 37. The demo fills the blanks of the three digits with the fewest left, placing 7, 9 and 7 cells on the three boards.

08A Completion Wave Spreading With a Delay per Cell

A full board with no conflicts sends a wave from the last cell, and cells farther by city-block distance light later by WAVE_MS times the distance, a finishing screen that rewards a solve.

A Completion Wave Spreading With a Delay per Cell
Open in a new tab

08 · A Completion Wave Spreading With a Delay per Cell — Measured area 31.885% · moving frames 17/23Original by GODRICH · SCSS and React ship in the zip · See the password

WAVE_MSdistOfwaveP
    function waveP(i) {
        if (solvedT < 0) {
            return -1;
        }
        return (sceneT - solvedT - distOf(i) * WAVE_MS / 1000) / PULSE_S;
    }

On three boards the farthest cell is 12, 12 and 11 away, a delay of 480, 480 and 440 ms at WAVE_MS 40. One pulse lasts 0.55 s, so with the last cell's delay the wave ends in about 1.03 s.

09A Difficulty Score Bar Measured by Techniques Needed

A board solved by single candidates alone scores easy, one that needs a trial scores medium and one with three or more dead ends scores hard, which labels each board with a difficulty.

A Difficulty Score Bar Measured by Techniques Needed
Open in a new tab

09 · A Difficulty Score Bar Measured by Techniques Needed — Measured area 20.439% · moving frames 21/23Original by GODRICH · SCSS and React ship in the zip · See the password

rateOfbranchclueScore
    // score: 0 to 39 if single candidates alone solve it, 40 to 59 if a trial is needed, 60 or more with three or more backtrack dead ends
    function rateOf(puz, solution) {
        const chain = singlesFill(puz);
        const clues = filledOf(puz);
        let score = 0;
        let dead = 0;
        let branch = 0;
        if (chain.solved) {
            score = Math.min(39, 8 + Math.floor((81 - clues) / 1.6));
        }
        else {
            const s = search(puz, 1, 3000, false, false);
            dead = s.dead;
            branch = s.branch;
            score = dead <= 2 ? 40 + Math.min(19, branch * 2 + dead * 4) : 60 + Math.min(39, dead);
        }
        // score from the clue count alone: fewer clues is rated harder
        const clueScore = clamp(Math.round((46 - clues) * 5), 0, 99);
        return { puz: puz, sol: solution, clues: clues, chain: chain, level: levelOf(score), score: score, clueScore: clueScore, clueLevel: levelOf(clueScore), dead: dead, branch: branch };
    }

The four boards with 28, 40, 32 and 24 clues scored 39, 33, 46 and 85 by technique against 90, 30, 70 and 99 by clue count alone. Board 1 reads hard by clues but easy by technique and board 3 hard by clues but medium by technique, so the two verdicts disagree.

When You Put the Sudoku Rules in Code, How Many Values Decide the Candidates of One Cell?

The candidates of one cell come from three units and nothing else: the digits used in its row, its column and its box. Units number 27 in all, 9 rows, 9 columns and 9 boxes, and each cell has 20 peers.

The board array and 27 units are all there is

Value Meaning Changed by
g Board state, 0 for a blank putDigit
PEERS[i] The 20 peers of cell i Striking and conflict checks
candMask Candidate bits of a cell 01, 02, 03 and 06

One board feeds several calculations

On the same board array singlesFill computes the chain, search the backtrack and conflicts the duplicates. Since one rule makes the candidates for all nine scenes, the board of any scene can be checked by the functions of another.

Keep the Board as an 81-Number Array, Gather the Digits Used in Row, Column and Box to Strike Candidates, Fill the Cell With One Left and Strike Again: the Order in Which a Sudoku Gets Solved

The array changes first and the drawing follows

When a digit comes in, the board array changes first and candidates and conflicts are recomputed from it. Colors and bars only read computed values, so entering again in the middle of a tween keeps the board in step.

Trying a digit when stuck

Once single candidates run dry, the search commits a digit in the fewest-candidate cell and continues until a cell with zero candidates appears, then undoes one step. Committed digits are counted as nodes and dead ends as dead, so each scene reads how hard its board was as a number.

Putting It on a Real Screen Like a Sudoku Site: Building Without a Library, Touch and Keyboard Input and When the Board Is Generated

Building without a library

The nine scenes use no library, WebGL or CDN, and each keeps its calculation and its demo in one source file. A page that serves sudoku online only needs that file and a place to host it.

Touch and keyboard input

The stage box has role="application" and tabindex 0 so it takes focus, and arrow keys move the cell, 1 to 9 enter a digit, Delete, Backspace and 0 clear it and H asks for a hint. Pointers go through pointerdown, pointermove, pointerup, pointercancel and setPointerCapture, and touch-action: none on the stage stops the page from scrolling during a press.

When the board is generated

It is safer to dig holes the 04 way and confirm a solution count of 1 before a player receives the board. If generating is heavy, set a cap or move the work into a web worker.

How this differs from the neighbors

The sliding puzzle post tells solvable boards apart by parity and searches by city-block distance, while this post strikes candidate sets per cell and counts whether a solution is unique. For flood-style spreading across neighboring grid cells, the minesweeper post uses the same kind of grid.

Where a Sudoku Breaks: a Trap of Boards With More Than One Solution, a Backtrack so Deep That the Screen Freezes and Pencil Notes Left Stale After an Entry

A board arrives with more than one solution

Dig holes in any cells you like and you can end up with a board of two or more solutions, where no digit can be called the answer. The 04 dig counts solutions up to 2 at each hole and restores the digit on two, which is why all four boards ended with a count of 1 at CLUES 36 and at 26.

A backtrack goes so deep that the screen freezes

The plain blank order hit the 20,000-node cap on all four boards with 24 to 25 clues, while fewest-first solved them in 150 to 244 nodes. A harder board can still arrive, so keep a cap like the NODE_CAP 400 of 03, and when it is reached, report no solution found and stop.

Pencil notes stay stale after an entry

If pencil notes are stored on their own, struck candidates linger after a digit is placed. Computing candidates from the board array with candMask on demand, as 01 does, keeps the row, column and box candidates right straight after an entry.

All nine scenes ship as source in the zip card below, and you open that archive with the password 6r5snyxx.

Change the Clue Count, the Backtrack Cap and the Wave Speed and How Much Does the Feel Shift? CLUES, NODE_CAP and WAVE_MS Compared

Name Changed value Feel
Fewer clues 04 CLUES 36 → 26 Cutting CLUES from 36 to 26 on the seed 4 board raises the blanks from 45 to 55, drops the cells filled by single candidates from 45 to 4 and lifts the search nodes from 45 to 653, while raising it makes the board easier.
A lower backtrack cap 03 NODE_CAP 400 → 60 Lowering NODE_CAP from 400 to 60 makes all four boards (needing 150, 167, 173 and 244 nodes) hit the cap and stop without a solution while the screen keeps running, and raising it finds the solution but stretches the scene.
A slower wave 08 WAVE_MS 40 → 120 Stretching WAVE_MS from 40 to 120 widens the delay of the farthest cell (distance 12) from 480 ms to 1,440 ms so the wave reads clearly, while shortening it looks like one block lighting at once.

These figures are node counts and delays calculated from the source functions, not render measurements. The three values sit at different stages: CLUES sets the difficulty of the board, NODE_CAP the point where the search stops and WAVE_MS only the screen after completion, so change one at a time to see which one moved the feel.

One Static Board Under Reduced Motion: Accessibility Through a Sentence for the Scene and the Current Count of Filled Cells

Arrow keys and digit keys solve it by hand

Touch the stage and the timetable stops while the calculation carries on. N starts a new board, R restarts, and Enter, Space and P pause.

Reading out only after a touch or a mode change

The on-screen status line is aria-live="off", so nothing is read during the demo, and a hidden role="status" paragraph gets the scene name and the count of filled cells as a sentence only right after a touch and when the mode changes.

Reduced motion and a hidden tab

With prefers-reduced-motion on, no loop runs and one board is drawn at the rest time of the timetable, without digit tweens. A hidden tab stops the loop, and coming back drops the accumulated time and resumes. The setting and its behavior are described in the prefers-reduced-motion documentation.

    // stop when the tab hides, and on return reset the clock and start
    document.addEventListener('visibilitychange', function () {
        if (document.hidden) {
            stopLoop();
        }
        else if (!paused && !still) {
            startLoop();
        }
    }, { signal: off.signal });
    // when the setting changes: on shows one board, off moves again
    reduceQuery.addEventListener('change', function () {
        still = reduceQuery.matches;
        if (still) {
            showRest();
        }
        else {
            lap = 0;
            play();
        }
    }, { signal: off.signal });

Sudoku FAQ: Sudoku Strategies for Harder Boards, What Makes a Board Have One Solution and What You Need Before Putting It on the Web

Where do harder strategies start in code

Sudoku strategies begin with the single-candidate fill of 02, and when that stalls, 03 picks the fewest-candidate cell and tries a digit, which is the next step this post covers. Reading the strike reasons in 06 alongside shows which line removed a candidate.

What makes a board have one solution

The solution count measured after digging must be 1. The 04 dig counts only up to 2 and restores the digit on two, which keeps that condition.

What does it take to put it on the web

One HTML file runs with no server. The canvas scale uses devicePixelRatio capped at 2 and nothing calls an outside font or service, so you only need a place to host the file.

Source documentation: MDN Pointer events.

Enter the archive password

The password is inside this article. You will find it as you read.