回溯法求解组合数独

2023-12-27 14:09:51

用回溯法求解组合数独

1.问题描述

回溯法求解组合数独

如上图，在每个9 * 9的红色方框中，一些填入了0~9的数字，一些是空白。

在空白处填入0~9的数字，使得：

  • 每个蓝色的九空格不能有重复数字
  • 每一行不能有重复数字
  • 每一列不能有重复数字

2.思路及实现

整个问题可以分为五个子问题，即五个9*9的数独求解，中间那个数独的求解依赖于其余四个数独的求解结果。

思路就很明确了，即先求解周围四个数独，拼接成中间数独，再求解。

2.1单个数独求解

回溯法求解组合数独

数独每个空白格的数字填入，受到其所在的行、列和九宫格的约束，如果每次填入一个空白格的时候再计算，存在大量的重复计算，时间复杂度极高，因此可以把中间值存储起来，再进行查表。求解单个数独的步骤可以分为：

  1. 初始化中间值
  2. 填入一个空白格
  3. 更新中间值
  4. 是否为最后一个空白格
    1. 否执行2
    2. 是结束
  5. 还原中间值
2.1.1数独的存储

数独的存储使用一个9*9的整形数组，为方便中间值计算，以 2 n 2^n 2n进行存储。0表示还未填入数字。
0 − > 2 0 = 0 ( 0000000000 ) 1 − > 2 1 = 2 ( 0000000010 ) 2 − > 2 2 = 4 ( 0000000100 ) 3 − > 2 3 = 8 ( 0000001000 ) 4 − > 2 4 = 16 ( 0000010000 ) 5 − > 2 5 = 32 ( 0000100000 ) 6 − > 2 6 = 64 ( 0001000000 ) 7 − > 2 7 = 128 ( 0010000000 ) 8 − > 2 8 = 256 ( 0100000000 ) 9 − > 2 9 = 512 ( 1000000000 ) \\ 0 -> 2^{0} = 0(0000000000) \\ 1 -> 2^{1} = 2(0000000010)\\ 2 -> 2^{2} = 4(0000000100)\\ 3 -> 2^{3} = 8(0000001000)\\ 4 -> 2^{4} = 16(0000010000)\\ 5 -> 2^{5} = 32(0000100000)\\ 6 -> 2^{6} = 64(0001000000)\\ 7 -> 2^{7} = 128(0010000000)\\ 8 -> 2^{8} = 256(0100000000)\\ 9 -> 2^{9} = 512(1000000000)\\ 0−>20=0(0000000000)1−>21=2(0000000010)2−>22=4(0000000100)3−>23=8(0000001000)4−>24=16(0000010000)5−>25=32(0000100000)6−>26=64(0001000000)7−>27=128(0010000000)8−>28=256(0100000000)9−>29=512(1000000000)

设置转换数组， n u m [ n ] = 2 n num[n] = 2^n num[n]=2n 。

int num[] = {0, 2, 4, 8, 16, 32, 64, 128, 256, 512};

初始化数独数组：

