2 条题解

  • 1
    @ 2021-8-7 21:05:12

    C++ :

    #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=16;
int state[N][N];//用二进制数标记每一个位置的需要填字母的情况，即每个空格所有备选数字
char str[N][N+1];
int ones[1<<N],map[1<<N];//用于二进制中的识别问题
//ones数组存储每一个int值二进制中包含的1的数量
//map存储1、2、8……中二进制中1位于的位置
char bstr[N*N+1][N][N+1];//每一种空格数对应一个16*16字符宫格
int bstate[N*N+1][N][N],bstate2[N*N+1][N][N];//状态备份，后面会用到
//每一种空格数对应一种标记状态
inline int lowbit(int k)
{
	return k& -k;
}
void draw(int x,int y,int c)//填数
{
	str[x][y]='A'+c;
	for(int i=0;i<N;i++)
	{//对（x，y）向对应的行、列进行标记
		state[x][i]&=~(1<<c);//意思就是指将第c位与0，假如该位为1则置为0表示已填充
		state[i][y]&=~(1<<c);
	}//对（x，y）的十六宫格进行标记
	int sx=x/4*4,sy=y/4*4;//进行处理十六宫格
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			state[sx+i][sy+j]&=~(1<<c);
	state[x][y]=1<<c;//将（x，y）该位置标记为只能填该字母
}
bool dfs(int cnt)
{
	if(!cnt)return true;//如果当前空格数为0表示所有的空格都填上了
    int kcnt=cnt;//对当前所有的状态都进行保存，在下面剪枝的过程中若判断出当前状况非法，则还原会当前步骤的初始状态，然后回溯
    memcpy(bstate[kcnt],state,sizeof state);
    memcpy(bstr[kcnt],str,sizeof str);//备份两个数组


    //对于每个空格，如果一个字母都不能填，则无解；如果只能填一个字母，则直接填
    //开始枚举
    for(int i=0;i<N;i++)
    	for(int j=0;j<N;j++)
    		if(str[i][j]=='-')
    		{
    			if(!state[i][j])//如果不能填任何一个数字
    			{
    				memcpy(state,bstate[kcnt],sizeof state);
    				memcpy(str,bstr[kcnt],sizeof str);//恢复现场
    				return false;
    			}
    			if(ones[state[i][j]]==1)//如果只有一个格子可以填
    			{
    				draw(i,j,map[state[i][j]]);//填入该个位置上的“1”
    				cnt--;
    			}
    		}

    //对每一行进行判断，如果某个字母不能出现在任何一个位置，则无解；
    //如果某个字母，只能填在一个位置上，则直接填
	for(int i=0;i<N;i++)
	{
        int sor=0,sand=(1<<N)-1;
        int drawn=0;
        //每一行初始化sor表示当前行每一个位置能填的字母的并集，如果某个字母，只能填在一个位置上，则直接填
        //sand表示的是该行中所有的这样的字母：该字母是具有放到某一位置的唯一性
	    //drawn表示的是该行所有已经填上了的字母
	    for(int j=0;j<N;j++)
	    {
	    	int s=state[i][j];
	    	sand&=~(sor&s);//当前位置的要填情况与前面所有的要填的所有情况的重复情况，都在sand中标0去除掉
	    	//sor&s中的1表示某些位置在前面可以填，后面也可以填，表现出非唯一性，我们需要找到唯一的解，便把这些1通过取反去掉
	    	sor|=s;//sor表示前j个位置所有的可能的要填的情况
	        if(str[i][j]!='-')
	        	drawn|=state[i][j];//drawn标记所有的已经填过了的情况
	    }

	    if(sor!=(1<<N)-1)
	    {//由于sor标记的是当前行所有的可能填的字母，如果合法的化必定是有16种字母填入到该行中的
            //因为对于每一行我们做的是并集，假设合法，每一个位置的1都会存在（表示都能填），但如果某位不能填，则必出现0，出现0后就代表不合法了	    //若不是的话就表示非法，进行剪枝
         memcpy(state,bstate[kcnt],sizeof state);
         memcpy(str,bstr[kcnt],sizeof str);
         return false;
	    }
	    for(int j=sand;j;j-=lowbit(j))
	    {//由于sand中存储的是该行所有的确定性的字母
	     //我们接下来把这些确定性的字母且是在空格要填的确定性的字母填入到空格中
	    	int t=lowbit(j);
	    	if(!(drawn&t))//枚举所有唯一性的解，若没填过，就可以填进去了
	    	{//当该行中所有已经填入的字母中不包括当前确定性的字母
               for(int k=0;k<N;k++)
               	if(state[i][k]&t)
               	{//当i行k列正好需要匹配的是当前字母时
               		draw(i,k,map[t]);
                    cnt--;
                    break;
               	}
	    	}
	    }
	}


	//下面对列进行剪枝优化，过程与行的相同
	for(int i=0;i<N;i++)
	{
		int sor=0,sand=(1<<N)-1;
		int drawn=0;
		for(int j=0;j<N;j++)
		{
			int s=state[j][i];
			sand&=~(sor&s);
			sor|=s;

			if(str[j][i]!='-')
				drawn|=state[j][i];
		}
		if(sor!=(1<<N)-1)
		{
			memcpy(state,bstate[kcnt],sizeof state);
			memcpy(str,bstr[kcnt],sizeof str);
			return false;
		}
		for(int j=sand;j;j-=lowbit(j))
		{
			int t=lowbit(j);
			if(!(drawn&t))
			{
				for(int k=0;k<N;k++)
					if(state[k][i]&t)
					{
						draw(k,i,map[t]);
						cnt--;
						break;
					}
			}
		}
	}



	//下面对每一个16宫格进行剪枝，原理与上面相同
	for(int i=0;i<N;i++)
	{//i遍历的16个宫格
		int sor=0,sand=(1<<N)-1;
		int drawn=0;
		for(int j=0;j<N;j++)
		{//j遍历的时宫格里面的16个位置
            int sx=i/4*4,dx=j/4;
            int sy=i%4*4,dy=j%4;
            //其中（sx，sy）时每一个宫格的左上角，dx、dy时用来遍历这个宫格的所有位置

            int s=state[sx+dx][sy+dy];
            sand&=~(sor&s);
            sor|=s;

            if(str[sx+dx][sy+dy]!='-')
            	drawn|=state[sx+dx][sy+dy];
		}

		if(sor!=(1<<N)-1)
		{
			memcpy(state,bstate[kcnt],sizeof state);
			memcpy(str,bstr[kcnt],sizeof str);
			return false;
		}
		for(int j=sand;j;j-=lowbit(j))
		{
			int t=lowbit(j);
			if(!(drawn&t))
			{
				for(int k=0;k<N;k++)
				{
				int sx=i/4*4,dx=k/4;
				int sy=i%4*4,dy=k%4;
				if(state[sx+dx][sy+dy]&t)
				{
					draw(sx+dx,sy+dy,map[t]);
					cnt--;
					break;
				}
				}

			}
		}
	}


    if(!cnt)return true;

    //每次选择空格时，选择备选方案最少的格子来填
    int x,y,s=999;//s记录最小值
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        if(str[i][j]=='-'&&ones[state[i][j]]<s)
        {
        	x=i,y=j;
        	s=ones[state[i][j]];
        }
        //求出来x,y这个格子方案最少
    memcpy(bstate2[kcnt],state,sizeof state);//存储状态

    for(int i=state[x][y];i;i-=lowbit(i))//枚举这个格子
    {
    	memcpy(state,bstate2[kcnt],sizeof state);//恢复格子
    	draw(x,y,map[lowbit(i)]);//填入最后一个1
    	if(dfs(cnt-1))return true;//枚举下一代
    }
    memcpy(state,bstate[kcnt],sizeof state);//若枚举失败了恢复现场
    memcpy(str,bstr[kcnt],sizeof str);
    return false;
}
int main()
{
	//初始化两个二进制计算的数组
    for(int i=0;i<N;i++)
    	map[1<<i]=i;
    for(int i=1;i<1<<N;i++)
    {
    	for(int j=i;j;j-=lowbit(j))
    		ones[i]++;
    }
    while(cin>>str[0])
    {
    	for(int i=1;i<N;i++)
    		cin>>str[i];
    	for(int i=0;i<N;i++)
    		for(int j=0;j<N;j++)
    			state[i][j]=(1<<N)-1;//初始化每一个标记位，表示每个位置可以填任何数
        int cnt=0;
        for(int i=0;i<N;i++)
        	for(int j=0;j<N;j++)
        		if(str[i][j]!='-')
        		{
                   draw(i,j,str[i][j]-'A');
        		}
                 else cnt++;
       dfs(cnt);

       for(int i=0;i<N;i++)
       	cout<<str[i]<<endl;
       cout<<endl;
    }
    return 0;
}
    • -1
      @ 2022-10-18 17:36:11 
      #include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=16;

