Lesson 2 — Phase 2: Strategy Pattern với Validator

Commit: 2c97016 (một phần). Phase 2 của ứng dụng sudoku — thêm phần kiểm tra hợp lệ.

1. Mục tiêu

Sau lesson này bạn sẽ có:

• Một lớp trừu tượng Validator với destructor virtual và 2 phương thức pure virtual (name, conflicts)
• 3 validator cụ thể: RowValidator, ColValidator, BoxValidator — phát hiện trùng lặp trong nhóm tương ứng
• App chứa std::vector<std::unique_ptr<Validator>> — sở hữu đa hình
• Một UIPanel hiển thị các ô màu đỏ khi có xung đột (cả ô cố định lẫn ô có thể chỉnh sửa)
• Kiến trúc mở rộng được: thêm một validator mới (ví dụ DiagonalValidator cho X-Sudoku) không cần sửa đổi code hiện có

2. Cây thư mục

apps/sudoku/src/
├── app.h                       ← MODIFY: thêm field vector<unique_ptr<Validator>>
├── app.cpp                     ← MODIFY: push 3 validator trong init()
├── ui_panel.h                  ← MODIFY: signature draw() nhận validators
├── ui_panel.cpp                ← MODIFY: helper cell_has_conflict, render đỏ
├── validator.h                 ← NEW: lớp trừu tượng + 3 lớp dẫn xuất
├── validator.cpp               ← NEW: triển khai conflicts() cho từng lớp
├── grid.h, grid.cpp            (đã có, không thay đổi)
└── main.cpp                    (đã có, không thay đổi)

3. Nội dung cần học

1. Lớp trừu tượng — phương thức pure virtual (= 0)
2. Destructor virtual — vì sao bắt buộc đối với lớp cơ sở đa hình
3. Từ khoá override — override được compiler kiểm tra
4. = default cho destructor — dtor tầm thường, ý định rõ ràng
5. Kế thừa — class Derived : public Base
6. std::unique_ptr<Base> + đa hình — sở hữu đơn với dispatch virtual
7. std::make_unique<Derived>() — factory an toàn với exception
8. Container chứa kiểu đa hình — vector<unique_ptr<Base>>
9. Strategy pattern — họ thuật toán có thể hoán đổi cho nhau
10. Hàm tự do static — helper với internal linkage

4. Cách thực hiện

Bước 1 — Lớp cơ sở trừu tượng Validator (validator.h)

File: apps/sudoku/src/validator.h

#pragma once
#include "grid.h"   // Phase 2; ở Phase 3.0 đổi thành "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;
};

Giải thích:

• virtual ~Validator() = default;: destructor virtual cho phép xoá thông qua con trỏ base mà dispatch đúng destructor của lớp dẫn xuất. = default yêu cầu compiler tự sinh ra (thân hàm rỗng tầm thường).
• Specifier pure = 0: phương thức không có thân ở base, và các lớp dẫn xuất bắt buộc phải override. Một lớp có pure virtual là lớp trừu tượng — không thể khởi tạo trực tiếp.
• override sau signature: compiler kiểm tra ý định. Nếu signature không khớp với phương thức base, compiler báo lỗi. Điều này ngăn chặn lỗi gõ nhầm (nme() thay vì name()).
• const Grid& grid: truyền tham chiếu tránh việc copy 324 byte; const vì validator chỉ đọc.
• const ở cuối phương thức: phương thức không thay đổi *this. Điều này cho phép gọi thông qua const Validator&.

Bước 2 — Triển khai 3 validator (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;
}

Giải thích thuật toán:

Mỗi validator trả lời câu hỏi: "Giá trị tại (r, c) có bị trùng trong hàng/cột/box của nó không?"

• Kiểm tra v == 0 trước: một ô trống không gây xung đột
• Lặp qua nhóm (9 ô trong hàng/cột/box)
• Bỏ qua ô hiện tại (cc != c, hoặc rr != r, hoặc (rr != r || cc != c))
• So khớp giá trị: tìm thấy ô khác có cùng giá trị → xung đột

BoxValidator: tính bounding box 3x3:

int boxRow = r / 3;        // 0, 1, hoặc 2
int boxCol = c / 3;
// phạm vi box: hàng [boxRow*3, boxRow*3+3), cột [boxCol*3, boxCol*3+3)

Ví dụ: r = 4, c = 7 → boxRow = 1, boxCol = 2 → lặp rr ∈ [3,6), cc ∈ [6,9).

Bước 3 — App sở hữu các validator (app.h)

File: apps/sudoku/src/app.h (sửa)

#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
};

Giải thích kiểu của member:

std::vector<std::unique_ptr<Validator>> — một vector chứa smart pointer tới base.

So sánh các lựa chọn:

