简单的搜索题直接上代码
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> using namespace std; int flag; int arr[9][9]; bool judge(int num, int x, int y)//判断 { int i, j; for(i = 0; i < 9; i++) { if(arr[i][y] == num || arr[x][i] == num) return false; } int a = x / 3 * 3, b = y / 3 * 3; for(i = a; i < a+3; i++) { for(j = b; j < b+3; j++) { if(arr[i][j] == num) return false; } } return true; } void print()//输出 { int i, j; for(i = 0; i < 9; i++) { for(j = 0; j < 9; j++) { cout<<arr[i][j]<<' '; } cout<<endl; } } void dfs(int x, int y)//搜索 { if(flag == 1)//出口 { return ; } if(x==9 && y == 0) { flag = 1; print(); return ; } if( y == 9)//每行搜完之后搜索下一行 dfs(x+1,0); if(arr[x][y]!=0) dfs(x,y+1);//若当前已经填数字，搜下一个。 if(arr[x][y] == 0) { int i; for(i = 1; i <= 9; i++) { if(judge(i, x, y)) { arr[x][y] = i; dfs(x, y+1); arr[x][y] = 0; } } } } int main() { int n; cin>>n; while(n--) { memset(arr,0,sizeof(arr)); flag = 0; int i, j; for(i = 0; i < 9; i++) { for(j = 0; j < 9; j++) { cin>>arr[i][j]; } } dfs(0,0); } }
