笔试题——数独游戏实现

转载请注明：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;
}

---

 

测试结果：