build sudoku + sudoku solver from scratch
Lesson 2 — Phase 2 of the sudoku app. Build a `Validator` abstract base with `RowValidator`, `ColValidator`, `BoxValidator` concrete strategies. Own them in `std::vector<std::unique_ptr<Validator>>`. UIPanel turns conflicting cells RED. The strategy pattern lets DiagonalValidator / KillerValidator extend the engine without touching existing code.
Sudoku Lesson 2: A Validator Strategy Pattern in Modern C++
In Lesson 1 we drew a 9×9 grid and let the user type digits into cells. The board accepted anything. Type a 7 next to another 7 in the same row and the program shrugged. That is fine for a sketch, but a Sudoku app that does not enforce Sudoku rules is just a spreadsheet with thicker borders.
Phase 2 fixes that. By the end of this lesson, every cell that violates a rule will light up red the instant it is entered, and the validation engine will be open to extension. Adding a DiagonalValidator for Sudoku-X or a KillerValidator for Killer Sudoku will mean writing one new class, registering it in one line, and shipping. The existing row, column, and box logic stays untouched.
The pattern that buys us that property is the Strategy pattern, expressed in C++ with an abstract base class and a vector of std::unique_ptr<Validator>. We will build it step by step, then wire it into the UIPanel from Lesson 1.
Why not one big function
The temptation in Phase 2 is to write a single bool isValid(const Board& b, int row, int col) function. It works for classic Sudoku. It also works for the first 200 lines. Then you decide to support Sudoku-X.
A monolithic validator forces every variant to live inside one growing pile of branches. Each new ruleset adds another if (game_mode == ...) block, and each branch reads the entire board with subtly different semantics. After three rule variants the function is 400 lines, every variant has to be regression-tested every time anyone touches it, and the boundary between "row check" and "box check" has been erased by the refactor that interleaved them for performance.
Strategy gives you the opposite shape. Each rule lives in its own class with its own state, its own tests, and its own debug output. The engine asks each strategy in turn: does this cell violate your rule? If any says yes, the cell is invalid. Adding a rule is additive. Removing a rule (say, for an Easy difficulty that disables box validation) is a one-line change. The whole pattern is documented in detail by the canonical reference at refactoring.guru/design-patterns/strategy, and it maps cleanly onto C++ once you accept that the strategies need to be owned somewhere.
The trade-off is real. A vector of unique_ptr and three virtual calls per validation are slower than three inlined branches. On a 9×9 board the difference is in the low microseconds, which is invisible to a human player. On a 25×25 variant board with eight rule strategies it is still under a millisecond. If you are writing a solver that runs millions of validations per second, this lesson is the wrong tool. If you are writing an app that validates a cell after each keystroke, Strategy is the right tool by a wide margin.
Defining the abstract base
The Validator base class declares one job: given a board and the cell that just changed, return the set of cells that conflict. Returning a set rather than a boolean is deliberate. The UI does not just need to know that something is wrong. It needs to know which cells to color red so the player can see the conflict.
// validator.hpp
#pragma once
#include <unordered_set>
#include <utility>
#include "board.hpp"
struct CellHash {
std::size_t operator()(const std::pair<int, int>& p) const noexcept {
return std::hash<int>{}(p.first * 31 + p.second);
}
};
using CellSet = std::unordered_set<std::pair<int, int>, CellHash>;
class Validator {
public:
virtual ~Validator() = default;
virtual CellSet conflicts(const Board& board, int row, int col) const = 0;
virtual const char* name() const = 0;
};
Three things are worth noticing.
The destructor is virtual and defaulted. Without that, deleting a Validator* that points to a RowValidator is undefined behavior. The destructor is the one thing every polymorphic base class must declare explicitly, even when it does nothing. The unique_ptr documentation at en.cppreference.com/w/cpp/memory/unique_ptr covers the ownership semantics, but the destructor rule is older than smart pointers and applies to any virtual dispatch.
The conflicts method is const. A validator inspects the board and reports what is wrong. It never mutates state. Making this explicit at the interface level lets UIPanel keep its Board member as a const Board& while still calling validators on it.
There is no Validator(const Validator&) = delete. A validator is meant to be cheap, stateless, and shareable, but we do not need to forbid copies at the base level. Each concrete validator is a small object with no member data. The vector owns one of each.
Three concrete strategies
RowValidator reports every other cell in the same row that holds the same digit as (row, col). ColValidator does the same for the column. BoxValidator does the same for the 3×3 box that contains (row, col).
// row_validator.hpp
#pragma once
#include "validator.hpp"
class RowValidator final : public Validator {
public:
CellSet conflicts(const Board& board, int row, int col) const override {
CellSet out;
const int value = board.at(row, col);
if (value == 0) return out;
for (int c = 0; c < board.size(); ++c) {
if (c == col) continue;
if (board.at(row, c) == value) {
out.insert({row, c});
out.insert({row, col});
}
}
return out;
}
const char* name() const override { return "row"; }
};
// col_validator.hpp
#pragma once
#include "validator.hpp"
class ColValidator final : public Validator {
public:
CellSet conflicts(const Board& board, int row, int col) const override {
CellSet out;
const int value = board.at(row, col);
if (value == 0) return out;
for (int r = 0; r < board.size(); ++r) {
if (r == row) continue;
if (board.at(r, col) == value) {
out.insert({r, col});
out.insert({row, col});
}
}
return out;
}
const char* name() const override { return "col"; }
};
// box_validator.hpp
#pragma once
#include "validator.hpp"
class BoxValidator final : public Validator {
public:
CellSet conflicts(const Board& board, int row, int col) const override {
CellSet out;
const int value = board.at(row, col);
if (value == 0) return out;
const int boxRow = (row / 3) * 3;
const int boxCol = (col / 3) * 3;
for (int r = boxRow; r < boxRow + 3; ++r) {
for (int c = boxCol; c < boxCol + 3; ++c) {
if (r == row && c == col) continue;
if (board.at(r, c) == value) {
out.insert({r, c});
out.insert({row, col});
}
}
}
return out;
}
const char* name() const override { return "box"; }
};
Three points to call out.
Empty cells are not validated. A board with many empty cells is the normal in-progress state. If board.at(row, col) == 0 the validator returns an empty set immediately. This is a hot path. Sudoku-X plays with seven of nine cells empty for most of the game.
Each validator inserts both the offending cell and the current cell into the conflict set. The UI needs to color both. A 7 at (0, 0) and a 7 at (0, 5) are both wrong, and the player needs to see both to decide which one to erase.
final on each concrete class is a small win for the compiler. It tells the optimizer that no further override exists, which sometimes allows devirtualization of the call. It also tells the next maintainer that these are leaf classes by design. If you intend BoxValidator to be subclassed for a Jigsaw variant, drop the final and document the extension point.
Owning strategies in a vector of unique_ptr
The engine holds the strategies. It does not allocate them on every validation call; it holds them for the life of the app.
// validation_engine.hpp
#pragma once
#include <memory>
#include <vector>
#include "validator.hpp"
class ValidationEngine {
public:
void registerValidator(std::unique_ptr<Validator> v) {
validators_.push_back(std::move(v));
}
CellSet allConflicts(const Board& board, int row, int col) const {
CellSet out;
for (const auto& v : validators_) {
CellSet partial = v->conflicts(board, row, col);
out.insert(partial.begin(), partial.end());
}
return out;
}
private:
std::vector<std::unique_ptr<Validator>> validators_;
};
Why unique_ptr and not shared_ptr? The engine is the sole owner of each strategy. Nothing else needs a reference. unique_ptr is zero-overhead at runtime, expresses unique ownership at the type level, and prevents the accidental "I will keep a copy of this strategy in my UI layer" mistake that shared_ptr invites. The default deleter knows how to call the virtual destructor through the base pointer, which is why we made ~Validator virtual.
Why a vector and not a std::array? The number of strategies is decided at startup. We could template the engine on the count, but then registerValidator would be a compile-time operation and Sudoku-X mode could not register DiagonalValidator at runtime based on a settings flag. The vector pays one allocation at startup and zero allocations afterward.
Wiring three classic strategies takes three lines in main:
ValidationEngine engine;
engine.registerValidator(std::make_unique<RowValidator>());
engine.registerValidator(std::make_unique<ColValidator>());
engine.registerValidator(std::make_unique<BoxValidator>());
Wiring a Sudoku-X engine takes four:
ValidationEngine engine;
engine.registerValidator(std::make_unique<RowValidator>());
engine.registerValidator(std::make_unique<ColValidator>());
engine.registerValidator(std::make_unique<BoxValidator>());
engine.registerValidator(std::make_unique<DiagonalValidator>());
The classic engine code does not change. Lesson 2 graduates the app from "validates the rules we hardcoded" to "validates whatever rules were registered at startup". That is the Open/Closed Principle, made concrete in 40 lines of C++.
Wiring the UIPanel
UIPanel in Lesson 1 owned a Board and a std::set<std::pair<int, int>> highlighted_cells_. Phase 2 replaces the highlight set with a conflicts set, computed every time a cell changes.
// ui_panel.cpp (excerpt)
void UIPanel::onCellEdited(int row, int col, int newValue) {
board_.set(row, col, newValue);
conflicts_.clear();
for (int r = 0; r < board_.size(); ++r) {
for (int c = 0; c < board_.size(); ++c) {
CellSet partial = engine_.allConflicts(board_, r, c);
conflicts_.insert(partial.begin(), partial.end());
}
}
repaint();
}
void UIPanel::paintCell(QPainter& p, int row, int col) {
const bool red = conflicts_.contains({row, col});
p.setBrush(red ? QColor(255, 100, 100) : QColor(255, 255, 255));
p.drawRect(cellRect(row, col));
// draw the digit on top
}
The full-board scan is a deliberate choice for an 81-cell grid. A more incremental approach (only revalidate the row, column, and box of the edited cell) is a 5× speedup in the worst case, which on 81 cells is still imperceptible. The full scan is simpler, easier to test, and trivial to extend when a new strategy reads cells outside the edited row/column/box. Premature optimization here costs clarity.
When Strategy is the wrong choice
Strategy is overkill for a solver. A backtracking solver runs millions of validations per second and cannot afford a virtual call per check. Solvers tend to hardcode the three classic rules into a tight loop with bitmask state, which is roughly 50× faster than the polymorphic engine but ten times harder to extend. The solver and the UI engine can be different code paths in the same app. A reasonable split is: the UI engine uses Strategy and runs at human speed, the solver hardcodes the active ruleset at compile time using templates and runs at machine speed.
Strategy is also overkill for a single-rule game. If you are building Slitherlink, you have one validation rule. A single function is the right shape. Strategy pays for itself when you cross two rules and want extensibility for a third.
Extending the engine
This is the payoff. To add Sudoku-X diagonal validation, write one class:
class DiagonalValidator final : public Validator {
public:
CellSet conflicts(const Board& board, int row, int col) const override {
CellSet out;
const int value = board.at(row, col);
if (value == 0) return out;
const int n = board.size();
if (row == col) {
for (int i = 0; i < n; ++i) {
if (i != row && board.at(i, i) == value) {
out.insert({i, i});
out.insert({row, col});
}
}
}
if (row + col == n - 1) {
for (int i = 0; i < n; ++i) {
if (i != row && board.at(i, n - 1 - i) == value) {
out.insert({i, n - 1 - i});
out.insert({row, col});
}
}
}
return out;
}
const char* name() const override { return "diagonal"; }
};
Register it in main and the app validates diagonals. No other file changes. No regression risk to the row, column, and box logic. The Sudoku rules article at en.wikipedia.org/wiki/Sudoku covers the most common variants, and each of them maps to one new validator class with this pattern.
KillerValidator is more involved (it needs cage definitions and sums), but the shape is the same. It takes one new class file and one registration line. The engine, the UI, and the existing strategies do not change.
That is the lesson. Phase 2 of the Sudoku app gives the user red cells on rule violations, but the real lesson is structural. By the end of Lesson 2 the codebase has crossed the threshold from "code that works" to "code that extends". Lesson 3 will use the same engine to implement an undo history and a hint system without touching the validators at all.
References: