learning.
learning11 min read

build sudoku + sudoku solver from scratch

Bài 3 — Phase 3 của app sudoku. Viết class `Solver` với backtracking cổ điển — tìm ô trống → thử 1-9 với guard `can_place` row/col/box → recurse → undo khi fail. Hai entry: `solve(Grid&)` in-place cho UI, `try_solve(const Grid&)` trả `std::optional<Grid>` cho CLI + test. Thêm binary thứ hai `apps/sudoku_solver/` đọc stdin → giải → in stdout với timing `std::chrono::steady_clock`. Suite GoogleTest 3 case cover happy path + mâu thuẫn + side-effect contract.

Phase 3: Sudoku Solver C++ v\u1edbi Backtracking, std::optional v\u00e0 GoogleTest

Phase 1 \u0111\u00e3 cho ch\u00fang ta m\u1ed9t Grid 9x9 v\u1edbi accessor an to\u00e0n. Phase 2 th\u00eam Validator ki\u1ec3m tra h\u1ee3p l\u1ec7 theo lu\u1eadt row/col/box. Phase 3 \u0111\u1eb7t c\u00e2u h\u1ecfi kh\u00f3 h\u01a1n nhi\u1ec1u: cho m\u1ed9t grid \u0111i\u1ec1n d\u1edf, h\u00e3y \u0111i\u1ec1n n\u1ed1t. \u0110\u00e1p \u00e1n kinh \u0111i\u1ec3n l\u00e0 backtracking, m\u1ed9t thu\u1eadt to\u00e1n \u0111\u1ec7 quy g\u1ecdn l\u1ecfn nh\u01b0ng c\u0169ng d[u1ec5 vi](https://learning.nicedx.com/vi-index/)\u1ebft sai ch\u1ed7 undo nh\u1ea5t.

B\u00e0i n\u00e0y t\u1eadp trung v\u00e0o ba th\u1ee9. M\u1ed9t, vi\u1ebft class Solver v\u1edbi hai entry point kh\u00e1c h\u1eb3n nhau v\u1ec1 contract: solve(Grid&) mutate in-place cho UI c\u1ea7n animate, c\u00f2n try_solve(const Grid&) pure-function tr\u1ea3 std::optional<Grid> cho CLI v\u00e0 test. Hai, d\u1ef1ng th\u00eam m\u1ed9t binary th\u1ee9 hai apps/sudoku_solver/ \u0111\u1ecdc stdin, g\u1ecdi solver, in stdout, k\u00e8m timing b\u1eb1ng std::chrono::steady_clock. Ba, vi\u1ebft GoogleTest suite ba case bao \u0111\u1ee7 happy path, input \u0111\u00e3 m\u00e2u thu\u1eabn ngay t\u1eeb \u0111\u1ea7u, v\u00e0 side-effect contract (c\u00e1i n\u00e0y d\u1ec5 qu\u00ean nh\u1ea5t khi vi\u1ebft solver \u0111\u1ec7 quy).

V\u00ec sao backtracking l\u1ea1i h\u1ee3p v\u1edbi Sudoku

Sudoku v\u1ec1 b\u1ea3n ch\u1ea5t l\u00e0 constraint satisfaction problem. M\u1ed7i \u00f4 tr\u1ed1ng c\u00f3 9 gi\u00e1 tr\u1ecb kh\u1ea3 d\u0129, v\u00e0 m\u1ed7i gi\u00e1 tr\u1ecb b\u1ecb r\u00e0ng bu\u1ed9c b\u1edfi ba t\u1eadp: d\u00f2ng, c\u1ed9t, h\u1ed9p 3x3. Thu\u1eadt to\u00e1n naive l\u00e0 duy\u1ec7t m\u1ecdi t\u1ed5 h\u1ee3p, nh\u01b0ng kh\u00f4ng gian tr\u1ea1ng th\u00e1i l\u00e0 9 m\u0169 s\u1ed1 \u00f4 tr\u1ed1ng, l\u00ean t\u1edbi 9^60 cho puzzle kh\u00f3. Backtracking th\u00f4ng minh h\u01a1n \u1edf ch\u1ed7 n\u00f3 c\u1eaft nh\u00e1nh ngay khi vi ph\u1ea1m constraint thay v\u00ec \u0111i\u1ec1n h\u1ebft r\u1ed3i m\u1edbi ki\u1ec3m tra.

Pseudocode r\u1ea5t ng\u1eafn:

solve(grid):
  t\u00ecm \u00f4 tr\u1ed1ng \u0111\u1ea7u ti\u00ean
  n\u1ebfu kh\u00f4ng c\u00f2n \u00f4 tr\u1ed1ng: \u0111\u00e3 gi\u1ea3i xong
  v\u1edbi m\u1ed7i digit 1..9:
    n\u1ebfu can_place(grid, row, col, digit):
      grid[row][col] = digit
      n\u1ebfu solve(grid): tr\u1ea3 true
      grid[row][col] = 0   // undo b\u1eaft bu\u1ed9c
  tr\u1ea3 false

D\u00f2ng undo ngay sau solve(grid) th\u1ea5t b\u1ea1i l\u00e0 d\u00f2ng quan tr\u1ecdng nh\u1ea5t. N\u1ebfu qu\u00ean, grid s\u1ebd gi\u1eef l\u1ea1i c\u00e1c th\u1eed-sai t\u1eeb nh\u00e1nh tr\u01b0\u1edbc, khi\u1ebfn l\u1ea7n th\u1eed k\u1ebf ti\u1ebfp can_place b\u00e1o sai. \u0110\u00e2y c\u0169ng l\u00e0 ngu\u1ed3n g\u1ed1c c\u1ee7a test case side-effect m\u00e0 ch\u00fang ta s\u1ebd vi\u1ebft.

So v\u1edbi Dancing Links (DLX) c\u1ee7a Donald Knuth, backtracking th\u00f4 ch\u1eadm h\u01a1n cho puzzle si\u00eau kh\u00f3 (hard puzzles AI Escargot m\u1ea5t v\u00e0i gi\u00e2y v\u1edbi naive, v\u00e0i mili-gi\u00e2y v\u1edbi DLX). Nh\u01b0ng cho puzzle b\u00e1o h\u00e0ng ng\u00e0y, backtracking gi\u1ea3i trong kho\u1ea3ng 10 \u0111\u1ebfn 50ms tr\u00ean laptop t\u1ea7m trung. \u0110\u1ed5i l\u1ea1i, code ch\u1ec9 t\u1ed1n d\u01b0\u1edbi 80 d\u00f2ng v\u00e0 \u0111\u1ecdc th\u1eb3ng t\u1eeb pseudocode. V\u1edbi m\u1ee5c ti\u00eau h\u1ecdc, backtracking l\u00e0 l\u1ef1a ch\u1ecdn \u0111\u00fang. DLX \u0111\u1ec3 d\u00e0nh Phase 6 n\u1ebfu c\u1ea7n optimize.

Thi\u1ebft k\u1ebf class Solver v\u1edbi hai entry point

V\u1ea5n \u0111\u1ec1 thi\u1ebft k\u1ebf \u0111\u1ea7u ti\u00ean l\u00e0 API. Khi t\u00edch h\u1ee3p solver v\u00e0o UI (Phase 4 s\u1ebd l\u00e0m), ch\u00fang ta mu\u1ed1n animate t\u1eebng b\u01b0\u1edbc fill cell, ngh\u0129a l\u00e0 c\u1ea7n mutate grid in-place \u0111\u1ec3 render t\u1eebng frame. Nh\u01b0ng khi vi\u1ebft unit test ho\u1eb7c g\u1ecdi solver t\u1eeb CLI, mutate input l\u00e0 ph\u1ea3n t\u1ef1 nhi\u00ean: test c\u1ea7n grid g\u1ed1c l\u00e0m input v\u00e0 grid \u0111\u00e3 gi\u1ea3i l\u00e0m output ri\u00eang bi\u1ec7t \u0111\u1ec3 so s\u00e1nh.

Gi\u1ea3i ph\u00e1p: hai ph\u01b0\u01a1ng th\u1ee9c c\u00f9ng class, g\u1ecdi chung m\u1ed9t core \u0111\u1ec7 quy.

// solver.hpp
#pragma once
#include <optional>
#include "grid.hpp"

class Solver {
public:
    bool solve(Grid& grid) const;
    std::optional<Grid> try_solve(const Grid& grid) const;

private:
    bool solve_recursive(Grid& grid) const;
    bool can_place(const Grid& grid, int row, int col, int digit) const;
    std::optional<std::pair<int, int>> find_empty(const Grid& grid) const;
};

solve(Grid&) nh\u1eadn reference mutable, tr\u1ea3 v\u1ec1 bool \u0111\u01a1n gi\u1ea3n. try_solve(const Grid&) nh\u1eadn const reference, copy grid ra m\u1ed9t b\u1ea3n t\u1ea1m, g\u1ecdi core \u0111\u1ec7 quy l\u00ean b\u1ea3n t\u1ea1m, r\u1ed3i tr\u1ea3 std::optional<Grid> \u0111\u00e3 gi\u1ea3i ho\u1eb7c std::nullopt n\u1ebfu puzzle v\u00f4 nghi\u1ec7m. C\u00fa ph\u00e1p std::optional l\u00e0 c\u00e1ch C++17 ch\u00ednh th\u1ed1ng \u0111\u1ec3 bi\u1ec3u di\u1ec5n "c\u00f3 th\u1ec3 kh\u00f4ng c\u00f3 gi\u00e1 tr\u1ecb", tr\u00e1nh sentinel value nh\u01b0 Grid r\u1ed7ng ho\u1eb7c magic flag. T\u00e0i li\u1ec7u ch\u00ednh th\u1ee9c \u1edf cppreference std::optional li\u1ec7t k\u00ea \u0111\u1ea7y \u0111\u1ee7 semantic move/copy m\u00e0 ch\u00fang ta d\u1ef1a v\u00e0o \u1edf d\u00f2ng return solved.

// solver.cpp
#include "solver.hpp"

bool Solver::solve(Grid& grid) const {
    return solve_recursive(grid);
}

std::optional<Grid> Solver::try_solve(const Grid& grid) const {
    Grid copy = grid;                  // copy ctor preserves Phase-1 invariants
    if (solve_recursive(copy)) {
        return copy;                   // RVO + move ctor of optional
    }
    return std::nullopt;
}

S\u1ef1 t\u00e1ch bi\u1ec7t n\u00e0y r\u1ea5t quan tr\u1ecdng cho test. Khi tester vi\u1ebft solver.try_solve(input), h\u1ecd tin ch\u1eafc r\u1eb1ng input kh\u00f4ng b\u1ecb \u0111\u1ed9ng ch\u1ea1m sau call. Ch\u00fang ta s\u1ebd vi\u1ebft m\u1ed9t test kh\u1eb3ng \u0111\u1ecbnh contract \u0111\u00f3.

Core \u0111\u1ec7 quy: find_empty, can_place, solve_recursive

Ba private helper, m\u1ed7i c\u00e1i d\u01b0\u1edbi 20 d\u00f2ng:

std::optional<std::pair<int, int>> Solver::find_empty(const Grid& grid) const {
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            if (grid.at(row, col) == 0) {
                return std::make_pair(row, col);
            }
        }
    }
    return std::nullopt;
}

