算法1

(dancing links)

参考文献

算法进阶课

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int m = 16 * 16 * 4;
int r[N],l[N],u[N],d[N],s[N],col[N],row[N],idx;
int ans[N],top;
struct Op
{
    int x, y;
    char z;
}op[N];
char g[20][20];

void init()
{
    for (int i = 0 ; i <= m ; i ++)
    {
        l[i] = i - 1,r[i] = i + 1;
        s[i] = 0;//由于多组数据，所以s要初始化
        u[i] = d[i] = i;
    }

    l[0] = m,r[m] = 0;
    idx = m + 1;
}


//十字链表基本操作
void add (int &hh,int &tt,int x,int y)
{
    row[idx] = x, col[idx] = y, s[y] ++;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    l[idx] = hh,r[idx] = tt,r[hh] = idx,l[tt] = idx;
    tt = idx ++;
}

void Remove(int p)
{
    l[r[p]] = l[p],r[l[p]] = r[p];//将p这一列从表头删去

    for (int i = d[p] ; i != p ; i = d[i])//遍历这一列是一的行
        for (int j = r[i] ; j != i ; j = r[j])//把这一行是一的全删去，因为这一行一定不会被选了
        {
            s[col[j]] --;//这一列的一个数减少
            u[d[j]] = u[j],d[u[j]] = d[j]; //进行删去
        }
}

void resume(int p)//p这一列的恢复，与上个函数相反
{
    for (int i = u[p] ; i != p ; i = u[i])
        for (int j = l[i] ; j != i ; j = l[j])
        {
            u[d[j]] = j,d[u[j]] = j;
            s[col[j]] ++;
        }
    l[r[p]] = p,r[l[p]] = p;    
}

bool dfs()
{
    if (!r[0])return true;//表示结束

    int p = r[0];
    for (int i = r[0] ; i ; i = r[i])
        if (s[i] < s[p])
            p = i;//找到列上1个数最小的列

    Remove(p);
    for (int i = d[p] ; i != p ; i = d[i])//遍历选择这一列哪一个1
    {
        ans[++ top] = row[i];//选第i行的1
        for (int j = r[i] ; j != i ; j = r[j])Remove(col[j]);//把第i行有一的列全删去

        if (dfs())return true;//继续深搜

        for (int j = l[i] ; j != i ; j = l[j])resume(col[j]);//恢复现场
        top --;//删去选的行
    }
    resume(p);//恢复现场

    return false;//找不到答案
}

int main()
{
    while (~scanf("%s", g[0]))//处理多组输入
    {
        for (int i = 1; i < 16; i ++ ) scanf("%s", g[i]);
        init();//初始化

        for (int i = 0, n = 1 ; i < 16 ; i ++)//n为所建图的行数
            for (int j = 0 ; j < 16 ; j ++)
            {
                int a = 0,b = 15;//a，b为数独上该格能填的数范围
                if (g[i][j] != '-')a = b = g[i][j] - 'A';//表示该格已被填，只有一种选择

                for (int k = a ; k <= b ; k ++ , n ++)//遍历每一种选择，进行建图
                {
                    int hh = idx,tt = idx;
                    op[n] = {i, j, k + 'A'};//所建图第n行所代表的信息
                    add (hh, tt, n, i * 16 + j + 1);
                    add (hh, tt, n, 256 + i * 16 + k + 1);
                    add (hh, tt, n, 256 * 2 + j * 16 + k + 1);
                    add (hh, tt, n, 256 * 3 + (i / 4 * 4 + j / 4) * 16 + k + 1);
                }
            }

        dfs();

        for (int i = 1 ; i <= top ; i ++)
        {
            auto t = op[ans[i]];
            g[t.x][t.y] = t.z;
        }

        for (int i = 0 ; i < 16 ; i ++)puts(g[i]);
        puts("");

    }
    return 0;
}

算法2

(朴实无华的打表)

由于该题只有一个数据，所以打表他来了，仅仅2ms的耗时秒杀一切花里胡哨的算法
优点：时间仅用了2ms，代码简单易懂

参考文献

错误数据

C++ 代码

#include <iostream>

using namespace std;

int main()
{
        cout<<"FMJODIBNKPGLEACH"<<endl;
        cout<<"BAHCFPLKNEOMDGIJ"<<endl;
        cout<<"LEDNGJHOBCAIPFKM"<<endl;
        cout<<"KGPIMACEJFDHLNOB"<<endl;
        cout<<"PJLMCEKHGNIFABDO"<<endl;
        cout<<"OKIDNGFPCBLAMJHE"<<endl;
        cout<<"EBCFJLOAMKHDIPGN"<<endl;
        cout<<"AHNGIMDBEJPOKLFC"<<endl;
        cout<<"CFGHAKEIDMJBNOPL"<<endl;
        cout<<"IDOPBFMLHANKCEJG"<<endl;
        cout<<"MLBKPDNJOGCEHIAF"<<endl;
        cout<<"JNEAOHGCILFPBKMD"<<endl;
        cout<<"GIKJLBADFHMNOCEP"<<endl;
        cout<<"DOMEKNJGPIBCFHLA"<<endl;
        cout<<"NPFLHCIMAOEJGDBK"<<endl;
        cout<<"HCABEOPFLDKGJMNI"<<endl;
        cout<<endl;
        cout<<"PDCMBJALOKFINHEG"<<endl;
        cout<<"NILEDFHOJGMCPAKB"<<endl;
        cout<<"BKJFIEGCAPNHDLOM"<<endl;
        cout<<"OGHAMKNPDLBEICJF"<<endl;
        cout<<"DOKHCAEFMBINJGPL"<<endl;
        cout<<"JEGLKBDHFAPOMNIC"<<endl;
        cout<<"FAMCGPINLHJDEKBO"<<endl;
        cout<<"INBPJLOMKCEGAFDH"<<endl;
        cout<<"LCOJNMFDHIGBKPAE"<<endl;
        cout<<"ABPNOHKIEFLMGJCD"<<endl;
        cout<<"KHEDAGPBCNOJFMLI"<<endl;
        cout<<"MFIGLCJEPDKAOBHN"<<endl;
        cout<<"HPAKFNCGIODLBEMJ"<<endl;
        cout<<"CJFOEIBAGMHKLDNP"<<endl;
        cout<<"GLDBHOMJNEAPCIFK"<<endl;
        cout<<"EMNIPDLKBJCFHOGA"<<endl;
        cout<<endl;
        cout<<"MFHBELPOACKJGNID"<<endl;
        cout<<"JEKAFCNBGIDPLHOM"<<endl;
        cout<<"DOGPIHJMFNLECAKB"<<endl;
        cout<<"CILNKDGAHBMOPEFJ"<<endl;
        cout<<"IAFJOECGLDPBHMNK"<<endl;
        cout<<"GLBCDPMHEONKJIAF"<<endl;
        cout<<"PHNOBALKMJFIDCEG"<<endl;
        cout<<"KDEMJIFNCHGAOPBL"<<endl;
        cout<<"FPAHMJECNLBDKOGI"<<endl;
        cout<<"LNDKGFOIJEAHMBPC"<<endl;
        cout<<"BGCELKHPOFIMAJDN"<<endl;
        cout<<"OJMIANBDPKCGFLHE"<<endl;
        cout<<"NCJDHBAEKMOFIGLP"<<endl;
        cout<<"AKIGNODLBPJCEFMH"<<endl;
        cout<<"EBOFPMIJDGHLNKCA"<<endl;
        cout<<"HMPLCGKFIAENBDJO"<<endl;
        cout<<endl;
        cout<<"BMPNAJHCDKFIGELO"<<endl;
        cout<<"FDAKEIBLOMJGNCHP"<<endl;
        cout<<"ICEJFONGLHBPKDAM"<<endl;
        cout<<"LOGHPMDKENACFBIJ"<<endl;
        cout<<"EFLPOGMJBCIHDANK"<<endl;
        cout<<"CIKOBNAEFPGDMHJL"<<endl;
        cout<<"NGJDHCKIALEMBPOF"<<endl;
        cout<<"AHMBDLFPJONKCIEG"<<endl;
        cout<<"ONBLKFJDCIHAPGME"<<endl;
        cout<<"PEDFGAIMKJLBONCH"<<endl;
        cout<<"JAHICPONGDMELFKB"<<endl;
        cout<<"MKCGLHEBNFPOIJDA"<<endl;
        cout<<"HLNEMKPFIBCJAOGD"<<endl;
        cout<<"GBIMJDCHPAOLEKFN"<<endl;
        cout<<"DPOCNELAHGKFJMBI"<<endl;
        cout<<"KJFAIBGOMEDNHLPC"<<endl;
        cout<<endl;
    return 0;
}