笔试题——数独游戏实现
2018-06-17 20:52:15来源:未知 阅读 ()
转载请注明: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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C语言实现经典游戏——扫雷! 2020-04-17
- [题记-数学-面试题]约瑟夫环-leetcode 2020-03-30
- 小游戏二之---------------五子棋 2020-03-23
- Qt5小Demo之猜数字游戏 2020-03-19
- [Uva1637][DFS][记忆化] 纸牌游戏 Double Patience 2020-03-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash