Trò chơi 3: Giải Sudoku bằng quay lui trong C++ và Python: kiểm tra ô hợp lệ, cắt nhánh MRV và bitmask

Series: Thuật toán qua trò chơi Độ khó: Trung bình Trò chơi 3 / Thuật toán qua trò chơi Quay lui Bitmask

// Thuật toán qua trò chơi · Trò chơi 3

Sudoku: dạy máy tính giải mọi đề bằng quay lui

Một đề Sudoku khó có thể làm em mất cả buổi tối. Máy tính chỉ cần vài phần nghìn giây, và bí quyết của nó chỉ là thuật toán quay lui em đã học, cộng thêm hai mẹo cắt nhánh rất gọn.

Lời mở đầu

Sudoku có lẽ là trò chơi trí tuệ phổ biến nhất thế giới: một tờ báo, một cây bút chì là đủ. Luật chơi chỉ có ba dòng, vậy mà có những đề khiến người chơi lâu năm phải ngồi cả tiếng. Thế máy tính giải Sudoku như thế nào? Câu trả lời có thể làm em bất ngờ: máy không thông minh chút nào cả. Nó chỉ thử rất nhanh, và biết quay lại đúng lúc khi đi vào ngõ cụt. Đó chính là thuật toán quay lui mà em đã gặp ở bài 15: Đệ quy và quay lui với bài toán N quân hậu.

Ở Trò chơi 2: Mê cung, em đã dùng DFS đi trong mê cung, gặp ngõ cụt thì lùi lại. Sudoku cũng là một mê cung, chỉ khác là mỗi “ngã rẽ” là một con số. Hôm nay em sẽ tự tay chơi, rồi xem máy giải từng bước, và cuối cùng làm máy chạy nhanh hơn hàng trăm lần nhờ hai mẹo: chọn ô ít lựa chọn nhất trước, và lưu hàng, cột, khối bằng bitmask của bài 20: Thao tác bit.

Trò chơi 1Tháp Hà Nội Trò chơi 2Mê cung Trò chơi 3Sudoku Trò chơi 4Game 2048 Trò chơi 5Cờ caro

Trong bài này bạn sẽ học: luật Sudoku 9 × 9 và bản 4 × 4 cho người mới; một bàn Sudoku chơi được ngay trên trang có gợi ý và máy giải; hàm kiểm tra một ô theo hàng, cột, khối và công thức tìm khối 3 × 3; giải Sudoku bằng quay lui theo đúng khung Try của bài 15, đếm số lần thử; cắt nhánh bằng cách chọn ô ít lựa chọn nhất (MRV) và lưu hàng, cột, khối bằng bitmask: một đề khó từ hơn 100 nghìn lần thử xuống còn 120; cách kiểm tra đề có lời giải duy nhất. Có khung chạy tay, 2 mô phỏng từng bước và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Luật chơi, chơi thử Phần 2Kiểm tra một ô Phần 3Quay lui giải Sudoku Phần 4Cắt nhánh: MRV, bitmask Phần 5Lời giải duy nhất Bài tập8 bài + gợi ý

Phần 1Luật chơi Sudoku và chơi thử

Bàn Sudoku chuẩn là lưới 9 × 9, chia thành 9 khối 3 × 3 (viền đậm). Đề bài cho sẵn một số ô, nhiệm vụ của em là điền các ô còn lại bằng số từ 1 đến 9 sao cho:

mỗi hàng có đủ 9 số 1, 2, …, 9 (tức là không số nào lặp lại);
mỗi cột cũng có đủ 9 số đó;
mỗi khối 3 × 3 cũng vậy.

Tên “Sudoku” là cách viết tắt một cụm từ tiếng Nhật, đại ý “mỗi chữ số chỉ được xuất hiện một lần”. Nếu em chưa chơi bao giờ, hãy bắt đầu với bản 4 × 4: điền số 1 đến 4, khối chỉ có 2 × 2. Mọi lý luận đều giống hệt bản lớn:

Hình 1. Sudoku 4 × 4. Ô “?” nằm trong hàng 1 (xanh dương), cột 2 (tím) và khối trên trái (vàng). Ba vùng này đã chặn mất 1, 2, 3 nên ô “?” chắc chắn là 4.

Vài con số thú vị: Sudoku 4 × 4 chỉ có đúng 288 bàn điền đầy hợp lệ (phần 3 em sẽ tự đếm được), còn Sudoku 9 × 9 có khoảng $6{,}67 \cdot 10^{21}$ bàn. Một đề Sudoku “đúng chuẩn” phải có đúng một lời giải, và người ta đã chứng minh được (bằng máy tính) rằng đề như vậy cần ít nhất 17 ô cho sẵn.

Lý thuyết thế là đủ, giờ chơi đã! Em chọn đề, bấm vào ô trống rồi bấm số. Ô trùng hàng, cột hoặc khối sẽ đỏ lên ngay. Khi bí, nút Gợi ý 1 ô sẽ chỉ cho em ô dễ nhất. Còn nếu muốn xem máy làm thế nào, bấm Máy giải (máy giải tiếp từ bàn của em) hoặc bấm Tiếp ▶ ngay từ đầu. Thử chọn “Quay lui thường” với đề khó để thấy máy phải vất vả ra sao:

MÔ PHỎNGCHƠI THỬ: Sudoku – em giải hay để máy giải?Chọn ô rồi bấm số. Gợi ý 1 ô chọn ô ít lựa chọn nhất; Máy giải phát lại quá trình quay lui bằng nút Tiếp / Tự chạy.

ĐềMáy giải bằng

số đề chosố em điềnô đang chọn / máy đang xétbị trùng / ngõ cụtsố máy điền

Người chơi giỏi làm gì đầu tiên?

Họ không đoán bừa, mà đi tìm ô chỉ còn một khả năng như ô “?” ở Hình 1 rồi điền chắc chắn. Khi không còn ô nào như thế, họ chọn ô có ít khả năng nhất để thử. Hãy nhớ thói quen này: ở phần 4 ta sẽ dạy đúng nó cho máy, và máy sẽ nhanh hơn hàng trăm lần.

Phần 2Kiểm tra một ô có điền được không

Ta lưu bàn Sudoku trong mảng hai chiều g[9][9] (xem lại bài 7: Mảng 2 chiều), ô trống ghi số 0. Dữ liệu vào gồm 9 dòng, mỗi dòng 9 số. Viên gạch đầu tiên của mọi chương trình giải Sudoku là hàm ok(r, c, v): “điền số v vào ô hàng r, cột c có bị trùng không?”. Hàm cần nhìn ba chỗ:

Hàng r: các ô g[r][0..8];
Cột c: các ô g[0..8][c];
Khối chứa ô (r, c): 3 × 3 ô bắt đầu từ góc trên trái (br, bc).

Tìm góc khối thế nào? Hàng 0, 1, 2 thuộc dải khối đầu tiên (bắt đầu ở hàng 0), hàng 3, 4, 5 thuộc dải thứ hai (bắt đầu ở hàng 3)… Vậy br = r / 3 * 3 với phép chia lấy phần nguyên, cột cũng tương tự. Nếu cần đánh số khối từ 0 đến 8 (để làm chỉ số mảng) thì dùng b = (r / 3) * 3 + c / 3.

Hình 2. Chín khối của bàn Sudoku được đánh số từ 0 đến 8 theo thứ tự đọc. Ô (4, 7) nằm ở khối 5, góc khối là (3, 6).

Ô (r, c)	r / 3, c / 3	Góc khối (br, bc)	Số hiệu khối b
(0, 0)	0, 0	(0, 0)	0
(2, 8)	0, 2	(0, 6)	2
(4, 7)	1, 2	(3, 6)	5
(6, 5)	2, 1	(6, 3)	7
(8, 2)	2, 0	(6, 0)	6

