转载请注明：http://www.cnblogs.com/igoslly/p/8708960.html
题目：用户会输入数独预先填好的数字，请设计程序进行解题
输入：按行按列进行输入，空置位置以0输入
数独游戏要求：
根据表格里先给出的提示，填写1-9数字，使9×9的宫格满足每行、每列数字均不重复；同时9×9格盘中9个3×3的小格也必须满足1-9不重复。
体会一下（图片来自百度搜索）：
思路：
现实解数独游戏会有大师级的技巧，但是计算机解最直接的方法，那就是穷举法———某格从1~9尝试，填写正确后再进行次格的尝试，如是往下推理，若遇到某个格子1-9均无法满足，则返回上级+1
伪代码大概如下：
dfs（当前判断位置）{
结束条件: if（已完成）返回
if（当前位置不为0） //题目给定数字
{
dfs（当前判断位置+1）
}
else
{
for（从1到9进行尝试）
{
if（如果当前尝试数i合法）
填写数字；dfs（当前判断位置+1）；
返回时已填写完毕，直接返回；
}
当前填写位置=0；
}
}
int dfs(int n){
// 数独矩阵已经填完，返回
if(n>80)
{
sign=true;
return 0;
}
if(num[n/9][n%9]!=0)
{
// 该格存在规定值，继续
dfs(n+1);
}else{
for(int i=1;i<=9;i++)
{
// 分别从1开始穷举，前提是不与填数字矛盾
if(check(n,i)==true){
num[n/9][n%9]=i;
dfs(n+1);
//如果已完成 直接返回
if(sign==true) return 0;
}
}
// 若该格1-9均无法满足，则需返回上级dfs
// 此时若不置位0，上级dfs会将此格的9，默认为系统输入，进行报错
num[n/9][n%9]=0;
}
}
合法条件判断：
填写数字是否合法，是依据同行、同列以及同九宫格进行判断：
bool check(int n,int key){
// 对于每个n，所在行数n/9，列数n%9
// 检测同行是否存在相同数
for(int i=0;i<9;i++){
int j=n/9;
if(num[j][i]==key)
{
return false;
}
}
// 检测同列是否存在相同数
for(int i=0;i<9;i++)
{
int j=n%9;
if(num[i][j]==key){return false;}
}
// 检测同矩阵是否存在相同数
int x=n/9/3*3;
int y=n%9/3*3;
for(int i=x;i<x+3;i++){
for(int j=y;j<y+3;j++){
if(num[i][j]==key){return false;}
}
}
// 均不存在，返回true合法
return true;
}
添加输入、输出函数后，整体的代码如下：
#include<iostream>
using namespace std;
int num[9][9]={0};
bool sign=false;
// 输入
void input(){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cin>>num[i][j];
}
}
}
// 输出数独
void output(){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cout << num[i][j] << " ";
if(j%3==2){
cout<<" ";
}
}
cout<<endl;
if(i%3==2){
cout<<endl;
}
}
}
// 检测填入数字是否合法
bool check(int n,int key){
// 对于每个n，所在行数n/9，列数n%9
// 检测同行是否存在相同数
for(int i=0;i<9;i++){
int j=n/9;
if(num[j][i]==key)
{
return false;
}
}
// 检测同列是否存在相同数
for(int i=0;i<9;i++)
{
int j=n%9;
if(num[i][j]==key){return false;}
}
// 检测同矩阵是否存在相同数
int x=n/9/3*3;
int y=n%9/3*3;
for(int i=x;i<x+3;i++){
for(int j=y;j<y+3;j++){
if(num[i][j]==key){return false;}
}
}
// 均不存在，返回true合法
return true;
}
int dfs(int n){
// 数独矩阵已经填完，返回
if(n>80)
{
sign=true;
return 0;
}
if(num[n/9][n%9]!=0)
{
// 该格存在规定值，继续
dfs(n+1);
}else{
for(int i=1;i<=9;i++)
{
// 分别从1开始穷举，前提是不与填数字矛盾
if(check(n,i)==true){
num[n/9][n%9]=i;
dfs(n+1);
//如果已完成 直接返回
if(sign==true) return 0;
}
}
// 若该格1-9均无法满足，则需返回上级dfs
// 此时若不置位0，上级dfs会将此格的9，默认为系统输入，进行报错
num[n/9][n%9]=0;
}
}
int main(){
//freopen("C://Users//Lly//Desktop//input.txt","r",stdin);
input();
dfs(0);
output();
return 0;
}
测试结果：
当然数独游戏还是有更简便的实现的！
具体可看leetcode链接——https://www.cnblogs.com/igoslly/p/8719622.html