bool Solver::can_place(const Grid& grid, int row, int col, int digit) const {
    for (int i = 0; i < 9; ++i) {
        if (grid.at(row, i) == digit) return false;
        if (grid.at(i, col) == digit) return false;
    }
    const int box_row = (row / 3) * 3;
    const int box_col = (col / 3) * 3;
    for (int r = box_row; r < box_row + 3; ++r) {
        for (int c = box_col; c < box_col + 3; ++c) {
            if (grid.at(r, c) == digit) return false;
        }
    }
    return true;
}

bool Solver::solve_recursive(Grid& grid) const {
    const auto empty = find_empty(grid);
    if (!empty) return true;                 // base case: full grid
    const auto [row, col] = *empty;
    for (int digit = 1; digit <= 9; ++digit) {
        if (can_place(grid, row, col, digit)) {
            grid.set(row, col, digit);
            if (solve_recursive(grid)) return true;
            grid.set(row, col, 0);           // undo b\u1eaft bu\u1ed9c
        }
    }
    return false;
}

\u0110o\u1ea1n grid.set(row, col, 0) ngay sau call \u0111\u1ec7 quy tr\u1ea3 false l\u00e0 d\u00f2ng d\u1ec5 b\u1ecb qu\u00ean nh\u1ea5t. N\u1ebfu v\u00f4 t\u00ecnh b\u1ecf, solver v\u1eabn ch\u1ea1y \u0111\u00fang cho test case \u0111\u1ea7u ti\u00ean (v\u00ec base case tr\u1ea3 true tr\u01b0\u1edbc khi t\u1edbi nh\u00e1nh undo), nh\u01b0ng s\u1ebd fail tr\u00ean puzzle kh\u00f3 h\u01a1n v\u00e0 th\u1eadm ch\u00ed tr\u00ean test case m\u00e2u thu\u1eabn. \u0110\u00f3 l\u00e0 l\u00fd do test th\u1ee9 ba c\u1ee7a ch\u00fang ta s\u1ebd targeting \u0111\u00fang d\u00f2ng n\u00e0y.

