Судоку как CSP

Использование алгоритмов и методов из CSP для решения головоломки Sudoku размером NxN клеток.

Введение

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

Судоку?

Нам кажется, что каждый знаком с Судоку; если вы не знаете, что это такое, поищите информацию в Google или в Википедии.

Основные правила Судоку таковы:

1. Для каждой строки/столбца/области вы должны использовать различные числа.
2. Все клетки должны быть заполнены.

Доска Судоку – это матрица NxN, и это означает, что нужно использовать число из диапазона [1..N].

Что такое CSP?

CSP или Задача поиска допустимого решения определяется через три составляющие:

1. Конечный набор переменных.
2. Функция, которая устанавливает соответствие каждой переменной конечному домену (области).
3. Конечный набор ограничивающих условий.

Распространение ограничивающих условий и поиск с возвратом – это методы в 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;
}