int a[5][9][9] ={
		{
			{num[9], num[0], num[0], num[0], num[5], num[0], num[0], num[0], num[7]},
			{num[0], num[0], num[0], num[9], num[0], num[7], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[6], num[0], num[4], num[0], num[0], num[0]},
			{num[0], num[1], num[3], num[0], num[2], num[0], num[8], num[9], num[0]},
			{num[2], num[0], num[0], num[7], num[0], num[1], num[0], num[0], num[3]},
			{num[0], num[9], num[6], num[0], num[4], num[0], num[7], num[2], num[0]},
			{num[0], num[0], num[0], num[3], num[0], num[5], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[9], num[0], num[0], num[0]},
			{num[3], num[0], num[0], num[0], num[7], num[0], num[0], num[0], num[6]}
		},
		{
			{num[2], num[0], num[0], num[0], num[9], num[0], num[0], num[0], num[6]},
			{num[0], num[0], num[0], num[6], num[0], num[3], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[1], num[0], num[5], num[0], num[0], num[0]},
			{num[0], num[9], num[8], num[0], num[6], num[0], num[1], num[5], num[0]},
			{num[6], num[0], num[0], num[5], num[0], num[9], num[0], num[0], num[8]},
			{num[0], num[7], num[2], num[0], num[8], num[0], num[6], num[3], num[0]},
			{num[0], num[0], num[0], num[7], num[0], num[4], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[9], num[0], num[8], num[0], num[0], num[0]},
			{num[9], num[0], num[0], num[0], num[5], num[0], num[0], num[0], num[4]}
		},
		{
			{num[9], num[0], num[0], num[0], num[3], num[0], num[0], num[0], num[7]},
			{num[0], num[0], num[0], num[5], num[0], num[9], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[7], num[0], num[4], num[0], num[0], num[0]},
			{num[0], num[1], num[3], num[0], num[2], num[0], num[7], num[5], num[0]},
			{num[5], num[0], num[0], num[8], num[0], num[7], num[0], num[0], num[2]},
			{num[0], num[7], num[4], num[0], num[1], num[0], num[9], num[8], num[0]},
			{num[0], num[0], num[0], num[6], num[0], num[8], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[1], num[0], num[0], num[0]},
			{num[6], num[0], num[0], num[0], num[7], num[0], num[0], num[0], num[9]}
		},
		{
			{num[4], num[0], num[0], num[0], num[9], num[0], num[0], num[0], num[3]},
			{num[0], num[0], num[0], num[8], num[0], num[2], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[6], num[0], num[1], num[0], num[0], num[0]},
			{num[0], num[3], num[1], num[0], num[7], num[0], num[8], num[5], num[0]},
			{num[9], num[0], num[0], num[2], num[0], num[3], num[0], num[0], num[1]},
			{num[0], num[7], num[5], num[0], num[8], num[0], num[3], num[2], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[8], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[5], num[0], num[7], num[0], num[0], num[0]},
			{num[5], num[0], num[0], num[0], num[2], num[0], num[0], num[0], num[8]}
		},
		{
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[9], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[7], num[0], num[0], num[0]},
			{num[0], num[1], num[0], num[0], num[0], num[0], num[0], num[8], num[0]},
			{num[0], num[0], num[0], num[3], num[0], num[6], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[5], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]}
		}
	};
2.1.2中间值的计算

中间值的计算包括：

  • 所在九宫格的中间值
  • 所在行、列的中间值
2.1.2.1九宫格中间值的计算

回溯法求解组合数独

对于整个数独，要计算九个九宫格的中间值。由2.11可知，数独中数字的存储采用 2 n 2^n 2n。将单个九宫格的全部数字按位进行或运算得到结果 s s s， s s s的低10位二进制表示中，将所在位数记为 i i i(位数从0开始)。如果第 i i i位为0，则表示填入数字 i i i不会冲突。

//计算小九宫格 按位进行或运算  二进制中1的个数 记录 1-9 
//开始 (i, f) 
int cal_smallGrid(int a[9][9], int i, int f){
	int s = 0;
	for(int g = 0; g < 3; g++){
		for(int h = 0; h < 3; h++){
			s |= a[i + g][f + h];
		}
	}
	return s;
}
2.1.2.2行、列中间值的计算

回溯法求解组合数独

回溯法求解组合数独

原理同九宫格中间值的计算，将每一列每一行的所有数字按位进行或运算。

//  tag 0 - 固定 f  1 -固定 i 
// kind 0 第一种运算  1 第二种运算 
int cal_ranks(int a[9][9], int i, int f, int tag, int kind){
	int s = 0;
	for(int n = 0; n < 9; n++){
		if(kind == 0){
			if(tag == 0){
				s |= a[i + n][f];
			}else{
				s |= a[i][f + n];
			}
		}else{
			if(tag == 0){
				if(a[i + n][f] > 0) s++;
			}else{
				if(a[i][f + n] > 0) s++;
			}
		}
	}
	return s;
}
2.1.2.3初始化中间值

用 3 ∗ 3 3*3 3∗3的整形数组存储九宫格的中间值， 2 ∗ 9 2*9 2∗9的整形数组存储行列中间值，其中第一行存储列的中间值，第二行存储行的中间值。

//初始化 
void initial(int a[9][9], int b[3][3], int c[2][9]){
	
	for(int i = 0, g = 0; i < 3; i++, g += 3){
		for(int f = 0, h = 0; f < 3; f++, h += 3){
			b[i][f] = cal_smallGrid(a, g, h);
		}
	}
	
	for(int i = 0; i < 2; i++){
		for(int f = 0; f < 9; f++){
			if(i == 0){
				c[i][f] = cal_ranks(a, 0, f, i, 0);
			}else{
				c[i][f] = cal_ranks(a, f, 0, i, 0);
			}
		}
	}
    
}
2.1.2.4更新、还原中间值

