РЕШЕНИЕ  СУДОКУ  С  ПОМОЩЬЮ  АЛГОРИТМА  РАСКРАСКИ  ГРАФОВ

Лапшова  Марина  Александровна

студент  4  курса,  факультет  информатики,  Самарский  государственный  аэрокосмический  университет  имени  академика  С.П.  Королева  (Национальный  исследовательский  университет), 
РФ,  г.  Самара

E-mail:  marina.260494@mail.ru

Додонова  Наталья  Леонидовна

научный  руководитель,  канд.  физ.-мат.  наук,  доцент,  кафедра  прикладной  математики,  Самарский  государственный  аэрокосмический  университет  им.  Академика  С.П.  Королева  (Национальный  исследовательский  университет), 
РФ,  г.  Самара

Многие  люди  любят  разгадывать  разнообразные  головоломки  и  решать  задачи,  чтобы  отдохнуть,  потренировать  свои  мозги  или  просто  занять  время.  Одной  из  таких  задач  является  судоку.  Это  известная  головоломка  с  числами,  которая  пришла  из  Японии  и  завоевала  себе  любовь  в  разных  странах  мира,  в  том  числе  и  в  России.  На  родине  судоку  верили,  что  время  для  решения  головоломок  не  потрачено  зря:  цифры  спасали  мужчин  и  женщин  от  одиночества  и  холостой  жизни.  Разнообразные  журналы  и  газеты  публикуют  на  своих  страницах  таблицы  с  судоку,  а  так  же  издаются  периодически  специальные  сборники.

Обычно  эту  задачу  решают,  просто  смотря  на  цифры  и  подбирая  им  подходящие  места.  Мало  кто  задумывался  о  том,  как  можно  алгоритмизировать  решение  этой  головоломки,  и  мало  кто  задавался  вопросом,  есть  ли  математическая  модель  данной  задачи.

Разумеется,  ответ  на  последний  вопрос  однозначный.  Математическая  модель,  несомненно,  существует  и  она  довольно  проста.  Но  чтобы  разобраться  в  ней,  нужно  вспомнить  правила  игры.

В  классическом  варианте  квадратное  поле  размером  9x9  разделено  на  меньшие  квадраты,  каждая  сторона  которых  равна  3  (такие  квадраты  называются  боксами).  Всего  81  клетка.  Так  же  существуют  и  другие  поля  для  игры,  например,  для  детей  поля  размерами  4x4,  а  для  профессионалов  в  решении  судоку  есть  поля,  состоящие  из  трех  пересекающихся  квадратов  9x9.  Но  сейчас  я  рассматриваю  только  классические  правила.

В  некоторых  клетках  уже  расставлены  числа  от  1  до  9.  Необходимо  заполнить  свободные  клетки  таким  образом,  чтобы  во  всех  строках,  столбцах  и  боксах  каждая  цифра  встречалась  только  один  раз.  Если  судоку  составлено  правильно,  то  оно  имеет  единственное  решение.

Таким  образом,  если  применить  теорию  графов,  мы  можем  представить  поле  как  неориентированный  граф,  вершинами  которого  являются  клетки  головоломки.  То,  что  в  каждой  строке,  столбце  и  боксе  цифры  не  должны  повторятся,  напоминает  раскраску  вершин  графа.  Действительно,  раскраска  вершин  графа  это  такой  способ  окраски  вершин,  при  котором  двум  смежным  вершинам  соответствуют  разные  цвета,  в  нашем  случае  разные  цифры.

Рисунок  1.  Пронумерованный  граф  поля  для  судоку

Кликой  в  теории  графов  называют  подмножество  его  вершин,  таких,  что  любые  две  вершины  этого  подмножества  смежны.

В  нашем  неориентированном  графе-судоку  кликой  является  каждая  строка,  каждый  столбец  и  каждый  бокс.

В  итоге,  получается,  что  в  графе  из  81  вершины  27  клик  (9  строк,  9  столбцов  и  9  боксов),  каждую  из  которых  необходимо  раскрасить  в  9  цветов.  Если  пронумеровать  вершины  графа  как  на  рисунке  1,  то  клики  этого  графа:

{1,  2,  3,  4,  5,  6,  7,  8,  9},  {10,  11,  12,  13,  14,  15,  16,  17,  18},  …

{1,  10,  19,  28,  37,  46,  55,  64,  73},  {2,  11,  20,  29,  38,  47,  56,  65,  74},  …

