Lesson 2 — Phase 2: Strategy Pattern with Validator

Commit: 2c97016 (partial). Phase 2 of the sudoku app — adding validation.

1. Goals

After this lesson you will have:

• An abstract Validator class with a virtual destructor and 2 pure virtual methods (name, conflicts)
• 3 concrete validators: RowValidator, ColValidator, BoxValidator — detecting duplicates within their respective groups
• App containing std::vector<std::unique_ptr<Validator>> — polymorphic ownership
• A UIPanel that displays cells in red when there is a conflict (both fixed and editable cells)
• An extensible architecture: adding a new validator (e.g. DiagonalValidator for X-Sudoku) does not require modifying existing code

2. File tree

apps/sudoku/src/
├── app.h                       ← MODIFY: add vector<unique_ptr<Validator>> field
├── app.cpp                     ← MODIFY: push 3 validators in init()
├── ui_panel.h                  ← MODIFY: draw() signature receives validators
├── ui_panel.cpp                ← MODIFY: cell_has_conflict helper, render red
├── validator.h                 ← NEW: abstract + 3 derived classes
├── validator.cpp               ← NEW: implement conflicts() for each class
├── grid.h, grid.cpp            (existing, no change)
└── main.cpp                    (existing, no change)

3. Content to learn

1. Abstract class — pure virtual method (= 0)
2. Virtual destructor — why it is mandatory for a polymorphic base class
3. override keyword — compiler-checked override
4. = default for destructor — trivial dtor, clear intent
5. Inheritance — class Derived : public Base
6. std::unique_ptr<Base> + polymorphism — single ownership with virtual dispatch
7. std::make_unique<Derived>() — exception-safe factory
8. Container of polymorphic types — vector<unique_ptr<Base>>
9. Strategy pattern — interchangeable family of algorithms
10. static free function — internal linkage helper

4. How to do it

Step 1 — Validator abstract base (validator.h)

File: apps/sudoku/src/validator.h

#pragma once
#include "grid.h"   // Phase 2; in Phase 3.0 change to "solver/grid.h"

class Validator {
public:
    virtual ~Validator()                                                = default;
    virtual const char* name() const                                    = 0;
    virtual bool        conflicts(const Grid& grid, int r, int c) const = 0;
};

class RowValidator : public Validator {
public:
    const char* name() const override;
    bool        conflicts(const Grid& grid, int r, int c) const override;
};

class ColValidator : public Validator {
public:
    const char* name() const override;
    bool        conflicts(const Grid& grid, int r, int c) const override;
};

class BoxValidator : public Validator {
public:
    const char* name() const override;
    bool        conflicts(const Grid& grid, int r, int c) const override;
};

Explanation:

• virtual ~Validator() = default;: a virtual destructor allows deletion through a base pointer to dispatch the correct derived destructor. = default requests that the compiler synthesize one (trivial empty body).
• = 0 pure specifier: the method has no body in the base, and derived classes are required to override it. A class with a pure virtual is abstract — it cannot be instantiated directly.
• override after the signature: the compiler checks the intent. If the signature does not match the base method, an error is emitted. This prevents typos (nme() instead of name()).
• const Grid& grid: pass-by-reference avoids copying 324 bytes; const because the validator only reads.
• const at the end of the method: the method does not mutate *this. This allows it to be called through a const Validator&.

Step 2 — Implement the 3 validators (validator.cpp)

File: apps/sudoku/src/validator.cpp

#include "validator.h"

const char* RowValidator::name() const { return "Row"; }

bool RowValidator::conflicts(const Grid& grid, int r, int c) const {
    int v = grid[r][c];
    if (v == 0) return false;          // empty cell never conflicts

    for (int cc = 0; cc < N; ++cc) {
        if (cc != c && grid[r][cc] == v) {
            return true;
        }
    }
    return false;
}

const char* ColValidator::name() const { return "Column"; }

bool ColValidator::conflicts(const Grid& grid, int r, int c) const {
    int v = grid[r][c];
    if (v == 0) return false;

    for (int rr = 0; rr < N; ++rr) {
        if (rr != r && grid[rr][c] == v) {
            return true;
        }
    }
    return false;
}

const char* BoxValidator::name() const { return "Box"; }

bool BoxValidator::conflicts(const Grid& grid, int r, int c) const {
    int v = grid[r][c];
    if (v == 0) return false;

    int boxRow = r / 3;
    int boxCol = c / 3;

    for (int rr = boxRow * 3; rr < boxRow * 3 + 3; ++rr) {
        for (int cc = boxCol * 3; cc < boxCol * 3 + 3; ++cc) {
            if ((rr != r || cc != c) && grid[rr][cc] == v) {
                return true;
            }
        }
    }
    return false;
}

Algorithm explanation:

Each validator answers the question: "Does the value at (r, c) have a duplicate in its row/col/box?"

• Check v == 0 first: an empty cell causes no conflict
• Loop over the group (9 cells in the row/col/box)
• Skip the current cell (cc != c, or rr != r, or (rr != r || cc != c))
• Match the value: find another cell with the same value → conflict

BoxValidator: computing the 3x3 bounding box:

int boxRow = r / 3;        // 0, 1, or 2
int boxCol = c / 3;
// box span: rows [boxRow*3, boxRow*3+3), cols [boxCol*3, boxCol*3+3)

Example: r = 4, c = 7 → boxRow = 1, boxCol = 2 → loop rr ∈ [3,6), cc ∈ [6,9).

Step 3 — App owns the validators (app.h)

File: apps/sudoku/src/app.h (modify)

#pragma once

#include "grid.h"
#include "ui_panel.h"
#include "validator.h"        // ← ADD
#include <memory>             // ← ADD
#include <vector>             // ← ADD

struct GLFWwindow;

class App {
public:
    App();
    ~App();
    App(const App&)            = delete;
    App& operator=(const App&) = delete;
    int run();

private:
    bool init();
    bool shutdown();
    void draw_frame();

    GLFWwindow*                             window_ = nullptr;
    Grid                                    grid_;
    FixedMap                                fixed_;
    UIPanel                                 panel_;
    std::vector<std::unique_ptr<Validator>> validators_;   // ← ADD
};

Explanation of the member type:

std::vector<std::unique_ptr<Validator>> — a vector containing smart pointers to the base.

Comparison of options:

| Type | Problem | |---|---| | std::vector<Validator> | Compile error: Validator is abstract. Even if it were possible, object slicing — only the Validator part is stored, the derived data is lost | | std::vector<Validator*> | Compiles. But raw pointers — ownership is unclear, leaks are easy | | std::vector<std::unique_ptr<Validator>> | ✓ Owning smart pointer, polymorphism through the pointer, RAII cleanup |

Step 4 — Push the validators in init (app.cpp)

File: apps/sudoku/src/app.cpp — inside App::init(), after fixed_ = make_fixed_map(grid_);:

validators_.push_back(std::make_unique<RowValidator>());
validators_.push_back(std::make_unique<ColValidator>());
validators_.push_back(std::make_unique<BoxValidator>());

Explanation:

• std::make_unique<T>() — single allocation, exception-safe. Always prefer it over std::unique_ptr<T>(new T()).
• The vector's push_back move-constructs the unique_ptr in — no copying (unique_ptr is non-copyable).

Step 5 — UIPanel signature (ui_panel.h)

File: apps/sudoku/src/ui_panel.h (modify)

#pragma once

#include "grid.h"
#include "validator.h"          // ← ADD
#include <memory>               // ← ADD
#include <vector>               // ← ADD

class UIPanel {
public:
    void draw(Grid& grid, const FixedMap& fixed,
              const std::vector<std::unique_ptr<Validator>>& validators);
};

Step 6 — UIPanel render with conflict (ui_panel.cpp)

File: apps/sudoku/src/ui_panel.cpp (modify)

#include "ui_panel.h"
#include "imgui.h"

static bool cell_has_conflict(const Grid& grid, int r, int c,
                              const std::vector<std::unique_ptr<Validator>>& validators) {
    for (const auto& v : validators) {
        if (v->conflicts(grid, r, c)) {
            return true;
        }
    }
    return false;
}

void UIPanel::draw(Grid& grid, const FixedMap& fixed,
                   const std::vector<std::unique_ptr<Validator>>& validators) {
    if (ImGui::BeginTable("grid", N,
            ImGuiTableFlags_Borders | ImGuiTableFlags_SizingFixedFit)) {

        for (int i = 0; i < N; ++i) {
            ImGui::TableSetupColumn("", ImGuiTableColumnFlags_WidthFixed, 40.0f);
        }

        for (int r = 0; r < N; ++r) {
            ImGui::TableNextRow();
            for (int c = 0; c < N; ++c) {
                ImGui::TableNextColumn();
                bool conflict = cell_has_conflict(grid, r, c, validators);

                int box_r = r / 3, box_c = c / 3;
                if ((box_r + box_c) % 2 == 1) {
                    ImGui::TableSetBgColor(ImGuiTableBgTarget_CellBg,
                                           IM_COL32(40, 40, 40, 255));
                }

                if (fixed[r][c]) {
                    if (conflict) {
                        ImGui::TextColored(ImVec4(1.0f, 0.5f, 0.5f, 1.0f),
                                           "%d", grid[r][c]);
                    } else {
                        ImGui::Text("%d", grid[r][c]);
                    }
                } else {
                    ImVec4 input_color = conflict
                        ? ImVec4(1.0f, 0.5f, 0.5f, 1.0f)
                        : ImVec4(0.5f, 1.0f, 0.5f, 1.0f);

                    char buf[2] = "";
                    if (grid[r][c] != 0) buf[0] = '0' + grid[r][c];
                    buf[1] = '\0';

                    ImGui::PushID(r * N + c);
                    ImGui::SetNextItemWidth(34.0f);
                    ImGui::PushStyleColor(ImGuiCol_Text, input_color);
                    ImGui::InputText("##cell", buf, sizeof(buf),
                                     ImGuiInputTextFlags_CharsDecimal);
                    ImGui::PopStyleColor();
                    ImGui::PopID();

                    if (buf[0] >= '1' && buf[0] <= '9')
                        grid[r][c] = buf[0] - '0';
                    else
                        grid[r][c] = 0;
                }
            }
        }
        ImGui::EndTable();
    }
}

Explanation of the key parts:

• static bool cell_has_conflict(...): a free helper function; static gives it internal linkage (only this TU uses it). It loops over the validators and asks each one. If any validator reports a conflict, the cell conflicts.
• for (const auto& v : validators): range-for; v is deduced as const unique_ptr<Validator>&.
• v->conflicts(...): unique_ptr::operator-> returns a raw Validator*, and the method call dispatches virtually through the vtable.
• Fixed cell + conflict: ImGui::TextColored with a light red. The default ImGui::Text is white.
• Editable cell + conflict: use PushStyleColor(ImGuiCol_Text, red) so the InputText text is red. Match with a Pop after Input.

Step 7 — Call site (app.cpp draw_frame)

void App::draw_frame() {
    ImGui::Begin("Sudoku");
    panel_.draw(grid_, fixed_, validators_);   // ← add validators_
    ImGui::End();
}

Step 8 — Update CMakeLists

File: apps/sudoku/CMakeLists.txt — add src/validator.cpp to the sources:

add_executable(sudoku
    src/main.cpp
    src/grid.cpp
    src/ui_panel.cpp
    src/app.cpp
    src/validator.cpp        # ← ADD
)

5. Key learning — Lesson 2 vs Lesson 1

| Lesson 1 (Phase 1) | Lesson 2 (Phase 2) | |---|---| | App owns Grid + FixedMap (POD types) | App owns a vector of polymorphic smart pointers | | UIPanel only renders | UIPanel + business-logic helper (cell_has_conflict) | | No class hierarchy | Abstract base + 3 derived = inheritance + polymorphism | | Grid g{}; value type | std::make_unique<RowValidator>() heap-allocated polymorphic | | Compile-time dispatch | Virtual dispatch at runtime (vtable) |

New patterns:

• Strategy pattern — interchangeable family of algorithms behind a base interface
• Abstract class with pure virtuals
• Virtual destructor + dispatch
• override keyword safety
• Polymorphic container — vector<unique_ptr<Base>>
• std::make_unique<Derived>() factory