| Kiểu | Vấn đề | |---|---| | std::vector<Validator> | Lỗi biên dịch: Validator là trừu tượng. Cho dù có khả thi, object slicing — chỉ phần Validator được lưu, dữ liệu dẫn xuất bị mất | | std::vector<Validator*> | Biên dịch được. Nhưng raw pointer — quyền sở hữu không rõ, dễ rò rỉ | | std::vector<std::unique_ptr<Validator>> | ✓ Smart pointer sở hữu, đa hình qua con trỏ, dọn dẹp RAII |

Bước 4 — Push các validator trong init (app.cpp)

File: apps/sudoku/src/app.cpp — bên trong App::init(), sau 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>());

Giải thích:

• std::make_unique<T>() — một lần cấp phát, an toàn với exception. Luôn ưu tiên dùng nó thay vì std::unique_ptr<T>(new T()).
• push_back của vector move-construct unique_ptr vào — không copy (unique_ptr không thể copy).

Bước 5 — Signature của UIPanel (ui_panel.h)

File: apps/sudoku/src/ui_panel.h (sửa)

#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);
};

Bước 6 — UIPanel render với conflict (ui_panel.cpp)

File: apps/sudoku/src/ui_panel.cpp (sửa)

#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();
    }
}

Giải thích các phần quan trọng:

• static bool cell_has_conflict(...): một hàm helper tự do; static cho nó internal linkage (chỉ TU này sử dụng). Nó lặp qua các validator và hỏi từng cái. Nếu bất kỳ validator nào báo xung đột, ô đó xung đột.
• for (const auto& v : validators): range-for; v được suy ra là const unique_ptr<Validator>&.
• v->conflicts(...): unique_ptr::operator-> trả về raw Validator*, và lời gọi phương thức dispatch virtual qua vtable.
• Ô cố định + xung đột: ImGui::TextColored với màu đỏ nhạt. ImGui::Text mặc định là màu trắng.
• Ô có thể chỉnh sửa + xung đột: dùng PushStyleColor(ImGuiCol_Text, red) để text của InputText có màu đỏ. Đi cùng với Pop sau Input.

Bước 7 — Điểm gọi (app.cpp draw_frame)

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

Bước 8 — Cập nhật CMakeLists

File: apps/sudoku/CMakeLists.txt — thêm src/validator.cpp vào sources:

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

5. Bài học chính — Lesson 2 so với Lesson 1

| Lesson 1 (Phase 1) | Lesson 2 (Phase 2) | |---|---| | App sở hữu Grid + FixedMap (kiểu POD) | App sở hữu một vector các smart pointer đa hình | | UIPanel chỉ render | UIPanel + helper business-logic (cell_has_conflict) | | Không có hệ phân cấp lớp | Lớp trừu tượng base + 3 lớp dẫn xuất = kế thừa + đa hình | | Grid g{}; kiểu giá trị | std::make_unique<RowValidator>() cấp phát heap đa hình | | Dispatch tại thời điểm biên dịch | Virtual dispatch tại thời điểm chạy (vtable) |

Pattern mới:

• Strategy pattern — họ thuật toán có thể hoán đổi đằng sau một interface base
• Lớp trừu tượng với pure virtual
• Destructor virtual + dispatch
• An toàn nhờ từ khoá override
• Container đa hình — vector<unique_ptr<Base>>
• Factory std::make_unique<Derived>()

Dễ mở rộng:

Thêm class DiagonalValidator : public Validator trong một file mới cộng thêm một dòng push trong App::init(). UI tự động render đỏ cho xung đột với rule mới. Đây là Open-Closed Principle trong thực tế.

6. Cách kiểm tra hoạt động

Build

cd apps/sudoku
cmake --build build

Kỳ vọng:

[100%] Built target sudoku

Chạy

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

Checklist quan sát

• [ ] Cửa sổ "Sudoku" hiển thị lưới 9x9 với SAMPLE_PUZZLE
• [ ] Các ô cố định (số đã điền sẵn): trắng
• [ ] Ô trống có thể chỉnh sửa: con trỏ input màu xanh lá
• [ ] Test xung đột hàng: gõ 5 vào ô (0, 1). Ô (0, 0) đã có 5 trong cùng hàng → cả hai ô chuyển đỏ.
• [ ] Test xung đột cột: gõ 6 vào ô (3, 0). Ô (1, 0) đã có 6 trong cùng cột → đỏ.
• [ ] Test xung đột box: gõ 9 vào ô (0, 1). Ô (1, 4) — hoặc một ô tương đương trong box 3x3 (0,0) — chứa 9 → đỏ.
• [ ] Xoá số đã gõ → màu đỏ biến mất ở frame tiếp theo.
• [ ] Nhiều xung đột trên cùng một ô: gõ một số vi phạm cả hàng lẫn cột → vẫn chỉ là một màu đỏ duy nhất (không có phiên bản "đỏ hơn") — đúng.

Verify bằng CLI (nâng cao)

Kiểm tra bảng ký hiệu:

nm build/sudoku 2>/dev/null | grep -i validator | head
# Hoặc trên macOS:
nm -gU build/sudoku | grep -i validator

Kỳ vọng: RowValidator::name, RowValidator::conflicts, các entry vtable.

