Vấn đề mã hóa hàng ngày: Sử dụng kỹ năng mã hóa của bạn để kiểm tra Checkmate

Kiểm tra chiếu tướng

Chào mừng bạn đến với một vấn đề khác cần giải quyết! Nếu bạn thích chơi cờ và viết mã : cái này dành cho bạn! Hôm nay chúng ta sẽ giúp nhà vua sống sót qua một ngày khác trên chiến trường, đồng thời viết một đống mật mã khá lớn.

Vì vậy, không có gì khó chịu, hãy xem vấn đề của chúng ta. Tuy nhiên, trước khi bắt đầu, như mọi khi, có hai tuyên bố từ chối trách nhiệm:

• Những vấn đề này được cung cấp bởi bản tin tuyệt vời Vấn đề mã hóa hàng ngày mà bạn có thể đăng ký đây : hãy xem và thử giải quyết thử thách hàng ngày của bạn!
• Tôi không phải là một lập trình viên chuyên nghiệp, chỉ là một người thích chia sẻ những nỗ lực (và thất bại) của mình. Nếu bạn có ý tưởng hoặc giải pháp tốt hơn, bạn rất sẵn lòng chia sẻ nó: Tôi rất muốn thấy bạn giải quyết vấn đề đó!

Vấn đề

Vấn đề hôm nay ban đầu được hỏi bởi Oracle.

Bạn được cung cấp một ma trận 8 nhân 8 đại diện cho vị trí của các quân cờ trên bàn cờ vua. Các quân duy nhất trên bàn cờ là vua đen và các quân trắng khác nhau. Với ma trận này, hãy xác định xem vua có bị chiếu hay không.

Để biết chi tiết về cách mỗi quân cờ di chuyển, xem đây .

Ví dụ, cho ma trận sau:

 ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..

Bạn nên trả về True , vì giám mục đang tấn công vua theo đường chéo.

Vấn đề khá rõ ràng, vì vậy chúng tôi sẽ không giải thích thêm về nó. Chúng tôi chỉ cần một số thông số kỹ thuật ban đầu:

1. Chúng ta đang ở trên một biểu đồ, không phải trên một bảng: chúng ta sẽ coi mỗi điểm mà bài toán đưa ra là tâm của một trường hợp trên bảng . Kết quả là như nhau;
2. Vua trắng đã đi nghỉ cùng với 7 quân tốt khác: quân vua và quân tốt là những quân cờ nhàm chán nhất và việc loại bỏ chúng sẽ không thay đổi nhiều giải pháp của chúng ta;
3. Chúng ta cần xác minh xem vua có đang chiếu ở lượt này hay không , nghĩa là ở lượt trắng tiếp theo, quân vua không di chuyển sẽ được thực hiện;
4. Các vị trí ban đầu được đưa ra bởi trò chơi : Tôi sẽ không đi vào xác minh các quân cờ chồng chéo hoặc vị trí xuất phát sai.

Giải pháp

Trước hết, tóm tắt nhanh về quân cờ và nước đi:

Với vị trí bắt đầu của mỗi quân cờ và nước đi của quân cờ đó, chúng ta có thể “dễ dàng” tính toán mọi nước đi tiếp theo có thể có của mỗi quân cờ .

Và vì tất cả họ đều quan tâm đến việc bắt vua càng nhanh càng tốt, nên chúng ta có thể cho rằng nước đi tiếp theo của họ sẽ là bắt vua đen . Vì vậy, vì chúng ta cũng biết vị trí quân vua đen, nên chúng ta chỉ cần kiểm tra xem vị trí quân đen có phải là một trong những nước đi tiếp theo có thể có của các quân khác hay không . Nếu đúng như vậy, trong lượt trắng tiếp theo, quân trắng sẽ di chuyển đến đó để bắt vua đen.

Tình hình trông giống như thế này:
Trong hình trên, bạn có thể thấy (… Tôi hy vọng vậy, xin lỗi vì sự nhầm lẫn…) mọi nước đi có thể có của từng quân ở bên trắng, được tô bằng các màu khác nhau và quân đen ở trên đang chờ bị bắt. Vì vậy, ví dụ, giám mục, bắt đầu từ (2,7), có thể di chuyển đến (1,6), (1,8), (3,8), (3,6), (4,5), (5, 4) và vân vân.

Tôi chỉ quyết định ngẫu nhiên vị trí bắt đầu của những quân cờ này vì điều này không ảnh hưởng đến kết quả cuối cùng.