Easy to extend:

Add class DiagonalValidator : public Validator in a new file plus push one more line in App::init(). The UI automatically renders red conflicts for the new rule. This is the Open-Closed Principle in action.

6. How to verify it works

Build

cd apps/sudoku
cmake --build build

Expected:

[100%] Built target sudoku

Run

./build/sudoku            # Mac
build\Debug\sudoku.exe    # Windows

Visual checklist

• [ ] The "Sudoku" window shows a 9x9 grid with SAMPLE_PUZZLE
• [ ] Fixed cells (pre-filled numbers): white
• [ ] Empty editable cells: green input cursor
• [ ] Test row conflict: type 5 into cell (0, 1). Cell (0, 0) already has 5 in the same row → both cells turn red.
• [ ] Test col conflict: type 6 into cell (3, 0). Cell (1, 0) already has 6 in the same column → red.
• [ ] Test box conflict: type 9 into cell (0, 1). Cell (1, 4) — or an equivalent cell in the 3x3 box (0,0) — contains 9 → red.
• [ ] Deleting the typed number → the red disappears on the next frame.
• [ ] Multiple conflicts on the same cell: typing a number that violates both row and col → still a single red color (no "redder" version) — correct.

CLI verify (advanced)

Inspect the symbol table:

nm build/sudoku 2>/dev/null | grep -i validator | head
# Or on macOS:
nm -gU build/sudoku | grep -i validator

Expect: RowValidator::name, RowValidator::conflicts, vtable entries.

7. Common errors / pitfalls

| Symptom | Cause | Fix | |---|---|---| | Compile error cannot allocate an object of abstract type 'Validator' | Code has Validator v; somewhere | Validator is abstract — must go through a derived class. Check there is no Validator{} | | Compile error 'override' marked but doesn't override | Typo in the method name or signature mismatch | Carefully check name() const override — the const matters | | Linker error undefined reference to vtable for Validator | Forgot to implement the virtual destructor | Add ~Validator() = default; or declare-define it out-of-line | | Cell never turns red | The validators vector is empty (forgot to push) or cell_has_conflict always returns false | Debug: print validators_.size() at init; print the conflict result in the helper | | Infinite loop when typing a number | for (int cc = 0; cc < N; ++c) typo (++c instead of ++cc) | Rename the loop variable to something distinct from the parameter (e.g. col_iter) | | App crashes on exit | Missing virtual destructor → wrong delete cascade | Always use a virtual dtor for a base class | | Pushing a value type instead of a smart pointer | validators_.push_back(RowValidator{}); compile error | Use std::make_unique<RowValidator>() | | Multiple-definition linker error | Method body defined inline in validator.h | Declaration-only header, implementation in .cpp | | Missing ; after class Validator { ... } | The compiler reports a confused error on the following line | Always end a class brace with ; | | Fixed-cell conflict does not display red | Forgot to check conflict in the fixed branch | The fixed branch also checks and uses TextColored |

8. Space for self-study

1. DiagonalValidator for X-Sudoku: the 2 diagonals must each contain 9 distinct numbers. Try to implement it (similar to RowValidator but indexed i, i or i, N-1-i).
2. Killer Sudoku regions: define a free-form region (a group of cells) whose cell sum equals a target. Implement KillerValidator.
3. Conflict counter: count the total number of conflicting cells in the grid. Display "Errors: N" in the UI.
4. Toggle validators: add a checkbox for each validator (Row/Col/Box) — disable them at runtime. The UI updates conflicts based on the enabled set.
5. Performance: each frame loops 81 cells * 3 validators * 9 = 2187 comparisons. Is caching needed? Measure FPS, try disabling a validator → compare.
6. Color severity: if one cell conflicts with 3 validators (extremely rare), display a different color (dark red) instead of the same red.

9. End-of-lesson exercises

Exercise 1 — DiagonalValidator (X-Sudoku)

Create class DiagonalValidator : public Validator. Logic: if (r, c) lies on one of the 2 diagonals, check the 9 cells on that diagonal. Push it into App::init().

Exercise 2 — Error count UI

