Die Shisen-Sho-App (Nikaku-tori) prüft jedes Mal, wenn du zwei Steine auswählst, ob diese zwei Steine mit höchstens zwei Knicken verbunden sind. Auch wenn der Tipp entfernbare Paare sucht, wird dieselbe Prüfung für alle Paare benutzt. Dieser Artikel stellt das Verfahren als Programm vor.

Die Idee: für jede Zahl von Knicken ausweiten

Eine Linie geht senkrecht oder waagerecht gerade voran und knickt ab und zu ab. Deshalb prüfen wir vom ersten Stein aus so:

  1. 0 Knicke: Vom ersten Stein aus nach oben, unten, links und rechts über freie Felder gerade vorangehen. Wenn du beim zweiten Stein ankommst, sind sie verbunden.
  2. 1 Knick: Von jedem Feld, das du in Schritt 1 erreicht hast, die Richtung wechseln und wieder gerade vorangehen.
  3. 2 Knicke: Von jedem Feld, das du in Schritt 2 erreicht hast, die Richtung wechseln und noch einmal gerade vorangehen.

Kommst du bis zum dritten Durchgang nicht beim zweiten Stein an, sind sie nicht mit höchstens zwei Knicken verbunden. Gerade voran geht es immer bis zu einem Stein oder bis hinaus aus dem Brett.

Umgang mit dem Außenrand

Linien dürfen auch durch das äußere Feld um das Brett laufen. Im Programm nimmst du ein Brett, dem du rundherum eine Reihe freier Felder hinzugefügt hast, dann zählt auch der Außenrand als normale freie Felder. Bei einem Brett mit 6 Spalten × 8 Reihen prüfst du ein Brett mit 8 Spalten × 10 Reihen.

五索二萬三萬五索東南西北

Die beiden 5 der Bambus an den Enden der obersten Reihe in dieser Abbildung sind über freie Felder im oberen Außenrand mit zwei Knicken verbunden.

Das Programm

In JavaScript sieht es so aus:

// board[r][c] ist der Name des Steins, ein freies Feld ist null. Rundherum ist je ein Rahmen freier Felder hinzugefügt.
function canConnect(board, from, to) {
  const rows = board.length;
  const cols = board[0].length;
  const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  // Das aktuelle Feld und die zuletzt gegangene Richtung (am Anfang -1)
  let frontier = [[from[0], from[1], -1]];
  const seen = new Set();
  for (let turn = 0; turn <= 2; turn++) {
    const next = [];
    for (const [r0, c0, dir] of frontier) {
      for (let d = 0; d < 4; d++) {
        if (d === dir) continue;
        let r = r0;
        let c = c0;
        while (true) {
          r += steps[d][0];
          c += steps[d][1];
          if (r < 0 || c < 0 || r >= rows || c >= cols) break;
          if (r === to[0] && c === to[1]) return true;
          if (board[r][c] !== null) break;
          const key = r + ',' + c + ',' + d;
          if (!seen.has(key)) {
            seen.add(key);
            next.push([r, c, d]);
          }
        }
      }
    }
    frontier = next;
  }
  return false;
}
  • board ist das Brett mit dem hinzugefügten Rahmen freier Felder. In Steinfeldern steht der Name des Steins, in freien Feldern null.
  • from und to sind [Reihe, Spalte] der zwei Steine (Position auf dem Brett mit Rahmen).
  • frontier ist die Liste der Felder, die mit der aktuellen Zahl von Knicken erreichbar sind, samt der Richtung, in der man dorthin gegangen ist.
  • Gerade in dieselbe Richtung weiterzugehen, wurde im vorigen Durchgang schon geprüft und wird übersprungen (d === dir).
  • seen merkt sich, dass man dasselbe Feld in derselben Richtung schon erreicht hat, damit nichts doppelt geprüft wird.

Das Programm prüft sogar, ob man nach dem zweiten Knick beim geraden Weitergehen beim zweiten Stein ankommt. Über Steine kann man nicht gehen, also hält man an, wo man anstößt (nur beim zweiten Stein wird beim Ankommen entschieden).

Abgleich mit der App

Wir haben dieses Programm mit der Linien-Suche der App verglichen (derselben Rechnung, die auch für die Abbildungen der Artikel benutzt wird). Wir haben 300 Bretter mit 48 Steinen erzeugt, die genauso entstehen wie in der App, und auch teilweise abgeräumte Bretter einbezogen. Bei 5044 wahllos ausgewählten Steinpaaren stimmten die Antworten „verbunden“ und „nicht verbunden“ ausnahmslos überein.

Wenn die App eine Verbindung findet, zeichnet sie die Linie auf den Bildschirm. Deshalb merkt sie sich nicht nur, ob verbunden ist, sondern auch die Lage der Knicke. Gibt es mehrere mögliche Linien, zeichnet sie die mit weniger Knicken, bei gleich vielen die kürzere.

Alle entfernbaren Paare finden

Wenn wie beim Tipp entfernbare Paare gesucht werden, prüft dieses Programm jedes Paar aus zwei gleichen Steinen. Auf einem Brett mit 48 Steinen gibt es 72 Paare aus gleichen Steinen, also genügen höchstens 72 Prüfungen. Wie viele Paare am Anfang entfernbar sind, haben wir unter Wie viele Paare kannst du am Anfang entfernen? gezählt.