Судоку как CSP - Поиск с возвратом

Поиск с возвратом

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

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

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;
}

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