数独实验报告范文

本文格式为Word版下载后可任意编辑和复制第第页数独实验报告范文Sudoku数独试验报告

一、算法描述

求解Sudoku让人最简单想到的方法是穷举每个方格可能的值，假如符合条件，则得到解，不符合条件则进行回溯。通过递归的方法，明显可以得到数独的解。

我想到的简洁的递归方法，是每一行从左到右，试验每一个方格可能的数字，进行递归。这种方法看似特别麻烦，实际上对于一般的数独题，速度是特别快的，思想比较简洁，写出来的代码也特别简洁、易懂。

算法1：简洁递归方法

从第一个格开头，从1到9试验，是否满意行、列、九宫格互不相同的条件。若满意条件，则填入该数字，再试验下一个格。当一个格子消失没有数字能填的状况时，说明已经填的数字有误，回溯，再进行递归。

算法2：优化的递归算法

先遍历全部格子，统计每种格子可能消失数字的个数。每次选择可能消失数字个数最少的格子来进行递归。

设置三维数组poss[i][j][k]来存储可能消失数字的信息。poss[i][j][0]记录i行j列的格子可能消失数字的个数，poss[i][j][k](1算法3：生成数独棋盘的算法

我最开头的想法是穷举法，随机生成满意行各不相同的9行，再推断9宫格、每列是否符合要求，符合条件时，随机生成停止。然而，这种算法的当然时间简单度明显是过高。第99一步的随机生成的次数是9*9/P9=9608。随机生成一组棋盘耗时就特别大。后来，我从求解的个数的程序获得启发。算法二对于1000多组解的数独棋盘，解起来也很快。随机生成填9个方格，再用算法一的方法解出来，取第一组正确的解作为棋盘即可生成填好的棋盘。再把肯定数量的格子的数字随机删除，计算解的个数。假如解唯一，就得到了棋盘。

二、数据结构

这三种算法的数据结构不是特别简单，只是一般的数组。

算法一：数组a[i][j]

算法二：数组a[i][j]和poss[i][j][k]

算法三：数组a[i][j]和poss[i][j][k]

三、时间效率分析

算法1：这种算法在tsinsen系统上只用了15ms得到全部答案。

虽然这种算法在tsinsen系统的测试中有很好的表现，但是我试了试在几道骨灰级难度的题，发觉这种算法可能会用到10秒以上的时间，并且测试数据不同，时间差异特别大。

我认为，这种算法的漏洞在于，假如开头的格子可能消失的数字特别多，递归树开头的枝会特别多。并且，我们一般做数独题，都会先挑可能消失数字个数最少的格子来填，充分利用了已知条件。然而，这种算法只按格子的行列挨次来试验，明显特别傻。于是，我想出了其次种算法。

算法2：这种算法耗时长。

特别令人绝望的是，虽然它能在短时间内解出骨灰级题目，但是，和上一个算法相比，对于简洁的题目，它比较耗时。在tsinsen系统中测试的时间是91ms。它的缺陷在于，每次递归都必需更新（i，j）格子所在的行、列、九宫格全部的元素。每次要求20个数的poss[i][j]。回溯同样要更新。并且求poss[i][j]的函数时间简单度是O（n）。每一步所耗时间比上一种算法多许多。但是，总的试验的步数能显著削减。所以，这种算法适用于数独解题的动画演示和解极难题目。

四、程序结构

五、运行结果

六、总结和反思

后来老师提高了难度，要求程序能求出多解数独题的解的个数。几千个解的数据都能快速得出答案，但是几万个解的数据，需要很长时间，更别提几百万的数据。这两种递归的算法都有问题，优化的空间也有限，需要更强大、高效的算法。

这次Project