Задача о точном покрытии и алгоритм X | Набор 2 (реализация с DLX)

Опубликовано: 19 Января, 2022

В статье Проблема точного покрытия и алгоритм X | В наборе 1 мы обсудили проблему точного покрытия и алгоритм X для решения проблемы точного покрытия. В этой статье мы обсудим детали реализации алгоритма X с использованием техники танцевальных связей (DLX), предложенной доктором Дональдом Э. Кнутом в его статье «Танцующие ссылки».

Техника Танцевальной Связи

Техника танцевальных ссылок основана на идее двусвязного списка. Как обсуждалось в предыдущей статье, мы преобразуем задачу точного покрытия в форму матрицы из 0 и 1. Здесь каждая «1» в матрице представлена узлом связанного списка, а вся матрица преобразуется в сетку из четырех связанных узлов. . Каждый узел содержит следующие поля -

Указатель на узел слева от него
Указатель на узел справа от него
Указатель на узел над ним
Указатель на узел под ним
Указатель на узел заголовка списка, которому он принадлежит

Таким образом, каждая строка матрицы представляет собой круговой связанный список, связанный друг с другом левым и правым указателями, и каждый столбец матрицы также будет круговым связанным списком, связанным с каждым из них указателем вверх и вниз. Каждый список столбцов также включает в себя специальный узел, называемый «узел заголовка списка». Этот узел заголовка похож на простой узел, но имеет несколько дополнительных полей -

Идентификатор столбца
Количество узлов в текущем столбце

У нас может быть два разных типа узлов, но в нашей реализации мы создадим только один вид узла со всеми полями для удобства с дополнительным полем «Идентификатор строки», которое будет указывать, к какой строке принадлежит этот узел.
Итак, для матрицы -

Матрица с четырехсторонней связью будет выглядеть так -

Четырехсторонняя связанная матрица

Таким образом, псевдокод для алгоритма поиска (алгоритм X) будет -

f (h.right == h) { 
     printSolutions (); 
     возвращение; 
} 
еще { 
     ColumnNode column = getMinColumn (); 
     крышка (столбик); 

     for (Узел row = column.down; rowNode! = column;
        rowNode = rowNode.down) { 
            решения.add (rowNode); 

            for (Узел rightNode = row.right; rightNode! = row;
                 rightNode = rightNode.right) 
                    крышка (rightNode); 

     Поиск (k + 1); 
     решения.remove (rowNode); 
     столбец = rowNode.column; 

     for (Узел leftNode = rowNode.left; leftNode! = row;
              leftNode = leftNode.left)                                                                             
            раскрыть (leftNode); 
     } 
     раскрыть (столбец); 
}

Покрывающий узел

Как обсуждалось в алгоритме, мы должны удалить столбцы и все строки, которым принадлежат узлы этого столбца. Этот процесс здесь называется покрытием узла.
Чтобы удалить столбец, мы можем просто отсоединить заголовок этого столбца от соседних заголовков. Таким образом, этот столбец будет недоступен. Этот процесс аналогичен удалению узла из двусвязного списка, предположим, мы хотим удалить узел x, тогда -

x.left.right = x.right
x.right.left = x.left

Аналогично, чтобы удалить строку, мы должны отсоединить все узлы строки от узлов строки выше и ниже нее.

x.up.down = x.down
x.down.up = x.up

Таким образом, псевдокод для покрытия (узла) становится -

Столбец узла = dataNode.column; 

column.right.left = column.left; 
column.left.right = column.right; 

for (Узел row = column.down; row! = column; row = row.down) 
    for (Узел rightNode = row.right; rightNode! = row; 
         rightNode = rightNode.right) { 
         rightNode.up.down = rightNode.down; 
         rightNode.down.up = rightNode.up; 
    } 
}

Так, например, после покрытия столбца A матрица будет выглядеть так:

покрытие

Здесь мы сначала удаляем столбец из других столбцов, затем мы переходим к каждому узлу столбца и удаляем строку, перемещаясь вправо, поэтому удаляются строки 2 и 4.

Раскрытие узла

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

x.left.right = x
x.right.left = x

Аналогично, чтобы раскрыть любой узел строки x -

x.up.down = x
x.down.up = x

Таким образом, псевдокод для раскрытия (узла) станет -

Столбец узла = dataNode.column; 

for (Узел row = column.up; row! = column; row = row.up) 
    for (Узел leftNode = row.left; leftNode! = row;
         leftNode = leftNode.right) { 
         leftNode.up.down = leftNode; 
         leftNode.down.up = leftNode; 
     } 
column.right.left = столбец; 
column.left.right = столбец; 
}

Following is the implementation of dancing link technique –

// C++ program for solving exact cover problem
// using DLX (Dancing Links) technique
  
#include <bits/stdc++.h>
  
#define MAX_ROW 100
#define MAX_COL 100
  
using namespace std;
  
struct Node
{
public:
    struct Node *left;
    struct Node *right;
    struct Node *up;
    struct Node *down;
    struct Node *column;
    int rowID;
    int colID;
    int nodeCount;
};
  
// Header node, contains pointer to the
// list header node of first column
struct Node *header = new Node();
  
// Matrix to contain nodes of linked mesh
struct Node Matrix[MAX_ROW][MAX_COL];
  
// Problem Matrix
bool ProbMat[MAX_ROW][MAX_COL];
  
// vector containing solutions
vector <struct Node*> solutions;
  
// Number of rows and columns in problem matrix 
int nRow = 0,nCol = 0;
  
  
// Functions to get next index in any direction
// for given index (circular in nature) 
int getRight(int i){return (i+1) % nCol; }
int getLeft(int i){return (i-1 < 0) ? nCol-1 : i-1 ; }
int getUp(int i){return (i-1 < 0) ? nRow : i-1 ; }  
int getDown(int i){return (i+1) % (nRow+1); }
  
// Create 4 way linked matrix of nodes
// called Toroidal due to resemblance to
// toroid
Node *createToridolMatrix()
{
    // One extra row for list header nodes
    // for each column
    for(int i = 0; i <= nRow; i++)
    {
        for(int j = 0; j < nCol; j++)
        {
            // If it"s 1 in the problem matrix then 
            // only create a node 
            if(ProbMat[i][j])
            {
                int a, b;
  
                // If it"s 1, other than 1 in 0th row
                // then count it as node of column 
                // and increment node count in column header
                if(i) Matrix[0][j].nodeCount += 1;
  
                // Add pointer to column header for this 
                // column node
                Matrix[i][j].column = &Matrix[0][j];
  
                // set row and column id of this node
                Matrix[i][j].rowID = i;
                Matrix[i][j].colID = j;
  
                // Link the node with neighbors
  
                // Left pointer
                a = i; b = j;
                do{ b = getLeft(b); } while(!ProbMat[a][b] && b != j);
                Matrix[i][j].left = &Matrix[i][b];
  
                // Right pointer
                a = i; b = j;
                do { b = getRight(b); } while(!ProbMat[a][b] && b != j);
                Matrix[i][j].right = &Matrix[i][b];
  
                // Up pointer
                a = i; b = j;
                do { a = getUp(a); } while(!ProbMat[a][b] && a != i);
                Matrix[i][j].up = &Matrix[a][j];
  
                // Down pointer
                a = i; b = j;
                do { a = getDown(a); } while(!ProbMat[a][b] && a != i);
                Matrix[i][j].down = &Matrix[a][j];
            }
        }
    }
  
    // link header right pointer to column 
    // header of first column 
    header->right = &Matrix[0][0];
  
    // link header left pointer to column 
    // header of last column 
    header->left = &Matrix[0][nCol-1];
  
    Matrix[0][0].left = header;
    Matrix[0][nCol-1].right = header;
    return header;
}
  
// Cover the given node completely
void cover(struct Node *targetNode)
{
    struct Node *row, *rightNode;
  
    // get the pointer to the header of column
    // to which this node belong 
    struct Node *colNode = targetNode->column;
  
    // unlink column header from it"s neighbors
    colNode->left->right = colNode->right;
    colNode->right->left = colNode->left;
  
    // Move down the column and remove each row
    // by traversing right
    for(row = colNode->down; row != colNode; row = row->down)
    {
        for(rightNode = row->right; rightNode != row;
            rightNode = rightNode->right)
        {
            rightNode->up->down = rightNode->down;
            rightNode->down->up = rightNode->up;
  
            // after unlinking row node, decrement the
            // node count in column header
            Matrix[0][rightNode->colID].nodeCount -= 1;
        }
    }
}
  
// Uncover the given node completely
void uncover(struct Node *targetNode)
{
    struct Node *rowNode, *leftNode;
  
    // get the pointer to the header of column
    // to which this node belong 
    struct Node *colNode = targetNode->column;
  
    // Move down the column and link back
    // each row by traversing left
    for(rowNode = colNode->up; rowNode != colNode; rowNode = rowNode->up)
    {
        for(leftNode = rowNode->left; leftNode != rowNode;
            leftNode = leftNode->left)
        {
            leftNode->up->down = leftNode;
            leftNode->down->up = leftNode;
  
            // after linking row node, increment the
            // node count in column header
            Matrix[0][leftNode->colID].nodeCount += 1;
        }
    }
  
    // link the column header from it"s neighbors
    colNode->left->right = colNode;
    colNode->right->left = colNode;
}
  
// Traverse column headers right and 
// return the column having minimum 
// node count
Node *getMinColumn()
{
    struct Node *h = header;
    struct Node *min_col = h->right;
    h = h->right->right;
    do
    {
        if(h->nodeCount < min_col->nodeCount)
        {
            min_col = h;
        }
        h = h->right;
    }while(h != header);
  
    return min_col;
}
  
  
void printSolutions()
{
    cout<<"Printing Solutions: ";
    vector<struct Node*>::iterator i;
  
    for(i = solutions.begin(); i!=solutions.end(); i++)
        cout<<(*i)->rowID<<" ";
    cout<<"
";
}
  
// Search for exact covers
void search(int k)
{
    struct Node *rowNode;
    struct Node *rightNode;
    struct Node *leftNode;
    struct Node *column;
  
    // if no column left, then we must
    // have found the solution
    if(header->right == header)
    {
        printSolutions();
        return;
    }
  
    // choose column deterministically
    column = getMinColumn();
  
    // cover chosen column
    cover(column);
  
    for(rowNode = column->down; rowNode != column; 
        rowNode = rowNode->down )
    {
        solutions.push_back(rowNode);
  
        for(rightNode = rowNode->right; rightNode != rowNode;
            rightNode = rightNode->right)
            cover(rightNode);
  
        // move to level k+1 (recursively)
        search(k+1);
  
        // if solution in not possible, backtrack (uncover)
        // and remove the selected row (set) from solution
        solutions.pop_back();
  
        column = rowNode->column;
        for(leftNode = rowNode->left; leftNode != rowNode;
            leftNode = leftNode->left)
            uncover(leftNode);
    }
  
    uncover(column);
}
  
// Driver code
int main()
{    
    /*
     Example problem
  
     X = {1,2,3,4,5,6,7}
     set-1 = {1,4,7}
     set-2 = {1,4}
     set-3 = {4,5,7}
     set-4 = {3,5,6}
     set-5 = {2,3,6,7}
     set-6 = {2,7}
     set-7 = {1,4}
  
     Solutions : {6 ,4, 2} and {6, 4, 7}
    */
  
    nRow = 7;
    nCol = 7;
      
    // initialize the problem matrix 
    // ( matrix of 0 and 1) with 0
    for(int i=0; i<=nRow; i++)
    {
        for(int j=0; j<nCol; j++)
        {
            // if it"s row 0, it consist of column
            // headers. Initialize it with 1
            if(i == 0) ProbMat[i][j] = true;
            else ProbMat[i][j] = false;
        }
    }
  
    // Manually filling up 1"s 
    ProbMat[1][0] = true; ProbMat[1][3] = true;
    ProbMat[1][6] = true; ProbMat[2][0] = true;
    ProbMat[2][3] = true; ProbMat[3][3] = true;
    ProbMat[3][4] = true; ProbMat[3][6] = true;
    ProbMat[4][2] = true; ProbMat[4][4] = true;
    ProbMat[4][5] = true; ProbMat[5][1] = true;
    ProbMat[5][2] = true; ProbMat[5][5] = true;
    ProbMat[5][6] = true; ProbMat[6][1] = true;
    ProbMat[6][6] = true; ProbMat[7][0] = true;
    ProbMat[7][3] = true;
  
    // create 4-way linked matrix
    createToridolMatrix();
      
    search(0);
    return 0;
}

Выход:

Решения для печати: 6 4 2 
Решения для печати: 6 4 7

использованная литература

https://www.ocf.berkeley.edu/%7Ejchu/publicportal/sudoku/sudoku.paper.html
Танцующие ссылки Дональда Кнута

Эта статья предоставлена Атулом Кумаром . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Задача о точном покрытии и алгоритм X | Набор 2 (реализация с DLX)

РЕКОМЕНДУЕМЫЕ СТАТЬИ