P4205

2021CHD · 2025-01-11 14:39:38 · 题解

本题解没有使用搜索算法（包括 DLX）。

这是题目链接。

题目大意

有一个“智慧珠游戏”，有 12 种珠子和一个三角形的棋盘，如下图。

每种珠子都可以任意旋转和翻转，游戏目标是用珠子将棋盘填满。（每种珠子只能用一次）

给出一个填了一半的棋盘，保证棋盘合法，并且保证用珠子将棋盘填满的方案不超过一种，如果有解，复原出这个解，如果无解，输出 No solution。

解法

部分一

其实一开始没有想着做这道题的，只不过在翻洛谷的时候看到了这道题。由于我在小时候也玩过“智慧珠游戏”，所以我当时产生了一个疑问：“智慧珠游戏”合法的棋盘填充方案一共有几种呢？经过一番思考，我感觉可能很多，并且只得出答案是偶数的结论。（一个解沿棋盘斜边上的高线对称可以得到另一个解）

由于我很好奇，于是我想了一上午，得出了一个一定可以在我能接受的时间内求出答案的解法，以下是我的做法：（和本题我的做法强相关，不要跳过）

设计递推 f_{x,y,S,T}，表示当前填到 x 行 y 列的这个格子（这个格子是空的），剩余的珠子状态为 S，当前棋盘的状态为 T 的方案数。

关于“棋盘状态”，我是这样考虑的：在第 x 行上面以及在第 x 行中第 y 列左边的部分一定被填满了，第 x 行第 y 列这个格子一定是空的，所以不用记，剩下的部分有可能被填了，也有可能是空的，所以 T 表示剩下部分的棋盘按行从小到大、列从小到大的顺序排列依次是否被填上。

但是 T 最多会有多少位呢？

最坏情况就是下面这张图：（* 表示当前 DP 的位置，有颜色的格子表示已经填放的珠子，G 珠子未填放）

容易看出，T<2^{24}=16777216，于是可以用 int 类型存储，由于不知道实际状态数（我当时猜的可能是会过亿），所以我使用了 unordered_map 进行存储，转移时只枚举有用状态。（顺带一提，上面这个例子有唯一解）

那么如何转移呢？

由于每次转移（也就是填放珠子）的时候，这一格左边和上面的所有格子都被填满了，所以填的时候只能将一个状态的珠子最上最左的格子对准这个格子尝试填进去，我们称一个状态的珠子的这个位置为关键位置。

那每种珠子的旋转与翻转的情况就是自己动手打个表就可以完成的事情了，这里已经把表画好了，可以看一下：（箭头指向的就是这个状态的珠子的关键位置）

然后就可以打出表：

const int rr=12,//珠子的种类数
num[20]={2,3,3,3,4,4,4,4,4,4,4,4},//珠子非关键位置覆盖的格子数
lim[20]={4,2,8,1,4,8,4,8,8,1,4,8},//珠子的状态数
//下面是珠子的状态的非关键位置相对关键位置的 x 坐标（正方向向下）
vx[20][20][20]={{{0,1},{0,1},{1,1},{1,1}},{{0,0,0},{1,2,3}},{{0,0,1},{0,1,2},{1,1,1},{1,2,2},{1,1,1},{0,1,2},{0,0,1},{1,2,2}},{{0,1,1}},{{1,2,2,2},{0,0,1,2},{1,2,2,2},{0,0,1,2}},{{0,0,0,1},{0,0,0,1},{1,1,1,1},{1,1,1,1},{1,1,2,3},{1,1,2,3},{1,2,2,3},{1,2,2,3}},{{0,0,1,1},{0,1,2,2},{0,1,1,1},{0,1,2,2}},{{0,0,1,1},{0,1,1,1},{0,0,1,1},{0,1,1,1},{1,1,2,2},{1,1,2,2},{0,1,1,2},{0,1,1,2}},{{0,0,1,1},{0,1,1,1},{0,1,1,1},{0,0,1,1},{1,2,2,3},{1,1,2,3},{1,2,2,3},{1,1,2,3}},{{1,1,1,2}},{{1,1,2,2},{0,1,1,2},{1,1,2,2},{0,1,1,2}},{{0,0,0,1},{0,0,0,1},{1,1,1,1},{1,1,1,1},{0,1,2,3},{0,1,2,3},{1,2,3,3},{1,2,3,3}}},
//下面是珠子的状态的非关键位置相对关键位置的 y 坐标（正方向向右）
vy[20][20][20]={{{1,0},{1,1},{0,1},{-1,0}},{{1,2,3},{0,0,0}},{{1,2,0},{1,1,1},{-2,-1,0},{0,0,1},{0,1,2},{1,0,0},{1,2,2},{0,-1,0}},{{1,0,1}},{{0,0,1,2},{1,2,0,0},{0,-2,-1,0},{1,2,2,2}},{{1,2,3,1},{1,2,3,2},{-1,0,1,2},{-2,-1,0,1},{-1,0,0,0},{0,1,0,0},{0,-1,0,0},{0,0,1,0}},{{1,2,0,2},{1,1,0,1},{2,0,1,2},{1,0,0,1}},{{1,2,0,1},{1,0,1,2},{1,2,1,2},{1,-1,0,1},{0,1,0,1},{-1,0,-1,0},{1,0,1,0},{1,0,1,1}},{{1,2,2,3},{1,1,2,3},{1,-2,-1,0},{1,2,-1,0},{0,0,1,1},{0,1,1,1},{0,-1,0,-1},{-1,0,-1,-1}},{{-1,0,1,0}},{{0,1,1,2},{1,1,2,2},{-1,0,-2,-1},{1,-1,0,-1}},{{1,2,3,0},{1,2,3,3},{0,1,2,3},{-3,-2,-1,0},{1,1,1,1},{1,0,0,0},{0,0,-1,0},{0,0,0,1}}};

然后只需要枚举一种剩下的珠子然后尝试把它以各种状态填进去就可以转移了，不过要注意由于相对 y 坐标可能是负的，所以可能需要把整个棋盘向右移动几个单位存放。

这是我当时写出来的代码。

出人意料的是，有用状态只有八百多万种，我也只等了十秒它就运行完了。

答案也只有 32288 而不是当时预计的可能会超过 int 的表示范围。

部分二

那么此时，我发现了这道题其实就是求唯一解（或无解），而我已经写出了一个可以计算空棋盘方案数的做法，于是我想着：水一道紫题岂不是美事？于是计划先把我的代码修改成能输入一个棋盘并求出这个棋盘对应的方案数。

修改其实是不难的，只需要把输入的棋盘里已经填好的部分打上永久标记，然后在记录状态 T 的时候不记录这些格子就可以了。

不过要注意这次 DP 不一定从左上角的第一格开始了，因为这一格可能已经被填满了，所以要找到第一个没有被填的格子，从那个格子开始 DP。（可能还需要特判一下初始时棋盘已放满的情况）

然后发现这样跑得比较慢，于是考虑加一个剪枝：由于最小的珠子都要占据 3 个格子，所以如果一个状态形成了大小小于 3 的连通块，那就可以不对这个状态进行下一步的转移。在实际操作的时候，我只判断了完全在状态 T 表示范围内的部分的棋盘。

然后发现这样跑得不够快，就比如这两组数据：（显然无解）

由于棋盘左上半边是空的，所以状态数就比较大，所以考虑当棋盘左上半边都是空的时候将棋盘转置后再求解，就像这样：（涂灰的部分就是棋盘左上半边）

（顺带一提，上面这个例子有唯一解）

于是这一步改进就愉快地完成了，这里存放了这一份代码，并且我对这份代码的速度进行了一定量的检测，测试的结果存放在这里。

部分三

最后，就是要把这份代码改造成这道题的正解。

思路很简洁，只需要在转移的时候存储转移的来源，最后如果有解就从结束状态倒着推回去就可以了。

由于多写一遍转移会使得代码很长，所以可以不止记录转移的来源，还可以记录转移的方式，这样倒着推回去的时候就可以方便很多了。

到这里就做完了？

有这样一组毒瘤数据：（显然无解）

因为左上半边不是空的，所以棋盘不会转置，而左上角的 K 珠子对状态数的剪枝也是少的，右下角的 D 珠子对状态数的剪枝也是少的，最后导致了这种结果。

那还有什么办法呢？

其实到现在这道题还有一个特殊限制没用上：保证最多只有一组解。

那也就是说，如果一个状态被转移到了多次，就可以直接将这个状态舍去，因为它不可能转移到最后的答案处。当然这样做不能筛除所有存在多解的状态，但是可以筛除相当一部分，要修改的东西也很少。

这样，就可以跑过上面那一组毒瘤数据了。

这里放出 AC 记录以及完整的代码，其实这个代码也不难写，只要把表打好，剩下的部分很自然地就写出来了，甚至都没怎么调就过了。我对这个代码进行了上百组测试，结果放在这里，没有一组数据的运行时间或空间超过或逼近这题的限制。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int rr=12,num[20]={2,3,3,3,4,4,4,4,4,4,4,4},lim[20]={4,2,8,1,4,8,4,8,8,1,4,8},vx[20][20][20]={{{0,1},{0,1},{1,1},{1,1}},{{0,0,0},{1,2,3}},{{0,0,1},{0,1,2},{1,1,1},{1,2,2},{1,1,1},{0,1,2},{0,0,1},{1,2,2}},{{0,1,1}},{{1,2,2,2},{0,0,1,2},{1,2,2,2},{0,0,1,2}},{{0,0,0,1},{0,0,0,1},{1,1,1,1},{1,1,1,1},{1,1,2,3},{1,1,2,3},{1,2,2,3},{1,2,2,3}},{{0,0,1,1},{0,1,2,2},{0,1,1,1},{0,1,2,2}},{{0,0,1,1},{0,1,1,1},{0,0,1,1},{0,1,1,1},{1,1,2,2},{1,1,2,2},{0,1,1,2},{0,1,1,2}},{{0,0,1,1},{0,1,1,1},{0,1,1,1},{0,0,1,1},{1,2,2,3},{1,1,2,3},{1,2,2,3},{1,1,2,3}},{{1,1,1,2}},{{1,1,2,2},{0,1,1,2},{1,1,2,2},{0,1,1,2}},{{0,0,0,1},{0,0,0,1},{1,1,1,1},{1,1,1,1},{0,1,2,3},{0,1,2,3},{1,2,3,3},{1,2,3,3}}},vy[20][20][20]={{{1,0},{1,1},{0,1},{-1,0}},{{1,2,3},{0,0,0}},{{1,2,0},{1,1,1},{-2,-1,0},{0,0,1},{0,1,2},{1,0,0},{1,2,2},{0,-1,0}},{{1,0,1}},{{0,0,1,2},{1,2,0,0},{0,-2,-1,0},{1,2,2,2}},{{1,2,3,1},{1,2,3,2},{-1,0,1,2},{-2,-1,0,1},{-1,0,0,0},{0,1,0,0},{0,-1,0,0},{0,0,1,0}},{{1,2,0,2},{1,1,0,1},{2,0,1,2},{1,0,0,1}},{{1,2,0,1},{1,0,1,2},{1,2,1,2},{1,-1,0,1},{0,1,0,1},{-1,0,-1,0},{1,0,1,0},{1,0,1,1}},{{1,2,2,3},{1,1,2,3},{1,-2,-1,0},{1,2,-1,0},{0,0,1,1},{0,1,1,1},{0,-1,0,-1},{-1,0,-1,-1}},{{-1,0,1,0}},{{0,1,1,2},{1,1,2,2},{-1,0,-2,-1},{1,-1,0,-1}},{{1,2,3,0},{1,2,3,3},{0,1,2,3},{-3,-2,-1,0},{1,1,1,1},{1,0,0,0},{0,0,-1,0},{0,0,0,1}}};
unordered_map<int,long long> a[12][12][4100];
int i,j,k,l,m,n,o,p,r,t,u,q[20][20],z[20][20],s,ns,nnum,full=(1<<rr)-1,fl,zz;
long long v;
char in[20][20],tt;
void fill(int s1,int s2,int s3,int s4)
{
    long long i;
    int w1,w2,w3,w4,t1,t2;
    i=a[s1][s2][s3][s4];
    if(i<0)
    return;
    w1=i/100000000000000000;
    w2=i/1000000000000000%100;
    w3=i/100000000000%10000;
    w4=i/1000%100000000;
    t1=i/10%100;
    t2=i%10;
    in[w1][w2]=t1+'A';
    for(i=0;i<num[t1];i++)
    in[w1+vx[t1][t2][i]][w2+vy[t1][t2][i]]=t1+'A';
    fill(w1,w2,w3,w4);
}
main()
{
    for(i=1;i<=10;i++)
    scanf("%s\n",in[i]+1);
    for(i=0;i<=15;i++)
    for(j=0;j<=15;j++)
    q[i][j]=-1;
    for(i=1;i<=10;i++)
    for(j=1;j<=i;j++)
    q[i][j+3]=0;
    for(i=1;i<=10;i++)
    {
        for(j=1;j<=i;j++)
        if(i+j<=10&&in[i][j]!='.')
        break;
        if(j<=i)
        break;
    }
    if(i>10)
    {
        fl=1;
        for(i=1;i<=10;i++)
        for(j=1;j<=i;j++)
        if(i+j<=10)
        {
            tt=in[i][j];
            in[i][j]=in[11-j][11-i];
            in[11-j][11-i]=tt;
        }
    }
    for(i=1;i<=10;i++)
    for(j=1;j<=i;j++)
    if(in[i][j]!='.')
    {
        if(full&1<<in[i][j]-'A')
        full=full^1<<in[i][j]-'A';
        q[i][j+3]=2;
    }
    for(i=1;i<=10;i++)
    {
        for(j=1;j<=i;j++)
        if(in[i][j]=='.')
        break;
        if(j<=i)
        break;
    }
    if(i>10)
    {
        for(i=1;i<=10;i++)
        printf("%s\n",in[i]+1);
        return 0;
    }
    a[i][j][full][0]=-1;
    for(i=1;i<=10;i++)
    for(j=1;j<=i;j++)
    for(k=0;k<1<<rr;k++)
    for(auto pr:a[i][j][k])
    {
        s=pr.first;
        v=pr.second;
        if(v==-2)
        continue;
        zz=s;
        l=i;
        m=j;
        while(s)
        {
            m++;
            if(m>l)
            {
                l++;
                m=1;
            }
            if(q[l][m+3]<2)
            q[l][m+3]=s&1;
            s=s>>1;
        }
        s=zz;
        p=l;
        r=m;
        for(;l<=10;l++)
        {
            for(m++;m<=l;m++)
            {
                if(q[l][m+3]==1)
                q[l][m+3]=0;
                z[l][m]=0;
            }
            m=0;
        }
        q[i][j+3]=0;
        while(p>i||r>j)
        {
            if(q[p][r+3]==0)
            z[p][r]=(q[p-1][r+3]!=0)+(q[p+1][r+3]!=0)+(q[p][r-1+3]!=0)+(q[p][r+1+3]!=0);
            else
            z[p][r]=0;
            if(z[p][r]==4||z[p][r]+z[p+1][r]==6||z[p][r]+z[p][r+1]==6)
            break;
            r--;
            if(r==0)
            {
                p--;
                r=p;
            }
        }
        q[i][j+3]=1;
        if(p>i||r>j)
        continue;
        for(l=0;l<rr;l++)
        if(k&1<<l)
        for(n=0;n<lim[l];n++)
        {
            for(o=0;o<num[l];o++)
            if(q[i+vx[l][n][o]][j+3+vy[l][n][o]]!=0)
            break;
            if(o>=num[l])
            {
                for(o=0;o<num[l];o++)
                q[i+vx[l][n][o]][j+3+vy[l][n][o]]=1;
                p=i;
                r=j;
                while(q[p][r+3]>0)
                {
                    r++;
                    if(r>p)
                    {
                        p++;
                        r=1;
                    }
                }
                t=p;
                u=r;
                nnum=0;
                ns=0;
                while(nnum<24)
                {
                    u++;
                    if(u>t)
                    {
                        t++;
                        u=1;
                    }
                    if(t>10)
                    break;
                    if(q[t][u+3]<2)
                    ns=ns|q[t][u+3]<<nnum;
                    nnum++;
                }
                if(a[p][r][k^1<<l][ns]==0)
                a[p][r][k^1<<l][ns]=i*100000000000000000ll+j*1000000000000000ll+k*100000000000ll+s*1000ll+l*10ll+n;
                else
                a[p][r][k^1<<l][ns]=-2;
                for(o=0;o<num[l];o++)
                q[i+vx[l][n][o]][j+3+vy[l][n][o]]=0;
            }
        }
    }
    if(a[11][1][0][0]==0)
    {
        printf("No solution");
        return 0;
    }
    fill(11,1,0,0);
    if(fl==1)
    for(i=1;i<=10;i++)
    for(j=1;j<=i;j++)
    if(i+j<=10)
    {
        tt=in[i][j];
        in[i][j]=in[11-j][11-i];
        in[11-j][11-i]=tt;
    }
    for(i=1;i<=10;i++)
    printf("%s\n",in[i]+1);
}