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

Идея: выкладывать в порядке, обратном уборке

Чтобы получить расклад, который можно убрать до конца, достаточно сначала решить, «как убирать», а потом пройти этот путь в обратном порядке.

  1. Берём пустое поле.
  2. Пару, которую уберут последней, выкладываем первой.
  3. Потом выкладываем пару, которую уберут предпоследней.
  4. Так продолжаем до пары, которую уберут первой.

Когда мы выкладываем пару, уже выложенные фишки это те фишки, которые к моменту уборки этой пары ещё останутся на поле. А клетки, куда фишки ещё не выложены, к тому моменту уже освободятся, потому что их фишки будут убраны. Поэтому выложенные фишки считаем стенами, а ещё не занятые клетки свободными и ставим пару только в две клетки, которые соединяет линия не более чем с двумя поворотами.

Когда все пары выложены, то, если идти в порядке, обратном выкладке, у каждой пары линия соединится. Это и есть решение расклада.

Пример: поле 4×4

Мы создали по этому способу небольшое поле из 16 фишек (4 вида по 4).

七索七索四萬二萬四萬六萬四萬七索四萬二萬六萬六萬六萬二萬七索二萬

Последней мы выложили пару из двух нижних фишек во втором столбце слева («2 символа»). Поэтому эту пару можно убрать первой (золотая линия). Если убрать четыре пары, идя в обратном порядке выкладки, поле станет таким. Пятой убирается пара «6 символов».

二萬六萬四萬七索四萬六萬七索二萬

Если убрать так 8 пар по порядку, то все фишки будут убраны.

Как не остаться без места

У этого способа есть ловушка. Если в середине окажется, что никакие две из оставшихся клеток нельзя соединить линией, то выкладывать дальше будет некуда.

Чтобы этого избежать, в приложении используется такое свойство.

  • Две соседние клетки всегда соединяются (длина линии 1, ничто её не закрывает).
  • Поэтому всегда поддерживается состояние, в котором ещё не занятые клетки можно разбить на пары соседних клеток без остатка.

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

Чтобы пары не были только соседними

Если все пары соседние, ответ виден с первого взгляда. Поэтому места для выкладки мы стараемся искать сначала среди далёких друг от друга двух клеток.

Мы создали 2000 игр на поле из 48 фишек тем же способом, что и в приложении. Среди пар решения пар из двух соседних клеток было около 28 %. Остальные примерно 70 % это далёкие пары, которые убираются Г-образными или П-образными линиями.

Перемешивание устроено так же

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

Но этот способ гарантирует только то, что существует хотя бы один способ решения. Если ошибиться с порядком ходов, можно и зайти в тупик. О том, что делать в тупике, рассказано в статье Если зашли в тупик: перемешайте.