Судоку как CSP - Эвристика значения

Эвристика значения

Мы знаем, как выбрать ячейку, теперь нужно выбрать, которое  значение из вероятностей (домена) проверить первым. Это называется Эвристикой значения.

Эвристика лексикографического (словарного) порядка:

В начале эвристики значения мы снова выбираем первое значение.

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