在一个空白格插入或者去除一个数字，其所在行列的中间值会发生变化。因此需要进行中间值的更新以及还原。

当插入一个数字时，将这个数字与所对应的行列，九宫格中间值进行按位或运算。

当去除一个数字时，将这个数字取反与所对应的行列，九宫格中间值进行按位与运算。

// 改变（i， f）后更新 
//tag = 0 -- 更新 
//tag = 1 -- 还原
void update(int i, int f, int n, int b[3][3], int c[2][9], int tag){
	
	int index_i = i / 3;
	int index_f = f / 3;
	
	if(tag == 0){
		b[index_i][index_f] |= n;
		c[0][f] |= n;
		c[1][i] |= n;
	}else{
		n = ~n;
		b[index_i][index_f] &= n;
		c[0][f] &= n;
		c[1][i] &= n;
	}
	
}
2.1.3单个数独求解算法

求解整个数独，可以转换为求解每个空白格的取值，而空白格的可能取值取决于其所在九宫格、行和列的中间值。可用回溯递归求解，直到解出整个数独。

2.1.3.1定义数据结构

为了使用STl库里面的队列，定义保存单个数独的big_A结构，以及保存结果的total_A结构。

用四个队列存储周围四个数独的结果，方便后续组合求解第五个数独。

struct big_A{
	int a[9][9];
};

struct total_A{
	big_A a[5];
};

total_A totalA;
queue<big_A> Bigqueue1;
queue<big_A> Bigqueue2;
queue<big_A> Bigqueue3;
queue<big_A> Bigqueue4;
2.1.3.2回溯求解

根据数独表以及九宫格、行列中间变量，可以开始求解数独。

求解的过程如下：

开始：求解数独下一个单元格

  • 如果超出了数独单元格的个数，即代表走到最后，保存结果
  • 没有超出
    • 单元格为空白，根据中间值尝试所有可能的数字填入，更新中间值，跳转到开始，恢复中间值，标记此单元格未插入数字。
    • 单元格已经填入数字，跳转到开始

可用一个数字 n n n表示正在求解的单元格，那么其在二维数独数组中的行列分别是 i = n / 9 i = n/9 i=n/9以及 f = n % 9 f = n\%9 f=n%9。其对应的九宫格中间变量的下标为 [ i / 3 ] [ f / 3 ] [i/3][f/3] [i/3][f/3]，对应的列中间变量下标为 [ 0 ] [ f ] [0][f] [0][f]，对应的行中间变量的下标为 [ 1 ] [ i ] [1][i] [1][i]。将九宫格变量、行变量和列变量进行按位或运算，再除以2（去除零），其低9位二进制中0的个数即对应可能的取值。

//tag   求解第tag+1个数独 
int backTrack(int a[9][9], int b[3][3], int c[2][9], int n, int tag){
	//出口 
	if(n == 81){
		big_A A;
		memcpy(A.a, a, 81 * sizeof(int));
		switch(tag){
			case 0: Bigqueue1.push(A); break;
			case 1: Bigqueue2.push(A); break;
			case 2: Bigqueue3.push(A); break;
			case 3: Bigqueue4.push(A); break;
			case 4: 
				totalA.a[4] =  A; 
				cout << "finish!" << endl; 
				for(int i = 0; i < 5; i++){
					cout << i << " " << endl;
					for(int f = 0; f < 9; f++){
						for(int g = 0; g < 9; g++){
							cout << tab(totalA.a[i].a[f][g]) << " ";
						}
						cout << endl;
					}
					cout << endl << endl;
				}
				break;
			default: cout << "Error!" << endl; break;
		}
		
	}else{
		int index_i, index_f;
		index_i = n / 9;
		index_f = n % 9;
		
		if(a[index_i][index_f] == 0){
			int mid = b[index_i / 3][ index_f / 3];
			int lie = c[0][index_f];
			int hang = c[1][index_i];
			int s = mid | lie | hang;
            
			s /= 2;
			for(int i = 1; i <= 9; i++){
				int yu = s % 2;
				if(yu == 0){
					a[index_i][index_f] = num[i];
					update(index_i, index_f, num[i], b, c, 0);
					backTrack(a, b, c, n + 1, tag);
					update(index_i, index_f, num[i], b, c, 1);
					a[index_i][index_f] = 0;
				}
				s /= 2;
			}
		}else if(a[index_i][index_f] > 0){
			backTrack(a, b, c, n + 1, tag);
		}
	}
}

2.2组合求解最后一个数独

回溯法求解组合数独

