В головоломке “Звездная битва” нужно расставить звезды так, чтобы в каждом столбце, строке и каждой обведенной границами области было по одной звезде (в более сложном варианте по 2 звезды). Звезды не могут соприкасаться даже по диагонали.
Как правило, принцип решения заключается в том, что мы ставим крестики там, где звезд точно быть не может исходя из правил головоломки. Затем для областей, где есть только одна возможность поставить звезду, ставим ее и далее все повторяем по кругу, пока не решим полностью.
Рассмотрим алгоритм решения этой головоломки на примере задачи: https://grandgames.ru/starbattle/id576319
У нас есть две области в виде линии в крайнем левом и крайнем правом столбцах. Так как хоть где-то в них должна стоять звезда, а в вертикали может быть только одна звезда, то можем исключить остальные ячейки в тех же столбцах.
В соседних столбцах можем еще исключить пару клеток, так как там точно не будет звезды, из-за того, что клетки будут диагональю касаться звезды, где бы конкретно она не стояла в соседнем регионе.
В регионе сверху осталась одна свободная клетка – ставим звезду. В регионе снизу образовалась линия, которая позволит еще исключить клетку в левом нижнем углу и клетку посредине (из-за диагонального правила, так как в любом из 3 вариантов расположения звезду, эта клетка касается).
Ставим звезду в оставшуюся клетку и крестик.
Снова образовалась область с одной клеткой для звезды, после того как мы ее поставили, снизу – еще одна.
Завершаем решение
Головоломка весьма проста и увлекательна! Попробуйте сами: https://grandgames.ru/starbattle/id576319
Звездная битва с двумя звездами решается схожим образом. Если вы хорошо в них разобрались, другие игроки будут признательны за новую статью с разбором такой головоломки большого размера.
Спасибо, буду разбираться. Сейчас так часто что-то новое добавляется, что не успеваешь все освоить.