can_place \u0111\u01b0\u1ee3c vi\u1ebft t\u00e1ch th\u00e0nh ba v\u00f2ng ri\u00eang cho row, col, box \u0111\u1ec3 d\u1ec5 \u0111\u1ecdc. M\u1ed9t s\u1ed1 implementation g\u1ed9p row v\u00e0 col v\u00e0o c\u00f9ng v\u00f2ng, hay h\u01a1n 2-3 ns nh\u01b0ng kh\u00f3 \u0111\u1ecdc. \u1ede Phase 3 ch\u00fang ta \u01b0u ti\u00ean clarity. N\u1ebfu Phase 6 c\u1ea7n optimize, h\u1ed3 s\u01a1 profiling s\u1ebd ch\u1ec9 \u0111i\u1ec3m: th\u01b0\u1eddng find_empty l\u00e0 hotspot l\u1edbn h\u01a1n can_place.

Binary th\u1ee9 hai: apps/sudoku_solver

Phase 1 \u0111\u00e3 c\u00f3 apps/sudoku_validator/. B\u00e2y gi\u1edd th\u00eam apps/sudoku_solver/ \u0111\u1ec3 ch\u1ea1y solver t\u1eeb CLI. Layout sau Phase 3:

sudoku/
\u251c\u2500\u2500 CMakeLists.txt
\u251c\u2500\u2500 src/
\u2502   \u251c\u2500\u2500 grid.cpp
\u2502   \u251c\u2500\u2500 validator.cpp
\u2502   \u2514\u2500\u2500 solver.cpp
\u251c\u2500\u2500 include/
\u2502   \u251c\u2500\u2500 grid.hpp
\u2502   \u251c\u2500\u2500 validator.hpp
\u2502   \u2514\u2500\u2500 solver.hpp
\u251c\u2500\u2500 apps/
\u2502   \u251c\u2500\u2500 sudoku_validator/main.cpp
\u2502   \u2514\u2500\u2500 sudoku_solver/main.cpp
\u2514\u2500\u2500 tests/
    \u251c\u2500\u2500 grid_test.cpp
    \u251c\u2500\u2500 validator_test.cpp
    \u2514\u2500\u2500 solver_test.cpp

