笔试题——数独游戏实现

2018-06-17 20:52:15来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

 

测试结果:

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:CodeForces April Fools Contest 2018题解

下一篇:BZOJ4810: [Ynoi2017]由乃的玉米田(莫队+bitset)