«Восьминашки» и поиск в ширину

Студент Московского физико-технического института (МФТИ), II курс, факультет управления и прикладной математики

Современные компьютеры имеют огромную память и мощные процессоры. В данной статье предлагается рассмотреть задачу, которая может занять даже очень современный  компьютер на несколько дней – это решение головоломки «Пятнашки». С упрощённым вариантом этой головоломки – «Восьминашками» – компьютер вполне справляется – на вычисления уходит несколько секунд. Интересующийся читатель без труда переделает приведённые здесь коды и сможет узнать, по зубам ли его компьютеру серьёзные вычислительные задачи. В статье на элементарном уровне рассказывается про метод поиска в ширину,  так что алгоритм решения будет понятен даже неискушённым в дискретной математике читателям.