Судоку как CSP - Согласованность по дугам

ОГЛАВЛЕНИЕ

Согласованность по дугам

То, что мы делаем, не является в точности согласованием arc, но основано на этом. Мы  выполняем три типа сокращения (уменьшения), некоторые для сокращения доменов и некоторые, чтобы увидеть ошибки заблаговременно и сэкономить время:

  1. Когда символ 'd' присваивается ячейке s1, используется выражение вида присвоить(ячейки, s, d). С помощью этого мы хотим присвоить s значение d, но  также хотим исключить данную вероятность из ее узлов сети (как делает FC). Если исключение уменьшает число вероятностей одного (или нескольких) из узлов сети до одной вероятности, которую мы называем d2, то мы хотим присвоить d2 узлу сети и с помощью этого исключить d2 из всех узлов этого узла, то данное действие может вызвать другую цепную реакцию. Эта цепная реакция называется распространением ограничивающих условий: помещение ограничения на одну ячейку может вызвать дальнейшее помещение ограничений на другие ячейки.
  2. Второй тип: можно сказать, что мы просто исключаем 6 как возможное значение ячейки [0,0], и если мы посмотрим на первый блок (блок строк) [0,0], то увидим, что единственной ячейкой, имеющей 6 как вероятность, является [0,7]. Мы присвоим 6 ячейке [0,7], и снова произойдет цепная реакция.
  3. Последнее – это предварительная проверка на наличие ошибок, потому что Судоку объявляется как ограничение 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;
}

Это был первый шаг, но некоторые Судоку не оставляют нам другого выбора и вынуждают использовать угадывание, чтобы найти решение. Но если догадка неверная? Приходится возвращаться прежним путем, следовательно, мы используем поиск с возвратом.