Bảng 1. Tìm khối của một ô bằng phép chia lấy phần nguyên (hàng, cột đánh số từ 0).

Khuôn mẫu hàm kiểm tra một ô

bool ok(int r, int c, int v){
    for(int k = 0; k < 9; k++)
        if(g[r][k] == v || g[k][c] == v) return false;   // hàng, cột
    int br = r / 3 * 3, bc = c / 3 * 3;                  // góc khối
    for(int i = br; i < br + 3; i++)
        for(int j = bc; j < bc + 3; j++)
            if(g[i][j] == v) return false;               // khối
    return true;
}

Hàm này chỉ đúng khi ô (r, c) đang trống. Nếu ô đã có số v thì nó sẽ “trùng với chính mình”, nhớ điều này khi làm bài tập 1.

Ví dụ. Xét đề dễ của khung chơi thử, ô ở hàng 2, cột 4 (đánh số từ 1 như người chơi). Hàng 2 là 4 7 9 0 8 0 3 0 5 đã có 3, 4, 5, 7, 8, 9; cột 4 đã có 2, 4, 7; khối giữa phía trên đã có 2, 3, 4, 5, 7, 8. Gộp lại, các số bị chặn là 2, 3, 4, 5, 7, 8, 9, nên ô này chỉ còn hai lựa chọn: 1 hoặc 6. Chương trình dưới đây làm đúng việc đó: đọc bàn và một ô (đánh số từ 1), in mọi số điền được.

Xem code C++ / Python: liệt kê các số điền được vào một ô (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int g[9][9];

bool ok(int r, int c, int v){             // điền v vào ô (r, c) có bị trùng không?
    for(int k = 0; k < 9; k++)
        if(g[r][k] == v || g[k][c] == v) return false;   // trùng hàng hoặc cột
    int br = r / 3 * 3, bc = c / 3 * 3;                  // góc trên trái của khối
    for(int i = br; i < br + 3; i++)
        for(int j = bc; j < bc + 3; j++)
            if(g[i][j] == v) return false;               // trùng khối 3 x 3
    return true;
}

int main(){
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++) cin >> g[i][j];
    int r, c;
    cin >> r >> c;
    r--; c--;                              // đề đánh số từ 1, mảng đánh số từ 0
    vector<int> res;
    for(int v = 1; v <= 9; v++)
        if(ok(r, c, v)) res.push_back(v);
    if(res.empty()) cout << "KHONG CO";
    for(int v : res) cout << v << " ";
    return 0;
}

import sys

def ok(g, r, c, v):                        # điền v vào ô (r, c) có bị trùng không?
    for k in range(9):
        if g[r][k] == v or g[k][c] == v:   # trùng hàng hoặc cột
            return False
    br, bc = r // 3 * 3, c // 3 * 3        # góc trên trái của khối
    for i in range(br, br + 3):
        for j in range(bc, bc + 3):
            if g[i][j] == v:               # trùng khối 3 x 3
                return False
    return True

data = sys.stdin.read().split()
g = [[int(data[i * 9 + j]) for j in range(9)] for i in range(9)]
r, c = int(data[81]) - 1, int(data[82]) - 1    # đề đánh số từ 1
res = [v for v in range(1, 10) if ok(g, r, c, v)]
print(' '.join(map(str, res)) if res else 'KHONG CO')

Hàng, cột đánh số từ 0 hay từ 1?

Đề bài và người chơi thường đếm từ 1, còn mảng trong code đếm từ 0. Hãy đổi một lần ngay khi đọc dữ liệu (r--; c--;) rồi bên trong chương trình chỉ dùng một cách đếm. Trộn lẫn hai cách là nguồn gốc của rất nhiều lỗi “sai một ô”.

Phần 3Quay lui: thử – sai – quay lại

Nhắc lại khung quay lui ở bài 15: muốn xây lời giải gồm nhiều bước, ở mỗi bước ta thử lần lượt mọi lựa chọn; lựa chọn nào hợp lệ thì ghi nhận rồi đệ quy sang bước sau; đệ quy xong thì xoá lựa chọn đó để thử lựa chọn tiếp theo. Với Sudoku:

Mỗi bước là một ô trống, đi theo thứ tự đọc sách: ô p = r * 9 + c với p từ 0 tới 80.
Các lựa chọn là số 1 đến 9; lựa chọn hợp lệ khi ok(r, c, v) đúng.
Gặp ô có sẵn số thì bỏ qua, gọi luôn bước sau.
Đi hết 81 ô là có lời giải: trả về true để mọi lời gọi phía trên dừng lại ngay.
Thử hết 9 số mà không được: trả về false. Lỗi không nằm ở ô này mà ở một ô trước đó, nên ô trước phải đổi số. Đó chính là “quay lui”.

Khuôn mẫu quay lui cho bài toán điền ô

bool solve(int p){
    if(p == SỐ_Ô) return true;              // điền xong
    if(ô p có sẵn) return solve(p + 1);
    for(mỗi lựa chọn v){
        if(!hợp_lệ(p, v)) continue;
        đặt v vào ô p;
        if(solve(p + 1)) return true;       // tìm thấy: dừng luôn
        xoá v khỏi ô p;                      // quay lui
    }
    return false;                           // hết lựa chọn
}

Dòng xoá v rất quan trọng: nếu quên, ô vẫn giữ số cũ, hàm ok của các ô sau sẽ “nhìn thấy” một số không còn tồn tại và loại nhầm những lựa chọn đúng.

Để thấy rõ thế nào là “thử – sai – quay lại”, ta xem máy giải một đề 4 × 4. Mỗi bước là một lần thử một con số: ô đỏ cho biết số đó trùng với ai. Để ý những lúc một ô thử hết 1, 2, 3, 4 mà không được: máy phải lùi về ô trước, xoá số ở đó và thử số lớn hơn. Đề mặc định có 11 lần quay lui như vậy:

MÔ PHỎNGThử – sai – quay lui trên Sudoku 4 × 4Sửa đề (4 hàng, ô trống ghi 0) rồi bấm Tiếp / Tự chạy. Mỗi bước là một lần thử số.

Đề 4 × 4

số đề choô đang thửbị trùng / hết sốsố đã đặtô trống

Bây giờ em đối chiếu với code thật. Khung chạy tay dưới đây đi từng dòng của hàm solve cho Sudoku 4 × 4. Em để ý biến depth (độ sâu đệ quy) tăng khi đi tới, giảm khi quay lui, và dòng g[r][c] = 0 chạy mỗi khi một nhánh thất bại:

C++▶ Chạy tay từng dòng codesolve(p): bỏ qua ô có sẵn, thử v = 1..4, hợp lệ thì đặt rồi gọi solve(p + 1), thất bại thì xoá (ô vàng: ô đang xét, ô đỏ: ô gây trùng).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int g[4][4];

6bool ok(int r, int c, int v){

7 for(int k = 0; k < 4; k++)

8 if(g[r][k] == v || g[k][c] == v) return false;

9 int br = r / 2 * 2, bc = c / 2 * 2;

10 for(int i = br; i < br + 2; i++)

11 for(int j = bc; j < bc + 2; j++)

12 if(g[i][j] == v) return false;

13 return true;

14}

16bool solve(int p){

17 if(p == 16) return true;

18 int r = p / 4, c = p % 4;

19 if(g[r][c] != 0) return solve(p + 1);

20 for(int v = 1; v <= 4; v++){

21 if(!ok(r, c, v)) continue;

22 g[r][c] = v;

23 if(solve(p + 1)) return true;

24 g[r][c] = 0;

25 }

26 return false;

27}

29int main(){

30 for(int i = 0; i < 4; i++)

31 for(int j = 0; j < 4; j++) cin >> g[i][j];

32 solve(0);

33 for(int i = 0; i < 4; i++){

34 for(int j = 0; j < 4; j++) cout << g[i][j] << " ";

35 cout << "\n";

36 }

37 return 0;

38}