可根据2.1中方法求解1-4号数独，对于5号数独的求解，可基于1-4号数独的结果。即根据所求结果，填充中间的数独数组，判断合法性，再进行数独求解。

2.2.1填充中间的数独

根据1~4号数独结果，填充5号数独：

  • 1号数独的右下九宫格填充5号数独的左上九宫格。
  • 2号数独的左下九宫格填充5号数独的右上九宫格。
  • 3号数独的右上九宫格填充5号数独的左下九宫格。
  • 4号数独的左上九宫格填充5号数独的右下九宫格。
// 将a1 填入 a2  tag+1 -- 第tag+1个矩阵 
void fill(int a1[9][9], int a2[9][9], int tag){
	int i1, f1, i2, f2;
	switch(tag){
		case 0: 
		i1 = f1 = 6;
		i2 = f2 = 0;
		break;
		case 1: 
		i1 = f2 = 6;
		f1 = i2 = 0;
		break;
		case 2: 
		i1 = f2 = 0;
		f1 = i2 = 6;
		break;
		case 3: 
		i1 = f1 = 0;
		i2 = f2 = 6;
		break;
		default: cout << "Error!" << endl; break;
	}
	for(int i = 0; i < 3; i++){
		for(int f = 0; f < 3; f++){
			a2[i2 + i][f2 + f] = a1[i1 + i][f1 + f];
		}
	}
}
2.2.2判断组合数独的合法性

填充组合成5号数独，可能因此产生同一行或列有相同的数字，需要进行了重复判断，检查合法性。

对2.1.2.2行、列中间值的计算以及2.1.2.3初始化中间值进行改进，可以达到组合的数独合法性的判断。

计算行、列按位或运算时：

  • 在将当前数字与前结果进行或运算
    • 当前数字为0，继续
    • 当前数字不为0，或运算得到结果
      • 结果与前结果相同，则必定有重复数字，结束
      • 结果与前结果不同，继续
//  tag 0 - 固定 f  1 -固定 i 
// kind 0 第一种运算  1 第二种运算 
int cal_ranks(int a[9][9], int i, int f, int tag, int kind, int &ret){
	int s = 0;
	int pre_s = s;
	ret = 1;
	for(int n = 0; n < 9; n++){
		if(kind == 0){
			if(tag == 0){
				if(a[i + n][f] > 0){
					s |= a[i + n][f];
					if(s == pre_s){
						ret = 0;
						return s;
					}
				}
			}else{
				if(a[i][f + n] > 0){
					s |= a[i][f + n];
					if(s == pre_s){
						ret = 0;	
						return s;
					}
				}
			}
			pre_s = s;
		}else{
			if(tag == 0){
				if(a[i + n][f] > 0) s++;
			}else{
				if(a[i][f + n] > 0) s++;
			}
		}
	}
	return s;
}
//初始化 
int initial(int a[9][9], int b[3][3], int c[2][9]){
	//
	for(int i = 0, g = 0; i < 3; i++, g += 3){
		for(int f = 0, h = 0; f < 3; f++, h += 3){
			b[i][f] = cal_smallGrid(a, g, h);
//			cout << b[i][f] << "  ";
		}
//		cout << endl;
	}
	int ret = 1;
	for(int i = 0; i < 2; i++){
		for(int f = 0; f < 9; f++){
			if(i == 0){
				c[i][f] = cal_ranks(a, 0, f, i, 0, ret);
			}else{
				c[i][f] = cal_ranks(a, f, 0, i, 0, ret);
			}
			if(ret == 0) return 0;
//			cout << c[i][f] << "  ";
		}
//		cout << endl << endl;
	}
	return ret;
}
2.2.3组合求解算法

由2.1.3单个数独求解算法可知，1~4号数独的结果分别存储于四个队列，将其取出填充组合成5号数独，进行合法性判断，再用单个数独求解算法求解5号数独，最终保存结果。

	big_A A1, A2, A3, A4;
	int n1, n2, n3, n4;
	n1 = Bigqueue1.size();
	n2 = Bigqueue2.size();
	n3 = Bigqueue3.size();
	n4 = Bigqueue4.size();
	cout << n1 << " " << n2 << " " << n3 << " " << n4 << endl;

	for(int i = 0; i < n1; i++){
		cout << i << endl;
		A1 = Bigqueue1.front();
		Bigqueue1.pop();
		for(int f = 0; f < n2; f++){
			A2 = Bigqueue2.front();
			Bigqueue2.pop();
			for(int g = 0; g < n3; g++){
				A3 = Bigqueue3.front();
				Bigqueue3.pop();
				for(int h = 0; h < n4; h++){
					A4 = Bigqueue4.front();
					Bigqueue4.pop();
					
					int num = sizeof(total_A) / 4;
					totalA.a[0] = A1;
					totalA.a[1] = A2;
					totalA.a[2] = A3;
					totalA.a[3] = A4;
					for(int i = 0; i < 4; i++){
						fill(totalA.a[i].a, a[4], i);
					}
					
					int ret = initial(a[4], b, c);
					if(ret == 1){
						backTrack(a[4], b, c, 0, 4);
					}
					
					Bigqueue4.push(A4);
				}
				Bigqueue3.push(A3);
			}
			Bigqueue2.push(A2);
		}
	}

3.实验结果

3.1第一个问题结果

第一个问题中，1~4号数独的可能情况分别是511,143,250,444种，组合求解，计算量庞大，需在小时级得出结果。结果如下：

回溯法求解组合数独

3.2第二个问题结果

第二个问题：
回溯法求解组合数独

第二个问题中，1~4号数独的可能情况分别是72,44,7,211种，组合求解，计算量适中，能在秒数级得出结果。结果如下：

回溯法求解组合数独

4.完整代码

#include <bits/stdc++.h>

using namespace std;
const int N = 0x3fe;

struct big_A{
	int a[9][9];
};

struct total_A{
	big_A a[5];
};

total_A totalA;
queue<big_A> Bigqueue1;
queue<big_A> Bigqueue2;
queue<big_A> Bigqueue3;
queue<big_A> Bigqueue4;

int num[] = {0, 2, 4, 8, 16, 32, 64, 128, 256, 512};


//转换 
int tab(int x){
	int y = x / 2;
	for(int i = 1; i <= 9; i++){
		int yu = y % 2;
		if(yu == 1) return i;
		y /= 2;
	}
}


void cover(int x[21][21], int a[9][9], int index_i, int index_f){
	for(int i = 0; i < 9; i++){
		for(int f = 0; f < 9; f++){
			x[i + index_i][f + index_f] = tab(a[i][f]);
		}
	}
}
void show(){
	int x[21][21];
	memset(x, 0, sizeof(int) * 21 *21);
	int y[5][2] = {
		{0, 0},
		{0, 12},
		{12, 0},
		{12, 12},
		{6, 6}
	};
	for(int i = 0; i < 5; i++){
		cover(x, totalA.a[i].a, y[i][0], y[i][1]);
	}
	
	for(int i = 0; i < 21; i++){
		for(int f = 0; f < 21; f++){
			if(x[i][f] > 0){
				cout << x[i][f] << " ";
			}else{
				cout << "  ";
			}
			
		}
		cout << endl;
	}
}
	
	
	

//计算小九宫格 按位进行或运算  二进制中1的个数 记录 1-9 
//开始 (i, f) 
int cal_smallGrid(int a[9][9], int i, int f){
	int s = 0;
	for(int g = 0; g < 3; g++){
		for(int h = 0; h < 3; h++){
			s |= a[i + g][f + h];
		}
	}
	return s;
}

//  tag 0 - 固定 f  1 -固定 i 
// kind 0 第一种运算  1 第二种运算 
int cal_ranks(int a[9][9], int i, int f, int tag, int kind, int &ret){
	int s = 0;
	int pre_s = s;
	ret = 1;
	for(int n = 0; n < 9; n++){
		if(kind == 0){
			if(tag == 0){
				if(a[i + n][f] > 0){
					s |= a[i + n][f];
					if(s == pre_s){
						ret = 0;
						return s;
					}
				}
			}else{
				if(a[i][f + n] > 0){
					s |= a[i][f + n];
					if(s == pre_s){
						ret = 0;	
						return s;
					}
				}
			}
			pre_s = s;
		}else{
			if(tag == 0){
				if(a[i + n][f] > 0) s++;
			}else{
				if(a[i][f + n] > 0) s++;
			}
		}
	}
	return s;
}

//初始化 
int initial(int a[9][9], int b[3][3], int c[2][9]){
	//
	for(int i = 0, g = 0; i < 3; i++, g += 3){
		for(int f = 0, h = 0; f < 3; f++, h += 3){
			b[i][f] = cal_smallGrid(a, g, h);
		}
	}
	int ret = 1;
	for(int i = 0; i < 2; i++){
		for(int f = 0; f < 9; f++){
			if(i == 0){
				c[i][f] = cal_ranks(a, 0, f, i, 0, ret);
			}else{
				c[i][f] = cal_ranks(a, f, 0, i, 0, ret);
			}
			if(ret == 0) return 0;
		}
	}
	return ret;
}

// 改变（i， f）后更新 
//tag = 0 -- 更新 
//tag = 1 -- 还原
void update(int i, int f, int n, int b[3][3], int c[2][9], int tag){
	
	int index_i = i / 3;
	int index_f = f / 3;
	
	if(tag == 0){
		b[index_i][index_f] |= n;
		c[0][f] |= n;
		c[1][i] |= n;
	}else{
		n = ~n;
		b[index_i][index_f] &= n;
		c[0][f] &= n;
		c[1][i] &= n;
	}
	
}



//回溯 
//tag   tag+1 个 
int backTrack(int a[9][9], int b[3][3], int c[2][9], int n, int tag){
	//出口 
	if(n == 81){

		big_A A;
		memcpy(A.a, a, 81 * sizeof(int));
		switch(tag){
			case 0: Bigqueue1.push(A); break;
			case 1: Bigqueue2.push(A); break;
			case 2: Bigqueue3.push(A); break;
			case 3: Bigqueue4.push(A); break;
			case 4: 
				totalA.a[4] =  A; 
				cout << "finish!" << endl; 
				show();
				break;
			default: cout << "Error!" << endl; break;
		}
		
	}else{
		int index_i, index_f;
		index_i = n / 9;
		index_f = n % 9;
		
		if(a[index_i][index_f] == 0){
			int mid = b[index_i / 3][ index_f / 3];
			int lie = c[0][index_f];
			int hang = c[1][index_i];
			
			int s = mid | lie | hang;
			s /= 2;
			for(int i = 1; i <= 9; i++){
				int yu = s % 2;
				if(yu == 0){
					a[index_i][index_f] = num[i];
					update(index_i, index_f, num[i], b, c, 0);
					backTrack(a, b, c, n + 1, tag);
					update(index_i, index_f, num[i], b, c, 1);
					a[index_i][index_f] = 0;
				}
				s /= 2;
				
			}
		}else if(a[index_i][index_f] > 0){
			backTrack(a, b, c, n + 1, tag);
		}
	}
}

// 将a1 填入 a2  tag+1 -- 第tag+1个矩阵 
void fill(int a1[9][9], int a2[9][9], int tag){
	int i1, f1, i2, f2;
	switch(tag){
		case 0: 
		i1 = f1 = 6;
		i2 = f2 = 0;
		break;
		case 1: 
		i1 = f2 = 6;
		f1 = i2 = 0;
		break;
		case 2: 
		i1 = f2 = 0;
		f1 = i2 = 6;
		break;
		case 3: 
		i1 = f1 = 0;
		i2 = f2 = 6;
		break;
		default: cout << "Error!" << endl; break;
	}
	for(int i = 0; i < 3; i++){
		for(int f = 0; f < 3; f++){
			a2[i2 + i][f2 + f] = a1[i1 + i][f1 + f];
		}
	}
}
int count_num(int x){
	int s = 0;
	int mid = x / 2;
	for(int g = 1; g <= 9; g++){
		if(mid % 2 == 1) s++;
		mid /= 2;
	}
	return s;
}

int judge(int a[9][9], int c[2][9]){

	int x;
	for(int i = 0; i < 2; i++){
		for(int f = 0; f < 9; f++){
			if(i == 0){
				int num = cal_ranks(a, 0, f, i, 1, x);
				int s = count_num(c[i][f]);
				if(s != num) return -1;
			}else{
				int num = cal_ranks(a, f, 0, i, 1, x);
				int s = count_num(c[i][f]);
				if(s != num) return -1;
			}
		}
	}
	return 1;
}


