Obsessive robot (bluxer) wrote,
Obsessive robot
bluxer

Minesweeper Icon

САПЕР: НАИМЕНЬШИЕ ИНВАРИАНТЫ

Очень часто (но не всегда) возникают ситуации, когда некоторые мины невозможно просчитать и приходится угадывать.
Это удивительно: количество мин всегда одно и то же, но их взаимное расположение может быть таким, что в него не проникнуть.

Хочется понять природу неопределенностей и найти простейшие из них.
Под "простейшими" я понимаю неизменяемые типы с минимальным количеством клеток.
Похоже, что таких простейших неопределенностей две.



I.
Первый тип упоминается в интернете по названием "'T' situation".

Буква Т
Это когда три мины расположены в ряд на расстоянии двух клеток от края (с любой стороны). Если там в клетках посередине две мины или ноль, то никаких проблем. Если же там одна мина, то невозможно посчитать, где она. Почему это невозможно, и как вообще классифицировать способы просчитывания мин, - над этим стоит порассуждать отдельно.

По краям поля "Буквы Т" тоже встречаются, но в усеченном виде (вместо трех клеток подряд две). На этой картинке интересный двойной случай, возникший в углу:
Двойная неопределенность
Если бы вместо "6" было "5", то тоже пришлось бы угадывать.

II.
Про второй тип я информации не видел. Как бы его назвать?... Ну, допустим "квадрат".
Это когда есть квадрат из четырех клеток, и к каждой его вершине диагонально примыкает мина. Но такое редко бывает. Чаще он возникает у края поля, и тогда достаточно двух мин у вершин. Или в углу - тогда остается всего одна вершина.
На картинке таких квадратов как бы три, но настоящих только два. Верхний левый ненастоящий, потому что в нем три мины, и поэтому они просчитываются:
Тройной квадрат

Неопределенности возникают в квадрате, ТОЛЬКО если в нем две мины, расположенные по диагонали (количество мин можно понять по цифрам на прилегающих клетках). Куда направлена диагональ, мы просчитать не можем.

Только такими почему-то и бывают наименьшие неопределенности. Либо сводятся к ним.
Их можно назвать "инвариантами": взаимное расположение мин не меняется, меняется только положение относительно других клеток.

Такую "структуру" можно мысленно покрутить вокруг центра в плоскости поля.
Есть "инварианты" посложнее: их надо "крутить" не в плоскости поля, а в трехмерном пространстве, вокруг оси симметрии :))
Как, например, вот эту странную, но красивую штуку:
Странная штука

Tags: Околоматематика
Subscribe

  • (no subject)

    Актёрских способностей никогда не проявлял, но в последние годы достаточно свободно могу заставить себя расплакаться, как по команде. Стоит чуть-чуть…

  • (no subject)

    МЫСЛИТЬ СИСТЕМНО В самом начале трудового пути моим руководителем и наставником был один человек, который из военного инженера переучился на юриста.…

  • (no subject)

    Дверь как предостережение... ... о грядущей катастрофе. Лет 7 назад через дорогу вдоль моего дома шла активная стройка с забиванием свай. С тех пор…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments