Máy tính bác bỏ

28

máy tính
bác bỏ

bài toán sau đây thuộc về nhà toán học vĩ đại L. Euler:

Cùng hiệp sĩ của bạn đi xung quanh tất cả các ô trên bàn cờ, nâng từng ô một trong mỗi ô.

Vào năm 1823, Varisdorf, trong tập tài liệu “Đơn giản và tổng quát nhất lời giải bài toán về nước đi của hiệp sĩ,” đã đề xuất các quy tắc sau để đi ngang bàn cờ:

Trong mỗi lần di chuyển, hiệp sĩ đặt cược vào ô mặt nạ mà từ đó có thể thực hiện số lần di chuyển nhỏ nhất đến các ô chưa được che. Nếu có nhiều mặt nạ tế bào, bạn được phép chọn bất kỳ mặt nạ nào trong số đó.

Lưu ý rằng quy tắc Warisdorff không phải là một thuật toán, vì nó không phải lúc nào cũng chỉ rõ bước đi tiếp theo của hiệp sĩ (xem cụm từ thứ hai của quy tắc).

Ví dụ: nếu một hiệp sĩ bắt đầu di chuyển từ ô d4, quy tắc Warisdorff cho phép anh ta thực hiện bước đi đầu tiên đến bất kỳ ô b3, b5, c2, e2 nào (Hình 1). (Tuy nhiên, nếu quân mã bắt đầu di chuyển từ ô c2, thì ngay cả ở nước đi đầu tiên, quy tắc Warisdorff sẽ cho anh ta biết rõ ràng nơi phải đi - đến ô a1!)

Warisdorf tuyên bố rằng, bất kể hiệp sĩ bắt đầu di chuyển ở đâu, bất kỳ con đường nào thỏa mãn các quy tắc của anh ta cuối cùng sẽ dẫn đến một vòng hoàn chỉnh của bàn cờ (tức là tới lời giải bài toán của Euler). Cho đến gần đây, người ta vẫn chưa biết liệu tuyên bố này có đúng hay không. Trở lại năm 1971, E. Ya. Gik đã viết trong «Kvant» (Số 9, trang 53) rằng tuyên bố của Varisdorf “luôn hợp lý trong thực tế…, mặc dù nó không được xác nhận về mặt lý thuyết.”

Một chương trình được biên soạn cho máy tính “Promin-2” để liệt kê một số đường đi của ngựa. Biện pháp đối phó đầu tiên được xây dựng trong vòng chưa đầy 1 phút. Đã thử 6464 đường dẫn, máy tính nhận được biện pháp đối phó

Hình 1.
Hình 2.