HDOJ-1031 N皇后问题

题目

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。

输入给定的N（N≤10），输出有多少种合法的放置方法。

思路

在N*N棋盘中摆N个皇后，意味着每行有一个皇后，每列有一个皇后，每条主对角线有一个皇后，每条副对角线有一个皇后；换言之，每个皇后控制着一行、一列。一条主对角线、一条副对角线。因此，以每行对应一次循环，用a,b,c三个数组存储各主对角线、副对角线、列的占用情况。点(x,y)位于第x行，第y列，第y-x+n条主对角线(1-n<=y-x<=n-1，处理使数组从1开始)，第x+y条副对角线(2<=x+y<=2n)。

代码 

#include<iostream>
#include<cstring>
using namespace std;
int n,so;
bool a[25],b[15],c[25];//a代表主对角线，b代表列，c代表副对角线
void dfs(int i)
{
	if(i>n) {so++;return;}
	for(int j=1;j<=n;j++)//每列
	{
		if(a[j-i+n]||b[j]||c[i+j]) continue;//不可用，则跳过
		a[j-i+n]=true;b[j]=true;c[i+j]=true;//标记控制区域
		dfs(i+1);//查找下一行可用点
		a[j-i+n]=false;b[j]=false;c[i+j]=false;//取消标记
	}
}
int main()
{
	int ans[15]={0};
	for(n=1;n<=10;n++)
	{
		memset(a,false,sizeof(a));
		memset(b,false,sizeof(b));
		memset(c,false,sizeof(c));	
		so=0;dfs(1);ans[n]=so;
	}
	while(cin>>n&&n)
		cout<<ans[n]<<endl;
	return 0;
}

HDOJ-1426 Sudoku Killer

题目

输入一批不完整的数独地图（未知数值用’?’表示），输出它们的解。（对于每组测试数据保证它有且只有一个解）

思路

仔细分析，发现与上一题有类似之处：小格中的每一个数字x，都可以看做是所在行、列、九宫格的数字x的控制数字——这个数字控制着所在行、列、九宫格，在其控制区域内不能出现另一个x。用结构体存储空格的位置，i（0~8）代表小格行标，j（0~8）代表小格列标，则i/3代表九宫格行标，j/3代表九宫格列标。以每个空格对应一层递归，用a,b,c三个数组存储各行、列、九宫格的可用性，数组最后一维代表9个可能的数字，其他维度代表序号。

由题意，每个空格的值不全为9。当从最后一个空格（已填写）出发进行下一层递归时，触发条件空格溢出，记录填写完成，函数返回到倒数第二个空格的下一次循环。填写完成条件满足，循环变量的上一个值填写到真正的数独空格中，函数再返回到倒数第三个空格……对于值为9的情况，在循环之外另行处理。

用两层循环读入数独地图存到字符数组中，读入的字符若是数字，标记控制区域；若是空格，记录其位置坐标。

代码 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char map[9][9];
struct space
	{int i;int j;}s[81];
bool a[9][12],b[9][12],c[3][3][12];//a代表行，b代表列，c代表九宫格
int sn,snm;//sn=Space Number空格编号,snm=空格编号最大值
int done;//done为1代表所有空格填写完成
void dfs(int sn)
{
	if(sn>snm) {done=1;return;}
	int v;
	for(v=1;v<=9;v++)//每个可能值
	{
		if(done==1) {map[s[sn].i][s[sn].j]='0'+v-1;break;}
		if(a[s[sn].i][v]||b[s[sn].j][v]||c[s[sn].i/3][s[sn].j/3][v]) continue;//不可用，则跳过
		a[s[sn].i][v]=true;b[s[sn].j][v]=true;c[s[sn].i/3][s[sn].j/3][v]=true;//标记控制区域
		dfs(sn+1);//填写下一个空格
		a[s[sn].i][v]=false;b[s[sn].j][v]=false;c[s[sn].i/3][s[sn].j/3][v]=false;//取消标记
	}
	if(v==10&&done==1) map[s[sn].i][s[sn].j]='0'+v-1;
}
int main()
{
	char ch;int f=1;
	do{
		int i,j;
		memset(a,false,sizeof(a));
		memset(b,false,sizeof(b));
		memset(c,false,sizeof(c));
		done=0;sn=0;
		for(i=0;i<9;i++)
		{
			for(j=0;j<9;j++)
			{
				cin>>ch;
				if(ch!='?') 
					{a[i][ch-'0']=true;b[j][ch-'0']=true;c[i/3][j/3][ch-'0']=true;}
				else {s[sn].i=i;s[sn].j=j;sn++;}
				map[i][j]=ch;
			}						
		}
		snm=sn-1;
		dfs(0);
		if(f==0) cout<<endl; else f=0;
		//第二组数据开始，输出前加一空行
		for(i=0;i<9;i++)
		{
			for(j=0;j<8;j++)
				cout<<map[i][j]<<" ";
			cout<<map[i][j]<<endl;			
		}	
	}while(scanf("%c",&ch)!=EOF);
	return 0;
}