数独求解问题（DFS+位运算优化）

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

.	2	7	3	8	.	.	1	.
.	1	.	.	.	6	7	3	5
.	.	.	.	.	.	.	2	9
3	.	5	6	9	2	.	8	.
.	.	.	.	.	.	.	.	.
.	6	.	1	7	4	5	.	3
6	4	.	.	.	.	.	.	.
9	5	1	8	.	.	.	7	.
.	8	.	.	6	5	3	4	.

Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input

The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

Output

For each test case, print a line representing the completed Sudoku puzzle.

Sample Input

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.

......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.

end

Sample Output

527389416819426735436751829375692184194538267268174593643217958951843672782965341

416837529982465371735129468571298643293746185864351297647913852359682714128574936

思路：DFS解这道题有点极限，需要优化的东西比较复杂，参考了网上的位运算优化，终于以700ms的解决了，如果不位运算优化很难去不超时的去解这道问题

附上原超时代码,此代码修改一下应该可以过F题，单纯的求数独的题

代码：

​

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

#include<cmath>

#include<set>

#include<stack>

#include<map>

#define MAX 10005

typedef long long ll;

using namespace std;

int cnt,flag;

int Map[10][10],vistrow[10][10],vistcol[10][10],vistkaui[10][10][10];

struct node

{

	int x,y;

}a[100];

void DFS(int x)

{

	if(x == cnt)

	{

		flag = 1;

		return;

	}

	int I = a[x].x;

	int J = a[x].y;

	for(int i = 1; i < 10; i++)

	{

		if(!vistrow[I][i] && !vistcol[J][i] && !vistkaui[I/3][J/3][i])

		{

			Map[I][J] = i;

			vistrow[I][i] = 1;

			vistcol[J][i] = 1;

			vistkaui[I/3][J/3][i] = 1;

			DFS(x+1);

			if(!flag)

			{

				Map[I][J] = '.';

				vistrow[I][i] = 0;

				vistcol[J][i] = 0;

				vistkaui[I/3][J/3][i] = 0;

			}

		}

	}

}

int main()

{

	int T;

	while(1)

	{

		memset(vistrow,0,sizeof(vistrow));

		memset(vistcol,0,sizeof(vistcol));

		memset(vistkaui,0,sizeof(vistkaui));

		cnt = 0;

		flag = 0;

		for(int i = 0; i < 9; i++)

		{

			for(int j = 0; j < 9; j++)

			{

			    scanf("%c",Map[i][j]);

				if(Map[i][j] == '.')

				{

					a[cnt].x = i;

					a[cnt++].y = j;

				}

				else

				{

					vistrow[i][Map[i][j]-'] = 1;

					vistcol[j][Map[i][j]] = 1;

					vistkaui[i/3][j/3][Map[i][j]] = 1;

				}

			}

		}

		DFS(0);

		for(int i = 0; i < 9; i++)

			for(int j = 0; j < 9; j++)

			{

				if(j == 8)

					printf("%c\n",Map[i][j]);

				else

					printf("%c",Map[i][j]);

			}

	}

	return 0;

}

​

AC代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

#include<cmath>

#include<set>

#include<stack>

#include<map>

#define MAX 10005

using namespace std;

char Map[10][10];

int vistrow[10],vistcol[10];

int grid[10],rec[512],num[512];

inline int g(int x,int y)

{

    return (x/3)*3+y/3;

}

inline void flip(int x,int y,int to)

{

    vistrow[x]^=1<<to;

    vistcol[y]^=1<<to;

    grid[g(x,y)]^=1<<to;

}

bool DFS(int x)

{

    if(x==0) return 1;

    int minn=10,xx,yy;

    for(int i=0;i<9;i++) {

        for(int j=0;j<9;j++)

		{

            if(Map[i][j]=='.')

			{

                int val=vistrow[i]&vistcol[j]&grid[g(i,j)];

                if(!val) return 0;

                if(rec[val]<minn) {

                    minn=rec[val],xx=i,yy=j;

                }

            }

        }

    }

    int val=vistrow[xx]&vistcol[yy]&grid[g(xx,yy)];

    for(;val;val-=val&-val) {

        int to=num[val&-val];

        Map[xx][yy]=to+'1';

        flip(xx,yy,to);

        if(DFS(x-1)) return 1;

        flip(xx,yy,to);

        Map[xx][yy]='.';

    }

    return 0;

}

int main() {

    for(int i=0;i<1<<9;i++) {

        for(int j=i;j;j-=j&-j)

            rec[i]++;

    }

    for(int i=0;i<9;i++) {

        num[1<<i]=i;

    }

    char s[100];

    while(~scanf("%s",s)&&s[0]!='e') {

        for(int i=0;i<9;i++)

		vistrow[i]=vistcol[i]=grid[i]=(1<<9)-1;

        int tot=0;

        for(int i=0;i<9;i++) {

            for(int j=0;j<9;j++) {

                Map[i][j]=s[i*9+j];

                if(Map[i][j]!='.') flip(i,j,Map[i][j]-'1');

                else ++tot;

            }

        }

        DFS(tot);

        for(int i=0;i<9;i++)

            for(int j=0;j<9;j++)

                printf("%c",Map[i][j]);

        printf("\n");

    }

    return 0;

}

数独求解问题（DFS+位运算优化）的相关教程结束。