Bản 9 × 9 chỉ khác ở kích thước. Mình thêm biến tries đếm số lần đặt một chữ số vào ô (mỗi lần là một nút trong cây tìm kiếm) để đo xem máy vất vả cỡ nào. Chương trình in lời giải, dòng cuối là tries:

Xem code C++ / Python: giải Sudoku 9 × 9 bằng quay lui cơ bản (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int g[9][9];
long long tries = 0;                       // số lần đặt một chữ số vào ô

bool ok(int r, int c, int v){
    for(int k = 0; k < 9; k++)
        if(g[r][k] == v || g[k][c] == v) return false;
    int br = r / 3 * 3, bc = c / 3 * 3;
    for(int i = br; i < br + 3; i++)
        for(int j = bc; j < bc + 3; j++)
            if(g[i][j] == v) return false;
    return true;
}

bool solve(int p){                         // điền các ô từ vị trí p = r * 9 + c trở đi
    if(p == 81) return true;               // đã điền hết: tìm được lời giải
    int r = p / 9, c = p % 9;
    if(g[r][c] != 0) return solve(p + 1);  // ô có sẵn số: bỏ qua
    for(int v = 1; v <= 9; v++){
        if(!ok(r, c, v)) continue;
        g[r][c] = v; tries++;              // thử đặt v
        if(solve(p + 1)) return true;      // phía sau điền được hết: xong
        g[r][c] = 0;                       // thất bại: xoá v rồi thử số khác
    }
    return false;                          // hết cách: báo cho ô trước quay lui
}

int main(){
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++) cin >> g[i][j];
    if(solve(0)){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++) cout << g[i][j] << " ";
            cout << "\n";
        }
    } else cout << "VO NGHIEM\n";
    cout << tries;
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def ok(g, r, c, v):
    for k in range(9):
        if g[r][k] == v or g[k][c] == v:
            return False
    br, bc = r // 3 * 3, c // 3 * 3
    for i in range(br, br + 3):
        for j in range(bc, bc + 3):
            if g[i][j] == v:
                return False
    return True

def solve(g, p):                           # điền các ô từ vị trí p = r * 9 + c trở đi
    global tries
    if p == 81:                            # đã điền hết: tìm được lời giải
        return True
    r, c = divmod(p, 9)
    if g[r][c] != 0:                       # ô có sẵn số: bỏ qua
        return solve(g, p + 1)
    for v in range(1, 10):
        if not ok(g, r, c, v):
            continue
        g[r][c] = v; tries += 1            # thử đặt v
        if solve(g, p + 1):
            return True
        g[r][c] = 0                        # thất bại: xoá v rồi thử số khác
    return False                           # hết cách: báo cho ô trước quay lui

data = sys.stdin.read().split()
g = [[int(data[i * 9 + j]) for j in range(9)] for i in range(9)]
tries = 0
if solve(g, 0):
    print('\n'.join(' '.join(map(str, row)) for row in g))
else:
    print('VO NGHIEM')
print(tries)

Đề	Số ô cho sẵn	Số lần đặt số (quay lui cơ bản)
Đề dễ (khung chơi thử)	36	59
Đề vừa	24	6 422
Đề khó (khung chơi thử)	24	103 319
Đề “khó nhất thế giới” của Arto Inkala (2012)	21	49 558

Bảng 2. Cùng một chương trình, số lần thử chênh nhau gần 2000 lần giữa đề dễ và đề khó. Với đề dễ, máy gần như không phải quay lui (45 ô trống mà chỉ 59 lần đặt số).

Vì sao đề khó lại tốn kém đến vậy?

Máy đi theo thứ tự đọc sách nên thường phải đoán ở những ô đầu bàn, nơi còn rất nhiều khả năng. Đoán sai ở ô thứ 3 có khi tới ô thứ 40 mới lộ ra mâu thuẫn, và toàn bộ công sức điền 37 ô ở giữa bị bỏ đi. Độ sâu đệ quy chỉ tối đa 81 nên không lo tràn bộ nhớ, cái đáng sợ là số nhánh của cây tìm kiếm.

Phần 4Cắt nhánh: chọn ô ít lựa chọn nhất và dùng bitmask

Mẹo 1: MRV (viết tắt tiếng Anh của “ít giá trị còn lại nhất”). Thay vì đi theo thứ tự đọc sách, ở mỗi bước ta tìm ô trống có ít số điền được nhất và xử lý ô đó trước, y như người chơi giỏi:

ô có 0 lựa chọn: bàn hiện tại chắc chắn sai, quay lui ngay lập tức thay vì đợi tới khi đi tới ô đó. Đây là cắt nhánh;
ô có 1 lựa chọn: điền chắc chắn, cây tìm kiếm không phải tách nhánh;
nếu phải đoán thì đoán ở ô có ít khả năng nhất, xác suất đoán trúng cao hơn và cây có ít nhánh hơn.

Mẹo 2: bitmask. MRV bắt máy mỗi bước phải tính số lựa chọn của mọi ô trống. Nếu mỗi ô lại gọi ok cho 9 số, mỗi số duyệt 27 ô, thì quá chậm. Ta dùng kỹ thuật ở bài 20: với mỗi hàng giữ một số nguyên rowM[r], bit thứ v bật nghĩa là hàng đó đã có số v; tương tự colM[c], boxM[b]. Khi đó:

rowM[r] | colM[c] | boxM[b]: tập các số đã bị chặn ở ô (r, c), chỉ một phép OR;
~(...) & 0x3FE: đảo bit rồi giữ lại bit 1 đến 9 (0x3FE = 1111111110 ở hệ nhị phân), được tập ứng viên;
__builtin_popcount(mask) đếm số ứng viên; __builtin_ctz(mask) cho số nhỏ nhất; mask &= mask - 1 xoá bit thấp nhất (mẹo Kernighan);
đặt hoặc xoá số v: chỉ cần rowM[r] ^= 1 << v (tương tự cho cột, khối).

	Các số đã có	Mặt nạ (bit 9 → bit 0)
hàng 2	3, 4, 5, 7, 8, 9	`1110111000`
cột 4	2, 4, 7	`0010010100`
khối 1	2, 3, 4, 5, 7, 8	`0110111100`
OR cả ba	2, 3, 4, 5, 7, 8, 9	`1110111100`
~OR & 0x3FE	ứng viên: 1, 6	`0001000010`

Bảng 3. Lại là ô hàng 2, cột 4 của đề dễ ở phần 2 (khối đánh số 0…8 như Hình 2), nhưng giờ chỉ cần 3 phép OR, một phép đảo bit và một phép AND. Bit 0 không dùng, luôn bằng 0.

Mô phỏng dưới đây chạy MRV + bitmask trên đề khó của khung chơi thử. Mỗi ô trống ghi một số nhỏ là số lựa chọn còn lại; ô nào chỉ còn 1 thì xanh, còn 0 thì đỏ. Bên dưới là mặt nạ của hàng, cột, khối tại ô được chọn. Em sẽ thấy phần lớn các bước là “chỉ còn 1 lựa chọn”, máy hiếm khi phải đoán:

MÔ PHỎNGMRV + bitmask: luôn chọn ô ít lựa chọn nhấtDán đề 9 × 9 bất kỳ (81 chữ số, ô trống ghi 0) rồi bấm Tiếp. Số nhỏ trong ô trống là số lựa chọn còn lại.

Đề (81 chữ số)

số đề choô MRV chọncòn 1 lựa chọn / bit ứng viên0 lựa chọn / bit đã có

