POJ2676 Sudoku、POJ2918 Tudoku（數獨（一））

POJ2676 Sudoku

題目連結

Description

Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task. 

Input

The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.

Output

For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
           

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
           

給定一個由3*3的方塊分割而成的9*9的格子。其中一些格子中填有1~9的數字，其餘格子則是空白的。請在空白的格子中填入1~9的數字，使得在每行、每列和每個3*3的方塊中，1~9的每個數字都恰好出現一次，如果解不唯一，輸出任意一組即可。

考慮從左上角的空白格子開始填數字的深度優先搜尋。所填的數字應該是所在行、列和方塊中都沒有填過的數字。

一開始利用函數bool isok(int x,int y,char num)計算數字num是否在可填在第(x,y)格中 ，結果逾時了

逾時代碼：

//CSDN部落格：https://blog.csdn.net/qq_40889820
#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<string>
#include<cstring>
#include<iomanip>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<map>
#define mem(a,b) memset(a,b,sizeof(a))
#define random(a,b) (rand()%(b-a+1)+a)
#define e 2.71828182
#define Pi 3.141592654
using namespace std;
char table[10][10];
bool isok(int x,int y,char num)//數字num是否在可填在第(x,y)格中 
{
	for(int j=1;j<=9;j++)//行
		if(table[x][j]==num) return false; 
	for(int i=1;i<=9;i++)//列 
		if(table[i][y]==num) return false;
	for(int i=(x-1)/3*3+1;i<(x-1)/3*3+1+3;i++)//3*3的方塊 
		for(int j=(y-1)/3*3+1;j<(y-1)/3*3+1+3;j++)
			if(table[i][j]==num) return false;	
	return true;
}
bool flag=false;
void dfs(int x,int y)//填第(x,y)格 
{
	if(flag) return;
	if(y>9) y=1,x+=1;
	if(x>9)
	{
		for(int i=1;i<=9;i++)
		cout<<table[i]+1<<endl;
		flag=true;
		return;
	}
	if(table[x][y]!='0') dfs(x,y+1);
	else if(table[x][y]=='0') 
	{
		for(char i='1';i<='9';i++)
		{
			if(isok(x,y,i))
			{
				table[x][y]=i;
				dfs(x,y+1);
				table[x][y]='0';//回溯 
			}
			//if(i=='9') return; 
		}
	}
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		for(int i=1;i<=9;i++)
		cin>>table[i]+1;
		
		dfs(1,1);
		cout<<endl;
		flag=false;
	}
}
           

後來改為用三個數組儲存數字的重複情況，然後就神奇的過了，也算是空間換時間了吧

row[i][j]為1代表第i行數字j已經出現過 ，col[i][j]為1代表第i列數字j已經出現過，grid[i][j]為1代表第i個方塊數字j已經出現過（從上往下從左往右數）

AC代碼：

//CSDN部落格：https://blog.csdn.net/qq_40889820
#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<string>
#include<cstring>
#include<iomanip>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<map>
#define mem(a,b) memset(a,b,sizeof(a))
#define random(a,b) (rand()%(b-a+1)+a)
#define e 2.71828182
#define Pi 3.141592654
using namespace std;
char table[10][10];
int row[10][10],col[10][10],grid[10][10];
bool flag=false;
void dfs(int x,int y)//填第(x,y)格 
{
	if(flag) return;//已找到一種解法 
	if(y>9) y=1,x+=1;
	if(x>9)
	{
		for(int i=1;i<=9;i++)
		cout<<table[i]+1<<endl;
		flag=true;
		return;
	}
	if(table[x][y]!='0') dfs(x,y+1);
	else if(table[x][y]=='0') 
	{
		int ord=(x-1)/3*3+(y-1)/3+1;//第幾個方塊 
		for(int i=1;i<=9;i++)
		{
			if(!row[x][i]&&!col[y][i]&&!grid[ord][i])
			{
				table[x][y]=i+'0';
				row[x][i]=1;col[y][i]=1;grid[ord][i]=1;
				dfs(x,y+1);
				//回溯 
				table[x][y]='0';
				row[x][i]=0;col[y][i]=0;grid[ord][i]=0;
			}
		}
	}
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		mem(row,0);mem(col,0);mem(grid,0);
		for(int i=1;i<=9;i++)
		{
			cin>>table[i]+1;
			for(int j=1;j<=9;j++)
			{
				row[i][table[i][j]-'0']=1;
				col[j][table[i][j]-'0']=1;
				int ord=(i-1)/3*3+(j-1)/3+1;
				grid[ord][table[i][j]-'0']=1;
			}
		}
		
		dfs(1,1);
		cout<<endl;
		flag=false;
	}
}
           

POJ2918

題目連結

和POJ2676大緻相同，輸出結果有着細微的差別

for(int k=1;k<=n;k++)
{
	mem(row,0);mem(col,0);mem(grid,0);
	for(int i=1;i<=9;i++)
	{
		cin>>table[i]+1;
		for(int j=1;j<=9;j++)
		{
			row[i][table[i][j]-'0']=1;
			col[j][table[i][j]-'0']=1;
			int ord=(i-1)/3*3+(j-1)/3+1;
			grid[ord][table[i][j]-'0']=1;
		}
	}
		
	cout<<"Scenario #"<<k<<":\n";
	dfs(1,1);
	cout<<endl;
	flag=false;
}