Каждый раз, когда вы выбираете две фишки, приложение Сисэн-сё (никаку-тори) проверяет, соединяются ли они линией не более чем с двумя поворотами. Когда подсказка ищет пару, которую можно убрать, та же проверка применяется ко всем парам. В этой статье показано, как это работает, на примере программы.

Идея: расширяем поиск по числу поворотов

Линия идёт прямо по вертикали или горизонтали и время от времени поворачивает. Поэтому от первой фишки мы проверяем так.

  1. 0 поворотов: от первой фишки идём прямо вверх, вниз, влево и вправо по свободным клеткам. Если дошли до второй фишки, они соединяются.
  2. 1 поворот: из каждой клетки, до которой дошли на шаге 1, меняем направление и снова идём прямо.
  3. 2 поворота: из каждой клетки, до которой дошли на шаге 2, меняем направление и ещё раз идём прямо.

Если до третьего шага мы не дошли до второй фишки, то с двумя поворотами они не соединяются. Прямо идут до тех пор, пока не упрутся в фишку или не выйдут за поле.

Как учитывается внешний ряд

Линии могут проходить и по внешнему ряду вокруг поля. В программе достаточно взять поле, к которому добавлен один круг свободных клеток, и тогда внешний ряд будет обычными свободными клетками. Для поля 6 столбцов на 8 строк проверка идёт на поле 8 столбцов на 10 строк.

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

Две «5 бамбуков» на концах верхней строки на этой схеме соединяются двумя поворотами через свободные клетки внешнего ряда сверху.

Программа

На JavaScript это выглядит так.

// board[r][c] это название фишки, свободная клетка это null. Вокруг поля добавлено по одной клетке свободной рамки.
function canConnect(board, from, to) {
  const rows = board.length;
  const cols = board[0].length;
  const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  // Текущая клетка и последнее направление движения (вначале -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 это поле с добавленной свободной рамкой. В клетках с фишками лежит название фишки, а в свободных клетках null.
  • from и to это [строка, столбец] двух фишек (положение на поле с добавленной рамкой).
  • frontier это список клеток, до которых можно дойти при текущем числе поворотов, и направлений, в которых туда пришли.
  • Движение в том же направлении, в котором мы уже шли, пропускается, потому что оно проверено на предыдущем шаге (d === dir).
  • seen запоминает, что мы уже приходили в эту клетку в этом направлении, чтобы не проверять одно и то же дважды.

Программа проверяет, дойдём ли мы до второй фишки, и на прямом участке после второго поворота. По фишкам пройти нельзя, поэтому при столкновении движение останавливается (вторую фишку определяем в момент, когда до неё дошли).

Сверка с приложением

Мы сравнили эту программу с тем способом поиска линии, который используется в приложении (тот же расчёт применён и для схем в статьях сайта). Мы создали 300 игр на поле из 48 фишек тем же способом, что и в приложении, и проверили 5044 случайные пары фишек, включая поля, на которых часть фишек уже убрана. Ответы «соединяются» и «не соединяются» полностью совпали.

Когда пара соединяется, приложение рисует на экране линию, поэтому оно запоминает не только сам факт соединения, но и положение углов. Если линий несколько, рисуется та, у которой меньше поворотов, а при равенстве самая короткая.

Как найти все пары, которые можно убрать

Когда подсказка ищет пары, которые можно убрать, эта программа проверяет каждую пару одинаковых фишек. На поле из 48 фишек одинаковых пар 72, поэтому достаточно максимум 72 проверок. Сколько пар можно убрать в начале, мы посчитали в статье Сколько пар можно убрать в начале?.