🎯 Mục tiêu bài học

• Áp dụng quay lui vào một bài thực tế phức tạp hơn tổ hợp/hoán vị.
• Hiểu cách kiểm tra điều kiện hợp lệ cục bộ trước khi đi sâu hơn.
• Đây là dạng bài rất hay gặp ở vòng loại HSG vì nó “đời thực nhưng giải thuật”.

📘 Mô tả bài toán

Sudoku chuẩn: bảng 9×9, điền số từ 1..9 sao cho: - Không lặp trong hàng - Không lặp trong cột - Không lặp trong mỗi ô vuông 3×3 Các ô chưa biết thường được đánh số 0.

💻 Thuật toán quay lui Sudoku

1. Tìm ô còn 0.
2. Thử đặt 1..9 vào ô đó nếu hợp lệ.
3. Nếu hợp lệ: đệ quy giải phần còn lại.
4. Nếu sau này bí → quay lui, thử giá trị khác.

Python

board = [list(map(int, input().split())) for _ in range(9)]

def ok(r, c, val):
    # check row, col
    for i in range(9):
        if board[r][i] == val: return False
        if board[i][c] == val: return False
    # check 3x3 box
    br, bc = (r//3)*3, (c//3)*3
    for i in range(3):
        for j in range(3):
            if board[br+i][bc+j] == val:
                return False
    return True

def solve():
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                for v in range(1,10):
                    if ok(r,c,v):
                        board[r][c] = v
                        if solve():
                            return True
                        board[r][c] = 0
                return False
    return True

solve()
for row in board:
    print(*row)

C++

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

int board[9][9];

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

bool solve(){
    for(int r=0;r<9;r++){
        for(int c=0;c<9;c++){
            if(board[r][c]==0){
                for(int v=1;v<=9;v++){
                    if(ok(r,c,v)){
                        board[r][c]=v;
                        if(solve()) return true;
                        board[r][c]=0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

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

🧩 Bài tập luyện tập

1. Đếm xem có bao nhiêu nghiệm Sudoku hợp lệ (không chỉ tìm 1 nghiệm).
2. Viết chương trình in từng bước thử (log lại các lựa chọn).
3. Nâng cấp để phát hiện input vô nghiệm (in ra “No solution”).

# Ý tưởng:
# - thay vì return True khi tìm được nghiệm đầu tiên
# - bạn tăng biến đếm global và TIẾP TỤC quay lui để tìm nghiệm tiếp
# => dùng cho đề kiểu "Có bao nhiêu cách điền?"