Nurikabe (Puzzle) – Wikipedia
Nurikabe (hiragana: ぬ り か べ) ist ein binäres Bestimmungsrätsel, das nach Nurikabe benannt ist, einer unsichtbaren Wand in der japanischen Folklore, die Straßen blockiert und Fußwege verzögert. Nurikabe wurde anscheinend von Nikoli erfunden und benannt; Andere Namen (und Lokalisierungsversuche) für das Puzzle sind: Zellstruktur und Inseln im Strom.
Das Puzzle wird auf einem typischen rechteckigen Gitter von Zellen gespielt, von denen einige Zahlen enthalten. Zellen haben anfangs eine unbekannte Farbe, können aber nur schwarz oder weiß sein. Zwei gleichfarbige Zellen gelten als “verbunden”, wenn sie vertikal oder horizontal, jedoch nicht diagonal benachbart sind. Verbundene weiße Zellen bilden “Inseln”, während verbundene schwarze Zellen das “Meer” bilden.
Die Herausforderung besteht darin, jede Zelle nach den folgenden Regeln schwarz oder weiß zu malen:
- Jede nummerierte Zelle ist eine Inselzelle, die Anzahl darin ist die Anzahl der Zellen auf dieser Insel.
- Jede Insel muss genau eine nummerierte Zelle enthalten.
- Es darf nur ein Meer geben, das keine “Pools” enthalten darf, dh 2 × 2 Bereiche schwarzer Zellen.
Menschliche Löser punktieren normalerweise die nicht nummerierten Zellen, von denen sie festgestellt haben, dass sie zu einer Insel gehören.
Wie bei den meisten anderen rein logischen Rätseln wird eine eindeutige Lösung erwartet, und es ist sehr unwahrscheinlich, dass ein Raster mit Zufallszahlen eine eindeutig lösbare Lösung liefert Nurikabe Puzzle.
Geschichte[edit]
Nurikabe wurde zuerst von “renin (れ ー に ん)” entwickelt, dessen Pseudonym die japanische Aussprache von “Lenin” ist und dessen Autonym als solches gelesen werden kann, in der 33. Ausgabe von (Puzzle Communication) Nikoli im März 1991. Bald hat eine Sensation geschaffen und ist in allen Ausgaben dieser Veröffentlichung vom 38. bis zur Gegenwart erschienen.
Ab 2005 bestehen sieben Bücher vollständig aus Nurikabe Rätsel wurden von Nikoli veröffentlicht.
(Dieser Absatz hängt hauptsächlich von “Nikoli komplette Werke von interessanten Rätseln (ニ コ リ オ モ ロ パ ズ ル 大 全集)” ab. https://web.archive.org/web/20060707011243/http://www.nikoli.co.jp/storage/addition/omopadaizen/)
Lösungsmethoden[edit]
Es sollte kein blindes Raten erforderlich sein, um a zu lösen Nurikabe Puzzle. Vielmehr kann eine Reihe einfacher Verfahren und Regeln entwickelt und befolgt werden, vorausgesetzt, der Löser ist ausreichend aufmerksam, um herauszufinden, wo er sie anwenden kann.
Der größte Fehler, den Anfänger machen, besteht darin, sich ausschließlich auf die Bestimmung von Schwarz oder Weiß zu konzentrieren und nicht auf das andere. die meisten Nurikabe Rätsel erfordern ein Hin und Her. Das Markieren weißer Zellen kann dazu führen, dass andere Zellen schwarz werden, damit kein schwarzer Abschnitt isoliert wird, und umgekehrt. (Diejenigen, die mit Go vertraut sind, können sich unbestimmte Zellen neben verschiedenen Regionen als “Freiheiten” vorstellen und “Atari” -Logik anwenden, um zu bestimmen, wie sie wachsen müssen.)
Grundstrategie[edit]
- Da sich zwei Inseln möglicherweise nur an Ecken berühren, müssen Zellen zwischen zwei Teilinseln (Zahlen und benachbarte weiße Zellen, deren Anzahl noch nicht summiert ist) schwarz sein. Dies ist oft ein Weg, um eine zu starten Nurikabe Rätsel, indem Zellen neben zwei oder mehr Zahlen als schwarz markiert werden.
- Sobald eine Insel “vollständig” ist – das heißt, sie hat alle weißen Zellen, die ihre Anzahl erfordert – müssen alle Zellen, die eine Seite mit ihr teilen, schwarz sein. Offensichtlich sind alle Zellen, die zu Beginn mit ‘1’ markiert sind, vollständige Inseln für sich und können zu Beginn mit Schwarz isoliert werden.
- Immer wenn drei schwarze Zellen einen “Ellbogen” bilden – eine L-Form – muss die Zelle in der Biegung (diagonal von der Ecke des L) weiß sein. (Die Alternative ist ein “Pool”, da es keinen besseren Begriff gibt.)
- Alle schwarzen Zellen müssen eventuell verbunden werden. Wenn es einen schwarzen Bereich gibt, in dem nur eine Möglichkeit besteht, eine Verbindung zum Rest der Platine herzustellen, muss der einzige Verbindungsweg schwarz sein.
- Folgerung: Es kann keinen kontinuierlichen Pfad zwischen weißen Zellen von einer Zelle am Rand der Tafel zu einer anderen Zelle wie dieser geben, die einige schwarze Zellen einschließt, da sonst das Schwarze Zellen werden nicht verbunden.
- Alle weißen Zellen müssen schließlich Teil genau einer Insel sein. Wenn es einen weißen Bereich gibt, der keine Nummer enthält, und es nur eine Möglichkeit gibt, eine Verbindung zu einem nummerierten weißen Bereich herzustellen, muss der einzige Verbindungspfad weiß sein.
- Einige Rätsel erfordern die Position von “nicht erreichbaren” Zellen, die nicht mit einer beliebigen Nummer verbunden werden können, entweder zu weit von allen entfernt sind oder von anderen Nummern blockiert werden. Solche Zellen müssen schwarz sein. Oft haben diese Zellen nur einen Verbindungsweg zu anderen schwarzen Zellen oder bilden einen Ellbogen, dessen erforderliche weiße Zelle (siehe vorheriges Aufzählungszeichen) nur eine Zahl erreichen kann, was weitere Fortschritte ermöglicht.
Fortgeschrittene Strategie[edit]
- Wenn es ein Quadrat gibt, das aus zwei schwarzen und zwei unbekannten Zellen besteht, muss mindestens eine der beiden unbekannten Zellen gemäß den Regeln weiß bleiben. Wenn also eine dieser beiden unbekannten Zellen (nennen wir es ‘A’) nur über die andere mit einem nummerierten Quadrat verbunden werden kann (nenne es ‘B’), muss B notwendigerweise weiß sein (und A kann oder darf nicht weiß sein).
- Wenn auf einer Insel der Größe N bereits N-1 weiße Zellen identifiziert wurden und nur noch zwei Zellen zur Auswahl stehen und diese beiden Zellen sich an ihren Ecken berühren, befindet sich die Zelle zwischen diesen beiden auf der anderen Seite der Insel muss schwarz sein.
- Wenn ein Quadrat weiß sein muss und nur zwei Inseln eine Verbindung herstellen können und nach dem Verbinden keine nicht identifizierten Zellen mehr vorhanden sind, werden die Inseln in einem 90-Grad-Winkel verbunden (Beispiel: Eine Insel kann sich mit der Oberseite und die andere mit der rechten Seite verbinden Seite) Die Zelle innerhalb des Winkels (diejenige, die im vorherigen Beispiel die obere linke Ecke des weißen Quadrats berührt) muss schwarz sein, um eine Verbindung der beiden Inseln zu vermeiden.
- Unbestimmte Zellen neben einer geraden Reihe (oder einer geraden Spalte) schwarzer Zellen können auf Schwarz getestet werden. Wenn sie schwarz sind, bilden sie zwei Ellbogen, und es gibt zwei benachbarte weiße Zellen, die von den Inseln aus erreichbar sein müssen . Wenn sie innerhalb der Einschränkungen nicht erfüllt werden können, bedeutet dies, dass die Zelle, die auf Schwärze untersucht wurde, weiß sein muss.
Rechenkomplexität[edit]
Es ist NP-vollständig, Nurikabe zu lösen, selbst wenn die beteiligten Zahlen nur 1 und 2 sind.
Betrachten Sie außerdem diese beiden Regeln von Nurikabe:
- Schwarze Zellen bilden einen verbundenen Bereich
- Schwarze Zellen können keine 2 × 2 Quadrate bilden.
Beide können ignoriert werden und ergeben insgesamt drei Varianten. Wie sich herausstellt, sind sie alle NP-vollständig.
[1]
Verwandte Rätsel[edit]
Die ebenfalls von Nikoli veröffentlichten binären Bestimmungsrätsel LITS und Mochikoro ähneln Nurikabe und ähnliche Lösungsverfahren anwenden. Das binäre Bestimmungsrätsel Atsumari ähnelt Nurikabe aber basierend auf einer sechseckigen Kachelung statt einer quadratischen Kachelung.
Mochikoro ist eine Variante des Nurikabe-Puzzles:
- Jede nummerierte Zelle gehört zu einem weißen Bereich. Die Nummer gibt an, wie viele Zellen zum weißen Bereich gehören. Einige weiße Bereiche enthalten möglicherweise keine nummerierte Zelle.
- Alle weißen Bereiche müssen diagonal verbunden sein.
- Die schwarze Zelle darf keinen Bereich von 2×2 Zellen oder mehr abdecken.
Recent Comments