Ноябрь 2016

Том 31 номер 11

Тесты - Решение судоку с применением метода комбинаторной эволюции

Джеймс Маккафри | Ноябрь 2016

Исходный код можно скачать по ссылке.

Джеймс Маккафри Задача комбинаторной оптимизации (combinatorial optimization problem) заключается в выстраивании набора дискретных элементов в определенном порядке. Головоломка судоку — пример такой задачи комбинаторной оптимизации. В этой статье я покажу, как написать программу для решения трудных задач судоку, используя метод, названный мной комбинаторной эволюцией (combinatorial evolution).

Демонстрационная программа подготавливает непростую задачу судоку (вскоре я поясню, какой смысл я вкладываю в слово «непростую»). В судоку есть несколько ограничений. Каждая строка сетки решения 9×9 должна содержать числа от 1 до 9 без дубликатов. Каждый столбец должен содержать числа от 1 до 9, то же самое относится к каждому квадрату размером 3×3. А сетка решения не может изменять никакие начальные числа в сетке задачи.

Демонстрационная задача представлена на рис. 1. Некоторые задачи судоку можно решить, используя алгоритм «грубой силы» (brute force algorithm), где вы анализируете каждую пустую ячейку в сетке и проверяете, какие значения допустимо туда поместить, учитывая ограничения строки, столбца и квадратов меньшего размера. Если возможно лишь одно значение, тогда это значение помещается в пустую ячейку. Процесс продолжается до тех пор, пока не будут заполнены все пустые ячейки. Эти непростые типы задач судоку обычно публикуются в газетах и журналах.

Рис. 1. Непростая задача судоку

Демонстрационная задача непростая потому, что алгоритм «грубой силы» не работает. Допустим, вы сканируете сетку задачи слева направо, а затем сверху вниз. Пустой ячейкой в (0, 0) может быть одна из (1, 3, 5, 9), пустой ячейкой в (0, 1) — одна из (1, 3, 9). Следующей пустой ячейкой в (0, 4) может быть только 3, так что вы помещаете туда 3 и продолжаете. Однако, используя этот подход, вы застряли бы после размещения девяти значений, поскольку все остальные ячейки могли бы быть двумя или более значениями.

Чтобы получить представление о том, что такое оптимизация на основе комбинаторной эволюции, взгляните на экранный снимок на рис. 2. В этой оптимизации используются идеи из нескольких биологических алгоритмов. Данный алгоритм содержит набор виртуальных организмов. Каждый организм представляет возможное решение задачи. Комбинаторная эволюция является итеративным процессом. Каждая итерация называется эпохой (epoch). В каждой эпохе каждый организм пытается найти более хорошее решение, анализируя новое возможное решение.

Рис. 2. Решение судоку с помощью комбинаторной эволюции

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

В демонстрации подготавливаются 200 виртуальных организмов и устанавливается лимит времени в 5000 эпох. Эти значения найдены методом проб и ошибок. Комбинаторная эволюция не гарантирует нахождения оптимального решения, поэтому задается ограничение в 20 перезапусков, чтобы предотвратить возможное попадание в бесконечный цикл.

Демонстрационная программа нашла оптимальное решение после трех перезапусков алгоритма, что заняло приблизительно восемь секунд работы на моем настольном компьютере. При прогоне демонстрации программа отображала меру ошибки лучшего организма. Я объясню, как определяется и вычисляется ошибка, когда буду представлять релевантный код. Но заметьте, что алгоритм проявляет тенденцию к очень быстрому нахождению очень хорошего решения (error = 2), а потом застревает. Процесс перезапуска — один из механизмов противодействия этой особенности и распространенный метод во многих алгоритмах оптимизации.

Демонстрационная программа

Чтобы создать демонстрационную программу, я запустил Visual Studio, выбрал шаблон C# Console Application и назвал проект SudokuEvo. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая версия Visual Studio. После загрузки кода шаблона я переименовал в окне Solution Explorer файл Program.cs в более описательный SudokuEvoProgram.cs, и Visual Studio автоматически переименовала класс Program за меня.

В начале кода я удалил все лишние выражения using, оставив только ссылки на пространства имен System и Collections.Generic. Общая структура программы с некоторыми правками для экономии места представлена на рис. 3. Демонстрационная программа слишком длинна, чтобы представить ее здесь во всей полноте, но весь исходный код вы найдете в пакете, сопутствующем этой статье.

Рис. 3. Структура демонстрационной программы

using System;
using System.Collections.Generic;
namespace SudokuEvo
{
  class SudokuEvoProgram
  {
    static Random rnd = new Random(0);
    static void Main(string[] args)
    {
      Console.WriteLine("Begin solving Sudoku");
      Console.WriteLine("The problem is: ");
      int[][] problem = new int[9][];
      problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
      problem[1] = new int[] { 0, 0, 8, 9, 7, 0, 0, 0, 0 };
      problem[2] = new int[] { 0, 0, 4, 8, 1, 0, 5, 0, 0 };
      problem[3] = new int[] { 0, 0, 0, 0, 6, 0, 0, 0, 2 };
      problem[4] = new int[] { 0, 7, 0, 0, 0, 0, 0, 3, 0 };
      problem[5] = new int[] { 6, 0, 0, 0, 5, 0, 0, 0, 0 };
      problem[6] = new int[] { 0, 0, 2, 0, 4, 7, 1, 0, 0 };
      problem[7] = new int[] { 0, 0, 3, 0, 2, 8, 4, 0, 0 };
      problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
      DisplayMatrix(problem);
      int numOrganisms = 200;
      int maxEpochs = 5000;
      int maxRestarts = 20;
      int[][] soln = Solve(problem, numOrganisms,
        maxEpochs, maxRestarts);
      Console.WriteLine("Best solution found: ");
      DisplayMatrix(soln);
      int err = Error(soln);
      if (err == 0)
        Console.WriteLine("Success \n");
      else
        Console.WriteLine("Did not find optimal solution \n");
      Console.WriteLine("End Sudoku demo");
      Console.ReadLine();
    } // Main()
    public static int[][] Solve(int[][] problem,
      int numOrganisms, int maxEpochs, int maxRestarts) { . . }
    public static void DisplayMatrix(int[][] matrix) { . . }
    public static int[][] SolveEvo(int[][] problem,
      int numOrganisms, int maxEpochs) { . . }
    public static int[][] RandomMatrix(int[][] problem) { . . }
    public static int[] Corner(int block) { . . }
    public static int Block(int r, int c) { . . }
    public static int[][] NeighborMatrix(int[][] problem,
      int[][] matrix)
    public static int[][] MergeMatrices(int[][] m1,
      int[][] m2) { . . }
    public static int Error(int[][] matrix) { . . }
    public static int[][] DuplicateMatrix(int[][] matrix) { . . }
    public static int[][] CreateMatrix(int n) { . . }
  } // Program
  public class Organism
  {
    public int type;  // 0 = рабочий, 1 = исследователь
    public int[][] matrix;
    public int error;
    public int age;
    public Organism(int type, int[][] m, int error, int age)
    {
      this.type = type;
      this.matrix = SudokuEvoProgram.DuplicateMatrix(m);
      this.error = error;
      this.age = age;
    }
  }
} // ns

Демонстрационная программа не столь сложна, как кажется на первый взгляд, поскольку многие методы являются короткими вспомогательными. В демонстрации два класса. Класс Main содержит всю логику, реализованную как статические методы. Класс Organism определяет возможное решение целевой задачи судоку.

Каждый объект Organism имеет тип, который может быть 0 для «рабочего» организма («worker» organism) или 1 для организма-«исследователя» («explorer» organism). Поле matrix — это целочисленная матрица в стиле массив массивов, представляющая возможное решение. Каждое возможное решение имеет ошибку, где значение ошибки, равное 0, означает, что никакие ограничения не нарушены и поэтому поле matrix содержит оптимальное решение. В каждом объекте Organism есть поле age, значение которого определяет, умирает ли данный организм в каждой эпохе.

Демонстрационная программа подготавливает и отображает задачу судоку, используя следующие выражения:

int[][] problem = new int[9][];
problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
...
problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
DisplayMatrix(problem);

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

Задача судоку обрабатывается, используя выражения:

int numOrganisms = 200;
int maxEpochs = 5000;
int maxRestarts = 20;
int[][] soln = Solve(problem, numOrganisms, maxEpochs, maxRestarts);
Console.WriteLine("Best solution found: ");
DisplayMatrix(soln);

Метод Solve — это по большей части оболочка метода SolveEvo, который и выполняет основную работу. Это распространенный проектировочный шаблон в комбинаторной оптимизации: один низкоуровневый метод решения пытается найти оптимальное решение, и этот метод обертывается в высокоуровневый метод решения, который выполняет перезапуск алгоритма.

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

int err = Error(soln);
if (err == 0)
  Console.WriteLine("Success");
else
  Console.WriteLine("Did not find optimal solution");

Инициализация матрицы и ошибка

По моему мнению, лучший способ понять оптимизацию на основе комбинаторной эволюции — начать с изучения вспомогательных методов. Как только они становятся понятны, разобраться в методе решения относительно легко. Позвольте мне начать с объяснения метода RandomMatrix, инициализирующего поле matrix объекта Organism случайным возможным решением. Как это ни удивительно, но метод RandomMatrix является самой хитроумной частью всего алгоритма.

Определение метода RandomMatrix показано на рис. 4.

Рис. 4. Определение метода RandomMatrix

public static int[][] RandomMatrix(int[][] problem)
{
  int[][] result = DuplicateMatrix(problem);
  for (int block = 0; block < 9; ++block) {
    // Создаем List со значениями 1-9.
    // Перетасовываем значения в List.
    // Перебираем каждую ячейку в текущем блоке.
    // Если ячейка занята, удаляем это значение из List.
    // Перебираем каждую ячейку в текущем блоке.
    // Если ячейка пуста, добавляем значение из List.
  }
  return result;
}

Алгоритм проектируется так, чтобы в любой момент времени каждый из девяти блоков 3×3 (квадратов меньшего размера) находится в норме в том смысле, что каждая ячейка содержит значение 1–9 и что дубликатов нет. Условие, которое всегда истинно, иногда называют инвариантом (invariant). Этот инвариант влияет на все другие методы алгоритма. В теории ограничение строки или столбца можно было бы использовать как инвариант, но на практике более эффективно использование ограничение блока.

С концептуальной точки зрения, перебор каждого блока 3×3 в матрице 9×9 не является глубоким, но реализация не столь проста. Я выбрал подход с определением двух вспомогательных методов: Block и Corner. Метод Block принимает индекс строки (r) и индекс столбца (c), а затем возвращает номер блока (0–8), где находится ячейка (r, c). Номера блокам назначаются слева направо и сверху вниз. Например, если (r, c) = (3, 8), метод Block возвращает 5.

Метод Corner принимает идентификатор блока (0–8) и возвращает индексы верхнего левого угла блока. Например, если block = 8, метод Corner возвращает (6, 6).

Как только становится известно, что каждый из девяти блоков 3×3 матрицы в порядке, можно определить сравнительно простой метод, который вычисляет ошибку:

public static int Error(int[][] matrix)
{
  int err = 0;
  for (int i = 0; i < 9; ++i) {  // по каждой строке
    // Определяем отсутствующие значения в строке.
    // Добавляем 1 к err для каждого отсутствующего значения.
  }
  for (int j = 0; j < 9; ++j) {  // по каждому столбцу
    // Определяем отсутствующие значения в столбце.
    // Добавляем 1 к err для каждого отсутствующего значения.
  }
  return err;
}

На словах, общая ошибка для возможного решения является суммой количества отсутствующих значений в строке плюс количество отсутствующих значений в столбце. Поскольку алгоритм инвариантен, все блоки 3×3 не имеют отсутствующих значений, поэтому они не вносят вклад в ошибку. Заметьте, что подсчет количества дублирующихся значений в каждой строке и каждом столбце эквивалентен подсчету количества отсутствующих значений.

Генерация смежной матрицы

В комбинаторной эволюции существует два типа объектов Organism. Относящиеся к типу исследователя ищут возможные решения случайным образом, используя метод RandomMatrix. Объекты Organism, относящиеся к типу рабочего, повторяют попытки найти более хорошее решение по сравнению с тем, которое хранится в их поле matrix, анализируя ближайшее, «смежное» возможное решение.

Из-за инвариантности блока 3×3 смежное решение должно быть ограничено перестановкой внутри блока. Конкретнее, чтобы определить смежную матрицу (neighbor matrix), алгоритм выбирает блок случайным образом, затем выбирает две ячейки в блоке (где ни одна из ячеек не содержит фиксированное значение из определения задачи) и обменивает значения в двух ячейках.

Метод NeighborMatrix определяется так:

public static int[][] NeighborMatrix(int[][] problem, int[][] matrix)
{
  int[][] result = DuplicateMatrix(matrix);
  int block = rnd.Next(0, 9);  // выбираем случайный блок
  // Определяем, какие ячейки имеют значения,
  // которые можно переставить местами.
  // Выбираем две из этих ячеек: (r1,c1) и (r2,c2).
  int tmp = result[r1][c1];
  result[r1][c1] = result[r2][c2];
  result[r2][c2] = tmp;
  return result;
}

Демонстрационная программа предполагает наличие объекта Random с именем rnd на уровне класса. Такая структура распространена во многих алгоритмах оптимизации. Идею генерации смежного решения можно найти в нескольких алгоритмах комбинаторной оптимизации, например, в оптимизации на основе имитации отжига (simulated annealing optimization) и имитации пчелиной семьи (simulated bee colony optimization).

Слияние двух матриц

Алгоритм оптимизации на основе комбинаторной эволюции реализует одну из форм виртуальной эволюции, отбирая два хороших объекта Organism (т. е. имеющих поле matrix с малой ошибкой), а затем используя эти объекты для создания нового дочернего объекта. Новый, предположительно очень хороший, дочерний объект Organism заменяет плохой объект Organism.

Метод MergeMatrices принимает две матрицы 9×9 от двух объектов Organism. Этот метод сканирует блоки 0–8. Для каждого блока генерируется случайное значение в диапазоне от 0.0 до 1.0. Если случайное число меньше 0.50 (что наблюдается примерно в половине случаев), то значения в двух блоках обмениваются. Код выглядит так:

public static int[][] MergeMatrices(int[][] m1, int[][] m2)
{
  int[][] result = DuplicateMatrix(m1);
  for (int block = 0; block < 9; ++block) {
    double pr = rnd.NextDouble();
    if (pr < 0.50) {
      // Заменяем значения в блоке m1 значениями в блоке m2    
    }
  }
  return result;
}

Это эволюционный механизм в какой-то мере похож на механизм кроссинговера хромосом (chromosome crossover mechanism), используемый в генетических алгоритмах.

Метод SolveEvo

Основной алгоритм реализуется в методе SolveEvo. Его лучше всего описать комбинацией кода и высокоуровневого псевдокода, как показано на рис. 5.

Рис. 5. Основной алгоритм, реализованный в методе SolveEvo

public static int[][] SolveEvo(int[][] problem,
  int numOrganisms, int maxEpochs)
{
  int numWorker = (int)(numOrganisms * 0.90);
  int numExplorer = numOrganisms - numWorker;
  Organism[] hive = new Organism[numOrganisms];
  // Инициализируем каждый Organism
  int epoch = 0;
  while (epoch < maxEpochs) {
    for (int i = 0; i < numOrganisms; ++i) {
      // Обрабатываем каждый Organism
    }
    // Объединяем лучшего рабочего с лучшим исследователем,
    // увеличивая счетчик эпох
  }
  return bestMatrix;
}

Метод начинается с определения числа рабочих объектов Organism как 90% от общего используемого количества объектов Organism. Это значение было определено методом проб и ошибок. Объекты Organism хранятся в массиве hive.

Псевдокод для обработки объектов Organism рабочего типы выглядит так:

Генерируем смежную матрицу
if смежное решение лучше (или Organism ошибается)
  Обновляем матрицу смежным решением
  Сбрасываем поле age в 0
else
  Не обновляем матрицу
  Увеличиваем значение поля age
end if

Алгоритм от случая к случаю (вероятность = 0.001) инструктирует объект Organism принять смежное решение, которое хуже текущего решения этого объекта. Это обычная стратегия оптимизации, помогающая алгоритму выйти из тупикового неоптимального решения.

На каждой итерации цикла каждый организм-исследователь генерирует случайную сетку решения. Затем после обработки всех объектов Organism создается новый Organism. В псевдокоде это выглядит так:

Определяем индекс лучшего Organism-рабочего
Определяем индекс лучшего Organism-исследователя
Создаем новый Organism, используя
  лучших рабочего и исследователя
Определяем индекс худшего Organism-рабочего
Заменяем худшего рабочего новым дочерним Organism

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

Заключение

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

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

Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Microsoft Крису Ли (Chris Lee) и Кирку Олинику (Kirk Olynyk).

Discuss this article in the MSDN Magazine forum

Last updated on 2016-12-22