learning.
learning11 min read

build sudoku + sudoku solver from scratch

Bài 2 — Phase 2 của app sudoku. Dựng base trừu tượng `Validator` với strategy cụ thể `RowValidator`, `ColValidator`, `BoxValidator`. Sở hữu chúng trong `std::vector<std::unique_ptr<Validator>>`. UIPanel chuyển ô xung đột thành ĐỎ. Strategy pattern cho phép DiagonalValidator / KillerValidator mở rộng engine mà không đụng code cũ.

build sudoku + sudoku solver from scratch

Sudoku C++ Phase 2: Strategy Pattern cho Validator (Bài 2)

Đây là Bài 2 trong chuỗi tự học dựng app Sudoku và Sudoku Solver từ đầu bằng C++17. Bài 1 đã dựng được lưới 9×9, Cell mang giá trị 0 (rỗng) đến 9, và một UIPanel render lưới ra terminal hoặc cửa sổ Qt. App chạy nhưng vẫn cho phép gõ số trùng hàng, trùng cột, trùng box 3×3 mà không phàn nàn. Phase 2 sửa lỗ hổng đó. Mục tiêu: viết engine kiểm tra xung đột bằng Strategy pattern, để sau này thêm các biến thể như Sudoku đường chéo (Diagonal) hay Killer Sudoku mà không phải mở lại file engine cũ.

Phase 1 để lại gì và Phase 2 cần thêm gì

Sau Bài 1, project có Grid, Cell, UIPanel, và một loop game đơn giản. Người chơi đánh số vào ô và lưới cập nhật state. Vấn đề rõ ràng: không có ai chặn việc đặt số 5 vào hai ô cùng hàng. Một solver chưa thể chạy trên dữ liệu sai, và người chơi thì không biết mình đang vi phạm luật nào.

Phase 2 đặt ba câu hỏi kỹ thuật. Một, ai biết một ô có hợp lệ hay không. Hai, kết quả kiểm tra được truyền cho UI bằng cách nào. Ba, nếu sáu tháng nữa muốn hỗ trợ Killer Sudoku (mỗi vùng cage có tổng số cố định), code cũ phải sửa bao nhiêu dòng. Câu trả lời lý tưởng cho câu hỏi thứ ba là 0 dòng. Đó là lý do bài hôm nay dùng Strategy pattern thay vì một hàm isGridValid() đơn lẻ.

Tại sao một hàm validate khổng lồ không trụ được

Cách phổ biến nhất khi mới học là viết một hàm tổng:

bool isGridValid(const Grid& g) {
    for (int r = 0; r < 9; ++r) { /* check row r */ }
    for (int c = 0; c < 9; ++c) { /* check col c */ }
    for (int b = 0; b < 9; ++b) { /* check box b */ }
    return true;
}

Hàm trên hoạt động cho Sudoku cổ điển. Vấn đề nảy sinh khi yêu cầu thay đổi. Muốn thêm luật đường chéo, ta phải mở lại hàm và thêm vòng lặp thứ tư. Muốn highlight ô nào sai (chứ không chỉ trả false/true), ta phải đổi chữ ký hàm thành vector<CellPos>. Muốn test riêng logic kiểm tra cột mà không kéo theo logic box, ta phải viết một copy nhỏ. Mỗi yêu cầu mới làm hàm phình ra thêm 30–50 dòng, và mỗi lần sửa lại là một lần rủi ro hồi quy: thêm luật đường chéo có khi vô tình phá test row.

Nguyên tắc Open/Closed của SOLID nói: module nên mở để mở rộng nhưng đóng với sửa đổi. Hàm khổng lồ vi phạm cả hai vế. Strategy pattern là cách trực tiếp nhất để gỡ nó ra.

Strategy pattern trong một câu

Strategy pattern (mô tả lần đầu trong sách Gang of Four năm 1994) đóng gói mỗi thuật toán vào một class riêng cùng chia chung một interface. Code khách giữ một con trỏ tới interface, không biết và không cần biết thuật toán cụ thể nào đang chạy. Khi cần thêm thuật toán mới, ta tạo class mới implement interface đó, không sửa code khách. Refactoring Guru có hình minh họa rõ ràng tại https://refactoring.guru/design-patterns/strategy.

