Kiểm tra vua có nước đi hợp lệ khi có N mã trên bàn cờ vô hạn trong Python

Cho bàn cờ vô hạn, tọa độ N con mã (knight) và vị trí vua (king). Kiểm tra vua có bị chiếu bí (không có nước đi an toàn) không. Tọa độ trong khoảng [-10^9, 10^9].

Ví dụ: mã tại [[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]], vua tại [4,3] → True (vua không có nước đi).

Thuật toán

• Dùng từ điển my_dict đánh dấu ô bị tấn công: vị trí mã + 8 ô mã có thể nhảy đến
• Kiểm tra 8 ô xung quanh vua (kể cả chéo): nếu có ô không bị đánh dấu → vua có nước đi → False
• Nếu tất cả 8 ô đều bị tấn công → True (chiếu bí)

Ví dụ mã Python

def is_checkmate(a, n, king_pos):
    my_dict = {}
    for i in range(n):
        x, y = a[i][0], a[i][1]
        my_dict[(x, y)] = 1
        my_dict[(x-2, y+1)] = 1
        my_dict[(x-2, y-1)] = 1
        my_dict[(x+1, y+2)] = 1
        my_dict[(x+1, y-2)] = 1
        my_dict[(x-1, y+2)] = 1
        my_dict[(x+2, y+1)] = 1
        my_dict[(x+2, y-1)] = 1
        my_dict[(x-1, y-2)] = 1
    for i in range(-1, 2):
        for j in range(-1, 2):
            nx = king_pos[0] + i
            ny = king_pos[1] + j
            if i != 0 and j != 0:
                if not my_dict.get((nx, ny), 0):
                    return False
    return True

a = [[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]]
n = len(a)
pos = [4, 3]
print(is_checkmate(a, n, pos))

Đầu vào

[[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]], 6, [4, 3]

Đầu ra

True