Trong CMakeLists.txt:

add_executable(sudoku_solver apps/sudoku_solver/main.cpp)
target_link_libraries(sudoku_solver PRIVATE sudoku_core)
target_include_directories(sudoku_solver PRIVATE include)

V\u00e0 apps/sudoku_solver/main.cpp:

#include <chrono>
#include <iostream>
#include <string>
#include "grid.hpp"
#include "solver.hpp"

int main() {
    Grid input;
    for (int row = 0; row < 9; ++row) {
        std::string line;
        if (!std::getline(std::cin, line) || line.size() < 9) {
            std::cerr << "expected 9 lines of 9 digits each\
";
            return 1;
        }
        for (int col = 0; col < 9; ++col) {
            const char ch = line[col];
            input.set(row, col, ch == '.' ? 0 : ch - '0');
        }
    }

    const auto start = std::chrono::steady_clock::now();
    Solver solver;
    const auto result = solver.try_solve(input);
    const auto elapsed = std::chrono::steady_clock::now() - start;

    if (!result) {
        std::cerr << "no solution\
";
        return 2;
    }
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            std::cout << result->at(row, col);
        }
        std::cout << '\
';
    }
    const auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(elapsed).count();
    std::cerr << "solved in " << ms << "ms\
";
    return 0;
}

Hai l\u1ef1a ch\u1ecdn nh\u1ecf \u0111\u00e1ng \u0111\u1ec3 \u00fd. Th\u1ee9 nh\u1ea5t, d\u00f9ng try_solve ch\u1ee9 kh\u00f4ng ph\u1ea3i solve. CLI l\u00e0 pure flow stdin-stdout, kh\u00f4ng c\u00f3 g\u00ec \u0111\u1ec3 mutate s\u1eb5n, n\u00ean contract no-side-effect kh\u1edbp t\u1ef1 nhi\u00ean. Th\u1ee9 hai, timing in ra stderr ch\u1ee9 kh\u00f4ng ph\u1ea3i stdout. Stdout l\u00e0 \u0111\u01b0\u1eddng gi\u1ea3i \u0111\u00e3 \u0111i\u1ec1n, m\u1ed9t tool kh\u00e1c c\u00f3 th\u1ec3 pipe l\u1ea1i \u0111\u1ec3 verify (./sudoku_solver < puzzle.txt | ./sudoku_validator). Tr\u1ed9n timing v\u00e0o stdout s\u1ebd ph\u00e1 pipeline.

std::chrono::steady_clock l\u00e0 l\u1ef1a ch\u1ecdn \u0111\u00fang cho measure duration v\u00ec n\u00f3 monotonic, kh\u00f4ng b\u1ecb NTP nh\u1ea3y ng\u01b0\u1ee3c nh\u01b0 system_clock. T\u00e0i li\u1ec7u \u1edf cppreference steady_clock nh\u1ea5n m\u1ea1nh \u0111i\u1ec3m n\u00e0y. M\u1ed9t sai l\u1ea7m ph\u1ed5 bi\u1ebfn l\u00e0 d\u00f9ng system_clock \u0111\u1ec3 \u0111o time-elapsed r\u1ed3i g\u1eb7p \u00e2m khi m\u00e1y \u0111\u1ed3ng b\u1ed9 gi\u1edd.

GoogleTest suite: ba case bao qu\u00e1t contract

GoogleTest l\u00e0 framework test C++ ph\u1ed5 bi\u1ebfn nh\u1ea5t, repo ch\u00ednh th\u1ee9c t\u1ea1i github.com/google/googletest. Phase 1 ch\u00fang ta \u0111\u00e3 wire n\u00f3 v\u00e0o CMake b\u1eb1ng FetchContent. B\u00e2y gi\u1edd th\u00eam tests/solver_test.cpp:

#include <gtest/gtest.h>
#include "grid.hpp"
#include "solver.hpp"

namespace {

Grid make_grid(const std::array<std::string, 9>& rows) {
    Grid g;
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            const char ch = rows[row][col];
            g.set(row, col, ch == '.' ? 0 : ch - '0');
        }
    }
    return g;
}

}  // namespace

TEST(SolverTest, SolvesEasyPuzzle) {
    const Grid input = make_grid({{
        "53..7....", "6..195...", ".98....6.",
        "8...6...3", "4..8.3..1", "7...2...6",
        ".6....28.", "...419..5", "....8..79"
    }});
    Solver solver;
    const auto result = solver.try_solve(input);
    ASSERT_TRUE(result.has_value());
    EXPECT_EQ(result->at(0, 2), 4);
    EXPECT_EQ(result->at(8, 8), 9);
}

TEST(SolverTest, ReturnsNulloptOnContradiction) {
    Grid input;
    input.set(0, 0, 5);
    input.set(0, 1, 5);                 // hai s\u1ed1 5 tr\u00ean c\u00f9ng d\u00f2ng, v\u00f4 nghi\u1ec7m
    Solver solver;
    const auto result = solver.try_solve(input);
    EXPECT_FALSE(result.has_value());
}

TEST(SolverTest, TrySolveDoesNotMutateInput) {
    Grid input = make_grid({{
        "53..7....", "6..195...", ".98....6.",
        "8...6...3", "4..8.3..1", "7...2...6",
        ".6....28.", "...419..5", "....8..79"
    }});
    const Grid before = input;
    Solver solver;
    (void) solver.try_solve(input);
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            EXPECT_EQ(input.at(row, col), before.at(row, col))
                << "input changed at (" << row << ',' << col << ')';
        }
    }
}