Vì chúng ta đang ở trên biểu đồ 8x8 (rõ ràng, bất kỳ kích thước nào khác sẽ hoạt động theo cách tương tự) và chúng ta có tọa độ bắt đầu của từng quân cờ, nên chúng ta có thể tạo chuỗi tọa độ x, y sẽ là các quân cờ tiếp theo của chúng ta. Để làm điều này, trước tiên chúng ta xác định một lớp cho mỗi quân cờ, xác định tọa độ của nó và sau đó xác định các quy tắc để tính toán mọi nước đi có thể có từ đó.

Các quân cờ — The Pawn

Hãy bắt đầu đơn giản với Cầm đồ. Nhân tiện, tôi đang xây dựng cái này bằng Python , vì nó là một trong những ngôn ngữ phổ biến nhất vào lúc này và được cho là dễ đọc nhất đối với bất kỳ ai. Tuy nhiên, bạn sẽ cần biết lớp học là gì để có thể theo dõi kể từ bây giờ. Đây là một lời giải thích khá gọn gàng về khái niệm này.

Hãy giải thích ngắn gọn: trước tiên chúng ta định nghĩa lớp class Pawn và __init__ tọa độ của nó x,y . Sau đó, chúng tôi xác định phương thức possibleMoves để tính toán các nước đi tốt có thể từ đó. Các bước di chuyển của con tốt tương đối dễ dàng, vì vậy chúng ta chỉ cần thêm chúng vào moves số lần di chuyển, sau khi kiểm tra rằng nó không di chuyển ra ngoài lưới của chúng ta và trả về mảng moves . Hai điều cần lưu ý ở đây, đặc biệt đối với cầm đồ:

1. Chúng ta coi quân tốt trắng di chuyển từ dưới lên trên, giống như nếu chúng ta là người chơi trắng di chuyển quân tốt về phía đối thủ của chúng ta. Điều này không thực sự thay đổi bất cứ điều gì, nó chỉ giữ mọi thứ theo thứ tự.

2. Chúng tôi cố ý bỏ qua chuyển động bình thường , vì chúng tôi quan tâm đến việc bắt vua đen: vì quân tốt chỉ có thể bắt theo đường chéo và chúng tôi không quan tâm đến việc di chuyển quân theo các hướng khác, chúng tôi có thể bỏ qua chuyển động bình thường của nó.

   
   

Bây giờ chúng ta có thể đơn giản kiểm tra nước đi của quân tốt bằng cách cho anh ta print(Pawn(7,2).possibleMoves()) độ của nó và gọi phương thức possibleMoves [(6,3),(8,3)] .

Ngoài ra, bạn có thể thấy ở trên cùng rằng chúng tôi đã xác định kích thước lưới của mình là các biến , vì vậy chúng tôi có thể thay đổi chúng để chạy thuật toán trên các bảng có kích thước khác.

Bây giờ chúng ta hãy chuyển sang tháp.

Tháp

Một lần nữa, chúng ta khởi tạo lớp Tower với tọa độ của nó và định nghĩa hàm possibleMoves . Để thu thập tất cả các bước di chuyển có thể có ở đây , chúng tôi sắp xếp tất cả các điểm trên hai trục của tháp và thêm từng tọa độ đơn lẻ vào moves số lần di chuyển, giá trị này sẽ được trả về sau tất cả các vòng lặp. Như trước đây, để kiểm tra các bước di chuyển của tháp, chúng ta chỉ cần print(Tower(5,3).possibleMoves()) và chúng ta sẽ nhận được kết quả như sau: [(1,3), (2,3), (3,3), ..., (5,8)] .

giám mục

Bây giờ là lúc cho giám mục.

Di chuyển của Bishop phức tạp hơn tháp, vì vậy chúng tôi có thể giải thích một chút về những gì đang xảy ra ở đây. Về cơ bản, chúng ta cần thu thập các điểm trên hai trục chéo bắt đầu từ vị trí bắt đầu của nó . Sau khi khai báo lớp và phương thức init, chúng tôi tạo hai biến: moves , như trước đây và currentPos , sẽ được sử dụng để theo dõi các điểm chúng tôi đã thu thập được khi di chuyển dọc theo các trục của nó. Bây giờ sử dụng vòng lặp while và kiểm tra xem chúng ta có di chuyển ra ngoài lưới không, chúng ta tăng và giảm x và y tương ứng với nơi chúng ta muốn di chuyển . Ví dụ: nếu chúng ta muốn di chuyển lên trên bên trái từ vị trí bắt đầu của nó, chúng ta sẽ cần giảm giá trị x trong khi tăng giá trị y . Nếu chúng ta muốn di chuyển xuống bên phải, chúng ta sẽ cần tăng giá trị x trong khi giảm giá trị y , v.v. Cuối cùng, chúng tôi chỉ cần quay lại moves một lần nữa.

Nữ hoàng

Bây giờ bạn có thể nghĩ: nếu di chuyển tháp phức tạp và giám mục thậm chí còn nhiều hơn, làm thế quái nào chúng ta sẽ mã hóa nữ hoàng? Trên thực tế, các nước đi của nữ hoàng là dễ dàng nhất để mã hóa, chỉ với sự trợ giúp của một thủ thuật đơn giản. Hãy xem nữ hoàng sau đó.

Được rồi, có chuyện gì vậy? Chà, nếu chúng ta nghĩ về điều đó, quân hậu có những nước đi giống quân tượng và tòa tháp cộng lại . Cô ấy giống một mecha-bot giám mục hình tháp hơn là một nữ hoàng. Vì lý do này, mã hóa các bước di chuyển của cô ấy thực sự đơn giản. Sau khi khai báo lớp của cô ấy, chúng ta chỉ cần định nghĩa possibleMoves của cô ấy là một mảng kết hợp các bước di chuyển do các bước di chuyển có thể có của tượng và tháp .

Lưu ý rằng trong khi gọi các lớp Bishop và Tower trong hàm possibleMoves , các tham số x và y của chúng được cung cấp là self.x, self.y , vì vậy chúng thực sự là tọa độ của quân hậu.

Hiệp sĩ

Bây giờ đến hiệp sĩ!

Hiệp sĩ là đặc biệt nhất đối với tôi. Bộ di chuyển của anh ấy rất lạ, giống như hình chữ “L”, vì vậy tôi không tìm ra cách nào đặc biệt thông minh hoặc nhanh chóng để mã hóa nó và cuối cùng tôi đã khó mã hóa các bước đi của nó chỉ đơn giản là tính toán từng nước đi trong số 8 nước đi có thể có của anh ấy từ vị trí bắt đầu .

Nhà vua

Đôi nét khái niệm về vua. Vì chúng ta không bắt buộc phải di chuyển vua, chỉ đưa ra nếu anh ta được kiểm tra hay không, nên chúng ta không thực sự cần thực hiện bộ di chuyển của anh ta . Tuy nhiên, chúng ta cũng sẽ thấy một triển khai ngắn gọn ở cuối bài viết. Ngoài ra, mã hóa nó không đơn giản như giảm sức mạnh cho nước đi của nữ hoàng, như chúng ta sẽ thấy sau. Vì vậy, bây giờ, hãy bỏ qua các chuyển động của anh ấy và xem giải pháp.

Mã giải pháp

Cho rằng chúng ta có các vị trí có thể cho mỗi quân, giải pháp bây giờ khá đơn giản: chúng ta chỉ cần kiểm tra xem tọa độ của quân đen có nằm trong tập hợp các nước đi của một hoặc nhiều quân khác hay không. Hãy mã hóa nó!

Bây giờ chúng ta chỉ cần tạo một biến blackKing dưới dạng một vài tọa độ. Sau đó, đối với mỗi phần, chúng tôi tạo một thể hiện của lớp mà chúng tôi vừa tạo và gọi phương thức possibleMoves để tính toàn bộ các bước di chuyển của nó. Khi chúng tôi có nó, chúng tôi kiểm tra xem tọa độ blackKing có xuất hiện trong các bộ di chuyển đó hay không : nếu có, chúng tôi in ra rằng quân vua được kiểm tra bởi quân cờ cụ thể đó. Kết quả ở đây là một cái gì đó như thế này:

 Pawn moves: [(8, 3), (6, 3)] Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)] Check by the tower! Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)] Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)] Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)] Check by the knight!

Tôi đã sử dụng hình ảnh lộn xộn ở trên để tham khảo, vì vậy bạn có thể kiểm tra xem nhà vua có thực sự bị kiểm tra bởi tháp và hiệp sĩ hay không.

kiểm tra người bạn đời

Còn nếu chúng ta cũng muốn tính toán xem vua vẫn còn một số cơ hội sống sót hay nó thực sự là người kiểm tra thì sao? Với mục đích này, chúng ta cần tính toán các nước đi của nhà vua.

Hãy mô tả nó một chút. Trước hết, chúng tôi xác định lớp và tọa độ của chúng tôi như trước. Sau đó, chúng tôi tạo phương thức possibleMoves và mã hóa các nước đi có thể có của quân vua (một lần nữa, tôi khá chắc chắn rằng có một cách nhanh hơn, nhưng chỉ có 8 nước đi khả thi nên…). Sau đó, chúng tôi kiểm tra những nước đi nào là bất hợp pháp (di chuyển ra ngoài bàn cờ) và chỉ trả về những validMoves .

Vì vậy, bây giờ, để kiểm tra xem quân vua có còn cơ hội sống sót hay không, chúng ta cần kiểm tra xem có bất kỳ nước đi khả thi nào của anh ta không nằm trong một tập hợp các nước đi khác hay không. Để làm điều này, chúng ta chỉ cần lặp lại các nước đi của quân vua và các nước đi khác.