Xem code C++ / Python: giải Sudoku bằng quay lui + MRV + bitmask (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int g[81];                                 // ô p = r * 9 + c, 0 là ô trống
int rowM[9], colM[9], boxM[9];             // bit v bật: số v đã có trong hàng / cột / khối
long long tries = 0;

int boxOf(int p){ return p / 27 * 3 + p % 9 / 3; }

void flip(int p, int v){                   // bật (khi đặt) hoặc tắt (khi xoá) bit v
    rowM[p / 9] ^= 1 << v;
    colM[p % 9] ^= 1 << v;
    boxM[boxOf(p)] ^= 1 << v;
}

bool solve(){
    int best = -1, bestMask = 0, bestCnt = 10;
    for(int p = 0; p < 81; p++){           // MRV: tìm ô trống ít lựa chọn nhất
        if(g[p] != 0) continue;
        int mask = ~(rowM[p / 9] | colM[p % 9] | boxM[boxOf(p)]) & 0x3FE;   // bit 1..9 còn trống
        int cnt = __builtin_popcount(mask);
        if(cnt < bestCnt){ bestCnt = cnt; best = p; bestMask = mask; }
        if(cnt == 0) return false;         // có ô hết lựa chọn: cắt nhánh ngay
    }
    if(best == -1) return true;            // không còn ô trống: xong
    for(int m = bestMask; m > 0; m &= m - 1){   // duyệt từng bit đang bật
        int v = __builtin_ctz(m);          // vị trí bit thấp nhất = số nhỏ nhất còn lại
        g[best] = v; flip(best, v); tries++;
        if(solve()) return true;
        flip(best, v); g[best] = 0;        // quay lui: tắt bit, xoá ô
    }
    return false;
}

int main(){
    bool bad = false;
    for(int p = 0; p < 81; p++){
        cin >> g[p];
        if(g[p] == 0) continue;
        int v = g[p];
        if((rowM[p / 9] | colM[p % 9] | boxM[boxOf(p)]) >> v & 1) bad = true;   // số cho sẵn bị trùng
        else flip(p, v);
    }
    if(!bad && solve()){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++) cout << g[i * 9 + j] << " ";
            cout << "\n";
        }
    } else cout << "VO NGHIEM\n";
    cout << tries;
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def solve():
    global tries
    best, best_mask, best_cnt = -1, 0, 10
    for p in range(81):                    # MRV: tìm ô trống ít lựa chọn nhất
        if g[p]:
            continue
        r, c = divmod(p, 9)
        mask = ~(row[r] | col[c] | box[r // 3 * 3 + c // 3]) & 0x3FE   # bit 1..9 còn trống
        cnt = bin(mask).count('1')
        if cnt < best_cnt:
            best, best_mask, best_cnt = p, mask, cnt
        if cnt == 0:
            return False                   # có ô hết lựa chọn: cắt nhánh ngay
    if best == -1:
        return True                        # không còn ô trống: xong
    r, c = divmod(best, 9)
    b = r // 3 * 3 + c // 3
    m = best_mask
    while m:
        low = m & -m                       # bit thấp nhất đang bật
        m ^= low
        g[best] = low.bit_length() - 1     # vị trí của bit đó = số cần thử
        tries += 1
        row[r] |= low; col[c] |= low; box[b] |= low
        if solve():
            return True
        row[r] ^= low; col[c] ^= low; box[b] ^= low   # quay lui: tắt bit, xoá ô
        g[best] = 0
    return False

g = list(map(int, sys.stdin.read().split()[:81]))
row, col, box = [0] * 9, [0] * 9, [0] * 9
tries, bad = 0, False
for p in range(81):
    if g[p]:
        r, c = divmod(p, 9)
        b, bit = r // 3 * 3 + c // 3, 1 << g[p]
        if (row[r] | col[c] | box[b]) & bit:
            bad = True                     # số cho sẵn bị trùng
        row[r] |= bit; col[c] |= bit; box[b] |= bit
if not bad and solve():
    print('\n'.join(' '.join(map(str, g[i * 9:i * 9 + 9])) for i in range(9)))
else:
    print('VO NGHIEM')
print(tries)

Đề	Quay lui cơ bản	Quay lui + MRV	Giảm
Đề dễ	59	45	1,3 lần
Đề vừa	6 422	95	68 lần
Đề khó	103 319	120	861 lần
Đề của Arto Inkala	49 558	10 101	4,9 lần

Bảng 4. Số lần đặt số của hai chương trình (in ở dòng cuối). Với đề dễ, MRV đặt đúng 45 lần cho 45 ô trống: không đoán sai lần nào. Đề của Inkala được thiết kế để ô nào cũng còn nhiều khả năng, nên MRV vẫn phải đoán khá nhiều, nhưng vẫn nhanh hơn gần 5 lần.

Bật, tắt bit bằng XOR

Phép ^= bật bit khi đặt số và tắt bit khi quay lui, rất gọn. Nhưng nó chỉ đúng khi bit đó đang tắt lúc đặt. Nếu đề cho sẵn hai số 8 cùng hàng, lần XOR thứ hai sẽ tắt mất bit 8 và chương trình giải ra một bàn sai. Vì vậy lúc đọc đề phải kiểm tra trùng trước (dòng bad = true trong code).

Bit trong Python

Python không có __builtin_popcount, ta đếm bit bằng bin(m).count('1') (Python 3.10 trở lên có m.bit_count()). Bit thấp nhất là low = m & -m, và số tương ứng là low.bit_length() - 1. Bản Python giải đề khó trong chưa tới một giây.

Phần 5Đề có lời giải duy nhất không?

Một đề Sudoku tử tế phải có đúng một lời giải, nếu không người chơi sẽ phải đoán mà không có cách nào suy luận được. Kiểm tra điều này chỉ cần sửa nhẹ hàm quay lui: khi điền xong bàn thì không dừng mà tăng biến đếm cnt rồi đi tìm tiếp. Nhưng đếm hết lời giải có thể rất lâu (bàn trống có tới $6{,}67 \cdot 10^{21}$ lời giải!), mà ta chỉ cần biết “0, 1 hay nhiều”, nên dừng ngay khi cnt đạt 2.

Đề	Kết quả
Đề dễ của khung chơi thử	DUY NHAT
Đề dễ nhưng xoá số 8 ở ô (1, 1)	NHIEU LOI GIAI
Bàn trống	NHIEU LOI GIAI
Hàng 1 là 1 2 3 4 5 6 7 8 _, ô (2, 9) là 9	VO NGHIEM

Bảng 5. Chỉ bỏ đi một số cho sẵn là đề dễ đã có 2 lời giải. Ở dòng cuối, ô (1, 9) không thể là 9 (cùng cột với ô 9) mà cũng không thể là 1…8 (cùng hàng).

Xem code C++ / Python: kiểm tra đề Sudoku có lời giải duy nhất (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int g[81], ans[81], cnt = 0;               // cnt: số lời giải đã thấy (dừng ở 2)
int rowM[9], colM[9], boxM[9];

int boxOf(int p){ return p / 27 * 3 + p % 9 / 3; }
void flip(int p, int v){ rowM[p / 9] ^= 1 << v; colM[p % 9] ^= 1 << v; boxM[boxOf(p)] ^= 1 << v; }

void solve(){
    int best = -1, bestMask = 0, bestCnt = 10;
    for(int p = 0; p < 81; p++){
        if(g[p] != 0) continue;
        int mask = ~(rowM[p / 9] | colM[p % 9] | boxM[boxOf(p)]) & 0x3FE;
        int k = __builtin_popcount(mask);
        if(k < bestCnt){ bestCnt = k; best = p; bestMask = mask; }
        if(k == 0) return;
    }
    if(best == -1){                        // gặp một lời giải
        if(cnt == 0) copy(g, g + 81, ans);
        cnt++;
        return;
    }
    for(int m = bestMask; m > 0 && cnt < 2; m &= m - 1){   // đủ 2 lời giải thì thôi
        int v = __builtin_ctz(m);
        g[best] = v; flip(best, v);
        solve();
        flip(best, v); g[best] = 0;
    }
}

int main(){
    bool bad = false;
    for(int p = 0; p < 81; p++){
        cin >> g[p];
        if(g[p] == 0) continue;
        if((rowM[p / 9] | colM[p % 9] | boxM[boxOf(p)]) >> g[p] & 1) bad = true;
        else flip(p, g[p]);
    }
    if(!bad) solve();
    if(cnt == 0) cout << "VO NGHIEM";
    else if(cnt >= 2) cout << "NHIEU LOI GIAI";
    else {
        cout << "DUY NHAT\n";
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++) cout << ans[i * 9 + j] << " ";
            cout << "\n";
        }
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def solve():
    global cnt, ans
    best, best_mask, best_cnt = -1, 0, 10
    for p in range(81):
        if g[p]:
            continue
        r, c = divmod(p, 9)
        mask = ~(row[r] | col[c] | box[r // 3 * 3 + c // 3]) & 0x3FE
        k = bin(mask).count('1')
        if k < best_cnt:
            best, best_mask, best_cnt = p, mask, k
        if k == 0:
            return
    if best == -1:                         # gặp một lời giải
        if cnt == 0:
            ans = g[:]
        cnt += 1
        return
    r, c = divmod(best, 9)
    b = r // 3 * 3 + c // 3
    m = best_mask
    while m and cnt < 2:                   # đủ 2 lời giải thì thôi
        low = m & -m
        m ^= low
        g[best] = low.bit_length() - 1
        row[r] |= low; col[c] |= low; box[b] |= low
        solve()
        row[r] ^= low; col[c] ^= low; box[b] ^= low
        g[best] = 0

g = list(map(int, sys.stdin.read().split()[:81]))
row, col, box = [0] * 9, [0] * 9, [0] * 9
cnt, ans, bad = 0, None, False
for p in range(81):
    if g[p]:
        r, c = divmod(p, 9)
        b, bit = r // 3 * 3 + c // 3, 1 << g[p]
        if (row[r] | col[c] | box[b]) & bit:
            bad = True
        row[r] |= bit; col[c] |= bit; box[b] |= bit
if not bad:
    solve()
if cnt == 0:
    print('VO NGHIEM')
elif cnt >= 2:
    print('NHIEU LOI GIAI')
else:
    print('DUY NHAT')
    print('\n'.join(' '.join(map(str, ans[i * 9:i * 9 + 9])) for i in range(9)))

Người ta làm ra đề Sudoku thế nào? Chính bằng chương trình trên! Bắt đầu từ một bàn đã điền đầy (sinh ngẫu nhiên bằng quay lui, thử các số theo thứ tự xáo trộn), lần lượt thử xoá từng ô theo thứ tự ngẫu nhiên: nếu sau khi xoá mà đề vẫn có lời giải duy nhất thì xoá luôn, ngược lại thì trả số về chỗ cũ. Các đề trong bài này, kể cả đề của bài tập 7 và 8, đều được tạo theo đúng cách đó. Muốn đề khó hơn thì xoá nhiều ô hơn, hoặc chọn đề mà MRV phải đoán nhiều.

Quay lui: một khuôn, nhiều trò chơi

Cùng một khung solve giải được rất nhiều trò điền số: Sudoku biến thể (chẵn lẻ, đường chéo), Kakuro, N quân hậu, xếp hình… Chỉ có ba thứ thay đổi: trạng thái lưu gì, lựa chọn ở mỗi bước là gì, và kiểm tra hợp lệ ra sao. Muốn nhanh thì thêm hai gia vị của bài này: chọn bước ít lựa chọn nhất, và cắt nhánh càng sớm càng tốt.

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

Nuôi bò 1 (Dễ)
Chia Xâu Thành Số Lượng Lớn Nhất Các Xâu Con Duy Nhất (Dễ)
Rút Tiền ATM (Trung bình)
Tiền Tệ (TIENTE) (Trung bình)
Chèn Phép Toán (Khá)
Biểu Thức Bằng K (EXPR) (Khá)
Minimum Incompatibility (LeetCode 1681) (Khó)

Xem toàn bộ bài cùng chủ đề: nhãn Quay lui.

Bài tậpLuyện quay lui qua các trò điền số

Bài 1Kiểm tra bàn SudokuDễ

Cho bàn Sudoku 9 × 9 gồm 9 dòng, mỗi dòng 9 số nguyên từ 0 đến 9 (0 là ô trống). In ra SAI nếu có hai ô khác 0 bằng nhau nằm cùng hàng, cùng cột hoặc cùng khối 3 × 3; ngược lại in XONG nếu bàn không còn ô trống, CHUA XONG nếu còn ô trống.

Input

8 3 1 7 2 5 4 6 9
4 7 9 1 8 6 3 2 5
2 6 5 4 3 9 8 7 1
3 8 7 6 4 1 9 5 2
5 1 2 3 9 7 6 4 8
6 9 4 2 5 8 7 1 3
9 4 6 5 1 3 2 8 7
7 5 3 8 6 2 1 9 4
1 2 8 9 7 4 5 3 6

Output

XONG

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đừng dùng hàm ok của phần 2 cho ô đã có số (nó sẽ thấy ô “trùng với chính mình”). Cách gọn nhất: duyệt các ô theo thứ tự, giữ ba mảng bitmask rowM, colM, boxM. Gặp số v mà bit v đã bật ở hàng, cột hoặc khối của nó thì trùng; nếu không thì bật bit lên. Mẫu là lời giải của đề dễ nên in XONG.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int g[9][9];
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++) cin >> g[i][j];
    int rowM[9] = {0}, colM[9] = {0}, boxM[9] = {0};
    bool full = true;
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++){
            int v = g[i][j];
            if(v == 0){ full = false; continue; }
            int b = i / 3 * 3 + j / 3, bit = 1 << v;
            if((rowM[i] & bit) || (colM[j] & bit) || (boxM[b] & bit)){   // số v đã xuất hiện trước đó
                cout << "SAI";
                return 0;
            }
            rowM[i] |= bit; colM[j] |= bit; boxM[b] |= bit;
        }
    cout << (full ? "XONG" : "CHUA XONG");
    return 0;
}

import sys

data = sys.stdin.read().split()
g = [[int(data[i * 9 + j]) for j in range(9)] for i in range(9)]
row, col, box = [0] * 9, [0] * 9, [0] * 9
full, bad = True, False
for i in range(9):
    for j in range(9):
        v = g[i][j]
        if v == 0:
            full = False
            continue
        b, bit = i // 3 * 3 + j // 3, 1 << v
        if (row[i] | col[j] | box[b]) & bit:   # số v đã xuất hiện trước đó
            bad = True
        row[i] |= bit; col[j] |= bit; box[b] |= bit
print('SAI' if bad else ('XONG' if full else 'CHUA XONG'))

Bài 2Ô chỉ có một lựa chọnDễ

Cho bàn Sudoku 9 × 9 hợp lệ (0 là ô trống). Một ô trống gọi là ô chắc chắn nếu chỉ có đúng một số điền được vào nó mà không trùng hàng, cột, khối (tính trên bàn ban đầu, không điền thêm gì). In ra số ô chắc chắn $K$, sau đó $K$ dòng, mỗi dòng gồm hàng, cột (đánh số từ 1) và số duy nhất điền được, theo thứ tự đọc từng hàng từ trên xuống.

Input

8 0 0 7 2 5 0 0 0
4 7 9 0 8 0 3 0 5
2 6 0 4 3 0 0 7 0
0 0 7 0 4 1 9 0 0
0 1 0 0 0 0 6 4 0
6 0 4 2 0 0 0 0 3
9 0 0 0 1 0 0 0 0
7 0 0 0 0 0 1 0 4
0 2 0 0 0 4 5 3 6

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dựng ba mảng bitmask từ các số cho sẵn, với mỗi ô trống tính mask = ~(rowM | colM | boxM) & 0x3FE. Ô chắc chắn khi mask có đúng một bit bật: __builtin_popcount(mask) == 1, hay mẹo bài 20 mask & (mask - 1) == 0. Số cần điền là vị trí bit đó. Ô (1, 2) của đề mẫu giống hệt ô “?” ở Hình 1: hàng, cột, khối đã chặn hết mọi số trừ số 3.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int g[81], rowM[9] = {0}, colM[9] = {0}, boxM[9] = {0};
    for(int p = 0; p < 81; p++){
        cin >> g[p];
        if(g[p]){
            int bit = 1 << g[p];
            rowM[p / 9] |= bit; colM[p % 9] |= bit; boxM[p / 27 * 3 + p % 9 / 3] |= bit;
        }
    }
    vector<array<int, 3>> res;
    for(int p = 0; p < 81; p++){
        if(g[p]) continue;
        int mask = ~(rowM[p / 9] | colM[p % 9] | boxM[p / 27 * 3 + p % 9 / 3]) & 0x3FE;
        if(__builtin_popcount(mask) == 1)                      // đúng một bit bật
            res.push_back({p / 9 + 1, p % 9 + 1, __builtin_ctz(mask)});
    }
    cout << res.size() << "\n";
    for(auto &t : res) cout << t[0] << " " << t[1] << " " << t[2] << "\n";
    return 0;
}

import sys

g = list(map(int, sys.stdin.read().split()[:81]))
row, col, box = [0] * 9, [0] * 9, [0] * 9
for p in range(81):
    if g[p]:
        bit = 1 << g[p]
        row[p // 9] |= bit; col[p % 9] |= bit; box[p // 27 * 3 + p % 9 // 3] |= bit
res = []
for p in range(81):
    if g[p]:
        continue
    mask = ~(row[p // 9] | col[p % 9] | box[p // 27 * 3 + p % 9 // 3]) & 0x3FE
    if mask & (mask - 1) == 0 and mask:          # đúng một bit bật
        res.append('%d %d %d' % (p // 9 + 1, p % 9 + 1, mask.bit_length() - 1))
print(len(res))
if res:
    print('\n'.join(res))

Bài 3Sudoku 4 × 4Dễ

Cho bàn Sudoku 4 × 4 gồm 4 dòng, mỗi dòng 4 số từ 0 đến 4 (0 là ô trống). Dữ liệu đảm bảo có ít nhất một lời giải. Hãy in ra một lời giải; nếu có nhiều lời giải, in lời giải nhỏ nhất khi đọc 16 số lần lượt theo từng hàng như một dãy số.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đúng code của khung chạy tay phần 3. Vì ta đi các ô theo thứ tự đọc và ở mỗi ô thử số từ nhỏ tới lớn, lời giải đầu tiên tìm được chính là lời giải nhỏ nhất, không cần làm gì thêm. Mẫu là đề của mô phỏng 4 × 4 ở phần 3.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int g[4][4];

bool ok(int r, int c, int v){
    for(int k = 0; k < 4; k++)
        if(g[r][k] == v || g[k][c] == v) return false;
    int br = r / 2 * 2, bc = c / 2 * 2;
    for(int i = br; i < br + 2; i++)
        for(int j = bc; j < bc + 2; j++)
            if(g[i][j] == v) return false;
    return true;
}

bool solve(int p){
    if(p == 16) return true;
    int r = p / 4, c = p % 4;
    if(g[r][c] != 0) return solve(p + 1);
    for(int v = 1; v <= 4; v++){
        if(!ok(r, c, v)) continue;
        g[r][c] = v;
        if(solve(p + 1)) return true;
        g[r][c] = 0;
    }
    return false;
}

int main(){
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++) cin >> g[i][j];
    solve(0);
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++) cout << g[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

import sys

def ok(r, c, v):
    for k in range(4):
        if g[r][k] == v or g[k][c] == v:
            return False
    br, bc = r // 2 * 2, c // 2 * 2
    return all(g[i][j] != v for i in range(br, br + 2) for j in range(bc, bc + 2))

def solve(p):
    if p == 16:
        return True
    r, c = divmod(p, 4)
    if g[r][c]:
        return solve(p + 1)
    for v in range(1, 5):
        if ok(r, c, v):
            g[r][c] = v
            if solve(p + 1):
                return True
            g[r][c] = 0
    return False

d = list(map(int, sys.stdin.read().split()))
g = [d[i * 4:i * 4 + 4] for i in range(4)]
solve(0)
print('\n'.join(' '.join(map(str, row)) for row in g))

Bài 4Đếm lời giải Sudoku 4 × 4Trung bình

Cho bàn Sudoku 4 × 4 (0 là ô trống), các số cho sẵn có thể đã mâu thuẫn với nhau. Đếm số cách điền các ô trống để được một bàn hợp lệ.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Vẫn là quay lui, nhưng khi điền xong 16 ô thì tăng biến đếm rồi quay lui tiếp thay vì dừng. Phải kiểm tra trước các số cho sẵn: nếu chúng đã trùng nhau thì đáp án là 0 (hàm ok trong lời giải bỏ qua chính ô đang xét nên dùng được cho cả việc này). Bàn trống có 288 lời giải: hàng đầu có $4! = 24$ cách, và mỗi cách đó có 12 cách điền phần còn lại.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int g[16];
long long cnt = 0;

bool ok(int p, int v){                      // đặt v ở ô p có trùng ô nào KHÁC không?
    int r = p / 4, c = p % 4;
    for(int q = 0; q < 16; q++){
        if(q == p || g[q] != v) continue;
        int r2 = q / 4, c2 = q % 4;
        if(r2 == r || c2 == c || (r2 / 2 == r / 2 && c2 / 2 == c / 2)) return false;
    }
    return true;
}

void go(int p){
    while(p < 16 && g[p] != 0) p++;         // bỏ qua ô có sẵn số
    if(p == 16){ cnt++; return; }           // điền xong: thêm một lời giải
    for(int v = 1; v <= 4; v++)
        if(ok(p, v)){
            g[p] = v;
            go(p + 1);                      // KHÔNG dừng lại: đếm tiếp
            g[p] = 0;
        }
}

int main(){
    for(int p = 0; p < 16; p++) cin >> g[p];
    for(int p = 0; p < 16; p++)
        if(g[p] != 0 && !ok(p, g[p])){ cout << 0; return 0; }   // đề tự mâu thuẫn
    go(0);
    cout << cnt;
    return 0;
}

import sys

def ok(p, v):                               # đặt v ở ô p có trùng ô nào KHÁC không?
    r, c = divmod(p, 4)
    for q in range(16):
        if q != p and g[q] == v:
            r2, c2 = divmod(q, 4)
            if r2 == r or c2 == c or (r2 // 2 == r // 2 and c2 // 2 == c // 2):
                return False
    return True

def go(p):
    while p < 16 and g[p]:                  # bỏ qua ô có sẵn số
        p += 1
    if p == 16:
        return 1                            # điền xong: một lời giải
    total = 0
    for v in range(1, 5):
        if ok(p, v):
            g[p] = v
            total += go(p + 1)              # KHÔNG dừng lại: đếm tiếp
            g[p] = 0
    return total

g = list(map(int, sys.stdin.read().split()[:16]))
if any(g[p] and not ok(p, g[p]) for p in range(16)):
    print(0)                                # đề tự mâu thuẫn
else:
    print(go(0))

Bài 5N quân hậu bằng bitmaskTrung bình

Đếm số cách đặt $n$ quân hậu lên bàn cờ $n \times n$ ($1 \le n \le 12$) sao cho không hai quân nào cùng hàng, cùng cột hay cùng đường chéo.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Bài kinh điển của bài 15, giờ tăng tốc bằng bitmask giống phần 4. Đặt mỗi hàng một quân; giữ ba mặt nạ: cols (cột đã có hậu), d1 và d2 (các cột ở hàng hiện tại bị hai loại đường chéo chiếu tới). Cột đặt được là ~(cols | d1 | d2) & full. Sang hàng sau, đường chéo dịch đi một cột: d1 dịch trái, d2 dịch phải. Lấy từng bit bằng bit = free & -free. Với $n = 8$ có 92 cách.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int n, full;
long long cnt = 0;

void go(int row, int cols, int d1, int d2){     // d1, d2: các cột bị 2 loại đường chéo chiếu tới hàng này
    if(row == n){ cnt++; return; }
    int freeM = ~(cols | d1 | d2) & full;        // các cột còn đặt được ở hàng này
    while(freeM){
        int bit = freeM & -freeM;                // lấy cột thấp nhất
        freeM ^= bit;
        go(row + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
    }
}

int main(){
    cin >> n;
    full = (1 << n) - 1;
    go(0, 0, 0, 0);
    cout << cnt;
    return 0;
}

n = int(input())
full = (1 << n) - 1

def go(row, cols, d1, d2):                  # d1, d2: các cột bị 2 loại đường chéo chiếu tới hàng này
    if row == n:
        return 1
    total = 0
    free = ~(cols | d1 | d2) & full         # các cột còn đặt được ở hàng này
    while free:
        bit = free & -free                  # lấy cột thấp nhất
        free ^= bit
        total += go(row + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
    return total

print(go(0, 0, 0, 0))

Bài 6Kakuro miniTrung bình

Cho lưới $n \times m$ ($1 \le n, m \le 3$). Điền vào mỗi ô một chữ số từ 1 đến 9 sao cho các số trong cùng một hàng khác nhau, các số trong cùng một cột khác nhau, tổng hàng $i$ bằng $R_i$ và tổng cột $j$ bằng $C_j$. Đếm số cách điền.

Dòng đầu: $n$, $m$. Dòng hai: $R_1, \ldots, R_n$. Dòng ba: $C_1, \ldots, C_m$ (mọi tổng không quá 45).

Input

2 3
6 15
7 6 8

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Quay lui điền từng ô theo thứ tự đọc, nhớ phần tổng còn thiếu của mỗi hàng, mỗi cột. Cắt nhánh: sau khi đặt $v$, nếu hàng còn $k$ ô thì phần tổng còn thiếu phải nằm trong đoạn $[k, 9k]$ (ô cuối hàng còn $k = 0$ nên tổng phải vừa khít), cột cũng vậy. Hai cách của mẫu là 1 2 3 / 6 4 5 và 3 1 2 / 4 5 6.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int n, m, remR[3], remC[3];
bool usedR[3][10], usedC[3][10];
long long cnt = 0;

void go(int p){
    if(p == n * m){ cnt++; return; }
    int i = p / m, j = p % m;
    int kr = m - 1 - j, kc = n - 1 - i;           // số ô còn lại phía sau trong hàng i, trong cột j
    for(int v = 1; v <= 9; v++){
        if(usedR[i][v] || usedC[j][v]) continue;  // trùng trong hàng hoặc cột
        int sr = remR[i] - v, sc = remC[j] - v;
        if(sr < kr || sr > 9 * kr || sc < kc || sc > 9 * kc) continue;   // cắt nhánh theo tổng
        usedR[i][v] = usedC[j][v] = true; remR[i] -= v; remC[j] -= v;
        go(p + 1);
        usedR[i][v] = usedC[j][v] = false; remR[i] += v; remC[j] += v;
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> remR[i];
    for(int j = 0; j < m; j++) cin >> remC[j];
    go(0);
    cout << cnt;
    return 0;
}

import sys

d = list(map(int, sys.stdin.read().split()))
n, m = d[0], d[1]
remR, remC = d[2:2 + n], d[2 + n:2 + n + m]
usedR = [[False] * 10 for _ in range(n)]
usedC = [[False] * 10 for _ in range(m)]

def go(p):
    if p == n * m:
        return 1
    i, j = divmod(p, m)
    kr, kc = m - 1 - j, n - 1 - i           # số ô còn lại phía sau trong hàng i, trong cột j
    total = 0
    for v in range(1, 10):
        if usedR[i][v] or usedC[j][v]:      # trùng trong hàng hoặc cột
            continue
        sr, sc = remR[i] - v, remC[j] - v
        if sr < kr or sr > 9 * kr or sc < kc or sc > 9 * kc:   # cắt nhánh theo tổng
            continue
        usedR[i][v] = usedC[j][v] = True; remR[i] -= v; remC[j] -= v
        total += go(p + 1)
        usedR[i][v] = usedC[j][v] = False; remR[i] += v; remC[j] += v
    return total

print(go(0))

Bài 7Sudoku chẵn lẻKhá

Một biến thể Sudoku 9 × 9: ngoài luật thông thường, một số ô được đánh dấu C (phải điền số chẵn) hoặc L (phải điền số lẻ). Dữ liệu gồm 9 dòng của bàn (0 là ô trống), tiếp theo là 9 xâu độ dài 9 gồm các ký tự ., C, L. Đề đảm bảo có đúng một lời giải, hãy in lời giải đó.

Input

0 0 0 0 0 0 0 0 6
3 0 0 8 0 0 0 5 0
0 0 0 0 7 6 0 0 0
0 8 0 1 0 0 4 0 0
6 0 3 0 0 0 0 0 0
0 5 0 0 0 0 0 0 0
5 0 0 9 0 0 0 6 0
0 0 0 0 0 0 9 0 0
0 0 4 0 1 0 0 0 0
.LCL.L.C.
L.CC.LL..
L..C.CCC.
.C.....L.
..L...L..
C.L.....C
L...L....
..C..C..L
L....C..L

Output

8 7 2 5 9 3 1 4 6
3 4 6 8 2 1 7 5 9
1 9 5 4 7 6 2 8 3
2 8 9 1 6 5 4 3 7
6 1 3 7 4 2 5 9 8
4 5 7 3 8 9 6 1 2
5 2 1 9 3 7 8 6 4
7 3 8 6 5 4 9 2 1
9 6 4 2 1 8 3 7 5

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Lấy nguyên code MRV + bitmask ở phần 4, mỗi ô có thêm một mặt nạ allow[p]: số chẵn là (1<<2)|(1<<4)|(1<<6)|(1<<8), số lẻ là các bit 1, 3, 5, 7, 9, ô tự do là 0x3FE. Tập ứng viên là ~(rowM | colM | boxM) & allow[p]. Ràng buộc thêm khiến các ô có ít lựa chọn hơn, nên MRV càng chạy nhanh: đề mẫu chỉ cho sẵn 18 số mà vẫn giải tức thì.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int g[81], allow[81], rowM[9], colM[9], boxM[9];

int boxOf(int p){ return p / 27 * 3 + p % 9 / 3; }
void flip(int p, int v){ rowM[p / 9] ^= 1 << v; colM[p % 9] ^= 1 << v; boxM[boxOf(p)] ^= 1 << v; }

bool solve(){
    int best = -1, bestMask = 0, bestCnt = 10;
    for(int p = 0; p < 81; p++){
        if(g[p] != 0) continue;
        int mask = ~(rowM[p / 9] | colM[p % 9] | boxM[boxOf(p)]) & allow[p];   // lọc thêm chẵn / lẻ
        int k = __builtin_popcount(mask);
        if(k < bestCnt){ bestCnt = k; best = p; bestMask = mask; }
        if(k == 0) return false;
    }
    if(best == -1) return true;
    for(int m = bestMask; m > 0; m &= m - 1){
        int v = __builtin_ctz(m);
        g[best] = v; flip(best, v);
        if(solve()) return true;
        flip(best, v); g[best] = 0;
    }
    return false;
}

int main(){
    const int EVEN = (1 << 2) | (1 << 4) | (1 << 6) | (1 << 8);
    const int ODD = (1 << 1) | (1 << 3) | (1 << 5) | (1 << 7) | (1 << 9);
    for(int p = 0; p < 81; p++){
        cin >> g[p];
        if(g[p]) flip(p, g[p]);
    }
    for(int i = 0; i < 9; i++){
        string s;
        cin >> s;
        for(int j = 0; j < 9; j++)
            allow[i * 9 + j] = s[j] == 'C' ? EVEN : (s[j] == 'L' ? ODD : 0x3FE);
    }
    solve();
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++) cout << g[i * 9 + j] << " ";
        cout << "\n";
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)

EVEN = sum(1 << v for v in (2, 4, 6, 8))
ODD = sum(1 << v for v in (1, 3, 5, 7, 9))

def solve():
    best, best_mask, best_cnt = -1, 0, 10
    for p in range(81):
        if g[p]:
            continue
        mask = ~(row[p // 9] | col[p % 9] | box[p // 27 * 3 + p % 9 // 3]) & allow[p]   # lọc thêm chẵn / lẻ
        k = bin(mask).count('1')
        if k < best_cnt:
            best, best_mask, best_cnt = p, mask, k
        if k == 0:
            return False
    if best == -1:
        return True
    r, c = divmod(best, 9)
    b = r // 3 * 3 + c // 3
    m = best_mask
    while m:
        low = m & -m
        m ^= low
        g[best] = low.bit_length() - 1
        row[r] |= low; col[c] |= low; box[b] |= low
        if solve():
            return True
        row[r] ^= low; col[c] ^= low; box[b] ^= low
        g[best] = 0
    return False

data = sys.stdin.read().split()
g = list(map(int, data[:81]))
pat = ''.join(data[81:90])
allow = [EVEN if ch == 'C' else (ODD if ch == 'L' else 0x3FE) for ch in pat]
row, col, box = [0] * 9, [0] * 9, [0] * 9
for p in range(81):
    if g[p]:
        bit = 1 << g[p]
        row[p // 9] |= bit; col[p % 9] |= bit; box[p // 27 * 3 + p % 9 // 3] |= bit
solve()
print('\n'.join(' '.join(map(str, g[i * 9:i * 9 + 9])) for i in range(9)))

Bài 8Sudoku đường chéoKhá

Sudoku đường chéo có thêm một luật: hai đường chéo chính của bàn 9 × 9 (từ góc trên trái xuống góc dưới phải, và từ góc trên phải xuống góc dưới trái) cũng phải chứa đủ các số 1 đến 9. Cho đề (9 dòng, 0 là ô trống) đảm bảo có đúng một lời giải, hãy in lời giải.

Input

0 0 2 0 9 0 0 0 0
0 4 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 0 0 4 0 0 2 5
5 0 0 0 0 7 8 0 0
6 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 8
9 0 0 0 0 0 0 0 0
0 6 8 2 0 0 0 0 0

Output

8 7 2 5 9 3 1 4 6
3 4 6 8 2 1 7 5 9
1 9 5 4 7 6 2 8 3
7 1 9 3 4 8 6 2 5
5 2 3 6 1 7 8 9 4
6 8 4 9 5 2 3 7 1
2 5 7 1 6 4 9 3 8
9 3 1 7 8 5 4 6 2
4 6 8 2 3 9 5 1 7

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Thêm hai mặt nạ cho hai đường chéo: ô $(r, c)$ thuộc đường chéo chính khi $r = c$, thuộc đường chéo phụ khi $r + c = 8$ (ô chính giữa thuộc cả hai). Khi tính ứng viên và khi đặt, xoá số, nhớ cập nhật cả mặt nạ đường chéo nếu ô nằm trên đó. Bản Python gom 29 “nhóm” (9 hàng, 9 cột, 9 khối, 2 đường chéo) vào một mảng, mỗi ô biết danh sách nhóm chứa nó, code vừa gọn vừa dễ mở rộng cho các biến thể khác.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int g[81], rowM[9], colM[9], boxM[9], diagM[2];   // diagM[0]: đường chéo chính, diagM[1]: chéo phụ

int boxOf(int p){ return p / 27 * 3 + p % 9 / 3; }
int used(int p){
    int r = p / 9, c = p % 9, u = rowM[r] | colM[c] | boxM[boxOf(p)];
    if(r == c) u |= diagM[0];
    if(r + c == 8) u |= diagM[1];
    return u;
}
void flip(int p, int v){
    int r = p / 9, c = p % 9;
    rowM[r] ^= 1 << v; colM[c] ^= 1 << v; boxM[boxOf(p)] ^= 1 << v;
    if(r == c) diagM[0] ^= 1 << v;
    if(r + c == 8) diagM[1] ^= 1 << v;
}

bool solve(){
    int best = -1, bestMask = 0, bestCnt = 10;
    for(int p = 0; p < 81; p++){
        if(g[p] != 0) continue;
        int mask = ~used(p) & 0x3FE;
        int k = __builtin_popcount(mask);
        if(k < bestCnt){ bestCnt = k; best = p; bestMask = mask; }
        if(k == 0) return false;
    }
    if(best == -1) return true;
    for(int m = bestMask; m > 0; m &= m - 1){
        int v = __builtin_ctz(m);
        g[best] = v; flip(best, v);
        if(solve()) return true;
        flip(best, v); g[best] = 0;
    }
    return false;
}

int main(){
    for(int p = 0; p < 81; p++){
        cin >> g[p];
        if(g[p]) flip(p, g[p]);
    }
    solve();
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++) cout << g[i * 9 + j] << " ";
        cout << "\n";
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def groups(p):                              # các nhóm chứa ô p: hàng, cột, khối, 2 đường chéo
    r, c = divmod(p, 9)
    gs = [r, 9 + c, 18 + r // 3 * 3 + c // 3]
    if r == c:
        gs.append(27)
    if r + c == 8:
        gs.append(28)
    return gs

def solve():
    best, best_mask, best_cnt = -1, 0, 10
    for p in range(81):
        if g[p]:
            continue
        u = 0
        for k in G[p]:
            u |= used[k]
        mask = ~u & 0x3FE
        k = bin(mask).count('1')
        if k < best_cnt:
            best, best_mask, best_cnt = p, mask, k
        if k == 0:
            return False
    if best == -1:
        return True
    m = best_mask
    while m:
        low = m & -m
        m ^= low
        g[best] = low.bit_length() - 1
        for k in G[best]:
            used[k] |= low
        if solve():
            return True
        for k in G[best]:
            used[k] ^= low
        g[best] = 0
    return False

g = list(map(int, sys.stdin.read().split()[:81]))
G = [groups(p) for p in range(81)]
used = [0] * 29                             # 9 hàng, 9 cột, 9 khối, 2 đường chéo
for p in range(81):
    if g[p]:
        for k in G[p]:
            used[k] |= 1 << g[p]
solve()
print('\n'.join(' '.join(map(str, g[i * 9:i * 9 + 9])) for i in range(9)))

Trò chơi tiếp theo · Trò chơi 4

Game 2048 với mảng hai chiều

Trượt, gộp, sinh ô mới: tự lập trình trọn vẹn trò 2048 chỉ với mảng hai chiều và vài vòng lặp gọn gàng, rồi chơi ngay trên trang.

Chơi trò chơi 4 →

← Trò chơi 2: Mê cung Xem cả series Thuật toán qua trò chơi

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!

Lập Trình Thuật Toán

Trò chơi 3: Giải Sudoku bằng quay lui trong C++ và Python: kiểm tra ô hợp lệ, cắt nhánh MRV và bitmask

Lời mở đầu

Phần 1Luật chơi Sudoku và chơi thử

Phần 2Kiểm tra một ô có điền được không

Phần 3Quay lui: thử – sai – quay lại

Phần 4Cắt nhánh: chọn ô ít lựa chọn nhất và dùng bitmask

Phần 5Đề có lời giải duy nhất không?

Bài tậpLuyện quay lui qua các trò điền số

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++