登录
  • #刷题

回溯法求解数独的一个CPP程序

TonyJang
717
2
// sudoku.cpp : Defines the entry point for the console application.[br][/br][br][/br]//[br][/br][br][/br]#include <iostream>[br][/br][br][/br]#include <vector>[br][/br][br][/br]using namespace std;[br][/br][br][/br]const int N = 9;[br][/br][br][/br]void valid(const int a[N][N], int x, int y, vector<int>& validList)[br][/br][br][/br]{[br][/br][br][/br]	for(int m=1; m<=N; m++)[br][/br][br][/br]	{[br][/br][br][/br]		bool flag = true;[br][/br][br][/br]		for(int j = 0; j<N; j++)[br][/br][br][/br]		{[br][/br][br][/br]			if(a[x][j] == m) //每行只能出现一次[br][/br][br][/br]			{[br][/br][br][/br]				flag = false;[br][/br][br][/br]				break;[br][/br][br][/br]			}[br][/br][br][/br]			if(a[j][y] == m)//每列只能出现一次[br][/br][br][/br]			{[br][/br][br][/br]				flag = false;[br][/br][br][/br]				break;[br][/br][br][/br]			}[br][/br][br][/br]			int xx,yy;//每3*3格子只能出现一次[br][/br][br][/br]			xx = (x/3)*3 + j/3;[br][/br][br][/br]			yy = (y/3)*3 + j%3;[br][/br][br][/br]			if(a[xx][yy] == m)[br][/br][br][/br]			{[br][/br][br][/br]				flag = false;[br][/br][br][/br]				break;[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]		if(flag) validList.push_back(m);[br][/br][br][/br]	}[br][/br][br][/br]}[br][/br][br][/br]int b[N][N] = {[br][/br][br][/br]				8, 0, 0, 0, 0, 0, 0, 0, 0, [br][/br][br][/br]				0, 0, 3, 6, 0, 0, 0, 0, 0, [br][/br][br][/br]				0, 7, 0, 0, 9, 0, 2, 0, 0, [br][/br][br][/br]				0, 5, 0, 0, 0, 7, 0, 0, 0, [br][/br][br][/br]				0, 0, 0, 0, 4, 5, 7, 0, 0, [br][/br][br][/br]				0, 0, 0, 1, 0, 0, 0, 3, 0, [br][/br][br][/br]				0, 0, 1, 0, 0, 0, 0, 6, 8, [br][/br][br][/br]				0, 0, 8, 5, 0, 0, 0, 1, 0, [br][/br][br][/br]				0, 9, 0, 0, 0, 0, 4, 0, 0[br][/br][br][/br]			};[br][/br][br][/br]void print(int a[N][N])[br][/br][br][/br]{[br][/br][br][/br]	for(int i=0; i<N; i++)[br][/br][br][/br]	{[br][/br][br][/br]		for(int j=0; j<N; j++)[br][/br][br][/br]		{[br][/br][br][/br]			printf("%d ", a[i][j]);[br][/br][br][/br]		}[br][/br][br][/br]		printf("        ");[br][/br][br][/br]		for(int j=0; j<N; j++)[br][/br][br][/br]		{[br][/br][br][/br]			printf("%d ", b[i][j]);[br][/br][br][/br]		}[br][/br][br][/br]		printf("\n");[br][/br][br][/br]	}[br][/br][br][/br]	cout<<endl;[br][/br][br][/br]}[br][/br][br][/br]bool success = false;[br][/br][br][/br]bool solve(int a[N][N], int x, int y)[br][/br][br][/br]{[br][/br][br][/br]	while(a[x][y] != 0)[br][/br][br][/br]	{[br][/br][br][/br]		if(++y==9)[br][/br][br][/br]		{[br][/br][br][/br]			y=0;[br][/br][br][/br]			x++;[br][/br][br][/br]			if(x==9) //到达右下角,游戏结束[br][/br][br][/br]				return true;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	if(b[x][y] != 0) return false;[br][/br][br][/br]	vector<int> validList;[br][/br][br][/br]	valid(a, x, y, validList); // 将这个格子所有可以填的数字放到list里[br][/br][br][/br]	if(validList.size() == 0) return false;[br][/br][br][/br]	//遍历这个list,每个数填进去试一试[br][/br][br][/br]	for(int i=0; i<validList.size(); i++)[br][/br][br][/br]	{[br][/br][br][/br]		a[x][y]=validList[i];[br][/br][br][/br]		bool f=solve(a, x,y);//递归试算[br][/br][br][/br]		if(f) return true;[br][/br][br][/br]		a[x][y]=0;[br][/br][br][/br]	}[br][/br][br][/br]	return false;[br][/br][br][/br]}[br][/br][br][/br]int main()[br][/br][br][/br]{[br][/br][br][/br]	int a[N][N] = {[br][/br][br][/br]					8, 0, 0, 0, 0, 0, 0, 0, 0, [br][/br][br][/br]					0, 0, 3, 6, 0, 0, 0, 0, 0, [br][/br][br][/br]					0, 7, 0, 0, 9, 0, 2, 0, 0, [br][/br][br][/br]					0, 5, 0, 0, 0, 7, 0, 0, 0, [br][/br][br][/br]					0, 0, 0, 0, 4, 5, 7, 0, 0, [br][/br][br][/br]					0, 0, 0, 1, 0, 0, 0, 3, 0, [br][/br][br][/br]					0, 0, 1, 0, 0, 0, 0, 6, 8, [br][/br][br][/br]					0, 0, 8, 5, 0, 0, 0, 1, 0, [br][/br][br][/br]					0, 9, 0, 0, 0, 0, 4, 0, 0[br][/br][br][/br]				};[br][/br][br][/br]	solve(a,0,0);[br][/br][br][/br]	print(a);[br][/br][br][/br]	return 0;[br][/br][br][/br]}[br][/br][br][/br]我没搞清楚,a[0][0]=b[0][0]=8,运行到84行应该直接返回false了啊,怎么还能接着运行下去?[/i][/i][/i]
2条回复
热度排序

发表回复