Test m\u1ed9t l\u00e0 happy path, d\u00f9ng puzzle n\u1ed5i ti\u1ebfng nh\u1ea5t internet (puzzle Wikipedia). Ch\u00fang ta kh\u00f4ng assert to\u00e0n b\u1ed9 81 \u00f4, ch\u1ec9 v\u00e0i \u00f4 \u0111\u1ea1i di\u1ec7n. L\u00fd do th\u1ef1c d\u1ee5ng: n\u1ebfu solver ph\u00e1 nh\u00e1nh sai, \u00f4 (0,2) ho\u1eb7c (8,8) s\u1ebd l\u1ec7ch v\u00e0 test fail r\u00f5 ngay; c\u00f2n assert \u0111\u1ea7y \u0111\u1ee7 81 \u00f4 khi test fail s\u1ebd in ra 81 d\u00f2ng error message r\u1ea5t kh\u00f3 \u0111\u1ecdc.

Test hai l\u00e0 negative case. Input c\u00f3 hai s\u1ed1 5 c\u00f9ng d\u00f2ng n\u00ean kh\u00f4ng th\u1ec3 c\u00f3 nghi\u1ec7m. Solver ph\u1ea3i tr\u1ea3 std::nullopt ch\u1ee9 kh\u00f4ng ph\u1ea3i crash, kh\u00f4ng ph\u1ea3i v\u00f2ng l\u1eb7p v\u00f4 t\u1eadn. C\u00e1i n\u00e0y verify r\u1eb1ng can_place \u0111ang \u0111\u01b0\u1ee3c g\u1ecdi ngay t\u1eeb initial state, kh\u00f4ng ph\u1ea3i ch\u1ec9 tr\u00ean c\u00e1c \u00f4 tr\u1ed1ng.

Test ba l\u00e0 side-effect contract. \u0110\u00e2y l\u00e0 test kh\u00f3 nh\u1edb vi\u1ebft nh\u1ea5t v\u00ec n\u00f3 ki\u1ec3m tra m\u1ed9t th\u1ee9 "kh\u00f4ng x\u1ea3y ra". N\u00f3 l\u00e0 ph\u00f2ng th\u1ee7 tr\u1ef1c ti\u1ebfp cho c\u00e1i d\u00f2ng Grid copy = grid; trong try_solve. N\u1ebfu m\u1ed9t ng\u00e0y n\u00e0o \u0111\u00f3 ai \u0111\u00f3 refactor cho "t\u1ed1i \u01b0u" b\u1eb1ng c\u00e1ch b\u1ecf copy v\u00e0 g\u1ecdi th\u1eb3ng solve_recursive(const_cast<Grid&>(grid)), test n\u00e0y s\u1ebd scream ngay.

Build v\u00e0 ch\u1ea1y

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build --output-on-failure

Tr\u00ean laptop Apple M-series ho\u1eb7c Ryzen 5000 series, puzzle Wikipedia n\u00f3i tr\u00ean gi\u1ea3i d\u01b0\u1edbi 5ms v\u1edbi Release build. Test suite ch\u1ea1y g\u1ecdn d\u01b0\u1edbi 50ms. Khi m\u1edf Phase 4 (UI), ch\u00fang ta s\u1ebd link l\u1ea1i sudoku_core v\u00e0 g\u1ecdi solve(Grid&) thay v\u00ec try_solve \u0111\u1ec3 m\u1ed7i step c\u00f3 th\u1ec3 trigger redraw.

B\u1eaby th\u01b0\u1eddng g\u1eb7p

L\u1ed7i \u0111\u1ea7u ti\u00ean hay g\u1eb7p l\u00e0 qu\u00ean grid.set(row, col, 0) \u1edf nh\u00e1nh undo. Nh\u01b0 \u0111\u00e3 n\u00f3i, l\u1ed7i n\u00e0y \u00e2m th\u1ea7m v\u00ec happy-path v\u1eabn pass. Test ba che \u0111\u01b0\u1ee3c nh\u01b0ng c\u0169ng c\u1ea7n \u00fd th\u1ee9c r\u1eb1ng "happy test pass" kh\u00f4ng b\u1eb1ng "solver \u0111\u00fang".