In App::draw_frame, before panel_.draw(...), compute the total number of conflicting cells and display ImGui::Text("Errors: %d", count). Count = sum of cell_has_conflict over the 81 cells.

Exercise 3 — Disable validator

Add 3 members bool enable_row_, enable_col_, enable_box_; in App, default true. Add 3 checkboxes in the UI. Modify cell_has_conflict to skip disabled validators. Hint: instead of passing the vector, pass vector + an enable_flags array.

Exercise 4 — Validate solved

Add a method App::is_solved() -> bool: return true when (1) no cell is == 0, and (2) there is no conflict. Display the text "🎉 SOLVED" when solved. (No emoji if it is hard to type — use "SOLVED")

Exercise 5 (challenge) — Hint mode

Add a "Hint" button. On click: find an empty cell that has exactly 1 conflict-free value 1-9 (i.e. a "naked single"). Auto-fill that cell. If none is found → log "No naked single available".

10. Answer key

class DiagonalValidator : public Validator {
public:
    const char* name() const override;
    bool        conflicts(const Grid& grid, int r, int c) const override;
};

const char* DiagonalValidator::name() const { return "Diagonal"; }

bool DiagonalValidator::conflicts(const Grid& grid, int r, int c) const {
    int v = grid[r][c];
    if (v == 0) return false;

    bool on_main_diag = (r == c);
    bool on_anti_diag = (r + c == N - 1);

    if (on_main_diag) {
        for (int i = 0; i < N; ++i) {
            if (i != r && grid[i][i] == v) return true;
        }
    }
    if (on_anti_diag) {
        for (int i = 0; i < N; ++i) {
            if (i != r && grid[i][N-1-i] == v) return true;
        }
    }
    return false;
}

validators_.push_back(std::make_unique<DiagonalValidator>());

void App::draw_frame() {
    ImGui::Begin("Sudoku");

    int errors = 0;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            for (const auto& v : validators_) {
                if (v->conflicts(grid_, r, c)) {
                    ++errors;
                    break;   // count each cell only once
                }
            }
        }
    }
    ImGui::Text("Errors: %d", errors);

    panel_.draw(grid_, fixed_, validators_);
    ImGui::End();
}

bool enable_row_ = true;
bool enable_col_ = true;
bool enable_box_ = true;

ImGui::Checkbox("Row", &enable_row_);
ImGui::SameLine();
ImGui::Checkbox("Column", &enable_col_);
ImGui::SameLine();
ImGui::Checkbox("Box", &enable_box_);

std::vector<std::unique_ptr<Validator>> active;
if (enable_row_) active.push_back(std::make_unique<RowValidator>());
if (enable_col_) active.push_back(std::make_unique<ColValidator>());
if (enable_box_) active.push_back(std::make_unique<BoxValidator>());
panel_.draw(grid_, fixed_, active);

bool is_solved() const;

bool App::is_solved() const {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (grid_[r][c] == 0) return false;
            for (const auto& v : validators_) {
                if (v->conflicts(grid_, r, c)) return false;
            }
        }
    }
    return true;
}

panel_.draw(grid_, fixed_, validators_);
if (is_solved()) {
    ImGui::TextColored(ImVec4(0, 1, 0, 1), "SOLVED");
}

bool App::try_hint() {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (grid_[r][c] != 0) continue;

            int candidate_count = 0;
            int candidate = 0;
            for (int v = 1; v <= 9; ++v) {
                grid_[r][c] = v;
                bool any_conflict = false;
                for (const auto& val : validators_) {
                    if (val->conflicts(grid_, r, c)) {
                        any_conflict = true;
                        break;
                    }
                }
                if (!any_conflict) {
                    ++candidate_count;
                    candidate = v;
                }
            }
            grid_[r][c] = 0;   // restore

            if (candidate_count == 1) {
                grid_[r][c] = candidate;
                return true;
            }
        }
    }
    return false;
}

if (ImGui::Button("Hint")) {
    if (!try_hint()) {
        std::fprintf(stderr, "No naked single available\n");
    }
}

→ Next: 03-phase3-0-shared-lib.md — Phase 3.0: Splitting libs/solver/ into a static library