Sudoku written for once and for all

166. Sudoku

Obviously, you need DFS, For each unfilled space , We should exclude the numbers that have appeared in the same column and the same nine palaces . If there is no accident without optimization, it will T fly ︿(￣︶￣)︿.

Consider pruning ：

1. Optimize search order
2. Eliminate redundant information
3. Feasibility pruning （ It is impossible to follow the current branch ）
4. Optimal pruning （ According to the current branch, the optimal solution is worse than the current solution ）
5. Memory search

Here we mainly consider optimizing the search order . This is actually the same as the simple perception when we do Sudoku , Start with a few optional spaces . So every time we search, we will judge which grid has the smallest number of choices （ All binary numbers that may be used can be preprocessed 1 The number of , Time consuming direct call ）.

Record the number of options for each grid , Can be compressed with binary state , Opening nine digits means nine numbers . For convenience , We put 1~9 mapping 0 ~8. Open three arrays $row[N],col[N],cell[N/3][N/3]$ Record each line separately 、 Each column 、 What numbers can't be filled in each Jiugong grid . For position at $(x,y)$ Number of numbers , use row[x] & col[y] & cell[x/3][y/3] You can find out which numbers can be filled in this blank , Then search these numbers honestly 233, It can be used lowbit Get binary, the following is 1 Every one of them , Convert it into decimal numbers （1 The number of digits corresponding to the position of , It can be processed in advance ）. Search for each number and change it row.col.cell The state of , Recover when you go back .

#include<bits/stdc++.h> 
using namespace std;
const int N=9;
string str;
int mp[1<<N],nums[1<<N],row[N],col[N],cell[N][N];

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

int get(int x,int y)
{
    
	return row[x]&col[y]&cell[x/3][y/3];// Find out what numbers may be filled in this position  
}

void init()// initialization ： All digits can be filled in  
{
    
	for(int i=0;i<N;i++) 
		row[i]=col[i]=(1<<N)-1;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cell[i][j]=(1<<N)-1;
}

bool dfs(int cnt)
{
    
	if(cnt==0) return true;// All the figures to be filled in have been filled in  
	int minn=10,x,y;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		{
    
			if(str[i*9+j]=='.')
			{
    
				int temp=nums[get(i,j)];
				if(temp<minn)
				{
    
					minn=temp;
					x=i,y=j;
				}
			}
		}// Find the smallest number set in all the remaining cells to be filled , It's a pruning process  
	for(int i=get(x,y);i;i-=lowbit(i))// Enumerate all possible numbers in this field  
	{
    
		int t=mp[lowbit(i)];
		row[x]-=(1<<t);
		col[y]-=(1<<t);
		cell[x/3][y/3]-=(1<<t);
		str[x*9+y]='1'+t;
		if(dfs(cnt-1)) return true;
		row[x]+=(1<<t);
		col[y]+=(1<<t);
		cell[x/3][y/3]+=(1<<t);
		str[x*9+y]='.';// Restore  
	}
	return false;
}


int main()
{
    
	for(int i=0;i<N;i++) mp[1<<i]=i;// Save binary in advance 1 Where it is  
	for(int i=1;i<(1<<N);i++)
		for(int j=i;j;j-=lowbit(j)) nums[i]++;
		// There are several binary numbers stored in advance that may be enumerated later 1 
	while(cin>>str&&str[0]!='e')
	{
    
		init();
		int cnt=0;
		for(int i=0,k=0;i<9;i++)
			for(int j=0;j<9;j++,k++)
			{
    
				if(str[k]!='.')
				{
    
					int t=str[k]-'1';//1~9 Mapping to 0~8 
					row[i]-=(1<<t);
					col[j]-=(1<<t);
					cell[i/3][j/3]-=(1<<t);
				}// This one digit number is given , Put it in the corresponding position  
				else cnt++;// Figures to be filled in +1 
			}
		dfs(cnt);
		cout<<str<<endl;
	}
	return 0;
}