一种不知道对不对的exact cover solution.

这是个NPC问题

先来看经典的Dancing Links

先看中文翻译，直到Four-way-linked插图，然后请看英文版pdf，结合代码，在pdf上用画笔抹一抹，就明白了。
粘链接

中文DLXcn翻译、及英文pdf在这里 https://github.com/sqybi/DLXcn
java代码看这里 http://blog.gssxgss.me/use-dlx-to-solve-sudoku-1/
我觉得这个java写的不错啊，没有很多多余代码的java。。

然后来看我写的代码

感觉比链表要好写点，看起来可能复杂。
Problem : select some projects (any number projects), to cover all constrain, and don't have overlay.

struct project 是方案做行
struct constrain 限制条件做列
Ideas :
If we select a project, all constraints relative to this project will disable.
If we select a constraint, all projects relative to this constrain will disable.
when we use brute-force DFS, we need set the state, and restore the state. Calling function cover(cid) to set the state, and calling function uncover(cid) to restore.
To use cover/uncover functions, we call function in the same relative order, to wind-up and untie the state on each column(constraint).
In cover/uncover functions, we reserve a cell not to update, because it will used into restore a state. (see codes below).

some definitions

//constrain is the columnHeaders;
struct Constrain {
    //set<projectID> available : the projectID(cell) not isolated from main map.
    //set<projectID> disable : the projectID(cell) has been chosen before.
    set<int> available, disable;
    bool chosen=false;
};
//project is the rowHeaders;
struct Project {
    int description;
    set<int> c;//constrains.
};
vector<Project> proj; //row
vector<Constrain> con; //column

/** 下面是工作区 **/
//在众多columnHeaders里面，找到最容易尝试的一个。
int findBestConstrain() {
    int minTryCnt=MAXPROJ,cid=-1;
    for (int i=0; i<con.size(); i++)
        if (con[i].chosen==false && con[i].available.size()<minTryCnt)
            minTryCnt = con[i].available.size(), cid = i;
    return cid;
}

//同DLX中的cover
void cover(int constraintID) {
    con[constraintID].chosen = true;
    for (int projectID : con[constraintID].available)
        for (int cellID : proj[projectID].c)
            if (cellID != constraintID) {//保留自己人，给uncover函数留线索。
                con[cellID].available.erase(projectID);
                con[cellID].disable.insert(projectID);
            }
}

//同DLX中的cover
void uncover(int constraintID) {
    con[constraintID].chosen = false;
    for (int projectID : con[constraintID].available)
        for (int cellID : proj[projectID].c) 
            if (cellID != constraintID){//自己人不能动，万一是在祖先bfs时候cover的呢。
                con[cellID].available.insert(projectID);
                con[cellID].disable.erase(projectID);
        }
}

vector<Project> ansList;
bool solve() {
    int cid = findBestConstrain();
    if (cid==-1)//answer..
        return true;
    cover(cid);//当前这列标记为“不要动啊！”
    for (int projID: con[cid].available) {
        //chosen a project and disable other column related with this project.
        ansList.push_back( proj[projID] );
        for (int columnID: proj[projID].c)
            cover(columnID);
        if (solve())
            return true;
        //Then, backtracking......
        ansList.pop_back();
        for (int columnID: proj[projID].c)
            uncover(columnID);
    }
    uncover(cid);//恢复一下当前这列的原始状态，可以认为cover(cid) -> uncover(cid)一定能还原！
    return false;
}

好了就这些，建完图调用solve()出结果，至于怎么建图。。。。。
举个例子 https://leetcode.com/problems/sudoku-solver/

int main()
{
        int rowHave[9][10]; memset(rowHave,0,sizeof(rowHave));
        int colHave[9][10]; memset(colHave,0,sizeof(colHave));
        int zoneHave[9][10]; memset(zoneHave,0,sizeof(zoneHave));
        int posHave[9][9];
        for (int i=0; i<9; i++)
            for (int j=0; j<9; j++) 
                if (board[i][j]!='.'){
                    int key=board[i][j]-'0';
                    rowHave[i][key]=-1;
                    colHave[j][key]=-1;
                    zoneHave[(i/3)*3+(j/3)][key]=-1;
                }
        
        //make Graphics.
        int cntC=0, cntProj=0;
        for (int i=0; i<9; i++)
            for (int j=0; j<9; j++) {
                if (board[i][j]=='.')
                    posHave[i][j]=cntC++;
            }
        for (int i=0; i<9; i++)
            for (int key=1; key<=9; key++) {
                if (rowHave[i][key] == 0)
                    rowHave[i][key]=cntC++;
                if (colHave[i][key] == 0)
                    colHave[i][key]=cntC++;
                if (zoneHave[i][key] == 0)
                    zoneHave[i][key]=cntC++;
            }
        con.assign(cntC, Constrain());
        for (int i=0; i<9; i++)
        for (int j=0; j<9; j++)
            if (board[i][j]=='.') {
                for (int key=1; key<=9; key++) {
                    if (rowHave[i][key]!=-1 && colHave[j][key]!=-1 && zoneHave[(i/3)*3+(j/3)][key]!=-1) {
                        Project p{i,j,key};
                        p.c.insert( rowHave[i][key] );
                        p.c.insert( colHave[j][key] );
                        p.c.insert( zoneHave[(i/3)*3+(j/3)][key] );
                        p.c.insert( posHave[i][j] );
                        proj.push_back(p);
                        con[rowHave[i][key]].available.insert(cntProj);
                        con[colHave[j][key]].available.insert(cntProj);
                        con[zoneHave[(i/3)*3+(j/3)][key]].available.insert(cntProj);
                        con[posHave[i][j]].available.insert(cntProj);
                        cntProj++;
                    }
                }
            }
        if (!solve())
            return ;
        for (auto &it : ansList)
            board[it.descR][it.descC] = it.descNum+'0';
}

序

发现自己真是漏掉了好多好多算法没有学过，太充分关注于能解的，对于NP问题，只学了比如八皇后这些。。
一张图送给自己

先来看经典的Dancing Links

然后来看我写的代码

Ideas :

some definitions

序

添加新评论