Chapter 16: Validation

Peers, candidates and honest conflict reporting

Chapter 15 built a board that will let you put a 5 next to another 5 without complaint. That was deliberate: storage and rules are different jobs, and a generator or a solver frequently needs to place a value it knows to be temporarily wrong. This chapter adds the rules layer that the board deliberately omits.

The rules of Sudoku fit in one sentence — no digit may repeat in a row, a column or a three-by-three box — and the naive implementation of that sentence is three nested loops that you write once and never look at again. It works. It is also somewhere between ten and a hundred times slower than it needs to be, which does not matter at all when a player types a digit and matters enormously when Chapter 19's solver evaluates a hundred thousand placements.

So this chapter does two things. It expresses the rules as a small set of questions you can ask about a board, and it precomputes the one piece of structure — the peer set — that turns all of those questions from loops into lookups. Along the way it makes an argument about how a conflict should be reported, which is a design question rather than a technical one and which most implementations get wrong.

What you will learn in this chapter

  • What a peer set is, why every cell has exactly twenty peers, and why that number is not twenty-four.
  • How to build the peer cache once at type initialisation, and why a static readonly field is the right place.
  • How legality, candidates and conflicts all reduce to one loop over peers.
  • Why a conflict must light up both cells, not just the one the player typed.
  • Why Candidates returns a List<int> here and what to use instead in a hot loop.
  • How to define "complete" so that a full board of wrong answers is not a win.
  • The caveats: allocation in Conflicts, the cost of HashSet, and where the naive version is still correct.

The code for this chapter

The demonstration is at github.com/nodoid/MonoGameBook/src/Chapter16. Place illegal digits on purpose and watch both ends of every conflict light up. The candidate list for the selected cell updates as you go, which is the same information a player works out in their head.

Chapter 16 running. Conflicting cells are highlighted at both ends; the panel shows the candidates still legal in the selected cell.
Chapter 16 running. Conflicting cells are highlighted at both ends; the panel shows the candidates still legal in the selected cell.

Peers

A cell's peers are the cells it shares a constraint with: the other eight in its row, the other eight in its column, and the other eight in its box.

Eight plus eight plus eight is twenty-four, and the correct answer is twenty. The box overlaps both the row and the column: two of the row's eight are also in the box, and two of the column's eight are also in the box. Four cells are counted twice, so twenty-four minus four is twenty.

That is exactly the sort of thing a HashSet gets right without being told:

private static int[][] BuildPeers()
{
    var peers = new int[SudokuBoard.CellCount][];

    for (int index = 0; index < SudokuBoard.CellCount; index++)
    {
        var set = new HashSet<int>();
        int row = SudokuBoard.RowOf(index);
        int column = SudokuBoard.ColumnOf(index);

        for (int step = 0; step < SudokuBoard.Size; step++)
        {
            set.Add(SudokuBoard.IndexOf(row, step));
            set.Add(SudokuBoard.IndexOf(step, column));
        }

        int boxRow = row / SudokuBoard.BoxSize * SudokuBoard.BoxSize;
        int boxColumn = column / SudokuBoard.BoxSize * SudokuBoard.BoxSize;

        for (int r = boxRow; r < boxRow + SudokuBoard.BoxSize; r++)
        for (int c = boxColumn; c < boxColumn + SudokuBoard.BoxSize; c++)
            set.Add(SudokuBoard.IndexOf(r, c));

        set.Remove(index);
        peers[index] = [.. set];
    }

    return peers;
}

Add every cell in the row, every cell in the column and every cell in the box — deliberately over-adding — then remove the cell itself. The set deduplicates the four overlaps and the one self-reference for you, and the result is materialised into a plain int[] for fast iteration.

boxRow and boxColumn are the top-left corner of the box, computed with the same / BoxSize * BoxSize idiom that Chapter 15's BoxOf used. Integer division discards the remainder and the multiply puts it back at a multiple of three: rows 3, 4 and 5 all give 3.

Caching, and where

private static readonly int[][] PeerCache = BuildPeers();

/// <summary>The twenty cells that share a row, column or box with this one.</summary>
public static ReadOnlySpan<int> Peers(int index) => PeerCache[index];

The class comment states the payoff plainly:

Peer sets are computed once and cached: every cell has exactly twenty peers, that never changes, and recomputing them inside a solver's inner loop is the difference between a solve that takes a millisecond and one that takes a second.

A static readonly field initialised from a method is run once, by the runtime, the first time the type is touched, with thread safety guaranteed by the CLR's type-initialisation rules. No lock, no null check, no Lazy<T>, no initialisation order to get wrong. For genuinely immutable derived data this is the simplest correct mechanism in C#, and it is under-used.

The cost is 81 arrays of 20 ints — about 8 KB — built in microseconds. The benefit is that every legality test in the next three chapters is a walk over a contiguous twenty-element array rather than three loops with divisions in them.

Peers returns ReadOnlySpan<int> rather than the array, so callers can iterate it with no allocation and cannot modify the cache. Handing out the int[] directly would let one careless caller corrupt the rules for the whole process.

One loop, three questions

With peers precomputed, the rules become almost trivial.

Legality

/// <summary>True if placing <paramref name="value"/> at <paramref name="index"/> breaks no rule.</summary>
public static bool IsLegal(SudokuBoard board, int index, int value)
{
    if (value == 0)
        return true;

    foreach (int peer in PeerCache[index])
        if (board[peer] == value)
            return false;

    return true;
}

Twenty comparisons, worst case, and it exits early. Compare that with the naive version — loop the row, loop the column, compute the box corner, loop three by three — which performs the same number of comparisons but recomputes the index arithmetic for every one of them, on every call.

The value == 0 case returns true, because clearing a cell is always legal. That is a small decision with a large effect on the call sites: the UI can call IsLegal unconditionally rather than special-casing erasure.

Note also what IsLegal does not do: it does not look at what is currently in index. It answers "would this be legal", not "is this legal", which is what a solver needs when it is considering a placement it has not made yet.

Candidates

/// <summary>The values that could still legally go in an empty cell.</summary>
public static List<int> Candidates(SudokuBoard board, int index)
{
    var candidates = new List<int>(SudokuBoard.Size);

    for (int value = 1; value <= SudokuBoard.Size; value++)
        if (IsLegal(board, index, value))
            candidates.Add(value);

    return candidates;
}

Nine legality tests. This is the information a human Sudoku player carries in their head — "this cell can only be a 4 or a 7" — and surfacing it is the difference between a puzzle app that is pleasant and one that is tedious. Chapter 18 turns it into pencil marks.

It is also the foundation of Chapter 19's solver: the cell with the fewest candidates is the best one to guess at, and a cell with zero candidates means the current partial solution is already dead.

The new List<int>(SudokuBoard.Size) pre-sizes the list so it never grows. That is a habit worth having, but it does not save the allocation of the list itself — see the caveats.

Reporting conflicts honestly

Here is the design decision this chapter cares most about:

/// <summary>Every cell currently in conflict with a peer.</summary>
public static HashSet<int> Conflicts(SudokuBoard board)
{
    var conflicts = new HashSet<int>();

    for (int index = 0; index < SudokuBoard.CellCount; index++)
    {
        int value = board[index];
        if (value == 0)
            continue;

        foreach (int peer in PeerCache[index])
        {
            if (board[peer] != value)
                continue;

            conflicts.Add(index);
            conflicts.Add(peer);
        }
    }

    return conflicts;
}

Look at the two Add calls. Both cells go into the set — the one being examined and the peer it clashes with.

The tempting alternative is to mark only the cell the player just typed. It is less code and it is what most implementations do, and it is worse for a specific reason: it tells the player that they are wrong without telling them why. A red 5 in the middle of a board is a puzzle in itself; two red 5s in the same column is an explanation.

It also matters for a subtler case. Suppose the player enters a 5 in a cell, and it is fine. Ten moves later they enter another 5 that conflicts with it. If only the new cell is highlighted, the player has to scan the row, column and box by hand to find the other one — which is the exact work the computer is supposed to be saving them. Highlighting both makes it a glance.

And there is a correctness argument too. Conflicts reports the state of the whole board, not the consequence of the last move. It is a pure function of the board, so it cannot get out of step with it, cannot be missed when a move is undone, and does not need to be maintained incrementally. Chapter 18's undo system relies on that.

Completeness

public static bool IsComplete(SudokuBoard board) =>
    board.FilledCount == SudokuBoard.CellCount && Conflicts(board).Count == 0;

Both halves are required, and it is worth saying why the obvious shortcut is wrong.

"The board is full" is not a win, because the board will happily hold eighty-one digits with dozens of repeats. "There are no conflicts" is not a win either, because an empty board has no conflicts at all. Only the conjunction means the puzzle is solved.

There is a third condition you might expect — "the answer matches the intended solution" — and it is deliberately absent. A well-formed Sudoku has exactly one solution, so a full board with no conflicts is that solution; checking against a stored answer would be redundant and would prevent the same function from validating a puzzle the player made up. Chapter 17's generator is what guarantees the uniqueness this relies on.

The naive version, and when it is fine

It would be dishonest to imply that the precomputed version is always necessary. Here is the straightforward implementation:

public static bool IsLegalNaive(SudokuBoard board, int index, int value)
{
    int row = SudokuBoard.RowOf(index);
    int column = SudokuBoard.ColumnOf(index);

    for (int step = 0; step < 9; step++)
    {
        if (step != column && board.At(row, step) == value) return false;
        if (step != row && board.At(step, column) == value) return false;
    }

    int boxRow = row / 3 * 3;
    int boxColumn = column / 3 * 3;

    for (int r = boxRow; r < boxRow + 3; r++)
    for (int c = boxColumn; c < boxColumn + 3; c++)
        if ((r != row || c != column) && board.At(r, c) == value)
            return false;

    return true;
}

For a player typing a digit — a handful of calls per second — this is perfectly good, and it has the advantage of needing no cache and no initialisation. If you were writing only Chapters 15, 16 and 18, you could stop here.

It becomes the wrong choice at Chapter 19, where the solver calls IsLegal in its innermost loop, potentially hundreds of thousands of times for a hard puzzle. At that volume the difference between "twenty array reads" and "twenty array reads plus about forty divisions, multiplications and comparisons for indexing" is the difference the class comment describes.

The general lesson is worth extracting: precompute the structure that does not change. A Sudoku's peer relationships are fixed by the rules of the game; they cannot vary with the board, the puzzle or the player. Anything with that property belongs in a cache built once.

Caveats

Conflicts allocates, twice

Conflicts allocates a HashSet<int> on every call, and IsComplete calls it. If the UI calls IsComplete every frame — which is the obvious thing to do — that is 60 hash sets a second, plus their internal buckets. It is not a disaster, but it is exactly the kind of steady background allocation Chapter 22 will teach you to find.

Two straightforward fixes: call it only when the board changes and cache the result, or replace the HashSet<int> with a bool[81] reused between calls. The latter is faster and allocation-free; the former is simpler and usually enough.

Candidates allocates a list per call

Drawing pencil marks for all eighty-one cells means eighty-one List<int> allocations per frame. For the demonstration, which shows candidates for one selected cell, it is nothing. For Chapter 18's notes feature, and certainly for Chapter 19's solver, use a bitmask instead:

public static int CandidateMask(SudokuBoard board, int index)
{
    int mask = 0;
    for (int value = 1; value <= 9; value++)
        if (IsLegal(board, index, value))
            mask |= 1 << value;
    return mask;
}

One int, no allocation, and System.Numerics.BitOperations.PopCount(mask) gives you the candidate count in one instruction — which is exactly what the solver wants when it is choosing which cell to try next.

The peer cache assumes a 9 × 9 board

BuildPeers runs at type initialisation using SudokuBoard's constants. If you ever make the board size dynamic, the cache has to become per-size, and the static-readonly simplicity goes with it.

IsLegal ignores the cell's own contents

IsLegal(board, index, 5) can return true when board[index] is already 5, because the cell is not its own peer. That is the correct behaviour for a solver and a surprising one for a UI, where "is this cell currently legal" needs IsLegal(board, index, board[index]) — which works, precisely because of that exclusion.

HashSet ordering is not stable

Conflicts returns a HashSet<int>, and its enumeration order is an implementation detail. Do not use it to decide which conflict to report first; if you need an order, sort it.

Building and running this chapter

The solution is src/Chapter16/Chapter16.sln in the book's repository at github.com/nodoid/MonoGameBook/src/Chapter16.

cd src/Chapter16
dotnet build Android/Chapter.Android.csproj
dotnet build iOS/Chapter.iOS.csproj

To deploy to a connected Android device or a running emulator:

dotnet build Android/Chapter.Android.csproj -t:Run

To run on the iOS Simulator:

dotnet build iOS/Chapter.iOS.csproj -p:RuntimeIdentifier=iossimulator-arm64
xcrun simctl install booted \
  iOS/bin/Debug/net10.0-ios/iossimulator-arm64/Chapter16.iOS.app
xcrun simctl launch booted com.monogamebook.chapter16

Try it yourself

  1. Place a digit that conflicts with a clue in another box. Both cells light up; find the conflict by eye and see how much slower that is.
  2. Print SudokuRules.Peers(40).Length and Peers(0).Length. Both are twenty — the centre cell and the corner cell have the same number of peers, which surprises most people.
  3. Change set.Remove(index) to nothing and rerun. Every cell now conflicts with itself, and the whole board is red.
  4. Add the CandidateMask method above and compare it with Candidates on a nearly-empty board. Confirm PopCount agrees with Count.
  5. Fill the board completely with 1s. FilledCount is 81 and IsComplete is false — which is why both halves of that test exist.

Summary

The rules of Sudoku are one sentence, and the efficient expression of that sentence is a peer set: the twenty cells sharing a row, column or box with a given cell. Twenty, not twenty-four, because the box overlaps the row and the column in four places — which a HashSet handles for you if you over-add and then remove the cell itself.

Because peer relationships are fixed by the rules and cannot vary with the board, they belong in a cache built once. A static readonly field initialised from a method gives you that with no lock, no null check and no initialisation order to get wrong, and returning ReadOnlySpan<int> lets callers iterate it without allocating or corrupting it.

With peers precomputed, all three questions collapse into one loop. IsLegal is twenty comparisons with an early exit and answers "would this be legal" rather than "is this legal". Candidates is nine calls to IsLegal, and is both the player's pencil marks and the solver's search heuristic. Conflicts is a pure function of the whole board that adds both ends of every clash to the set — because telling a player they are wrong without showing them what they clash with is making them do the work the computer exists to do.

IsComplete needs both a full board and an empty conflict set; either alone is satisfied by a board that is obviously not solved.

Chapter 17 turns the rules around. Instead of asking whether a board is legal, it asks how to produce one from nothing — fill a complete solution, then take clues away, carefully enough that exactly one answer remains.

← Chapter 15: The Board Model | Contents | Chapter 17: Puzzle Generation →