7. Lỗi thường gặp / cạm bẫy

| Triệu chứng | Nguyên nhân | Cách khắc phục | |---|---|---| | Lỗi biên dịch cannot allocate an object of abstract type 'Validator' | Code có Validator v; đâu đó | Validator là trừu tượng — phải đi qua lớp dẫn xuất. Kiểm tra không có Validator{} | | Lỗi biên dịch 'override' marked but doesn't override | Gõ sai tên phương thức hoặc signature không khớp | Kiểm tra cẩn thận name() const override — const quan trọng | | Lỗi linker undefined reference to vtable for Validator | Quên triển khai destructor virtual | Thêm ~Validator() = default; hoặc khai báo-định nghĩa out-of-line | | Ô không bao giờ chuyển đỏ | Vector validators rỗng (quên push) hoặc cell_has_conflict luôn trả về false | Debug: in validators_.size() lúc init; in kết quả conflict trong helper | | Vòng lặp vô tận khi gõ số | for (int cc = 0; cc < N; ++c) gõ nhầm (++c thay vì ++cc) | Đổi tên biến lặp thành thứ gì đó khác hẳn với tham số (ví dụ col_iter) | | App crash khi thoát | Thiếu destructor virtual → cascade delete sai | Luôn dùng dtor virtual cho lớp base | | Push kiểu giá trị thay vì smart pointer | validators_.push_back(RowValidator{}); lỗi biên dịch | Dùng std::make_unique<RowValidator>() | | Lỗi linker multiple-definition | Thân phương thức định nghĩa inline trong validator.h | Header chỉ khai báo, triển khai trong .cpp | | Thiếu ; sau class Validator { ... } | Compiler báo lỗi khó hiểu ở dòng tiếp theo | Luôn kết thúc dấu ngoặc lớp bằng ; | | Xung đột ở ô cố định không hiển thị đỏ | Quên kiểm tra conflict trong nhánh fixed | Nhánh fixed cũng phải kiểm tra và dùng TextColored |

8. Khoảng tự học

1. DiagonalValidator cho X-Sudoku: 2 đường chéo mỗi cái phải chứa 9 số khác nhau. Thử triển khai (tương tự RowValidator nhưng index i, i hoặc i, N-1-i).
2. Vùng Killer Sudoku: định nghĩa một vùng tự do (một nhóm ô) mà tổng giá trị các ô bằng một mục tiêu. Triển khai KillerValidator.
3. Bộ đếm xung đột: đếm tổng số ô xung đột trong lưới. Hiển thị "Errors: N" trên UI.
4. Bật/tắt validator: thêm một checkbox cho mỗi validator (Row/Col/Box) — vô hiệu hoá lúc chạy. UI cập nhật xung đột dựa trên tập đã bật.
5. Hiệu năng: mỗi frame lặp 81 ô * 3 validator * 9 = 2187 phép so sánh. Có cần cache không? Đo FPS, thử tắt một validator → so sánh.
6. Mức độ nghiêm trọng theo màu: nếu một ô xung đột với cả 3 validator (cực kỳ hiếm), hiển thị màu khác (đỏ đậm) thay vì màu đỏ cũ.

9. Bài tập cuối lesson

Bài tập 1 — DiagonalValidator (X-Sudoku)

Tạo class DiagonalValidator : public Validator. Logic: nếu (r, c) nằm trên một trong 2 đường chéo, kiểm tra 9 ô trên đường chéo đó. Push nó vào App::init().

Bài tập 2 — UI đếm số lỗi

Trong App::draw_frame, trước panel_.draw(...), tính tổng số ô xung đột và hiển thị ImGui::Text("Errors: %d", count). Count = tổng cell_has_conflict trên 81 ô.

Bài tập 3 — Vô hiệu hoá validator

Thêm 3 member bool enable_row_, enable_col_, enable_box_; trong App, mặc định true. Thêm 3 checkbox trong UI. Sửa cell_has_conflict để bỏ qua các validator bị vô hiệu. Gợi ý: thay vì truyền vector, truyền vector + mảng enable_flags.

Bài tập 4 — Kiểm tra đã giải xong

Thêm phương thức App::is_solved() -> bool: trả về true khi (1) không ô nào bằng 0, và (2) không có xung đột. Hiển thị text "🎉 SOLVED" khi đã giải. (Không dùng emoji nếu khó gõ — dùng "SOLVED")

Bài tập 5 (thử thách) — Chế độ Hint

Thêm nút "Hint". Khi nhấn: tìm một ô trống mà có đúng 1 giá trị 1-9 không gây xung đột (tức là "naked single"). Tự động điền ô đó. Nếu không tìm thấy → log "No naked single available".

10. Đáp án

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;   // đếm mỗi ô chỉ một lần
                }
            }
        }
    }
    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");
    }
}

→ Tiếp theo: 03-phase3-0-shared-lib.md — Phase 3.0: Tách libs/solver/ thành một thư viện static