Bài toán sudoku

[franciscokison]

Nguyên văn bởi khanhoatink4

Như chúng ta đã biết trò chơi sudoku là một trò chơi khá nổi tiếng...Mình có 1 thắc mắc là hỏi có bao nhiêu cách điền vào các ô sudoku mà không lặp lại. Ban đầu các ô của sudoku đều trống.

Số cách điền này phụ thuộc vào thuật toán mà mình đưa ra, nếu dùng nguyên quay lui thì là $9!\cdot 8!\cdot...\cdot\1! $, nếu kết hợp thêm các hàm (các nhiều càng tốt- đỡ mất nhiều trường hợp quay lui) nhưng số phép toán so sánh tăng lên):
-Kiểm tra tính hiện diện: xem trong hàng, cột, vùng (3x3) đã có chưa
-Kiểm tra tính tồn tại: nếu trong hàng, cột, vùng chưa có
-...
Tức là mỗi phần tử (ô) gắn cho một mảng chứa các địa chỉ "đánh dấu" được điền, không được điền và chưa điền, khi ấy ở mỗi bước backtracking kiểm tra là ok.
Cuối cùng tính độ phức tạp của nó
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]