Áp dụng vào Sudoku: mỗi luật kiểm tra (row, col, box, diagonal, killer cage) là một strategy. Engine giữ một danh sách strategy. Để xác định ô nào xung đột, engine lặp qua từng strategy và gộp kết quả.

Thiết kế class Validator abstract

Tạo file core/Validator.hpp:

#pragma once
#include <vector>
#include "Grid.hpp"

struct CellPos { int row; int col; };

class Validator {
public:
    virtual ~Validator() = default;
    virtual std::vector<CellPos> findConflicts(const Grid& grid) const = 0;
    virtual const char* name() const = 0;
};

Bốn quyết định thiết kế đáng dừng lại:

  1. Destructor virtual. Engine sẽ giữ con trỏ base, delete qua base. Không khai báo virtual ~Validator() là undefined behavior khi xóa subclass qua pointer base. Quy ước trong codebase Sudoku này: bất kỳ class có hàm ảo đều khai báo destructor ảo, kể cả = default.
  2. findConflicts trả về std::vector<CellPos> thay vì bool. UI cần biết ô nào sai để tô đỏ, không chỉ cần biết "có lỗi". Trả vector rỗng đồng nghĩa "không có xung đột".
  3. const Grid&. Validator không sửa lưới, chỉ đọc. Const-correctness chặn lỗi vô tình từ một strategy quá nhiệt tình.
  4. name() trả const char* để log và debug. Khi user gặp ô đỏ, log dòng "RowValidator marked (3,4)" giúp truy ngược.

Ba concrete strategies

RowValidator.cpp kiểm tra mỗi hàng có giá trị trùng:

#include "Validator.hpp"
#include <array>

class RowValidator : public Validator {
public:
    std::vector<CellPos> findConflicts(const Grid& grid) const override {
        std::vector<CellPos> conflicts;
        for (int r = 0; r < 9; ++r) {
            std::array<int, 10> count{};
            for (int c = 0; c < 9; ++c) {
                int v = grid.at(r, c);
                if (v > 0) count[v]++;
            }
            for (int c = 0; c < 9; ++c) {
                int v = grid.at(r, c);
                if (v > 0 && count[v] > 1) conflicts.push_back({r, c});
            }
        }
        return conflicts;
    }
    const char* name() const override { return "RowValidator"; }
};

ColValidator là bản đối xứng theo cột (grid.at(r, c) với c cố định, r chạy). BoxValidator chia lưới thành 9 vùng 3×3 và đếm cùng nguyên tắc. Tổng cộng ba file, mỗi file khoảng 25–30 dòng. So với hàm isGridValid() gộp ba luật, tổng số dòng tương đương, nhưng mỗi file giờ có một trách nhiệm duy nhất và unit test viết được độc lập.

Test ví dụ với GoogleTest:

TEST(RowValidator, DuplicatesInRowAreFlagged) {
    Grid g;
    g.set(0, 0, 5);
    g.set(0, 4, 5);
    RowValidator v;
    auto conflicts = v.findConflicts(g);
    EXPECT_EQ(conflicts.size(), 2);
}

Test này không cần ColValidator hay BoxValidator tồn tại để chạy. Đây là tách trách nhiệm ở mức compile, không chỉ ở mức tinh thần.

Sở hữu strategies bằng std::vector<std::unique_ptr<Validator>>

Class ValidationEngine giữ danh sách validators và chạy chúng:

#include <memory>
#include <vector>
#include <unordered_set>
#include "Validator.hpp"

class ValidationEngine {
public:
    void add(std::unique_ptr<Validator> v) {
        validators_.push_back(std::move(v));
    }

    std::unordered_set<int> runAll(const Grid& grid) const {
        std::unordered_set<int> bad;
        for (const auto& v : validators_) {
            for (auto pos : v->findConflicts(grid)) {
                bad.insert(pos.row * 9 + pos.col);
            }
        }
        return bad;
    }

private:
    std::vector<std::unique_ptr<Validator>> validators_;
};

