问题描述
在本次算法分析的课堂演示中，我做的是一个关于“裁切悖论——消失的正方形的
ppt
关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt
”，但是由于代码的问题，现在借鉴了同学的实验，写了一个关于数独算法的小题目。
如下图所示，有一个9*9的正方形，而正方形又分成了九个小正方形，现在已经在图示的正方形中给出了一些方格中的数字，要求将正方形中所有小方格的数字填充完，并且每个小正方形以及每行、每列，只能出现一次1~9这九个数字。
6
8
7
9
5
7
6
4
8
3
2
4
6
9
4
1
2
3
5
3
1
7
8
9
2
1
7
6
3
解决
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
我们先假设填入的数字为0~8共9个数字。
将整个图分成9个3*3的方块，从左到右，从上到下，依次编号0～8。
填每个格子的时候,我们可以选择.0~8。
对于选择的数字，有3种限制，我们通过这三种限制来对回溯过程进行剪枝。
1.行不重复 r[9][9]
2.列不重复 c[9][9]
3.块不重复 b[9][9]
对使用3个9×9的数组来描述这三种限制。
对于行 n 来说，所有之前填过的数字nums，都有r[n][nums] = 1。
同理，对与列和块来说，之前每个填过的数字都相应标记为1。
当尝试向一个格子[row][col] (块序号为bi)填充数据i（0<=i<=8,的时候，如果对应r[row][i] =1 或 c[col][i] = 1 或 b[bi][i] =1，说明无法满足条件，是非法的。）
这时再尝试i = i+1.
当向坐标为[row][col] 填入一个满足条件的数字i的时候，我们更新限制数组如下
r[row][i] = 1;
c[col][i] = 1;
b[bi][i] = 1;
然后坐标移到下一个，这里选用的顺序是右移动。
对于一个格子CX的后续CY，如果我们遍历0～9完成，那么返回。
尝试CX的其他可能性。
当填入的格子是 [8][8]时，整个问题处理完毕。
对于给定的输入，直接将初始状态的矩阵设置成相应的值，同时，根据给定的值，设置初始的r, c, b的限制条件。
当读到的格子内已经有给定值的时候，无需做其他尝试，直接进入处理下一个格子。
实际填入的是1～9,所以要对0~8做一点转换。
对于每次尝试完一个可能填入的数后，需要恢复现场，包括将该格子内的数重置为初始值0.同时，相应的限制条件r,c,b都应把刚才填入的值的位置0.
代码实现
下面给出这道题目的实现代码：
1. 打开codeblocks，新建一个项目；
2. 编写代码。
代码如下：
#include
#include
#define MMAX 9
char M[MMAX][MMAX] = {{0}};
int count = 0;
int getblockid(int row, int col)
{
return row/3 * 3 + col/3;
}
void getnext(int *row, int *col, int* nrow, int* ncol){
if(*col ==8)
{
*ncol = 0;
*nrow = (*row)+1;
}
Else
{
*nrow = *row;
*ncol = (*col) +1;
}
}
void outputmatrix(char mtr[MMAX][MMAX] ){
int i, j;
for(i=0;i
本文档为【算法分析与设计大作业】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483