Vì vậy, vẫn còn hy vọng cho vị vua của chúng ta sống sót! Tôi đoán là may mắn cho anh ấy…

Độ phức tạp về thời gian

Như mọi khi, một cái nhìn ngắn gọn về thời gian phức tạp của giải pháp này.

Trước hết, vì mỗi phần là một thể hiện của một lớp , chúng ta phải xem xét thời gian để khởi tạo thể hiện đó.

• Các quân cờ như quân tốt hoặc quân mã không có bất kỳ vòng lặp nào bên trong chúng và không phụ thuộc vào bất kỳ chiều biến đổi nào, vì vậy chúng ta có thể coi chúng là O(1);
• Cái tháp hơi phức tạp một chút: vì nó chứa 4 vòng lặp for nên bạn có thể nghĩ ngay rằng độ phức tạp thời gian của nó là O(n), phải không? Trên thực tế, nếu chúng ta nghĩ về cách di chuyển của tòa tháp, chúng ta sẽ nhận thấy rằng bất kể nó được đặt ở đâu trên bàn cờ, các bước di chuyển của nó bị giới hạn trong các trường hợp ván tự do trên các trục dọc và ngang của nó. Và vì bàn cờ là hình vuông nên chúng ta sẽ luôn có 14 thùng miễn phí để di chuyển tòa tháp của mình. Vì vậy, độ phức tạp thời gian của nó thực sự phải là O(1), không đổi với 14 cặp tọa độ. Đây là một ví dụ đồ họa:

• Thật không may, chúng ta không thể nói điều tương tự đối với giám mục , tập hợp các bước di chuyển có vẻ phức tạp hơn một chút. Về cơ bản, nó có 7, 9, 11 hoặc 13 nước đi tùy thuộc vào vị trí của nó trên bàn cờ. Do đó, các bước cần thiết để tính toán tập hợp các nước đi của anh ta dựa trên vị trí của anh ta, do đó chúng ta có thể coi tc là O(n).

• Nữ hoàng cần tập hợp các bước di chuyển của tháp và giám mục. Vì trong khi đánh giá độ phức tạp của thời gian, chúng ta phải tập trung vào kịch bản xấu nhất , tc của giám mục chiếm ưu thế so với tc của tòa tháp. Vì vậy, chúng ta phải xem xét một tc của O(n) cũng cho nữ hoàng.

• Cuối cùng, nhà vua có một tập hợp các bước di chuyển được mã hóa cứng, nhưng cũng có một quy trình xác thực liên quan sử dụng vòng lặp for . Vì vậy, về mặt kỹ thuật, ngay cả khi tập hợp các nước đi của vua tương đối nhỏ trong mọi trường hợp, chúng ta phải coi tc của anh ta là O(n), cũng tùy thuộc vào vị trí của anh ta trên bàn cờ.

  
  

Tại thời điểm này, chúng tôi sử dụng vòng lặp for cho từng quân cờ để xác minh và in ra trạng thái kiểm tra của vua đen . Điều này không gây ra vấn đề gì cho chúng tôi khi tc không đổi (ví dụ: lấy tháp: chúng tôi tính toán 14 lần di chuyển của nó và sau đó lặp tối đa 14 lần khác trên chúng, vì vậy chúng tôi có thể coi đó cũng là thời gian cố định). Tuy nhiên, chúng tôi sẽ gặp rắc rối khi tc là O(n) hoặc cao hơn, vì chúng tôi đang thêm một vòng lặp cũng sẽ tăng lên trong khi số lần di chuyển tăng lên.

Cuối cùng, chúng ta sử dụng vòng lặp for kép (bên trong) để xác minh quân cờ , chắc chắn sẽ là tc của O(n²), tùy thuộc vào số nước đi của quân vua và nước đi của các quân khác.

Đó là nó; có giải pháp của tôi. Tôi biết rõ rằng một số điểm không hiệu quả nhất có thể, nhưng trong khi viết, tôi thích ý tưởng mô tả quy trình hơn là xây dựng giải pháp hoàn hảo.

Bạn nghĩ gì về điều này? Hãy cho tôi ý kiến của bạn về nó và hãy thảo luận về các giải pháp của bạn trong phần bình luận!

Như mọi khi, nếu bạn thích bài viết này, vui lòng để lại một hoặc hai tiếng vỗ tay và đăng ký hoặc chia sẻ nó với ai đó có thể quan tâm đến loại thuật toán này, nếu bạn có thể! Cảm ơn bạn đã đọc đến cuối, lần này nhiều hơn mọi khi với độ dài của giải pháp này!

Như mọi khi, cảm ơn vì đã đọc.