std::unique_ptr thay vì raw pointer là quyết định an toàn nhất cho lifecycle. Ownership thuộc về vector. Khi ValidationEngine bị hủy, vector hủy theo, các unique_ptr gọi destructor ảo của từng validator. Không có memory leak, không có double-free, không có ai khác cùng giữ pointer mà không biết. Tài liệu cppreference tại https://en.cppreference.com/w/cpp/memory/unique_ptr nêu rõ chính sách move-only và RAII của unique_ptr, và đây là use case kinh điển: container giữ polymorphic ownership.

Tránh std::shared_ptr khi không có lý do thực sự cần share. Reference counting có chi phí runtime (atomic ops trên control block), và nó che giấu chuyện "ai sở hữu cái này". Trong app Sudoku, validators chỉ sống bên trong engine, không ai share. unique_ptr là default đúng.

Khởi tạo engine trong main hoặc App::init:

auto engine = std::make_unique<ValidationEngine>();
engine->add(std::make_unique<RowValidator>());
engine->add(std::make_unique<ColValidator>());
engine->add(std::make_unique<BoxValidator>());

Ba dòng. Thêm luật mới ngày mai sẽ là một dòng engine->add(std::make_unique<DiagonalValidator>()) nữa, không hơn.

UIPanel chuyển ô xung đột thành ĐỎ

UI không nên hiểu luật Sudoku. UI hiểu "ô này thuộc set bad, tô đỏ". Logic đó nằm trong UIPanel::paint:

void UIPanel::paint(const Grid& grid, const ValidationEngine& engine) {
    auto bad = engine.runAll(grid);
    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            int key = r * 9 + c;
            Color fg = bad.count(key) ? Color::Red : Color::Black;
            drawCell(r, c, grid.at(r, c), fg);
        }
    }
}

drawCell là API của lớp render bên dưới (ncurses, Qt, hoặc SDL tùy backend). Điểm cần nhấn: UIPanel không biết tại sao một ô đỏ. Nếu sau này thêm KillerCageValidator và một ô đỏ vì sai tổng cage, code render không đổi một dòng. Đây chính là điểm thắng của Strategy pattern.

Mặt cần thận trọng: runAll trả unordered_set<int> (encoded row*9+col). Đừng để UI gọi findConflicts trên từng validator rồi tự gộp. Đó là gộp logic vào lớp sai. Engine gộp, UI chỉ hỏi.

Mở rộng: DiagonalValidator và KillerValidator không đụng code cũ

Sudoku đường chéo yêu cầu hai đường chéo chính (từ (0,0) đến (8,8) và từ (0,8) đến (8,0)) đều phải có 9 số khác nhau. Class mới:

class DiagonalValidator : public Validator {
public:
    std::vector<CellPos> findConflicts(const Grid& grid) const override {
        std::vector<CellPos> conflicts;
        checkLine(grid, conflicts, true);
        checkLine(grid, conflicts, false);
        return conflicts;
    }
    const char* name() const override { return "DiagonalValidator"; }
private:
    void checkLine(const Grid& g, std::vector<CellPos>& out, bool mainDiag) const {
        std::array<int, 10> count{};
        for (int i = 0; i < 9; ++i) {
            int v = g.at(i, mainDiag ? i : 8 - i);
            if (v > 0) count[v]++;
        }
        for (int i = 0; i < 9; ++i) {
            int v = g.at(i, mainDiag ? i : 8 - i);
            if (v > 0 && count[v] > 1) out.push_back({i, mainDiag ? i : 8 - i});
        }
    }
};

Một file mới. Một dòng engine->add(std::make_unique<DiagonalValidator>()). Validator.hpp không sửa, ValidationEngine không sửa, UIPanel không sửa, không file nào trong số ba file row/col/box phải đụng. Diff Phase 2.5 nếu thêm tính năng này: 0 dòng thay đổi trong code cũ, khoảng 30 dòng code mới. Đó là Open/Closed bằng số liệu cụ thể.

Killer Sudoku phức tạp hơn (cần dữ liệu cage definition kèm theo), nhưng cấu trúc giống hệt: một KillerValidator mới, một dòng add, xong.

Strategy so với các giải pháp khác

Strategy không phải lựa chọn duy nhất. Cần biết khi nào nó vượt trội và khi nào không.

So với Template Method (kế thừa với hooks): Template Method gò bó vì base class quy định khung, subclass chỉ chen vào điểm định trước. Khi cần thay đổi luồng chính, phải đụng base. Strategy không có khung cứng đó, mỗi strategy là một thuật toán hoàn chỉnh.

So với CRTP (Curiously Recurring Template Pattern, static polymorphism): CRTP nhanh hơn vì virtual call bị eliminate ở compile time. Đo lường trên một Sudoku 9×9 với ba validator, chi phí virtual dispatch là khoảng 1–2 nanosecond mỗi call, hoàn toàn không đáng kể so với chi phí I/O của UI repaint. CRTP mất khả năng giữ heterogeneous container (vector<Validator*> không khai báo được khi base là template). Đối với app này, runtime polymorphism là default đúng. CRTP chỉ đáng cân nhắc khi profile cho thấy virtual dispatch là bottleneck thực sự, điều cực kỳ hiếm trong UI app.

So với std::variant<RowRule, ColRule, BoxRule> (sum type, visitor pattern): variant cho phép dispatch tĩnh và tránh allocation heap. Trade-off: thêm một luật mới = sửa kiểu variant ở mọi nơi nó xuất hiện = vi phạm Open/Closed. Strategy với unique_ptr<Validator> thắng ở tiêu chí "mở rộng không sửa code cũ".

Nguyên tắc chọn: ưu tiên Strategy khi danh sách thuật toán mở (sẽ thêm trong tương lai), khi cần test từng thuật toán độc lập, và khi runtime composition (chọn strategy dựa input người dùng) là yêu cầu thực. Trong app Sudoku có chế độ Classic / Diagonal / Killer mà người chơi chọn từ menu, ba điều kiện trên đều đúng.

Pitfalls thường gặp

Đừng nhét logic UI vào Validator. Nếu RowValidator::findConflicts gọi panel.highlight(...), validator đột nhiên phụ thuộc UI và không test được bằng GoogleTest. Tách render khỏi detection là điều bài này nhấn mạnh từ đầu.

Đừng dùng shared_ptr khi unique_ptr đủ dùng. Mỗi shared_ptr mang chi phí atomic reference count, và quan trọng hơn, nó làm mờ chuyện ai chịu trách nhiệm lifecycle. Khi engine sở hữu validator độc quyền, unique_ptr là lựa chọn rõ ràng.

Đừng quên virtual destructor trong base. Đây là lỗi C++ kinh điển dẫn đến leak vì destructor subclass không chạy. ISO C++ Core Guidelines mục C.35 tại https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rc-dtor-virtual quy định: "A base class destructor should be either public and virtual, or protected and non-virtual." Trong code Sudoku ta đi theo nhánh public-virtual.

Đừng gộp "ô có giá trị hợp lệ tại đây" và "ô có giá trị xung đột với ô khác" làm một. Một ô trống (giá trị 0) không phải xung đột, dù nó cũng chưa hợp lệ về mặt hoàn thành puzzle. Phase 2 chỉ phát hiện xung đột; Phase 3 (solver) sẽ trả lời câu hỏi hoàn thành.

Kết thúc Bài 2 và đặt nền cho Bài 3

Sau Phase 2, app Sudoku đã có engine validation thực sự: ô xung đột hiện đỏ trong real time, ba luật cổ điển được tách thành ba class độc lập có test riêng, và việc thêm luật mới chỉ tốn một class plus một dòng add. Codebase tăng khoảng 200 dòng so với cuối Phase 1 nhưng chia đều cho 5 file nhỏ thay vì một file engine.cpp 200 dòng.

Bài 3 sẽ tận dụng cấu trúc Validator này để dựng Sudoku solver bằng backtracking. Solver cần một API "ô (r, c) có thể đặt giá trị v hợp lệ hay không" và ValidationEngine đã sẵn sàng trả lời câu hỏi đó với mọi tổ hợp luật người chơi chọn. Strategy pattern hôm nay là khoản đầu tư cho solver ngày mai.

References: