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à : 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. viết mã 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ý : hãy xem và thử giải quyết thử thách hàng ngày của bạn! đây 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. ma trận Bạn được cung cấp một 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: Chúng ta đang ở trên một biểu đồ, không phải trên một bảng: . Kết quả là như nhau; 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 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; Chúng ta cần , nghĩa là ở lượt trắng tiếp theo, quân vua không di chuyển sẽ được thực hiện; xác minh xem vua có đang chiếu ở lượt này hay không : 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. Các vị trí ban đầu được đưa ra bởi trò chơi 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 . Vì vậy, vì chúng ta cũng biết vị trí quân vua đen, nên chúng ta . 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. nước đi tiếp theo của họ sẽ là bắt vua đen 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 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…) ở 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. mọi nước đi có thể có của từng quâ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 độ 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 xác định tọa độ của nó và sau đó x, y lớp cho mỗi quân cờ, 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 , 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, để có thể theo dõi kể từ bây giờ. một lời giải thích khá gọn gàng về khái niệm này. Python bạn sẽ cần biết lớp học là gì Đây là https://Gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py Hãy giải thích ngắn gọn: trước tiên chúng ta định nghĩa lớp và tọa độ của nó . Sau đó, chúng tôi xác định phương thức để 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 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 . Hai điều cần lưu ý ở đây, đặc biệt đối với cầm đồ: class Pawn __init__ x,y possibleMoves moves moves 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ự. Chúng tôi , 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ó. cố ý bỏ qua chuyển động bình thường 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 độ của nó và gọi phương thức . print(Pawn(7,2).possibleMoves()) possibleMoves [(6,3),(8,3)] Ngoài ra, bạn có thể thấy ở trên cùng rằng , 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. chúng tôi đã xác định kích thước lưới của mình là các biến Bây giờ chúng ta hãy chuyển sang tháp. Tháp https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py 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 . Để thu thập tất cả các bước di chuyển có thể có ở đây 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 và chúng ta sẽ nhận được kết quả như sau: . possibleMoves , 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 print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)] giám mục Bây giờ là lúc cho giám mục. https://Gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py 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, . Sau khi khai báo lớp và phương thức init, chúng tôi tạo hai biến: , như trước đây và , 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 và kiểm tra xem chúng ta có di chuyển ra ngoài lưới không, chúng ta và . 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ị trong khi tăng giá trị . 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ị trong khi giảm giá trị , v.v. Cuối cùng, chúng tôi chỉ cần quay lại một lần nữa. 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ó moves currentPos while tăng và giảm x y tương ứng với nơi chúng ta muốn di chuyển x y x y moves 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 đó. https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py Được rồi, có chuyện gì vậy? Chà, nếu chúng ta nghĩ về điều đó, . 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 của cô ấy là một . 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 possibleMoves 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 và trong hàm , các tham số và của chúng được cung cấp là , vì vậy chúng thực sự là tọa độ của quân hậu. Bishop Tower possibleMoves x y self.x, self.y Hiệp sĩ Bây giờ đến hiệp sĩ! https://Gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py 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, . 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. nên chúng ta không thực sự cần thực hiện bộ di chuyển của anh ta 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ó! https://Gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py Bây giờ chúng ta chỉ cần tạo một biến 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 để tính toàn bộ các bước di chuyển của nó. tọa độ : 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: blackKing possibleMoves Khi chúng tôi có nó, chúng tôi kiểm tra xem blackKing có xuất hiện trong các bộ di chuyển đó hay không 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 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. vua vẫn còn một số cơ hội sống sót https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py 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 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 đó, và chỉ trả về những . possibleMoves 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ờ) 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, Để 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. 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. https://Gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py 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 , chúng ta phải xem xét thời gian để khởi tạo thể hiện đó. thể hiện của một lớp Các quân cờ như 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); quân tốt hoặc quân mã Cái 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 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áp 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 Thật không may, chúng ta không thể nói điều tương tự đối với , 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). giám mục cần tập hợp các bước di chuyển của tháp và giám mục. Vì , 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. Nữ hoàng 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 Cuối cùng, 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 . 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ờ. nhà vua quy trình xác thực liên quan sử dụng vòng lặp for Tại thời điểm này, chúng tôi sử dụng . Đ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. 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 Cuối cùng, , 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. chúng ta sử dụng vòng lặp for kép (bên trong) để xác minh quân 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.

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Nghe bài viết này bằng Tiếng Anh, đọc bởi robot thông minh của HackerNoon

dài quá đọc không nổi

Making security fun one episode at a time

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

dài quá đọc không nổi

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

chuyên mục

Languages

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI...

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

dài quá đọc không nổi

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

chuyên mục

Languages

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI...

NHỮNG BÀI VIẾT LIÊN QUAN