{1,  2,  3,  10,  11,  12,  19,  20,  21,  28,  29,  30},  {4,  5,  6,  13,  14,  15,  22,  23,  24,  31,  32,  33},  …

Существует  много  алгоритмов,  приводящих  к  раскраске  вершин,  например,  алгоритм  неявного  перебора  или  метод  динамического  программирования  и  другие.  Но  ни  один  из  существующих  методов  не  подходит  в  данной  ситуации,  так  как  некоторые  вершины  уже  раскрашены  до  начала  работы  алгоритма.

Для  раскраски  этого  графа  можно  использовать  алгоритм  перебора  с  возвратами.  Он  заключается  в  том,  что  каждую  нераскрашенную  вершину  последовательно  красят  в  цвет,  не  противоречащий  уже  раскрашенным.  Если  таким  образом  решение  найдено,  то  головоломка  решена.  Но  если  на  каком-нибудь  шаге  сталкиваемся  с  невозможностью  выбора  цвета,  то  это  решение  неверно  и  возвращаемся  на  шаг  назад.  Далее  пробуем  другой  цвет  и  так  далее,  пока  не  найдем  правильного  решения.  Если  после  перебора  всех  возможных  вариантов,  ответ  не  найден,  то  задача  нерешаема.

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

с(v[i])  –  цвет  i-ой  вершины(цвета  обозначаются  цифрами  от  1  до  9);

p(v[i])  –  множество  возможных  цветов  для  i-ой  вершины;

N(p(v[i]))  –  мощность  множества  возможных  цветов(т.е.  количество  цветов,  в  которые  можно  окрасить  i-ю  вершину);

Соседние  вершины  –  вершины  находящиеся  в  одной  клике.

НАЧАЛО  АЛГОРИТМА

1. Для  вершин  известного  цвета  установить  с(v[i]).  Для  остальных  вершин  с(v[i])=0;
2. ЕСЛИ  с(v[i])  !=  0,  ТО 

НАЧАЛО

p(v[i])  =  с(v[i]);

N(p(v[i]))  =  1;

ИНАЧЕ 

НАЧАЛО

p(v[i])  =  множество  всех  возможных  цветов(от  1  до  9);

N(p(v[i]))  =  9;

КОНЕЦ 

3. ЕСЛИ  для  всех  вершин  N(p(v[i]))  =  1,  ТО 

КОНЕЦ  АЛГОРИТМА(решение  найдено)

ИНАЧЕ  перейти  к  шагу  4;

4. ЕСЛИ  есть  вершина,  в  которой  N(p(v[i]))  =  1,  ТО   

v[i])=  p(v[i]), 

из  множества  p(v[i]),  где  N(p(v[i]))!=1,  всех  вершин,  соседних  с  v[i],  удалить  с(v[i]),  N(p(v[i]))  =  N(p(v[i]))  -  1;

перейти  на  шаг  4;

КОНЕЦ 

ИНАЧЕ  перейти  к  шагу  5;

5. Для  вершины  v[i],  где  N(p(v[i]))  !=  1

ЕСЛИ  есть  неопробованный  цвет  из  p(v[i]),  ТО

  НАЧАЛО

           Установить  метку  М[j],  в  которую  поместить  все  текущие  значения;

           с(v[i])  =  неопробованный  цвет  из  p(v[i]);

p(v[i])  =  этот  неопробованный  цвет;

N (p(v[i]))  =  1;

  КОНЕЦ;

ИНАЧЕ  КОНЕЦ  АЛГОРИТМА  (решения  нет);

6. ЕСЛИ  есть  вершина  v[i],  такая  что  N(p(v[i]))  =  0  ТО

возвращаемся  на  последнюю  метку  М[j];

  ИНАЧЕ  переходим  на  шаг  4.

С  помощью  этого  алгоритма  может  быть  решено  судоку  любой  сложности  или  доказано,  что  оно  не  имеет  решения.  А  так  же  может  быть  написана  программа,  которая  перебирает  все  возможные  варианты  в  считанные  секунды.

Список  литературы:

1. Кристофидес  Н.  Теория  графов.  Алгоритмический  подход.  М.:  Мир,  1978.  –  432  с.
2. Математика.  Большой  энциклопедический  словарь.  М.:  Большая  Российская  Энциклопедия.  2000.  –  848  с. 
3. Тишин  В.В.  Дискретная  математика  в  примерах  и  задачах.  СПб.:  БХВ-Петербург.  2008.  –  352  с.
4. Уилсон  Р.  Введение  в  теорию  графов.  М.:  Мир,  2012.  –  280  с.