Решение головоломок методом О. Оре

В ряде случаев представление головоломки в терминах теории графов позволяет рассматривать ее решение как поиск пути в связном ориентированном ациклическом графе. Это утверждение из монографии О. Оре по теории графов получило в статье подтверждение на задачах принципиально различной природы. В каждом случае задаче сопоставляется связный ориентированный ациклический граф, узлы которого соответствуют некоторым «состояниям», а дуги служат для указания переходов между состояниями; затем показывается, что решение задачи сводится к поиску пути между узлами построенного графа.