Hashiwokakero (auf Japanisch "Brücken bauen") ist ein Rätsel, bei dem Sie eine Gruppe von Inseln mit Brücken verbinden müssen. Die Regeln sind:
- Brücken müssen entweder vertikal oder horizontal zwischen zwei Inseln verlaufen.
- Brücken dürfen sich nicht kreuzen.
- Ein Inselpaar darf höchstens durch zwei parallele Brücken verbunden sein.
- Jede Insel ist mit einer Nummer zwischen 1 und einschließlich 8 gekennzeichnet. Die Anzahl der mit einer Insel verbundenen Brücken muss mit der Anzahl auf dieser Insel übereinstimmen.
- Die Brücken müssen die Inseln zu einer einzigen verbundenen Gruppe verbinden.
Ihre Aufgabe ist es, ein Programm zu schreiben, das Hashiwokakero-Rätsel löst.
Sie können davon ausgehen, dass ein bestimmtes Rätsel lösbar ist und es nur eine Lösung gibt.
Das Programm sollte einigermaßen effizient sein. Zum Beispiel sollte das Lösen des folgenden 25x25-Puzzles auf einem durchschnittlichen PC nicht länger als 10 Minuten dauern, und es sollte nicht mehr als ein Gigabyte Speicher beanspruchen. Das Lösen kleinerer Rätsel wie des 7x7 sollte Sekunden dauern.
Eingang:
Das Rätsel wird als 2D-Karte mit Zeichen angegeben, wobei die Ziffern 1
für 8
Inseln und die Felder für Wasser stehen. Die Zeilen werden bei Bedarf mit Leerzeichen aufgefüllt, damit sie alle die gleiche Länge haben.
Inseln werden immer horizontal und vertikal durch mindestens ein Quadrat Wasser getrennt, sodass Platz für die mögliche Brücke zwischen ihnen vorhanden ist. Es werden immer mindestens zwei Inseln in einem Puzzle sein.
Ihr Programm sollte die Puzzle-Map vorzugsweise von der Standardeingabe lesen. Sie können jedoch eine alternative Eingabemethode angeben, wenn Ihre Programmiersprache dies erfordert.
Ausgabe:
Die Ausgabe sollte der Eingabe entsprechen, außer dass Leerzeichen bei Bedarf durch Brücken ersetzt werden. Die Brücken sollten mit den Unicode-Zeichen ─
(U + 2500), │
(U + 2502), ═
(U + 2550) und ║
(U + 2551) gezeichnet werden , um horizontale und vertikale Einzel- und Doppelbrücken darzustellen.
Wenn Unicode - Zeichen ein Problem sind, können Sie die ASCII - Zeichen verwenden -
, |
, =
und H
stattdessen.
Gewinnkriterien:
Das ist Code Golf. Die kürzeste richtige und einigermaßen effiziente Lösung gewinnt.
Beispiele:
Puzzle (7x7):
2 2 1
1 4 3
3 2
4
3 2 3
1
3 4 2
Lösung:
2─2──1
│1──4─3
3──2║ ║
│ │4 ║
│3─2║ 3
1║ ║ │
3──4─2
Puzzle (25 x 25):
2 2 2 2 1 1 2 2 2 2 2
1 3 5 4 4 2
2 2 4 5 5 4 2 2 1 3
2 1 1 3 3 2 2
3 4 4 4 4 5 4 3 2 3
2 4 5 4 2 3
2 1 4 2 4 3 1 1 2
2 1 3 1 1 6 4 2
3 2 4 3 6 3 2
2 2 3 3 2 5 2 4 3
2 1 1 2
1 3 3 3 3 5 8 7 6 5 4
2 3 1 1 2
1 1 5 1 4 5 6 3 1 2
1 1 2 2 3 4
3 5 4 4 3 3 8 7 5 1 2
2 3 1 2 2 1 1
2 2 2 2 5 7 6 3 3
3 3 6 3 5 3 2 2 2 3
2 1 2 3 2 2
3 4 6 4 5 5 3 3 5 1
2 1 2 2 1 1 3
2 1 1 2 3 6 5 2 2
2 3 4 4 4 2 1
2 2 2 2 2 2 2 1 1 3 2
Lösung:
2─2─2──2 1 1─2─2──2──2─2
│ │ │1─3═5══4══4─2│
2 2─4─5══5═4═2│2──1 │ │3
│ 2│ ║1│ 1─3═3─2│ │ 2║
│ ║3═4│4══4─4═5─4─3──2 │3
2 4═5─4│ │ │ ║ │ │2───3│
│2─1║ ║4─2│ 4─3 │ 1│ 1 │2
2│1─3 ║║ │1 ║1──6══4 │ 2│
│3─2──4║ 3══6─3 ║ │ │ │2
2│2═3 │3──2 │ ║ 5─2│ 4─3│
│2─1│ │ │ │ ║ ║ │1 ║ │2
│ 1─3─3─3─3─5═8═7═6──5═4│
2──3───1│1─2│ ║ │ ║ ││
1 │ 1──5─1││ 4─5─6─3─1│2
1│ │1──2║ │2 │ ║ ║ │3═4│
│3─5═4 │4──3│ 3═8═7═5│1│2
2│ │ ║ 3│ 1│2──2║ │ ║1│1│
│2 │ ║ ║2 │2──2│5═7═6─3─3
3│ 3─6─3│ 5═3 │2│ ║2│2─3│
║2 │ ║ │ ║ │ 1│2─3║2│ ║2
3│ 4═6──4─5─5──3─3─5││1║│
│2 │ │1 │ │2║2──1│ ║1││3│
2│ │ 1│ │ 1║2│3══6═5─2││2
│2─3──4═4──4─2│ │ │1│
2─2──2─2──2─2─2 1 1─3─2
1 1
Eingaben Gedanken machen ?1 1
, welches ein gültiges Puzzle ist und korrekt gehandhabt werden sollte.Antworten:
Haskell, 1074 Zeichen
Ursprünglich hatte ich es noch reiner japanisch, indem ich auch die primitiven Funktionen in Bezug auf einfachen Mustervergleich und Listenkombinationen implementierte:
Haskell, 1192
Läuft in 3 Minuten auf meinem i5 .
Kommentierte Version:
quelle
Python, 1079 Zeichen
Der Code führt eine recht unkomplizierte, umfassende Suche durch
S
und verwendet eine gewisse Einschränkungsausbreitung, um die Ausführung in einer angemessenen Zeit zu ermöglichen.E
repräsentiert die aktuelle Menge von Kanten im Format [von, bis, Delta, mögliche Gewichte] . von und bis sind Inselkennungen und Delta ist entweder 1 für horizontale Kanten oder W (= Linienbreite) für vertikale Kanten. Mögliche Gewichte ist eine Unterliste von [0,1,2] , die den derzeit bekannten Zustand dieser Kante codiert (0 = keine Brücke, 1 = einzelne Brücke, 2 = doppelte Brücke).S
macht drei Dinge. Zuerst werden Informationen weitergegeben, z. B. wenn eine Kante keine 0-Gewichtung mehr hat, werden alle Kanten, die sie kreuzen, eliminiert (ihre möglichen Gewichte werden auf [0] gesetzt). Wenn die Summe des Mindestgewichts für Kanten, die auf eine Insel fallen, gleich dem Gewicht der Insel ist, werden alle diese Kanten auf das Mindestgewicht gesetzt.Zweitens wird
S
überprüft, ob der Graph immer noch mit Kanten verbunden ist, die nicht [0] sind (dieQ
Berechnung).Zum Schluss wird
S
eine Kante ausgewählt, die noch nicht vollständig bestimmt ist, und sie wird rekursiv aufgerufen, wobei diese Kante auf eine ihrer verbleibenden Möglichkeiten gesetzt wird.Dauert etwa 2 Minuten für das größte Beispiel.
quelle
print(B);sys.exit(0)
C # -
660156612225Nicht besonders gut golfen. Verwendet die Constraint-Programmierbibliothek von Google oder Tools. Bildet Abhängigkeiten für die Gesamtanzahl der Kanten und zum Beseitigen von Überkreuzungsbrücken. Es ist jedoch etwas schwieriger, Abhängigkeiten zu definieren, um sicherzustellen, dass alle miteinander verbunden sind. Ich habe Logik hinzugefügt, um 2 = 2 und 1-1 Komponenten zu beschneiden, aber ich muss noch die letzte Liste (39 auf der großen) durchgehen und diejenigen eliminieren, die nicht vollständig verbunden sind. Funktioniert ziemlich schnell. Dauert beim größten Beispiel nur ein paar Sekunden. Ungolfed:
quelle