Überprüfen Sie den Schachmatt. Willkommen bei einem weiteren Problem, das es zu lösen gilt! Wenn Sie gerne Schach spielen und   : Das ist das Richtige für Sie! Heute werden wir dem König helfen, einen weiteren Tag auf dem Schlachtfeld zu überleben, und außerdem eine Menge Code schreiben.  programmieren  Sehen wir uns also ohne weitere Umschweife unser Problem an. Bevor es jedoch losgeht, wie immer, zwei Haftungsausschlüsse:  Diese Probleme liefert der wunderbare Newsletter Daily Coding Problem, den Sie abonnieren können  : Probieren Sie es aus und versuchen Sie auch, Ihre tägliche Herausforderung zu lösen!   Hier  Ich bin kein erfahrener Programmierer, sondern nur ein Typ, der gerne seine Versuche (und Misserfolge) teilt. Wenn Sie eine bessere Idee oder Lösung haben, können Sie diese gerne mit uns teilen: Ich würde mich freuen, wenn Sie sie in Angriff nehmen!  Das Problem  Das heutige Problem wurde ursprünglich von Oracle gestellt.  Ihnen wird eine       große Matrix    8 x 8 angezeigt, die die Positionen der Figuren auf einem Schachbrett darstellt. Die einzigen Figuren auf dem Spielbrett sind der schwarze König und verschiedene weiße Figuren. Bestimmen Sie anhand dieser Matrix, ob der König im Schach steht.     Einzelheiten dazu, wie sich die einzelnen Teile bewegen, finden Sie unter   Hier .   Zum Beispiel anhand der folgenden Matrix:   ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..      zurückgeben  Sie sollten True , da der Läufer den König diagonal angreift.  Das Problem ist ziemlich klar, daher werden wir nicht weiter darauf eingehen. Wir benötigen jedoch nur einige Startspezifikationen:  Wir befinden uns in einem Diagramm, nicht auf einer Tafel:   . Das Ergebnis ist genau das gleiche; Wir betrachten jeden durch das Problem vorgegebenen Punkt als Mittelpunkt eines Falles auf der Tafel  Der weiße König ist mit den anderen 7 Bauern in den Urlaub gefahren: König und Bauern sind von allen Figuren die langweiligsten und das Entfernen wird an unserer Lösung nicht viel ändern;  Wir müssen   , was bedeutet, dass er in der nächsten weißen Runde genommen wird, wenn er nicht zieht; überprüfen, ob der König in genau dieser Runde im Schach steht    : Ich werde nicht auf die Überprüfung auf überlappende Teile oder falsche Startpositionen eingehen. Die Positionen werden zunächst vom Spiel vorgegeben  Die Lösung  Zunächst eine kurze Zusammenfassung der Figuren und Zugsätze:   Angesichts der Startposition jeder Figur und ihres Zugsatzes können wir „einfach“   . jeden möglichen nächsten Zug jeder Figur berechnen  Und da sie alle daran interessiert sind, den König so schnell wie möglich zu schlagen, können wir davon ausgehen, dass   . Da wir also auch die Position des schwarzen Königs kennen,   . Wenn dies der Fall ist, wird die weiße Figur während der nächsten weißen Runde dorthin ziehen, um den schwarzen König zu schlagen. ihr nächster Zug der Schlag des schwarzen Königs sein wird müssen wir nur prüfen, ob die Position des schwarzen Königs einer der möglichen nächsten Züge der anderen Figuren ist  Die Situation sieht in etwa so aus:  Im Bild oben sieht man (… ich hoffe es, entschuldigen Sie die Verwirrung …)   auf der weißen Seite, gefärbt mit verschiedenen Farben, und den schwarzen König darüber, der darauf wartet, geschlagen zu werden. So kann zum Beispiel der Läufer, beginnend in (2,7), zu (1,6), (1,8), (3,8), (3,6), (4,5), (5, 4) und so weiter. jeden möglichen Zug jeder Figur  Ich habe die Startpositionen dieser Teile einfach zufällig festgelegt, da dies keinen Einfluss auf das Endergebnis hat.  Da wir uns in einem 8x8-Diagramm befinden (um es klarzustellen, alle anderen Dimensionen funktionieren genauso) und wir die Startkoordinaten jeder Figur haben, können wir eine Reihe von Koordinaten   erstellen, die unsere Figuren in den nächsten Zügen sein werden. Dazu definieren wir zunächst eine   definieren seine Koordinaten und  x,y Klasse für jedes Stück, definieren dann die Regeln, um von dort aus jeden möglichen Zug zu berechnen.   Die Figuren – Der Bauer  Beginnen wir einfach mit dem Bauern. Übrigens erstelle ich dies in   , da es derzeit eine der beliebtesten und wohl für jedermann am besten lesbaren Sprachen ist. Dennoch   um von nun an folgen zu können.  eine ziemlich nette Erklärung dieses Konzepts. Python müssen Sie wissen, was eine Klasse ist,   Hier ist   https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py  Lassen Sie es uns kurz erklären: Wir definieren zunächst die Klasse   und   ihre Koordinaten   . Danach definieren wir die Methode   , um von dort aus die möglichen Züge des Bauern zu berechnen. Die Bauernbewegungen sind relativ einfach, daher fügen wir sie einfach zur Variablen „   hinzu, nachdem wir überprüft haben, dass sie sich nicht außerhalb unseres Rasters bewegt, und geben das   -Array zurück. Hier sind zwei Dinge zu beachten, insbesondere für den Bauern: class Pawn __init__ x,y possibleMoves moves moves  Wir gehen davon aus, dass sich der weiße Bauer von unten nach oben bewegt, als ob wir der weiße Spieler wären, der seinen Bauern vorwärts in Richtung unseres Gegners bewegt. Das ändert eigentlich nichts, es sorgt nur für Ordnung.  Wir   , da wir daran interessiert sind, den schwarzen König zu schlagen: Da der Bauer nur diagonal schlagen kann und es uns egal ist, die Figuren in andere Richtungen zu bewegen, können wir seine normale Bewegung überspringen. überspringen absichtlich die normale Bewegung  Jetzt können wir einfach die Bewegungen des Bauern überprüfen, indem wir ihm seine Koordinaten geben und die Methode   aufrufen, etwa so:   und wir sollten so etwas wie   . possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)]  Außerdem können Sie oben sehen, dass   , sodass wir sie möglicherweise ändern können, um den Algorithmus auf Brettern mit anderen Maßen auszuführen. wir unsere Rastermaße als Variablen definiert haben  Kommen wir nun zum Turm.  Der Turm   https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py  Auch hier initialisieren wir die Tower-Klasse mit ihren Koordinaten und definieren die Funktion   . Um hier alle möglichen Bewegungen zu sammeln     , die nach allen Schleifen zurückgegeben wird. Um die Turmbewegungen zu überprüfen, können wir wie zuvor einfach   und erhalten dann etwa Folgendes:   . possibleMoves , ordnen wir alle Punkte auf den beiden Achsen des Turms an und addieren jede einzelne Koordinate zur Variablen „ moves print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)]  Der Bischof  Jetzt ist es Zeit für den Bischof.   https://gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py  Die Bewegungen des Bischofs sind komplexer als die des Turms, deshalb erklären wir vielleicht ein wenig, was hier passiert. Grundsätzlich   . Nachdem wir die Klasse und die Init-Methode deklariert haben, erstellen wir zwei Variablen:   “ wie zuvor und   “, die verwendet werden, um die Punkte zu verfolgen, die wir während der Bewegung entlang ihrer Achsen gesammelt haben. Verwenden Sie nun   Schleife und prüfen Sie, ob wir uns nicht außerhalb unseres Rasters bewegen. Wir     und     . Wenn wir uns beispielsweise von der Startposition aus nach links oben bewegen möchten, müssen wir den   Wert verringern und gleichzeitig den   Wert erhöhen. Wenn wir nach rechts unten gehen wollen, müssen wir den   Wert erhöhen und gleichzeitig den   Wert verringern usw. Zum Schluss führen wir einfach noch einmal   aus. müssen wir ausgehend von der Startposition Punkte auf den beiden Diagonalachsen sammeln moves currentPos while erhöhen und verringern x y entsprechend der Position, in die wir uns bewegen möchten x y x y moves  Die Königin  Nun könnten Sie denken: Wenn Turmbewegungen komplex sind und Läufer noch mehr, wie zum Teufel sollen wir dann die Dame kodieren? Tatsächlich sind die Bewegungen der Damen am einfachsten zu programmieren, einfach mit Hilfe eines einfachen Tricks. Dann lass uns die Königin sehen.   https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py  Okay, was passiert hier? Nun, wenn wir darüber nachdenken,   . Sie ähnelt eher einem turmförmigen Läufer-Mechabot als einer Königin. Aus diesem Grund ist es wirklich einfach, ihre Bewegungen zu programmieren. Nachdem wir ihre Klasse deklariert haben, definieren wir ihre   einfach als die   . hat die Königin die gleichen Züge wie der Läufer und der Turm zusammen possibleMoves Vereinigungsreihe von Bewegungen, die sich aus den möglichen Bewegungen des Läufers und des Turms ergeben  Beachten Sie, dass beim Aufrufen der Instanzen der Klassen   und   in der Funktion „   “ deren Parameter   und   als   angegeben werden, es sich also tatsächlich um die Koordinaten der Königin handelt. Bishop Tower possibleMoves x y self.x, self.y  Der Ritter  Nun zum Ritter!   https://gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py  Der Ritter ist für mich das Besondere. Sein Zugsatz ist seltsam, etwa „L“-förmig, daher habe ich keinen besonders cleveren oder schnellen Weg gefunden, ihn zu codieren, und am Ende habe ich seine Züge hart codiert und einfach   . jeden der 8 möglichen Züge berechnet, die er von seiner Startposition aus hat  Der König  Ein paar kurze Konzepte über den König. Da wir den König nicht bewegen müssen, sondern nur angeben müssen, ob er gecheckt hat oder nicht,   . Allerdings werden wir am Ende des Artikels auch eine kurze Implementierung sehen. Außerdem ist das Codieren nicht so einfach wie das Abschwächen des Zugsatzes der Königin, wie wir später sehen werden. Überspringen wir also vorerst seine Bewegungen und schauen wir uns die Lösung an. müssen wir seinen move-set nicht wirklich implementieren  Der Lösungscode  Da wir die möglichen Stellungen für jede Figur haben, ist die Lösung jetzt ziemlich einfach: Wir müssen nur prüfen, ob die Koordinaten des schwarzen Königs in der Zugmenge einer oder mehrerer der anderen Figuren enthalten sind. Lass es uns codieren!   https://gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py  Wir erstellen jetzt einfach eine Variable   als ein paar Koordinaten. Dann erstellen wir für jedes Stück eine Instanz seiner Klasse, die wir gerade erstellt haben, und rufen die Methode   auf, um den gesamten Satz an Bewegungen zu berechnen.       : Wenn ja, geben wir aus, dass der König von dieser bestimmten Figur überprüft wird. Das Ergebnis sieht hier etwa so aus: blackKing possibleMoves Sobald wir es haben, prüfen wir, ob die blackKing Koordinaten in diesen Zugsätzen vorhanden sind   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!  Ich habe das unordentliche Bild oben als Referenz verwendet, damit Sie überprüfen können, ob der König tatsächlich vom Turm und vom Ritter kontrolliert wird.  Schachmatt  Wie wäre es, wenn wir auch berechnen wollen   oder ob er tatsächlich Schachmatt ist? Zu diesem Zweck müssen wir die Züge des Königs berechnen. , ob der König noch Überlebenschancen hat   https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py  Lass es uns ein wenig beschreiben. Zunächst definieren wir wie zuvor unsere Klasse und Koordinaten. Danach erstellen wir die Methode   und codieren die möglichen Züge des Königs (ich bin mir wiederum ziemlich sicher, dass es einen schnelleren Weg gibt, aber es gibt nur 8 mögliche Züge, also …). Danach   und geben nur die   zurück. possibleMoves prüfen wir, welche Bewegungen illegal sind (Bewegungen außerhalb des Spielbretts) validMoves  Um nun zu prüfen, ob der König noch eine Überlebenschance hat,   Dazu durchlaufen wir einfach die Königszüge und die anderen Züge. müssen wir prüfen, ob einer seiner möglichen Züge nicht in einem anderen Zugsatz enthalten ist.   https://gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py  Es besteht also immer noch Hoffnung, dass unser König überlebt! Zum Glück für ihn, schätze ich ...  Zeitkomplexität  Wie immer ein kurzer Blick auf die zeitliche Komplexität dieser Lösung.  Da es sich bei jedem Teil um eine   handelt, müssen wir zunächst die Zeit für die Initialisierung dieser Instanz berücksichtigen. Instanz einer Klasse  Figuren wie der   haben keine Schleife in sich und sind nicht von einer variablen Dimension abhängig, daher können wir sie als O(1) betrachten; Bauer oder der Springer  Der   ist etwas knifflig: Da er 4 for-Schleifen enthält, könnte man sofort denken, dass seine Zeitkomplexität O(n) ist, oder? Wenn wir tatsächlich darüber nachdenken, wie sich der Turm bewegt, werden wir feststellen, dass   . Und da das Spielbrett ein Quadrat ist, haben wir immer 14 freie Felder, auf denen wir unseren Turm bewegen können. Daher sollte seine zeitliche Komplexität tatsächlich O(1) sein, konstant bis 14 Koordinatenpaare. Hier ist ein grafisches Beispiel:  Turm seine Bewegungen unabhängig von der Position auf dem Spielbrett auf die freien Spielfeldfelder auf seiner vertikalen und horizontalen Achse beschränkt sind  Leider können wir das Gleiche nicht vom   sagen, dessen Zugkombination etwas komplexer zu sein scheint. Grundsätzlich hat es 7, 9, 11 oder 13 Züge, je nachdem, wo es auf dem Spielbrett platziert wird. Daher basieren die Schritte, die zur Berechnung seiner Züge erforderlich sind, auf seiner Position, daher können wir einen tc von O(n) betrachten.  Läufer  Die   benötigt die kombinierten Züge des Turms und des Läufers. Da   , hat der Tc des Läufers Vorrang vor dem Tc des Turms. Daher müssen wir auch für die Königin einen tc von O(n) berücksichtigen. Königin wir uns bei der Bewertung der Zeitkomplexität auf das schlimmste Szenario konzentrieren müssen  Schließlich verfügt der   über einen fest codierten Satz an Zügen, aber auch über einen   . Technisch gesehen müssen wir also, auch wenn die Anzahl der Züge des Königs ohnehin relativ klein ist, seinen Tc als O(n) betrachten, auch abhängig von seiner Position auf dem Brett. König Validierungsprozess, der eine for-Schleife verwendet  An dieser Stelle verwenden wir   . Dies gibt uns keine Probleme, wenn der tc konstant ist (nehmen wir zum Beispiel den Turm: Wir berechnen seine 14 Züge und durchlaufen dann höchstens 14 Mal darüber, sodass wir ihn auch als feste Zeit betrachten können). Dennoch werden wir Probleme haben, wenn der tc O(n) oder höher ist, da wir eine Schleife hinzufügen, die ebenfalls wächst, wenn die Anzahl der Züge zunimmt. für jedes Stück eine for-Schleife, um den Prüfstatus des schwarzen Königs zu überprüfen und auszudrucken  Schließlich   , das definitiv ein Tc von O(n²) sein wird, abhängig von der Anzahl der Züge des Königs und der Züge der anderen Figuren.  verwenden wir eine doppelte (innere) for-Schleife, um das Schachmatt zu überprüfen  Das ist es; Da ist meine Lösung. Ich bin mir bewusst, dass einige Punkte nicht so effizient wie möglich sind, aber beim Schreiben gefiel mir die Idee, den Prozess zu beschreiben, mehr als die perfekte Lösung zu entwickeln.  Was denkst du darüber? Sagen Sie mir Ihre Meinung dazu und lassen Sie uns Ihre Lösungen in den Kommentaren diskutieren!  Wie immer gilt: Wenn Ihnen der Artikel gefallen hat, hinterlassen Sie bitte ein oder zwei Klatschzeichen und abonnieren Sie ihn oder teilen Sie ihn mit jemandem, der an dieser Art von Algorithmen interessiert sein könnte, wenn Sie können! Vielen Dank, dass Sie bis zum Ende gelesen haben, dieses Mal mehr als sonst angesichts der Länge dieser Lösung!  Wie immer vielen Dank fürs Lesen.

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.

Read My Stories

Dieses Audio ist in der Originalsprache der Geschichte produziert!

Zu lang; Lesen

Make resilience your competitive advantage

Tägliches Codierungsproblem: Nutzen Sie Ihre Codierungsfähigkeiten, um das Schachmatt zu überprüfen

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

Welcome to HackerNoon Decoded: The Best of 2024 Tech Blogging

HackerNoon Decoded 2024: Celebrating Our Cybersecurity Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

HackerNoon Decoded 2024: Celebrating Our Programming Community!

Welcome to HackerNoon Decoded: The Best of 2024 Tech Blogging

HackerNoon Decoded 2024: Celebrating Our Cybersecurity Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

HackerNoon Decoded 2024: Celebrating Our Programming Community!

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps