Challenge này thuộc khóa học Operations Research – Giải Các Challenges Tối Ưu Trong Thực Tế
Constraint Programming (CP) là phương pháp giải bài toán bằng cách khai báo điều kiện (ràng buộc) rồi để máy tự tìm đáp án thỏa mãn tất cả điều kiện đó.
TIẾN TRÌNH:
Bước 1 Bước 2 Bước 3
Mô hình hóa → Thu hẹp → Gán ô
(3 yếu tố CP) miền xác định
│ │
│ ┌──────────┘
▼ ▼
Bước 4 Bước 5
Lan truyền → Bảng dễ
dây chuyền giải xong.
│
Bảng khó?
│
▼
Bước 6
Search +
Backtracking
Quy Tắc Sudoku
Bảng Sudoku gồm 9 hàng, 9 cột, và 9 box (khung 3×3 in đậm). Quy tắc duy nhất: mỗi hàng, mỗi cột, mỗi box phải chứa đủ 9 số từ 1 đến 9, không trùng.
+-------+-------+-------+
| Box 1 | Box 2 | Box 3 |
| | | |
| | | |
+-------+-------+-------+
| Box 4 | Box 5 | Box 6 |
| | | |
| | | |
+-------+-------+-------+
| Box 7 | Box 8 | Box 9 |
| | | |
| | | |
+-------+-------+-------+
Mỗi box = 1 khung 3×3 ô.
Đánh số từ trái sang phải, trên xuống dưới.
Bảng Sudoku Cần Giải – Vừa Thực Hành Vừa Học Từng Bước
+-------+-------+-------+
| 5 3 . | . 7 . | . . . |
| 6 . . | 1 9 5 | . . . |
| . 9 8 | . . . | . 6 . |
+-------+-------+-------+
| 8 . . | . 6 . | . . 3 |
| 4 . . | 8 . 3 | . . 1 |
| 7 . . | . 2 . | . . 6 |
+-------+-------+-------+
| . 6 . | . . . | 2 8 . |
| . . . | 4 1 9 | . . 5 |
| . . . | . 8 . | . 7 9 |
+-------+-------+-------+
(Dấu chấm = ô trống cần điền)
51 ô trống, 30 ô đã điền.
Bước 1: Mô Hình Hóa Sudoku Bằng CP
Lý Thuyết Cần Biết
CP cần đúng 3 thứ để giải bất kỳ bài toán nào:
┌────────────────────────────────────────────────┐
│ 3 YẾU TỐ CỦA CP: │
│ │
│ 1. BIẾN = những thứ cần tìm │
│ 2. MIỀN = tập lựa chọn của mỗi biến │
│ 3. RÀNG BUỘC = quy tắc phải tuân theo │
└────────────────────────────────────────────────┘
Giải thích:
- Biến: mỗi biến đại diện 1 thứ chưa biết, cần tìm giá trị → Trong Sudoku: mỗi ô trống là 1 biến.
- Miền: tập hợp tất cả giá trị mà biến đó có thể nhận → Trong Sudoku: ban đầu mỗi ô trống có thể là 1 đến 9.
- Ràng buộc: điều kiện mà lời giải phải thỏa mãn → Trong Sudoku: các số trong cùng hàng/cột/box không được trùng.
- Mô hình hóa = dịch bài toán thực tế sang 3 yếu tố trên → Khi đã có đủ 3 yếu tố, solver tự động tìm đáp án.
Áp Dụng Lên Sudoku
MÔ HÌNH CP CHO BẢNG SUDOKU:
┌──────────────────────────────────────────────┐
│ │
│ BIẾN: 81 ô → gọi tên r{hàng}c{cột} │
│ hàng = 1..9, cột = 1..9 │
│ Ví dụ: r1c1 = ô hàng 1, cột 1 │
│ r5c3 = ô hàng 5, cột 3 │
│ │
│ MIỀN: Ô trống → {1,2,3,4,5,6,7,8,9} │
│ Ô đã điền → {giá trị đó} │
│ Ví dụ: r1c1 = {5} (đã điền) │
│ r1c3 = {1..9} (trống) │
│ │
│ RÀNG BUỘC: mỗi hàng — 9 số khác nhau │
│ mỗi cột — 9 số khác nhau │
│ mỗi box — 9 số khác nhau │
│ │
│ → Tổng: 27 ràng buộc "tất cả khác nhau" │
│ (9 hàng + 9 cột + 9 box) │
└──────────────────────────────────────────────┘
Ràng buộc “tất cả khác nhau” trong CP gọi là AllDifferent. Thay vì viết 36 cặp “ô A ≠ ô B” cho 1 hàng, chỉ cần 1 câu:
AllDifferent cho 1 hàng:
CŨ: ô1≠ô2, ô1≠ô3, ... ô8≠ô9 = 36 ràng buộc (9 ô, mỗi cặp khác nhau = 9*8/2 = 36 cặp)
MỚI: AllDifferent(ô1, ô2, ..., ô9) = 1 ràng buộc
Cả bảng: CŨ = 36 × 27 = 972 ràng buộc
MỚI = 27 AllDifferent
Bảng Sudoku = 81 biến + miền {1..9} + 27 AllDifferent. Đã có đủ 3 yếu tố. Bắt đầu áp dụng CP giải.
Bước 2: Thu Hẹp Miền — Loại Số Không Thể
Mục đích: giảm số lượng lựa chọn của mỗi ô trước khi tìm lời giải. Càng ít lựa chọn còn lại → càng nhanh tìm được giá trị đúng.
Lý Thuyết Cần Biết
THU HẸP MIỀN (Domain Reduction):
Mỗi ô trống thuộc 1 hàng + 1 cột + 1 box.
Số nào ĐÃ XUẤT HIỆN trong hàng/cột/box đó → CHẮC CHẮN không thể điền vào ô này → LOẠI.
Áp Dụng: Phân Tích Ô r1c4
+-------+-------+-------+
| 5 3 . |[?] 7 .| . . . | ← hàng 1
| 6 . . | 1 9 5| . . . |
| . 9 8 | . . .| . 6 . |
+-------+-------+-------+
| 8 . . | . 6 .| . . 3 |
| 4 . . | 8 . 3| . . 1 | cột 4 ↕
| 7 . . | . 2 .| . . 6 |
+-------+-------+-------+
| . 6 . | . . .| 2 8 . |
| . . . | 4 1 9| . . 5 |
| . . . | . 8 .| . 7 9 |
+-------+-------+-------+
Ô r1c4 = [?]
Hàng 1 đã có: {3, 5, 7}
Cột 4 đã có: {1, 4, 8}
Box 2 đã có: {1, 5, 7, 9}
Quá trình loại trừ từng bước:
{1 2 3 4 5 6 7 8 9} ← 9 lựa chọn
│
│ Hàng 1 loại: 3, 5, 7
▼
{1 2 · 4 · 6 · 8 9} ← 6 còn
│
│ Cột 4 loại: 1, 4, 8
▼
{· 2 · · · 6 · · 9} ← 3 còn
│
│ Box 2 loại: 9
▼
╔═══════╗
║ {2,6} ║ ← 2 lựa chọn.
╚═══════╝
Từ 9 lựa chọn cho xuống 2 lựa chọn — chưa xác định ngay, nhưng đã thu hẹp đáng kể.
Làm tương tự cho tất cả 51 ô trống còn lại (Code Python sẽ tự chạy)
SAU THU HẸP MIỀN — BẢNG MIỀN LẦN ĐẦU:
(Cách đọc: ô ghi 1 số = đã xác định.
Ô ghi nhiều số, ví dụ "124" = còn 3 lựa chọn: 1, 2, hoặc 4.)
c1 c2 c3 c4 c5 c6 c7 c8 c9
+---------------------+------------------+--------------------+
r1 | 5 3 124 | 26 7 2468 | 1489 1249 248 |
r2 | 6 247 247 | 1 9 5 | 3478 234 2478 |
r3 | 12 9 8 | 23 34 24 | 13457 6 247 |
+---------------------+------------------+--------------------+
r4 | 8 125 1259 | 579 6 147 | 4579 2459 3 |
r5 | 4 25 2569 | 8 5 3 | 579 259 1 |
r6 | 7 15 1359 | 59 2 14 | 4589 459 6 |
+---------------------+------------------+--------------------+
r7 | 139 6 13457 | 357 35 7 | 2 8 4 |
r8 | 23 278 237 | 4 1 9 | 36 3 5 |
r9 | 123 1245 12345 | 2356 8 26 | 1346 7 9 |
+---------------------+------------------+--------------------+
Kiểm tra bảng — tìm ô chỉ còn 1 số. Ô nào chỉ ghi 1 chữ số duy nhất (không phải số cho sẵn ban đầu) → ô đó đã xác định và có thể gán ngay.
Bước 3: Gán Ô Xác Định
Lý Thuyết Cần Biết
NAKED SINGLE:
Nếu miền của 1 ô chỉ còn ĐÚNG 1 giá trị → GÁN giá trị đó ngay — không cần đoán.
Tại sao chắc chắn đúng? Vì tất cả giá trị khác đã bị loại bởi ràng buộc hàng/cột/box. Chỉ còn 1 giá trị khả thi duy nhất → giá trị đó bắt buộc phải đúng.
Áp Dụng
TÌM Ô CHỈ CÒN 1 GIÁ TRỊ:
r5c5 = {5} ← chỉ 1 số → GÁN r5c5 = 5
r7c6 = {7} ← chỉ 1 số → GÁN r7c6 = 7
r7c9 = {4} ← chỉ 1 số → GÁN r7c9 = 4
r8c8 = {3} ← chỉ 1 số → GÁN r8c8 = 3
→ 4 ô xác định tức thì sau vòng 1.
Đánh dấu trên bảng:
c1 c2 c3 c4 c5 c6 c7 c8 c9
+----------------+---------------+----------------+
r5 | 4 25 2569| 8 [5] 3 | 579 259 1|
+----------------+---------------+----------------+
r7 | 139 6 13457| 357 35 [7]| 2 8 [4]|
r8 | 23 278 237| 4 1 9| 36 [3] 5|
+----------------+---------------+----------------+
[ ] = ô vừa xác định → gán ngay
4 ô đã gán. Mỗi gán tạo thông tin mới → các ô lân cận cần loại số vừa gán. Xem tiếp Bước 4.
Bước 4: Lan Truyền Dây Chuyền — 1 Gán Kéo Theo Nhiều Gán
Đây là kỹ thuật mạnh nhất của CP. Khi gán 1 ô, giá trị đó bị loại khỏi các ô cùng hàng/cột/box. Việc loại này có thể làm ô khác còn đúng 1 giá trị → gán tiếp → loại tiếp → tạo chuỗi gán liên tục tự động.
Lý Thuyết Cần Biết
LAN TRUYỀN RÀNG BUỘC (Constraint Propagation):
Gán 1 ô → loại giá trị đó khỏi hàng/cột/box
→ ô khác có thể bị thu hẹp còn 1 giá trị
→ gán tiếp → loại tiếp → gán tiếp...
→ GÁN LIÊN TIẾP TỰ ĐỘNG.
Áp Dụng: Gán r5c5 = 5 → Giải Cả Hàng 5
Bắt đầu từ r5c5 = 5. Loại 5 khỏi hàng 5, cột 5, box 5:
GÁN: r5c5 = 5
──── HÀNG 5 ────
TRƯỚC: | 4 25 2569 | 8 [5] 3 | 579 259 1 |
SAU: | 4 {2} {269} | 8 5 3 |{79} {29} 1 |
↑
r5c2: {2,5} → loại 5 → {2} → GÁN LUÔN
──── CỘT 5 ────
r7c5: {3,5} → loại 5 → {3} → GÁN LUÔN
──── BOX 5 ────
r6c4: {5,9} → loại 5 → {9} → GÁN LUÔN
Tiếp tục lan truyền từ các ô vừa gán:
Lan truyền từ r5c2 = 2:
r5c8: {2,9} → loại 2 → {9} → GÁN LUÔN
Lan truyền từ r5c8 = 9:
r5c3: {2,6,9} → loại 9 (vì r5c8=9, cùng hàng 5)
→ loại 2 (vì r5c2=2, cùng hàng 5)
→ {6} → GÁN LUÔN
r5c7: {5,7,9} → loại 9 (vì r5c8=9, cùng hàng 5)
→ loại 5 (vì r5c5=5, cùng hàng 5)
→ {7} → GÁN LUÔN
Toàn bộ chuỗi — nhìn tổng thể:
LAN TRUYỀN TỪ 1 GÁN:
r5c5=5 ──┬──► r5c2=2 ──► r5c8=9 ──┬──► r5c3=6
│ └──► r5c7=7
├──► r7c5=3
└──► r6c4=9
KẾT QUẢ: 1 gán → lan truyền thêm 6 gán = 7 ô xác định
Hàng 5 giải xong hoàn toàn:
TRƯỚC: | 4 . . | 8 . 3 | . . 1 |
SAU: | 4 2 6 | 8 5 3 | 7 9 1 |Sau khi gán được vào 1 ô, tiếp tục lan truyền → Bảng miền thu hẹp dần — ô xác định tăng, ô trống giảm.
Với bảng Sudoku này — chỉ cần lan truyền giải hoàn toàn trong 10 đợt lan truyền. Tuy nhiên, trong một số case Sudoku khác, phải kết hợp thêm với bước Search + Backtracking vì không thể thu hẹp xuống còn 1 lựa chọn được. Bạn sẽ học Search + Backtracking trong challenge tiếp theo.
Bước 5: Hoàn Thành — Bảng Dễ Giải Xong Bằng Lan Truyền
BẢNG SUDOKU ĐÃ GIẢI:
+-------+-------+-------+
| 5 3 4 | 6 7 8 | 9 1 2 |
| 6 7 2 | 1 9 5 | 3 4 8 |
| 1 9 8 | 3 4 2 | 5 6 7 |
+-------+-------+-------+
| 8 5 9 | 7 6 1 | 4 2 3 |
| 4 2 6 | 8 5 3 | 7 9 1 |
| 7 1 3 | 9 2 4 | 8 5 6 |
+-------+-------+-------+
| 9 6 1 | 5 3 7 | 2 8 4 |
| 2 8 7 | 4 1 9 | 6 3 5 |
| 3 4 5 | 2 8 6 | 1 7 9 |
+-------+-------+-------+
Kiểm tra:
✓ Mỗi hàng: 9 số khác nhau (AllDifferent)
✓ Mỗi cột: 9 số khác nhau (AllDifferent)
✓ Mỗi box: 9 số khác nhau (AllDifferent)
Tóm tắt quy trình đã dùng
DÙNG GÌ ĐỂ GIẢI?
Bước 1: Mô hình hóa → Biến + Miền + AllDifferent
Bước 2: Thu hẹp miền → Loại số theo hàng/cột/box
Bước 3: Naked Singles → Gán ô chỉ còn 1 số
Bước 4: Lan truyền → 1 gán → loại → gán tiếp
Kỹ thuật CHƯA CẦN dùng: Search, Backtracking
→ Bảng này đủ dễ để lan truyền giải hết.Code Python
"""
Mapping kiến thức → code:
cp-01.md Code
───────────────────── ──────────────────────────────────
Bước 1 — Mô hình hóa
81 biến (ô trống) new_int_var(1, 9, ...) [A]
Miền cố định (đề bài) new_int_var(v, v, ...) [B]
27 AllDifferent add_all_different(...) [C]
Bước 2 — Thu hẹp miền solver tự làm khi gọi solve() [D]
Bước 3 — Naked Singles solver tự làm khi gọi solve() [D]
Bước 4 — Lan truyền solver tự làm khi gọi solve() [D]
Bước 6 — Search+Quay lui solver tự làm khi gọi solve() [D]
→ Chỉ khai báo MÔ HÌNH (Bước 1).
Bước 2-6 solver thực hiện tự động bên trong solve().
Cài đặt: pip install ortools
"""
# Nạp thư viện CP-SAT từ Google OR-Tools.
# Thư viện này chứa sẵn solver để giải bài toán CP.
from ortools.sat.python import cp_model
# Nạp NumPy — dùng mảng 2 chiều để thao tác hàng/cột/box
import numpy as np
# Dữ liệu đầu vào
# Dùng np.array: grid[r, :] (hàng), grid[:, c] (cột), grid[r:r+3, c:c+3] (box).
# Số 0 = ô trống (chưa biết, cần tìm).
# Số 1-9 = ô đề bài (đã biết, cố định).
PUZZLE = np.array([
[5, 3, 0, 0, 7, 0, 0, 0, 0], # hàng 1
[6, 0, 0, 1, 9, 5, 0, 0, 0], # hàng 2
[0, 9, 8, 0, 0, 0, 0, 6, 0], # hàng 3
[8, 0, 0, 0, 6, 0, 0, 0, 3], # hàng 4
[4, 0, 0, 8, 0, 3, 0, 0, 1], # hàng 5
[7, 0, 0, 0, 2, 0, 0, 0, 6], # hàng 6
[0, 6, 0, 0, 0, 0, 2, 8, 0], # hàng 7
[0, 0, 0, 4, 1, 9, 0, 0, 5], # hàng 8
[0, 0, 0, 0, 8, 0, 0, 7, 9], # hàng 9
])
def solve_sudoku(grid: np.ndarray, name: str = "Sudoku") -> None:
"""
Tham số:
grid — np.array 9×9, giá trị 0 = ô trống
name — tên hiển thị khi in kết quả
"""
# Tạo mô hình CP rỗng.
model = cp_model.CpModel()
# [A][B] BƯỚC 1 — KHAI BÁO BIẾN (cp-01: "Mỗi ô = 1 biến")
# Dùng np.empty 9×9 kiểu object để chứa 81 biến IntVar.
cells = np.empty((9, 9), dtype=object)
# Duyệt 81 ô bằng np.ndindex
# np.ndindex(9,9) cho ra: (0,0), (0,1), ..., (8,8)
for r, c in np.ndindex(9, 9):
v = grid[r, c] # giá trị ô đề bài (0 = trống)
if v: # v != 0 → ô đề bài
# [B] Ô ĐỀ BÀI: miền cố định = {v}
# Ví dụ: v=5 → new_int_var(5, 5) — chỉ có thể = 5
cells[r, c] = model.new_int_var(v, v, f"c({r+1},{c+1})")
else: # v == 0 → ô trống
# [A] Ô TRỐNG: miền {1..9} — solver sẽ tìm giá trị
cells[r, c] = model.new_int_var(1, 9, f"c({r+1},{c+1})")
# [C] BƯỚC 1 (tiếp) — RÀNG BUỘC AllDifferent
# 27 AllDifferent = 9 hàng + 9 cột + 9 box
# cells[i, :] = hàng i
# cells[:, i] = cột i
for i in range(9):
# 9 hàng: cells[i, :] cắt trọn hàng i → mảng 9 biến
model.add_all_different(cells[i, :])
# 9 cột: cells[:, i] cắt trọn cột i → mảng 9 biến
model.add_all_different(cells[:, i])
# 9 box 3×3: cells[r:r+3, c:c+3] cắt box → mảng 3×3
# .flat biến thành 9 phần tử (add_all_different cần 1 chiều)
for br in range(0, 9, 3): # br = 0, 3, 6
for bc in range(0, 9, 3): # bc = 0, 3, 6
model.add_all_different(cells[br:br+3, bc:bc+3].flat)
# [D] BƯỚC 2→6 — SOLVER TỰ GIẢI
solver = cp_model.CpSolver()
status = solver.solve(model)
# IN KẾT QUẢ — dùng np.vectorize
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
# np.vectorize áp dụng solver.value() lên toàn bộ mảng
# cells 9×9 → result 9×9 chứa số nguyên.
result = np.vectorize(solver.value)(cells)
print(f"\n{name} — LỜI GIẢI:")
print("+-------+-------+-------+")
for r in range(9):
# Cắt 3 khối mỗi khối 3 số, nối bằng " | "
# Ví dụ: [5,3,4] → "5 3 4" → "| 5 3 4 | 6 7 8 | 9 1 2 |"
parts = [" ".join(map(str, result[r, c:c+3]))
for c in range(0, 9, 3)]
print(f"| {' | '.join(parts)} |")
if r % 3 == 2:
print("+-------+-------+-------+")
else:
print(f"\n{name} — Không tìm được lời giải.")
# CHẠY CHƯƠNG TRÌNH
if __name__ == "__main__":
solve_sudoku(PUZZLE, "Kết Quả")