int state[N][N];

char str[N][N+1];

int ones[1<<N],map[1<<N];

char bstr[N*N+1][N][N+1];

int bstate[N*N+1][N][N],bstate2[N*N+1][N][N];

inline int lowbit(int k)
{
	return k& -k;
}

void draw(int x,int y,int c)//填数
{
	str[x][y]='A'+c;
	for(int i=0;i<N;i++)
	{
		state[x][i]&=~(1<<c);
		state[i][y]&=~(1<<c);
	}

	int sx=x/4*4,sy=y/4*4;

	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			state[sx+i][sy+j]&=~(1<<c);

	state[x][y]=1<<c;
}

bool dfs(int cnt)
{
	if(!cnt)return true;

    int kcnt=cnt;

    memcpy(bstate[kcnt],state,sizeof state);
    memcpy(bstr[kcnt],str,sizeof str);

    for(int i=0;i<N;i++)
    	for(int j=0;j<N;j++)
    		if(str[i][j]=='-')
    		{
    			if(!state[i][j])
    			{
    				memcpy(state,bstate[kcnt],sizeof state);
    				memcpy(str,bstr[kcnt],sizeof str);

    				return false;
    			}
    			if(ones[state[i][j]]==1)
    			{
    				draw(i,j,map[state[i][j]]);

    				cnt--;
    			}
    		}

	for(int i=0;i<N;i++)
	{
        int sor=0,sand=(1<<N)-1;
        int drawn=0;
   
	    for(int j=0;j<N;j++)
	    {
	    	int s=state[i][j];

	    	sand&=~(sor&s);
	  
	    	sor|=s;

	        if(str[i][j]!='-')
	        	drawn|=state[i][j];
	    }

	    if(sor!=(1<<N)-1)
	    {
         memcpy(state,bstate[kcnt],sizeof state);
         memcpy(str,bstr[kcnt],sizeof str);

         return false;
	    }
	    for(int j=sand;j;j-=lowbit(j))
	    {
	    	int t=lowbit(j);

	    	if(!(drawn&t))
	    	{
               for(int k=0;k<N;k++)
                   if(state[i][k]&t)
               	   {
               		    draw(i,k,map[t]);

                        cnt--;

                        break;
               	   }
	    	}
	    }
	}

	for(int i=0;i<N;i++)
	{
		int sor=0,sand=(1<<N)-1;

		int drawn=0;

		for(int j=0;j<N;j++)
		{
			int s=state[j][i];

			sand&=~(sor&s);

			sor|=s;

			if(str[j][i]!='-')
				drawn|=state[j][i];
		}
		if(sor!=(1<<N)-1)
		{
			memcpy(state,bstate[kcnt],sizeof state);
			memcpy(str,bstr[kcnt],sizeof str);
			return false;
		}
		for(int j=sand;j;j-=lowbit(j))
		{
			int t=lowbit(j);
			if(!(drawn&t))
			{
				for(int k=0;k<N;k++)
					if(state[k][i]&t)
					{
						draw(k,i,map[t]);
						cnt--;
						break;
					}
			}
		}
	}

	for(int i=0;i<N;i++)
	{
		int sor=0,sand=(1<<N)-1;
		int drawn=0;

		for(int j=0;j<N;j++)
		{
            int sx=i/4*4,dx=j/4;
            int sy=i%4*4,dy=j%4;
   
            int s=state[sx+dx][sy+dy];

            sand&=~(sor&s);

            sor|=s;

            if(str[sx+dx][sy+dy]!='-')
            	drawn|=state[sx+dx][sy+dy];
		}

		if(sor!=(1<<N)-1)
		{
			memcpy(state,bstate[kcnt],sizeof state);
			memcpy(str,bstr[kcnt],sizeof str);

			return false;
		}
		for(int j=sand;j;j-=lowbit(j))
		{
			int t=lowbit(j);

			if(!(drawn&t))
			{
				for(int k=0;k<N;k++)
				{
				    int sx=i/4*4,dx=k/4;
				    int sy=i%4*4,dy=k%4;

				    if(state[sx+dx][sy+dy]&t)
				    {
					    draw(sx+dx,sy+dy,map[t]);

					    cnt--;

					    break;
				    }
				}

			}
		}
	}


    if(!cnt)return true;

    int x,y,s=999;

    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(str[i][j]=='-'&&ones[state[i][j]]<s)
            {
        	    x=i,y=j;
        	    s=ones[state[i][j]];
            }
  
    memcpy(bstate2[kcnt],state,sizeof state);

    for(int i=state[x][y];i;i-=lowbit(i))
    {
    	memcpy(state,bstate2[kcnt],sizeof state);

    	draw(x,y,map[lowbit(i)]);

    	if(dfs(cnt-1))return true;
    }
    memcpy(state,bstate[kcnt],sizeof state);
    memcpy(str,bstr[kcnt],sizeof str);
    return false;
}

int main()
{
    for(int i=0;i<N;i++)
    	map[1<<i]=i;
    for(int i=1;i<1<<N;i++)
    {
    	for(int j=i;j;j-=lowbit(j))
    		ones[i]++;
    }
    while(cin>>str[0])
    {
    	for(int i=1;i<N;i++)
    		cin>>str[i];
    	for(int i=0;i<N;i++)
    		for(int j=0;j<N;j++)
    			state[i][j]=(1<<N)-1;
        int cnt=0;
        for(int i=0;i<N;i++)
        	for(int j=0;j<N;j++)
        		if(str[i][j]!='-')
        		{
                   draw(i,j,str[i][j]-'A');
        		}
                 else cnt++;
       dfs(cnt);

       for(int i=0;i<N;i++)
       	cout<<str[i]<<endl;
       cout<<endl;
    }
    return 0;
}
      • 1

      数独2

      信息

      ID
      80
      时间
      1000ms
      内存
      128MiB
      难度
      1
      标签
      递交数
      50
      已通过
      44
      上传者
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. Theme
      3. Worker 0 in 21ms
      4. Powered by Hydro v3.15.13 Community