Mã đi tuần bằng quay lui

Trên bàn cờ 8×8, từ vị trí ban đầu cần tìm hành trình qua mọi ô đúng một lần. Bài không yêu cầu bước cuối quay về ô đầu. board dùng −1 cho ô chưa đi; ô xuất phát mang số 0, các ô sau mang 1…63. Trong tệp này dùng tên row cho hàng, col cho cột và truy cập board[row][col], tránh nhầm với x,y của bài mê cung. Quân Mã đi lệch 2 hàng và 1 cột, hoặc 1 hàng và 2 cột, theo các dấu âm/dương. Có tối đa tám ứng viên; ở biên hoặc gần ô đã đi thì số lựa chọn hợp lệ ít hơn.

```python def isOK(row, col, board): n = len(board) return 0 <= row < n and 0 <= col < n and board[row][col] == -1 ``` Kiểm biên trước khi đọc board[row][col]. Dấu−1 là điều kiện chọn ô tiếp theo; số 0 vẫn là một ô đã đi, không phải ô trống.

```python def knightTraverse(n, board, row, col, pos): if pos == n * n: return True move_row = [2, 1, -1, -2, -2, -1, 1, 2] move_col = [1, 2, 2, 1, -1, -2, -2, -1] for i in range(8): next_row = row + move_row[i] next_col = col + move_col[i] if isOK(next_row, next_col, board): board[next_row][next_col] = pos if knightTraverse(n, board, next_row, next_col, pos + 1): return True board[next_row][next_col] = -1 return False ``` Khởi tạo board toàn −1, đặt board[row][col]=0 ở vị trí xuất phát, gọi với pos=1. pos là số thứ tự sẽ gán cho ô kế tiếp. Khi pos==n*n, tất cả n*n ô đã được đánh số 0…n*n−1 nên trả True. Nếu nhánh con thất bại, trả ô vừa thử về −1 rồi xét ứng viên khác. Nếu thành công thì giữ ma trận và trả True qua các mức. Thứ tự tám nước trong tệp theo SGV; không bảo đảm thời gian chạy ngắn cho mọi điểm xuất phát.