Thinkfun в терминах теории графов.

Aug 04, 2011 17:04

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

А вот графы для "Tipover", "Solitaire Chess", "Hoppers" ориентированные. У каждого ребра есть только одно направление, по которому можно двигаться. И, следовательно, есть тупиковые ситуации. Да, можно возвращаться к ситуации, которая была ход назад. Но такое возвращение не является ходом, если исходить из правил игры.

Поэтому в "Rush hour" нет нужды запоминать расположение фигур на доске ход или несколько ходов назад. А в остальных играх при заходе в тупик приходится по сути дела снова расставлять фигуры так, как указано на карточке.

Доосмыслено в процессе решения карточки 34 из "Solitaire Chess", будь она неладна.

упражнения для мозга

Previous post Next post
Up