L\u1ed7i th\u1ee9 hai l\u00e0 g\u1ecdi \u0111\u1ec7 quy qu\u00e1 s\u00e2u kh\u00f4ng c\u00f3 guard. Sudoku 9x9 s\u00e2u nh\u1ea5t 81 frame, kh\u00f4ng g\u1ea7n stack limit. Nh\u01b0ng n\u1ebfu generalize cho 16x16 ho\u1eb7c 25x25 (Phase 7 tham v\u1ecdng), 256 ho\u1eb7c 625 frame m\u1edbi \u0111\u1ee5ng gi\u1edbi h\u1ea1n 1MB stack default, v\u1eabn an to\u00e0n nh\u01b0ng c\u1ea7n benchmark.

L\u1ed7i th\u1ee9 ba l\u00e0 d\u00f9ng std::system_clock thay steady_clock cho timing. \u0110\u00e3 nh\u1eafc b\u00ean tr\u00ean. \u0110\u1ed1i chi\u1ebfu hai lo\u1ea1i clock l\u1ea7n \u0111\u1ea7u t\u1ed1n 10 ph\u00fat Google, nh\u01b0ng sau khi n\u1eafm s\u1ebd l\u00e0 ph\u1ea3n x\u1ea1.

L\u1ed7i th\u1ee9 t\u01b0, tinh t\u1ebf h\u01a1n, l\u00e0 copy Grid trong try_solve n\u1ebfu Grid ch\u01b0a c\u00f3 copy ctor \u0111\u00fang. \u1ede Phase 1, n\u1ebfu ch\u00fang ta \u0111\u1ec3 default copy ctor cho Grid ch\u1ee9a std::array<std::array<int, 9>, 9>, m\u1ecdi th\u1ee9 \u1ed5n. Nh\u01b0ng n\u1ebfu Phase 4 th\u00eam raw pointer cho cache, copy n\u00f4ng s\u1ebd g\u00e2y double-free. \u0110\u00e2y l\u00e0 d\u1ecbp t\u1ed1t \u0111\u1ec3 confirm Rule-of-Zero hay Rule-of-Five.

T\u00f3m t\u1eaft v\u00e0 b\u01b0\u1edbc ti\u1ebfp

Sau Phase 3, d\u1ef1 \u00e1n c\u00f3 ba module (grid, validator, solver) t\u1ed5ng c\u1ed9ng d\u01b0\u1edbi 250 d\u00f2ng C++, hai binary CLI, v\u00e0 m\u1ed9t test suite m\u01b0\u1eddi-m\u1ea5y assertion. Solver naive backtracking \u0111\u1ee7 nhanh cho m\u1ecdi puzzle c\u00f3 th\u1ec3 \u0111\u0103ng b\u00e1o, \u0111\u1ee7 ng\u1eafn \u0111\u1ec3 \u0111\u1ecdc trong m\u1ed9t b\u1eefa \u0103n.

Phase 4 s\u1ebd k\u1ebft n\u1ed1i solver v\u00e0o m\u1ed9t UI t\u1ed1i gi\u1ea3n (SDL2 ho\u1eb7c ImGui) v\u00e0 animate t\u1eebng set \u0111\u1ec3 h\u1ecdc c\u00e1ch t\u00e1ch logic kh\u1ecfi rendering. Phase 5 th\u00eam puzzle generator (\u0111\u1ea3o ng\u01b0\u1ee3c solver). Phase 6 m\u1edbi ch\u1ea1m \u0111\u1ebfn DLX n\u1ebfu profiling cho th\u1ea5y backtracking l\u00e0 bottleneck th\u1eadt. M\u1ed7i phase ch\u1ec9 m\u1ed9t class m\u1edbi, m\u1ed7i class ch\u1ec9 v\u00e0i ch\u1ee5c d\u00f2ng. \u0110\u00f3 l\u00e0 c\u00e1ch build incremental: vi\u1ebft \u00edt, test s\u1edbm, refactor khi \u0111\u00e3 c\u00f3 ba implementation t\u01b0\u01a1ng t\u1ef1 ch\u1ee9 kh\u00f4ng ph\u1ea3i sau implementation \u0111\u1ea7u ti\u00ean.

References: