Ich habe kürzlich eine neue Sudoku-App bekommen, die wirklich harte Sudokus produziert, die mit den Standardstrategien nicht gelöst werden können. Also musste ich ein paar neue lernen. Eine dieser Strategien ist die Y-Wing-Strategie . Es ist unter "Tough Strategies" eingestuft, aber es ist eigentlich nicht so schwer.
Beispiel
Für diese Strategie sind nur 4 Zellen wichtig. Deshalb habe ich alle anderen Zellen in den Bildern ignoriert.
Wir betrachten alle Kandidaten für jede Zelle. Im folgenden Beispiel haben wir eine Zelle mit den Kandidaten 3 7(das heißt, wir haben die Kandidaten bereits abgelehnt 1 2 4 5 6 8 9, zum Beispiel, weil sich 1in derselben Zeile eine befindet, eine 2in derselben 3x3-Box, ...), eine Zelle mit den Kandidaten 6 7, eine Zelle mit den Kandidaten 3 6und eine Zelle mit den Kandidaten 2 6. Die Y-Wing-Strategie schlägt vor, dass das 6von den Kandidaten der rechten Zelle entfernt werden kann, wobei nur ein 2Kandidat übrig bleibt , den Sie ausfüllen können. Wir haben also eine korrekte Zahl gefunden und sind einen Schritt näher bei der Lösung des vollständigen Sudoku.
Warum kann das 6entfernt werden?
Erläuterung
Nehmen wir an, dass dies die 6richtige Zahl für die richtige Zelle ist. Jetzt gibt es ein 6in dieser Spalte, daher können wir das 6aus den Kandidaten der oberen rechten Zelle entfernen , wobei nur ein 7übrig bleibt, das wir ausfüllen können. Dasselbe passiert mit der unteren linken Zelle. Wir können das entfernen 6und das ausfüllen 3. Wenn wir uns nun die obere linke Zelle ansehen, erhalten wir einen Widerspruch. Weil es jetzt bereits ein 7in derselben Zeile und ein 3in derselben Spalte gibt, können wir das 7und das 3der Kandidaten entfernen und lassen überhaupt keine Kandidaten übrig. Welches ist eindeutig nicht möglich. Daher kann die 6 nicht die richtige Nummer der direkten Zelle sein.
Genauer gesagt: Wenn wir 4 Zellen mit den Kandidaten haben [A B] [A C] [C D] [B C](in dieser Reihenfolge oder kreisförmig gedreht) und die Zellen (über dieselbe Zeile, dieselbe Spalte oder dieselbe 3x3-Box) in einem Kreis verbunden sind (Zelle 1 ist mit Zelle 2 verbunden, dh verbunden mit Zelle 3, die mit Zelle 4 verbunden ist, die mit Zelle 1) verbunden ist, als Sie Caus der [C D]Zelle entfernen können. Es ist entscheidend, dass die drei Zellen [A B], [A C]und [B C]nur jeweils zwei Kandidaten enthalten. Anders die Zelle [C D], die mehr oder weniger enthalten Dkann ( kann null, ein oder sogar mehrere Kandidaten sein).
Beachten Sie, dass ich ausdrücklich gesagt habe, dass sie so oder so verbunden werden können. Im nächsten Beispiel sehen Sie die erneut angewendete Strategie. Diesmal bilden die 4 Zellen jedoch kein Rechteck. Die Zellen unten links und rechts unten werden einfach verbunden, da sie sich in derselben 3x3-Box befinden. Y-Wing sagt, dass wir die 1als Kandidat der oberen linken Zelle entfernen können. Dieses Mal sind noch 2 Kandidaten in dieser Zelle übrig, sodass wir keine neue korrekte Nummer gefunden haben. Trotzdem 1öffnet das Entfernen der Dose Türen zu verschiedenen Strategien.
Wenn Sie weitere Informationen zur Strategie oder einige weitere Beispiele wünschen , besuchen Sie sudokuwiki.org .
Herausforderungsspezifikationen
Sie erhalten 4 Listen als Eingabe, die die Kandidaten der Zellen darstellen. Die vier Zellen sind wie ein Kreis verbunden (Zelle 1 ist mit Zelle 2 verbunden, die mit Zelle 3 verbunden ist, die mit Zelle 4 verbunden ist, die mit Zelle 1 verbunden ist). Sie können davon ausgehen, dass jede Liste in aufsteigender Reihenfolge sortiert ist.
Ihre Aufgabe ist es, einen Kandidaten zu entfernen (indem Sie die Y-Wing-Strategie anwenden) und die resultierenden Kandidatenlisten in derselben Reihenfolge zurückzugeben. Wenn Sie die Strategie nicht anwenden können, geben Sie einfach dieselben Kandidatenlisten zurück.
Wenn es zwei mögliche Lösungen gibt (Sie könnten A von Zelle B oder C von Zelle D entfernen), geben Sie nur eine Lösung zurück. Es ist egal welches.
Die Eingabe kann in einem beliebigen nativen Listen- oder Array-Format erfolgen. Sie können auch eine Liste von Listen oder ähnliches verwenden. Sie können die Eingabe über STDIN, Befehlszeilenargument, Eingabeaufforderung oder Funktionsargument empfangen und die Ausgabe über den Rückgabewert oder einfach durch Drucken an STDOUT zurückgeben.
Das ist Code-Golf. Der kürzeste Code (in Bytes) gewinnt.
Testfälle
[3 7] [6 7] [2 6] [3 6] => [3 7] [6 7] [2] [3 6] # Example 1
[6 7] [2 6] [3 6] [3 7] => [6 7] [2] [3 6] [3 7] # Example 1, different order
[2 6] [3 6] [3 7] [6 7] => [2] [3 6] [3 7] [6 7] # Example 1, different order
[3 6] [3 7] [6 7] [2 6] => [3 6] [3 7] [6 7] [2] # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9] => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4] => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8] => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4] => [4 7] [7 8] [4 8] [] # Fictional example
[3 7] [2 6] [6 7] [3 6] => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4] => [4 7] [2 7 8] [4 8] [1 4] # -||-
7 8sind die Kandidaten für die erste und die zweite Zelle. Die Y-Wing-Strategie kann weiterhin angewendet werden.Antworten:
CJam, 90 Bytes
Ugghhh, das ist zu lang, weil die anderen 3 Zellen nur 2 Kandidaten haben sollten.
Dies erwartet eine Eingabe als Liste von Listen im CJam-Format. Zum Beispiel:
gibt die Ausgabe in einer CJam-Liste im Listenformat aus:
Wird eine Erklärung hinzufügen, sobald ich mit dem Golfen fertig bin.
Probieren Sie es hier online aus oder probieren Sie die gesamte Testsuite hier aus .
quelle
Mathematica,
124110 BytesBeispiele:
quelle