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

Überprüfen Sie den Schachmatt. Willkommen bei einem weiteren Problem, das es zu lösen gilt! Wenn Sie gerne Schach spielen und programmieren : 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.

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 Hier : Probieren Sie es aus und versuchen Sie auch, Ihre tägliche Herausforderung zu lösen!
• 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 8 x 8 große Matrix 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..

Sie sollten True zurückgeben , 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:

1. Wir befinden uns in einem Diagramm, nicht auf einer Tafel: Wir betrachten jeden durch das Problem vorgegebenen Punkt als Mittelpunkt eines Falles auf der Tafel . Das Ergebnis ist genau das gleiche;
2. 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;
3. Wir müssen überprüfen, ob der König in genau dieser Runde im Schach steht , was bedeutet, dass er in der nächsten weißen Runde genommen wird, wenn er nicht zieht;
4. Die Positionen werden zunächst vom Spiel vorgegeben : Ich werde nicht auf die Überprüfung auf überlappende Teile oder falsche Startpositionen eingehen.

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 ihr nächster Zug der Schlag des schwarzen Königs sein wird . Da wir also auch die Position des schwarzen Königs kennen, 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 . 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.

Die Situation sieht in etwa so aus:
Im Bild oben sieht man (… ich hoffe es, entschuldigen Sie die Verwirrung …) jeden möglichen Zug jeder Figur 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.

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 x,y erstellen, die unsere Figuren in den nächsten Zügen sein werden. Dazu definieren wir zunächst eine Klasse für jedes Stück, definieren seine Koordinaten und 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 Python , da es derzeit eine der beliebtesten und wohl für jedermann am besten lesbaren Sprachen ist. Dennoch müssen Sie wissen, was eine Klasse ist, um von nun an folgen zu können. Hier ist eine ziemlich nette Erklärung dieses Konzepts.

Lassen Sie es uns kurz erklären: Wir definieren zunächst die Klasse class Pawn und __init__ ihre Koordinaten x,y . Danach definieren wir die Methode possibleMoves , 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 „ moves hinzu, nachdem wir überprüft haben, dass sie sich nicht außerhalb unseres Rasters bewegt, und geben das moves -Array zurück. Hier sind zwei Dinge zu beachten, insbesondere für den Bauern:

1. 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.

2. Wir überspringen absichtlich die normale Bewegung , 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.

   
   

Jetzt können wir einfach die Bewegungen des Bauern überprüfen, indem wir ihm seine Koordinaten geben und die Methode possibleMoves aufrufen, etwa so: print(Pawn(7,2).possibleMoves()) und wir sollten so etwas wie [(6,3),(8,3)] .

Außerdem können Sie oben sehen, dass wir unsere Rastermaße als Variablen definiert haben , sodass wir sie möglicherweise ändern können, um den Algorithmus auf Brettern mit anderen Maßen auszuführen.

Kommen wir nun zum Turm.

Der Turm

Auch hier initialisieren wir die Tower-Klasse mit ihren Koordinaten und definieren die Funktion possibleMoves . Um hier alle möglichen Bewegungen zu sammeln , ordnen wir alle Punkte auf den beiden Achsen des Turms an und addieren jede einzelne Koordinate zur Variablen „ moves , die nach allen Schleifen zurückgegeben wird. Um die Turmbewegungen zu überprüfen, können wir wie zuvor einfach print(Tower(5,3).possibleMoves()) und erhalten dann etwa Folgendes: [(1,3), (2,3), (3,3), ..., (5,8)] .

Der Bischof

Jetzt ist es Zeit für den Bischof.

Die Bewegungen des Bischofs sind komplexer als die des Turms, deshalb erklären wir vielleicht ein wenig, was hier passiert. Grundsätzlich müssen wir ausgehend von der Startposition Punkte auf den beiden Diagonalachsen sammeln . Nachdem wir die Klasse und die Init-Methode deklariert haben, erstellen wir zwei Variablen: moves “ wie zuvor und currentPos “, die verwendet werden, um die Punkte zu verfolgen, die wir während der Bewegung entlang ihrer Achsen gesammelt haben. Verwenden Sie nun while Schleife und prüfen Sie, ob wir uns nicht außerhalb unseres Rasters bewegen. Wir erhöhen und verringern x und y entsprechend der Position, in die wir uns bewegen möchten . Wenn wir uns beispielsweise von der Startposition aus nach links oben bewegen möchten, müssen wir den x Wert verringern und gleichzeitig den y Wert erhöhen. Wenn wir nach rechts unten gehen wollen, müssen wir den x Wert erhöhen und gleichzeitig den y Wert verringern usw. Zum Schluss führen wir einfach noch einmal moves aus.

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.

Okay, was passiert hier? Nun, wenn wir darüber nachdenken, hat die Königin die gleichen Züge wie der Läufer und der Turm zusammen . 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 possibleMoves einfach als die 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 Bishop und Tower in der Funktion „ possibleMoves “ deren Parameter x und y als self.x, self.y angegeben werden, es sich also tatsächlich um die Koordinaten der Königin handelt.

Der Ritter

Nun zum Ritter!

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, müssen wir seinen move-set nicht wirklich implementieren . 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.

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!

Wir erstellen jetzt einfach eine Variable blackKing 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 possibleMoves auf, um den gesamten Satz an Bewegungen zu berechnen. Sobald wir es haben, prüfen wir, ob die blackKing Koordinaten in diesen Zugsätzen vorhanden sind : Wenn ja, geben wir aus, dass der König von dieser bestimmten Figur überprüft wird. Das Ergebnis sieht hier etwa so aus:

 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 , ob der König noch Überlebenschancen hat oder ob er tatsächlich Schachmatt ist? Zu diesem Zweck müssen wir die Züge des Königs berechnen.

Lass es uns ein wenig beschreiben. Zunächst definieren wir wie zuvor unsere Klasse und Koordinaten. Danach erstellen wir die Methode possibleMoves 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 prüfen wir, welche Bewegungen illegal sind (Bewegungen außerhalb des Spielbretts) und geben nur die validMoves zurück.

Um nun zu prüfen, ob der König noch eine Überlebenschance hat, müssen wir prüfen, ob einer seiner möglichen Züge nicht in einem anderen Zugsatz enthalten ist. Dazu durchlaufen wir einfach die Königszüge und die anderen Züge.

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 Instanz einer Klasse handelt, müssen wir zunächst die Zeit für die Initialisierung dieser Instanz berücksichtigen.

• Figuren wie der Bauer oder der Springer haben keine Schleife in sich und sind nicht von einer variablen Dimension abhängig, daher können wir sie als O(1) betrachten;
• Der Turm 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 seine Bewegungen unabhängig von der Position auf dem Spielbrett auf die freien Spielfeldfelder auf seiner vertikalen und horizontalen Achse beschränkt sind . 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:

• Leider können wir das Gleiche nicht vom Läufer 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.

• Die Königin benötigt die kombinierten Züge des Turms und des Läufers. Da wir uns bei der Bewertung der Zeitkomplexität auf das schlimmste Szenario konzentrieren müssen , 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.

• Schließlich verfügt der König über einen fest codierten Satz an Zügen, aber auch über einen Validierungsprozess, der eine for-Schleife verwendet . 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.

  
  

An dieser Stelle verwenden wir für jedes Stück eine for-Schleife, um den Prüfstatus des schwarzen Königs zu überprüfen und auszudrucken . 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.

Schließlich verwenden wir eine doppelte (innere) for-Schleife, um das Schachmatt zu überprüfen , 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.

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.