Судоку как CSP
ОГЛАВЛЕНИЕ
Введение
В курсе искусственного интеллекта изучаются задачи поиска допустимого решения (CSP) с учетом ограничивающих условий. Преподаватели просят написать небольшие решающие программы, а Судоку является классической задачей поиска допустимого решения.
Судоку?
Нам кажется, что каждый знаком с Судоку; если вы не знаете, что это такое, поищите информацию в Google или в Википедии.
Основные правила Судоку таковы:
- Для каждой строки/столбца/области вы должны использовать различные числа.
- Все клетки должны быть заполнены.
Доска Судоку – это матрица NxN, и это означает, что нужно использовать число из диапазона [1..N].
Что такое CSP?
CSP или Задача поиска допустимого решения определяется через три составляющие:
- Конечный набор переменных.
- Функция, которая устанавливает соответствие каждой переменной конечному домену (области).
- Конечный набор ограничивающих условий.
Распространение ограничивающих условий и поиск с возвратом – это методы в CSP, и их мы будем описывать в данной статье.
Постановка задачи (Или какое отношение это имеет к Судоку?)
Перед началом стоит привести ряд определений:
- Клетка (ячейка): Клетка - это 'квадрат' в сетке Судоку.
- Сетка: Сетка представляет доску Судоку.
- Узлы сети (равноправные): Все соседи клетки; соседи – все клетки, расположенные в том же самом блоке клеток.
- Блок: Набор клеток (ячеек) GRIDSIZE для каждой строки, столбца и области.
- Домен (область): Домен – это маленький квадрат, обычно размером sqrt(N) x sqrt(N), sqrt – квадратный корень
Алгоритм будет описан с помощью использования двух методов, основанных на идеях CSP: распространение ограничивающих условий и поиск с возвратом.
Сначала нужно определить задачу Судоку как CSP.
- Переменные: Переменной будет каждая ячейка сетки.
- Домен: Доменом будет любая цифра от 1 до GRIDSIZE. Если GRIDSIZE >9, мы будем использовать буквы от 'A' до .. сколько бы ни было нужно, где 'A' равняется 10 , 'B' равняется 11, и так далее.
- Ограничения: Ограничениями являются:
- Одна и та же цифра (или буква) не может появляться дважды (или больше раз) в одной и той же строке.
- Одна и та же цифра (или буква) не может появляться дважды (или больше раз) в одном и том же столбце.
- Одна и та же цифра (или буква) не может появляться дважды (или больше раз) в одной и той же области.
Мы представили домен переменных как строки (для эффективности), и когда любая длина домена ячейки станет равной 1, будет получено решение!
Распространение ограничивающих условий
Конечно, мы могли использовать грубый подбор всех возможных комбинаций, проверить варианты и найти решение (это может отнять немало времени, но это работает), но нам хотелось бы найти лучший способ.
Ключевая проблема в CSP – это распространение ограничивающих условий; можно увидеть два типа: предваряющая проверка и согласованность по дугам (2-согласованность).
Предваряющая проверка
Самое элементарное прохождение ограничивающих условий – это предваряющая проверка. Это означает заблаговременное исключение вероятностей, не соответствующих ограничениям, из доменов неопределенных переменных. Например, если символ 'd' присваивается ячейке c1, 'd' исключается из всех доменов узлов сети этой ячейки.
MyCell[,] EliminateFC(MyCell[,] branch, Pos p, char val)
{
branch[p.ln, p.col].Value =
branch[p.ln, p.col].Value.Replace(val.ToString(), "");
return branch;
}
MyCell[,] AssignFC(MyCell[,] branch, Pos p, char val)
{
for (int i = 0; i < branch[p.ln, p.col].Peers.Count; i++)
{
branch[branch[p.ln, p.col].Peers[i].ln, branch[p.ln, p.col].Peers[i].col].Value =
branch[branch[p.ln, p.col].Peers[i].ln,
branch[p.ln, p.col].Peers[i].col].Value.Replace(val.ToString(), "");
if (branch[branch[p.ln, p.col].Peers[i].ln,
branch[p.ln, p.col].Peers[i].col].Value.Length == 0)
return null;
}
branch[p.ln, p.col].Value = val.ToString();
branch[p.ln, p.col].assigned = true;
return branch;
}
Согласованность по дугам
То, что мы делаем, не является в точности согласованием arc, но основано на этом. Мы выполняем три типа сокращения (уменьшения), некоторые для сокращения доменов и некоторые, чтобы увидеть ошибки заблаговременно и сэкономить время:
- Когда символ 'd' присваивается ячейке s1, используется выражение вида присвоить(ячейки, s, d). С помощью этого мы хотим присвоить s значение d, но также хотим исключить данную вероятность из ее узлов сети (как делает FC). Если исключение уменьшает число вероятностей одного (или нескольких) из узлов сети до одной вероятности, которую мы называем d2, то мы хотим присвоить d2 узлу сети и с помощью этого исключить d2 из всех узлов этого узла, то данное действие может вызвать другую цепную реакцию. Эта цепная реакция называется распространением ограничивающих условий: помещение ограничения на одну ячейку может вызвать дальнейшее помещение ограничений на другие ячейки.
- Второй тип: можно сказать, что мы просто исключаем 6 как возможное значение ячейки [0,0], и если мы посмотрим на первый блок (блок строк) [0,0], то увидим, что единственной ячейкой, имеющей 6 как вероятность, является [0,7]. Мы присвоим 6 ячейке [0,7], и снова произойдет цепная реакция.
- Последнее – это предварительная проверка на наличие ошибок, потому что Судоку объявляется как ограничение AllDiff. Можно заранее проверить правильность решения, выполнив следующую простую форму проверки на противоречивость: если M переменных включены в ограничение и если они имеют всего N возможных различных значений, и M>N, то ограничение не может быть удовлетворено (и не нужно тратить время на эту ветвь, которая в итоге не приведет к верному решению.)
/// <summary>
/// Назначение ac3.
/// </summary>
/// <param name="Cells">Ячейки.</param>
/// <param name="assignmentPosition">Место присвоения.</param>
/// <param name="assignmentValue">Присваиваемое значение.</param>
/// <returns></returns>
MyCell[,] AssignWithAc3(MyCell[,] Cells, Pos assignmentPosition, char assignmentValue)
{
for (int i = 0; i < m_gridSize; i++)
if (m_MaxDomain[i] != assignmentValue)
{
Cells = EliminateWithAc3(Cells, assignmentPosition, m_MaxDomain[i]);
if (Cells == null)
return null;
}
Cells[assignmentPosition.ln, assignmentPosition.col].assigned = true;
return Cells;
}
/// <summary>
/// Исключает ac3.
/// </summary>
/// <param name="Cells">Ячейки.</param>
/// <param name="assignmentPosition"> Место присвоения.</param>
/// <param name="assignmentValue"> Присваиваемое значение.</param>
/// <returns></returns>
MyCell[,] EliminateWithAc3(MyCell[,] Cells,
Pos assignmentPosition, char assignmentValue)
{
//Проверяем, было ли уже выполнено исключение :
if (!Cells[assignmentPosition.ln, assignmentPosition.col].Value.Contains(
assignmentValue.ToString()))
return Cells;
//исключение :
Cells[assignmentPosition.ln, assignmentPosition.col].Value =
Cells[assignmentPosition.ln, assignmentPosition.col].Value.Replace(
assignmentValue.ToString(), "");
//проверка на противоречивость.
if (Cells[assignmentPosition.ln, assignmentPosition.col].Value.Length == 0)
return null;
if (Cells[assignmentPosition.ln, assignmentPosition.col].Value.Length == 1)
{
Cells[assignmentPosition.ln, assignmentPosition.col].assigned = true;
char val2 = Cells[assignmentPosition.ln, assignmentPosition.col].Value[0];
for (int i = 0; i < Cells[assignmentPosition.ln,
assignmentPosition.col].Peers.Count; i++)
{
Cells = EliminateWithAc3(Cells, Cells[assignmentPosition.ln,
assignmentPosition.col].Peers[i], val2);
if (Cells == null)
return null;
}
}
for (int i = 0; i < 3; i++)
{
int n = m_gridSize;
int m = 0;
List<Pos> val_place = new List<Pos>();
for (int j = 0; j < Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i].Count; j++)
{
if (Cells[Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].ln,
Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].col].assigned)
n--;
else
m++;
if (Cells[Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].ln,
Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].col].Value.Contains(
assignmentValue.ToString()))
{
val_place.Add(new Pos(Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].ln,
Cells[assignmentPosition.ln,
assignmentPosition.col].Units[i][j].col));
}
}
if (m > n)
return null;
if (val_place.Count == 0)
return null;
if (val_place.Count == 1)
{
Cells = AssignWithAc3(Cells, val_place[0], assignmentValue);
if (Cells == null)
return null;
}
}
return Cells;
}
Это был первый шаг, но некоторые Судоку не оставляют нам другого выбора и вынуждают использовать угадывание, чтобы найти решение. Но если догадка неверная? Приходится возвращаться прежним путем, следовательно, мы используем поиск с возвратом.
Поиск с возвратом
Используя поиск с возвратом, можно проходить сквозь деревья и проверять любую вероятность (но если мы умные, нам не нужно это делать) на недействительность. Но из-за ограничений каждое место становится все меньше и меньше, и если мы будем использовать какую-либо эвристику, то сделаем это намного лучше!
Поиск с возвратом происходит примерно так: если уже есть верное решение, это решение возвращается; если верного решения нет, выбирается незаполненная ячейка, и рассматриваются все ее возможные значения (в каком порядке?). Поодиночке мы пытаемся присвоить значение каждой ячейке и продолжаем искать от результирующей позиции.
MyCell[,] backtrackingSearch(MyCell[,] branch)
{
MyCell[,] ret;
if (branch == null) return null;
if (isFinish(branch)) return branch;
Pos s = SelectUnassignedVariable(branch);
while (branch[s.ln, s.col].Value.Length > 0)
{
char c = SelectDomainValue(branch, s);
ret = backtrackingSearch(Assign(Clone(branch), s, c));
if (ret != null)
return ret;
m_NumOfBacktracking++;
branch = Eliminate(branch, s, c);
if (branch == null) return null;
}
Эвристика переменной (Или: какую ячейку нужно проверить первой?)
В вышеупомянутом алгоритме поиска мы используем функцию SelectUnassignedVariable, но она не сообщает ничего о критерии, потому что данная 'функция’ является делегатом, предназначенным для сравнения с какой-либо другой эвристикой. Напишем обобщенный (групповой) поиск с возвратом, просто изменяя значение делегата с одного на другое. Наша программа реализует только классическую эвристику.
Первое неопределенное значение
Здесь используется самая простая эвристика. Это очень быстро, но, с другой стороны, очень глупо. Мы просто выбираем первое значение, которое находим, и используем его для поиска с помощью простого перебора, однако хотелось бы сделать что-то более серьезное.
Pos FirstUnassignedCell(MyCell[,] branch)
{
for (int i = 0; i < m_gridSize; i++)
for (int j = 0; j < m_gridSize; j++)
if (!branch[i, j].assigned)
return new Pos(i, j);
return null;
}
Эвристика минимального остающегося значения (MRV):
В данном случае выбирается ячейка с минимальной вероятностью. Это хорошо, потому что есть большой шанс правильного угадывания. Это также уменьшает коэффициент ветвления.
Pos MinimumRemainingValues(MyCell[,] branch)
{
int min = m_gridSize + 1;
Pos p=new Pos() ;
for (int i = 0; i < m_gridSize; i++)
for (int j = 0; j < m_gridSize; j++)
{
if ((!branch[i, j].assigned) &&
(branch[i, j].Value.Length < min))
{
p.ln = i;
p.col = j;
min = branch[i, j].Value.Length;
}
}
return p;
}
MRV + Максимальный порядок (MRV+MD)
У нас есть MRV, и это очень хорошо, но, может быть, можно сделать все еще лучше. Мы все еще используем MRV, но теперь как разрушитель связей. Мы выбираем ячейку с максимальным порядком (степенью). Порядок ячейки – это число неопределенных ячеек, на которые данная ячейка накладывает ограничение.
Pos MRV_With_MD(MyCell[,] branch)
{
return MaxDegree(branch, MinimumRemainingValuesList(branch));
}
/// <summary>
/// получаем список минимальных остающихся значений позиций переменных.
/// </summary>
/// <param name="branch">Ветвь.</param>
/// <returns></returns>
List<Pos> MinimumRemainingValuesList(MyCell[,] branch)
{
int min = m_gridSize + 1;
List<Pos> list = new List<Pos>();
for (int i = 0; i < m_gridSize; i++)
for (int j = 0; j < m_gridSize; j++)
{
if ((!(branch[i, j].assigned)) && (branch[i, j].Value.Length == min))
{
list.Add(new Pos(i, j));
continue;
}
if ((!(branch[i, j].assigned))&& (branch[i, j].Value.Length < min))
{
list.Clear();
min = branch[i, j].Value.Length;
list.Add(new Pos(i, j));
}
}
return list;
}
/// <summary>
/// получаем позицию переменной с максимальным порядком из позиций в MRVS.
/// </summary>
/// <param name="branch">Ветвь.</param>
/// <param name="MRVS">MRVS.</param>
/// <returns></returns>
Pos MaxDegree(MyCell [,]branch, List<Pos> MRVS)
{
int deg = -1;
Pos p =null;
for (int i = 0; i < MRVS.Count; i++)
{
int count = 0;
for (int k = 0; k < branch[MRVS[i].ln ,MRVS[i].col].Peers.Count; k++)
if (!branch[branch[MRVS[i].ln ,MRVS[i].col].Peers[k].ln,
branch[MRVS[i].ln ,MRVS[i].col].Peers[k].col].assigned)
count++;
if (count > deg)
{
deg = count;
p = MRVS[i];
}
}
return p;
}
Это выглядит лучше, но требует много времени на вычисления, так стоит ли использовать этот метод? Не всегда. Мы выполним ряд сравнений в конце.
Эвристика значения
Мы знаем, как выбрать ячейку, теперь нужно выбрать, которое значение из вероятностей (домена) проверить первым. Это называется Эвристикой значения.
Эвристика лексикографического (словарного) порядка:
В начале эвристики значения мы снова выбираем первое значение.
char LexicographicOrderFirst(MyCell[,] branch, Pos variablePosition)
{
return branch[variablePosition.ln, variablePosition.col].Value[0];
}
Эвристика наименьшего значения ограничения:
В этой эвристике выбирается значение, которое создает минимальную трудность для выбранных узлов ячеек. Например, если для нашей ячейки есть варианты 7 и 9, мы проверяем, в каком количестве узлов этой ячейки в домене появляется 7, и то же самое делаем для 9. Затем алгоритм выбирает число, которое меньше всего раз появляется в домене узлов ячейки.
char LeastConstraintValue(MyCell[,] branch, Pos variablePosition)
{
int[] arr = new int[branch[variablePosition.ln, variablePosition.col].Value.Length];
for (int i = 0; i < arr.Length; i++)
arr[i] = 0;
for (int i = 0; i < branch[variablePosition.ln, variablePosition.col].Value.Length; i++)
for (int j = 0; j < branch[variablePosition.ln, variablePosition.col].Peers.Count; j++)
{
if (branch[branch[variablePosition.ln, variablePosition.col].Peers[j].ln,
branch[variablePosition.ln,
variablePosition.col].Peers[j].col].Value.Contains(
branch[variablePosition.ln, variablePosition.col].Value[i].ToString()))
arr[i]++;
}
return branch[variablePosition.ln, variablePosition.col].Value[GetMinIndex(arr)];
}
Точки интереса
На этом все! Давайте посмотрим, как это работает:
Автор: Dotan Asselmann
Загрузить демо-пример - 181 KB
Загрузить исходный код - 207 KB