int main(){

//	int a[5][9][9] ={
//		{
//			{num[0], num[9], num[5], num[3], num[0], num[0], num[0], num[1], num[0]},
//			{num[7], num[0], num[0], num[0], num[1], num[0], num[0], num[0], num[3]},
//			{num[0], num[0], num[0], num[0], num[0], num[7], num[0], num[0], num[5]},
//			{num[0], num[0], num[7], num[0], num[0], num[0], num[0], num[0], num[1]},
//			{num[0], num[2], num[0], num[0], num[0], num[0], num[0], num[8], num[0]},
//			{num[1], num[0], num[0], num[0], num[0], num[0], num[6], num[0], num[0]},
//			{num[4], num[0], num[0], num[9], num[0], num[0], num[0], num[0], num[0]},
//			{num[2], num[0], num[0], num[0], num[4], num[0], num[0], num[0], num[6]},
//			{num[0], num[5], num[0], num[0], num[0], num[1], num[8], num[4], num[0]}
//		},
//		{
//			{num[0], num[2], num[5], num[3], num[0], num[0], num[0], num[6], num[0]},
//			{num[9], num[0], num[0], num[0], num[2], num[0], num[0], num[0], num[8]},
//			{num[0], num[0], num[0], num[0], num[0], num[6], num[0], num[0], num[4]},
//			{num[0], num[0], num[6], num[0], num[0], num[0], num[0], num[0], num[9]},
//			{num[0], num[4], num[0], num[0], num[0], num[0], num[0], num[5], num[0]},
//			{num[7], num[0], num[0], num[0], num[0], num[0], num[1], num[0], num[0]},
//			{num[6], num[0], num[0], num[7], num[0], num[0], num[0], num[0], num[0]},
//			{num[8], num[0], num[0], num[0], num[1], num[0], num[0], num[0], num[5]},
//			{num[0], num[5], num[0], num[0], num[0], num[4], num[3], num[9], num[0]}
//		},
//		{
//			{num[0], num[2], num[4], num[1], num[0], num[0], num[0], num[8], num[0]},
//			{num[6], num[0], num[0], num[0], num[9], num[0], num[0], num[0], num[5]},
//			{num[0], num[0], num[0], num[0], num[0], num[4], num[0], num[0], num[7]},
//			{num[0], num[0], num[1], num[0], num[0], num[0], num[0], num[0], num[9]},
//			{num[0], num[5], num[0], num[0], num[0], num[0], num[0], num[4], num[0]},
//			{num[7], num[0], num[0], num[0], num[0], num[0], num[2], num[0], num[0]},
//			{num[1], num[0], num[0], num[7], num[0], num[0], num[0], num[0], num[0]},
//			{num[3], num[0], num[0], num[0], num[8], num[0], num[0], num[0], num[6]},
//			{num[0], num[6], num[0], num[0], num[0], num[2], num[7], num[9], num[0]}
//		},
//		{
//			{num[0], num[1], num[2], num[3], num[0], num[0], num[0], num[7], num[0]},
//			{num[3], num[0], num[0], num[0], num[8], num[0], num[0], num[0], num[2]},
//			{num[0], num[0], num[0], num[0], num[0], num[6], num[0], num[0], num[3]},
//			{num[0], num[0], num[4], num[0], num[0], num[0], num[0], num[0], num[9]},
//			{num[0], num[9], num[0], num[0], num[0], num[0], num[0], num[8], num[0]},
//			{num[2], num[0], num[0], num[0], num[0], num[0], num[6], num[0], num[0]},
//			{num[9], num[0], num[0], num[1], num[0], num[0], num[0], num[0], num[0]},
//			{num[1], num[0], num[0], num[0], num[4], num[0], num[0], num[0], num[5]},
//			{num[0], num[5], num[0], num[0], num[0], num[7], num[2], num[1], num[0]}
//		},
//		{
//			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
//			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
//			{num[0], num[0], num[0], num[0], num[1], num[0], num[0], num[0], num[0]},
//			{num[0], num[0], num[0], num[3], num[0], num[6], num[0], num[0], num[0]},
//			{num[0], num[0], num[8], num[0], num[0], num[0], num[7], num[0], num[0]},
//			{num[0], num[0], num[0], num[5], num[0], num[9], num[0], num[0], num[0]},
//			{num[0], num[0], num[0], num[0], num[6], num[0], num[0], num[0], num[0]},
//			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
//			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]}
//		}
//	};
	int a[5][9][9] ={
		{
			{num[9], num[0], num[0], num[0], num[5], num[0], num[0], num[0], num[7]},
			{num[0], num[0], num[0], num[9], num[0], num[7], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[6], num[0], num[4], num[0], num[0], num[0]},
			{num[0], num[1], num[3], num[0], num[2], num[0], num[8], num[9], num[0]},
			{num[2], num[0], num[0], num[7], num[0], num[1], num[0], num[0], num[3]},
			{num[0], num[9], num[6], num[0], num[4], num[0], num[7], num[2], num[0]},
			{num[0], num[0], num[0], num[3], num[0], num[5], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[9], num[0], num[0], num[0]},
			{num[3], num[0], num[0], num[0], num[7], num[0], num[0], num[0], num[6]}
		},
		{
			{num[2], num[0], num[0], num[0], num[9], num[0], num[0], num[0], num[6]},
			{num[0], num[0], num[0], num[6], num[0], num[3], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[1], num[0], num[5], num[0], num[0], num[0]},
			{num[0], num[9], num[8], num[0], num[6], num[0], num[1], num[5], num[0]},
			{num[6], num[0], num[0], num[5], num[0], num[9], num[0], num[0], num[8]},
			{num[0], num[7], num[2], num[0], num[8], num[0], num[6], num[3], num[0]},
			{num[0], num[0], num[0], num[7], num[0], num[4], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[9], num[0], num[8], num[0], num[0], num[0]},
			{num[9], num[0], num[0], num[0], num[5], num[0], num[0], num[0], num[4]}
		},
		{
			{num[9], num[0], num[0], num[0], num[3], num[0], num[0], num[0], num[7]},
			{num[0], num[0], num[0], num[5], num[0], num[9], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[7], num[0], num[4], num[0], num[0], num[0]},
			{num[0], num[1], num[3], num[0], num[2], num[0], num[7], num[5], num[0]},
			{num[5], num[0], num[0], num[8], num[0], num[7], num[0], num[0], num[2]},
			{num[0], num[7], num[4], num[0], num[1], num[0], num[9], num[8], num[0]},
			{num[0], num[0], num[0], num[6], num[0], num[8], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[1], num[0], num[0], num[0]},
			{num[6], num[0], num[0], num[0], num[7], num[0], num[0], num[0], num[9]}
		},
		{
			{num[4], num[0], num[0], num[0], num[9], num[0], num[0], num[0], num[3]},
			{num[0], num[0], num[0], num[8], num[0], num[2], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[6], num[0], num[1], num[0], num[0], num[0]},
			{num[0], num[3], num[1], num[0], num[7], num[0], num[8], num[5], num[0]},
			{num[9], num[0], num[0], num[2], num[0], num[3], num[0], num[0], num[1]},
			{num[0], num[7], num[5], num[0], num[8], num[0], num[3], num[2], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[8], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[5], num[0], num[7], num[0], num[0], num[0]},
			{num[5], num[0], num[0], num[0], num[2], num[0], num[0], num[0], num[8]}
		},
		{
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[9], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[4], num[0], num[7], num[0], num[0], num[0]},
			{num[0], num[1], num[0], num[0], num[0], num[0], num[0], num[8], num[0]},
			{num[0], num[0], num[0], num[3], num[0], num[6], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[5], num[0], num[0], num[0], num[0]},
			{num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0], num[0]}
		}
	};
	

	int b[3][3];
	int c[2][9];
	
	for(int i = 0; i < 4; i++){
		initial(a[i], b, c);
		backTrack(a[i], b, c, 0, i);
	}

	big_A A1, A2, A3, A4;
	int n1, n2, n3, n4;
	n1 = Bigqueue1.size();
	n2 = Bigqueue2.size();
	n3 = Bigqueue3.size();
	n4 = Bigqueue4.size();
	cout << n1 << " " << n2 << " " << n3 << " " << n4 << endl;

	for(int i = 0; i < n1; i++){
		cout << i << endl;
		A1 = Bigqueue1.front();
		Bigqueue1.pop();
		for(int f = 0; f < n2; f++){
			A2 = Bigqueue2.front();
			Bigqueue2.pop();
			for(int g = 0; g < n3; g++){
				A3 = Bigqueue3.front();
				Bigqueue3.pop();
				for(int h = 0; h < n4; h++){
					A4 = Bigqueue4.front();
					Bigqueue4.pop();
					
					int num = sizeof(total_A) / 4;
					totalA.a[0] = A1;
					totalA.a[1] = A2;
					totalA.a[2] = A3;
					totalA.a[3] = A4;
					for(int i = 0; i < 4; i++){
						fill(totalA.a[i].a, a[4], i);
					}
					
					int ret = initial(a[4], b, c);

					int x = judge(a[4], c);
					if(x == 1){
						backTrack(a[4], b, c, 0, 4);
					}

					Bigqueue4.push(A4);
				}
				Bigqueue3.push(A3);
			}
			Bigqueue2.push(A2);
		}
	}
	return 0;
}
上一篇：在一个数组中实现两个堆栈


下一篇：gerrit中mysql配置