Skip to content

Instantly share code, notes, and snippets.

@MORTAL2000

MORTAL2000/dlx.h

Forked from diegode/dlx.h
Created May 12, 2018 05:47
Show Gist options
  • Save MORTAL2000/7ca208e3de77bf5abb6c8ccc6e818d9d to your computer and use it in GitHub Desktop.
Save MORTAL2000/7ca208e3de77bf5abb6c8ccc6e818d9d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @diegode diegode created this gist Mar 5, 2011.
    210 changes: 210 additions & 0 deletions dlx.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,210 @@
    //The following code is based on the paper "Dancing Links" by D. E. Knuth.
    //See http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
    #ifndef DLX_H
    #define DLX_H
    #include <cstring>
    #include <climits>
    struct data_object //A module in the sparse matrix data structure.
    {
    data_object* L; //Link to next object left.
    data_object* R; // " right.
    data_object* U; // " up.
    data_object* D; // " down.
    data_object* C; //Link to column header.
    int x; //In a column header: number of ones
    //in the column. Otherwise: row index.
    void cover() //Covers a column.
    {
    data_object *i, *j;
    R->L=L;
    L->R=R;
    for (i=D; i!=this; i=i->D)
    {
    for (j=i->R; j!=i; j=j->R)
    {
    j->D->U=j->U;
    j->U->D=j->D;
    j->C->x--;
    }
    }
    }
    void uncover() //Uncovers a column.
    {
    data_object *i, *j;
    for (i=U; i!=this; i=i->U)
    {
    for (j=i->L; j!=i; j=j->L)
    {
    j->C->x++;
    j->D->U=j;
    j->U->D=j;
    }
    }
    R->L=this;
    L->R=this;
    }
    };
    //Standard S-heuristic suggested in Knuth's paper: pick the column with the
    //fewest ones. Takes the root of the sparse matrix structure as an argument;
    //returns a pointer to the column header with the fewest ones.
    data_object* DLX_Knuth_S_heuristic(data_object* root)
    {
    data_object *P, *res;
    int best=INT_MAX/2;
    for (P=root->R; P!=root; P=P->R)
    {
    if (P->x<best)
    {
    best=P->x;
    res=P;
    }
    }
    return res;
    }
    template <typename Func1,typename Func2>
    /*
    Actual recursive function implementing Knuth's Dancing Links method.
    h is the root of the sparse matrix structure.
    O is the stack that will contain a list of rows used.
    */
    void DLX_search(data_object* h,int k,int* O,Func1 send_row,
    Func2 choose_column)
    {
    int i;
    data_object *r,*c,*j;
    if (h->R==h) //done - solution found
    {
    //send rows used in solution back...
    for (i=0; i<k; i++)
    send_row(O[i]);
    //-1 signifies end of solution
    send_row(-1);
    return;
    }
    //otherwise
    c=choose_column(h); //choose a column to cover
    c->cover(); //cover it
    for (r=c->D; r!=c; r=r->D)
    {
    O[k]=r->x;
    for (j=r->R; j!=r; j=j->R)
    j->C->cover();
    DLX_search(h,k+1,O,send_row,choose_column);
    //set r <- O[k], and c<- C[r], this is unnecessary
    for (j=r->L; j!=r; j=j->L)
    j->C->uncover();
    }
    c->uncover();
    }
    template <typename random_access_iterator,typename Func1,typename Func2>
    /*
    Meta-implementation of Knuth's Dancing Links method for finding solutions to
    the exact cover problem.
    PARAMETERS:
    int rows: Number of rows in the matrix.
    int cols: Number of columns in the matrix.
    random_access_iterator buf: A random access iterator to ints (either 0 or
    1), the entries of the matrix, in row major order.
    Func1 send_row: A function object with return type void which takes as a
    parameter the index of a row in a solution to the problem. (e.g. store it in
    a buffer or print it out) -1 signifies the end of a solution.
    Func2 choose_column: A deterministic function object taking as a parameter a
    data_object* (the root) and returning a data_object* (the header of the
    column to choose.)
    */
    void DLX_dancing_links(int rows,int cols,random_access_iterator buf,
    Func1 send_row,Func2 choose_column)
    {
    //step 1: construct the linked-list structure.
    //We can do this by iterating through the rows and columns. Time is
    //linear in the number of entries (optimal).
    //Space used is linear in the number of columns + the number of rows
    // + the number of ones.
    int i,j;
    data_object* root=new data_object; //root
    data_object* P=root; //left-right walker
    data_object* Q; //top-down walker
    //array of pointers to column headers
    data_object** walkers=new data_object*[cols];
    //auxiliary stack for recursion
    int* st=new int[rows];
    for (i=0; i<cols; i++)
    {
    //create a column header and L/R links
    (P->R=new data_object)->L=P;
    //store a pointer to the column header
    walkers[i]=Q=P=P->R;
    P->x=0; //reset popcount
    for (j=0; j<rows; j++)
    if (buf[i+cols*j]) //a 1 in the current location?
    {
    //create a data object and U/D links
    (Q->D=new data_object)->U=Q;
    Q=Q->D; //advance pointer
    Q->C=P; //link to the column header
    P->x++; //increment popcount for this column
    Q->x=j; //note the row number of this entry
    }
    Q->D=P; //complete the column
    P->U=Q;
    }
    P->R=root; //complete the column list
    root->L=P;
    //eliminate empty columns
    P=root;
    for (i=0; i<cols; i++)
    {
    P=P->R;
    if (!P->x)
    {
    P->L->R=P->R;
    P->R->L=P->L;
    }
    }
    //now construct the L/R links for the data objects.
    P=new data_object;
    for (i=0; i<rows; i++)
    {
    Q=P;
    for (j=0; j<cols; j++)
    if (buf[j+cols*i]) //a one
    {
    //in _this_ row...
    walkers[j]=walkers[j]->D;
    //create L/R links
    (Q->R=walkers[j])->L=Q;
    //advance pointer
    Q=Q->R;
    }
    if (Q==P) continue;
    Q->R=P->R; //link it to the first one in this row.
    P->R->L=Q; //link the first one to the last one.
    }
    delete P; //P is no longer needed
    delete walkers; //walkers are no longer needed
    //step 2: recursive algorithm
    DLX_search(root,0,st,send_row,choose_column);
    delete st;
    for (P=root->R; P!=root; ) //deallocate sparse matrix structure
    {
    for (Q=P->D; Q!=P; )
    {
    Q=Q->D;
    delete Q->U;
    }
    P=P->R;
    delete P->L;
    }
    delete root;
    }

    //If no heuristic is specified, Knuth's S heuristic is used - select the
    //column with the fewest ones to minimize the breadth of the search tree.
    template <typename random_access_iterator,typename Func1>
    void DLX_dancing_links(int rows,int cols,random_access_iterator buf,Func1 send_row)
    {
    DLX_dancing_links(rows,cols,buf,send_row,DLX_Knuth_S_heuristic);
    }

    #endif
    9 changes: 9 additions & 0 deletions input_example
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,9 @@
    . 5 . . . . 4 . .
    . . . 4 . . . 3 .
    4 . . . 9 . . . 6
    7 . . . . . 9 . 8
    9 . . 7 . . . 5 .
    . 8 3 . 5 . 6 2 .
    . . . . 2 8 . 4 .
    . . 2 . . . . . 5
    6 . . . . 3 . . .
    80 changes: 80 additions & 0 deletions sudoku.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,80 @@
    #include <iostream>
    #include "dlx.h"
    using namespace std;
    #define block(r,c) (3*((r)/3)+((c)/3))
    int cnt=0;
    int grid[9][9];
    void f(int x)
    {
    int i;
    int c;
    int r;
    if (x+1)
    {
    i=x%9; x/=9;
    c=x%9; r=x/9;
    grid[r][c]=i+1;
    }
    else
    {
    for (r=0; r<9; r++,putchar('\n'))
    for (c=0; c<9; c++)
    putchar(grid[r][c]+'0');
    printf("\n");
    }
    }
    int matrix[729][324];
    void cover_col(int col)
    {
    for (int row=0; row<729; row++)
    if (matrix[row][col])
    {
    matrix[row][col]=0;
    memset(matrix[row],0,sizeof(matrix[row]));
    }
    }
    void cover_row(int row)
    {
    for (int col=0; col<324; col++)
    if (matrix[row][col])
    {
    matrix[row][col]=0;
    cover_col(col);
    }
    }
    int main()
    {
    int row,r,c,i;
    char ch;
    for (row=0,r=0; r<9; r++)
    for (c=0; c<9; c++)
    for (i=0; i<9; i++,row++)
    {
    //uniqueness constraint
    matrix[row][r+9*c]=1;
    //row constraint
    matrix[row][81+i+9*r]=1;
    //column constraint
    matrix[row][162+i+9*c]=1;
    //block constraint
    matrix[row][243+i+9*block(r,c)]=1;
    }
    for (r=0; r<9; r++)
    for (c=0; c<9; c++)
    {
    scanf("%c",&ch);
    if (ch>='1'&&ch<='9') //known value
    {
    cover_row(81*r+9*c+ch-'1');
    grid[r][c]=ch-'0';
    }
    else if (ch!='.'&&ch!='0') //placeholder
    {
    c--;
    continue;
    }
    }
    putchar('\n');
    DLX_dancing_links(729,324,(int*)&matrix,f);
    return 0;
    }