查看: 3080|回复: 6
谁能写一个高效的c++数独代码呢？
主题帖子精华
在线时间 小时
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
才可以下载或查看，没有帐号？
如果还不知道什么叫做数独，那么请看百度百科吧。
九宫格数独：
写的代码要求如下：
3、必须有注释，如果没有注释，你就不要贴上来了，我最讨厌没有注释的程序
4、尽可能地能求出所有解
5、在开始的时候先判断下是否有解，有的时候给出的数独根本没有解。
请高人露面吧。贴上你的c++之类的代码吧。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
最高效的是DLX算法，对任何布局可瞬间求解。但网上的程序都没注释，就不贴上来了。
& &Dancing Link算法(以下简称DLX)是解NPC难题中的精确覆盖(Exact Cover)的高效算法，一个问题，如果能转化成Exact Cover模型，则都能用DLX解。数独的解法也不列外。
& && & 对于一个N*N的(N=K*K)数独，我们可以用一个3位的N进制数rck(0&=r,c,k&N)来表示第r行第c列放的数是k+1。这样我们就可以用N*N*N个状态来表示所有可能的状态，这同时也是转化成Exact Cover后矩阵的行的个数。
& && & 而对于每一个状态rck，该状态的Exact Cover的模型放置是怎样的呢？我们可以用[0,N*N)区间表示行冲突，[N*N,2*N*N)区间表示小方块冲突，[2*N*N,3*N*N)区间表示列冲突，[3*N*N,4*N*N)区间表示k这个数放置的位置。这里的4*N*N就是转化成Exact Cover后矩阵的列的个数。
& && & 至此，数独的Exact Cover模型已经建立完毕，剩下的就是DLX算法的实现了。
非常有价值
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
风云剑 在人工智能方面研究比较深，发的帖子比较切中主题。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
被机器人弄起来的
说说我对DLX算法的体会
是将求解状态以十字链表形式保留，减少了出入栈的花费，但本质上依然是NP的，而且可能出现重复求解。
选择最短的列来寻找适合的行，在递归前几层会迅速消耗“密切相关”的行与列，造成强烈剪枝的假象；但“关系疏远”的就没有改善。以我处理过的例子，各层循环数大概为 19、15、10、6、2、1（貌似很好）、20、17、11、8、3、1（又来？）、、20、17、11、8、3、1（还来！）……19、15、10、 6、2、1…… 你慢慢玩，偶回家吃饭了。
估计DLX近似O(a^n)。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
1、DLX做对称性01矩阵时存在重复分析的情况
如下面矩阵
它实质是两个相同子矩阵组成的，按基本DLX方法，会在求左上子矩阵一解后对右下矩阵重复求解。更好的办法是分割子矩阵，然后全问题解就是两部分解的组合。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
2、再看一般的精确覆盖01矩阵，任两行、任两列的交换后解是不变的。我们可以将一个0和1均匀分布的矩阵通过行列交换变成
左下、右上都是零的矩阵：
“x” 是不能彻底划分到左侧右侧的那些行，“+”是前“x”这类行的公共列。类似DLX算法的剪枝，不过我们首先选择的是“+”这类列。很快整个01矩阵被分成 L和R两个小矩阵，再分治。
如是这般，似乎能通向O(n^v * log n)的复杂性，log n是分治成本，n^v则是每次行列交换的计算成本。v是多少在于行列交换算法成本，我现在能到 3，但交换结果一般。
行列的交换算法有很大的优化潜力。高效的交换结果应当是L和R矩阵尽量大而接近，“+”列列数少而且每列短。这样能充分发挥分割分治的优势。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
主题帖子精华
在线时间 小时
还有就是，既然矩阵任两行、任两列的交换后解是不变的，能否构建一个HASH方法，记录已计算矩阵，避免重复计算。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
Powered byLintCode 判断数独是否合法 - 简书
LintCode 判断数独是否合法
请判定一个数独是否有效。
该数独可能只填充了部分数字，其中缺少的数字用 .表示。
一个合法的数独（仅部分填充）并不一定是可解的。我们仅需使填充的空格有效即可。
什么是 数独？
上面就是一个合法数独的样例
初看上去题目似乎很复杂，其实不然。本题就是判断数组行列不能有重复元素，以及小九宫格不能有重复元素的算法。
首先，分别判断行，列，最后判断九宫格。
class Solution {
* @param board: the board
@return: wether the Sudoku is valid
public boolean isValidSudoku(char[][] board) {
boolean[] visited = new boolean[9];
for(int i = 0; i&9; i++){
Arrays.fill(visited, false);
for(int j = 0; j&9; j++){
if(!process(visited, board[i][j]))
for(int i = 0; i&9; i++){
Arrays.fill(visited, false);
for(int j = 0; j&9; j++){
if(!process(visited, board[j][i]))
// sub matrix
for(int i = 0; i&9; i+= 3){
for(int j = 0; j&9; j+= 3){
Arrays.fill(visited, false);
for(int k = 0; k&9; k++){
if(!process(visited, board[i + k/3][ j + k%3]))
private boolean process(boolean[] visited, char digit){
if(digit == '.'){
int num = digit - '0';
if ( num & 1 || num & 9 || visited[num-1]){
visited[num-1] =
作者：杨舸 跟数独游戏的结缘，是一次次的空中飞行。经常出差，如何消磨旅途时间？航空杂志都翻烂了，小说也不是每次出差都能买到好看的。一次前往澳洲，在航空免税物品杂志上看见一款数独机，觉得好像是个不错的打发时间的玩意，据说还能有益锻炼脑力。一个星期后，又正好有事前往泰国，在普吉...
难度划分 影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言，了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。市面上数独刊物良莠不齐，在书籍、报...
喜欢看《最好的我们》的人不难发现，学霸余淮特别喜欢做数独，在上课的时候也会做数独题。最近重看电视剧，想起官网上的那道数独题，看到有网友直呼数独题太难，作为余淮党&数独迷，给大家讲解一下如何解那道数独题。其实，并不难。 此前，个人先提几个建议： 1、准备纸、笔，自行先画好上图...
看了《最强大脑》这期，不禁为13岁的数独少年胡宇轩的精彩表现点赞。 通过节目，很多人对“数独”游戏产生了兴趣。我们就用3分钟来认识一下。 什么是数独 数独（Sudoku）游戏，最普遍的形式就是九宫格，即在9格乘9格的大正方形（大宫）中有9个3格乘3格的小正方...
潜伏者 原题 R 国和 S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则：1． S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘...
推荐系统架构师 工作内容： 1.参与映客直播、短视频、游戏推荐系统的技术选型。 2.设计与搭建个性化推荐系统架构，提升系统稳定性。 3.优化系统架构可扩展性，保障算法策略模块快速迭代。 任职要求： 1.精通C++语言，有服务器端大型项目开发经验，熟悉NoSQL数据库、Thr...
海苔，我们并不陌生。 早些时候，我们都会看到电视广告 比如波力海苔：海的味道~我知道~ 比如美好时光海苔：好营养，更香脆，海苔我要美好时光 这两个品牌早已经是家喻户晓，每个商场，每个大街小巷小卖部，都有着它们的身影 只是，这两种海苔味道并不是很受小朋友的喜欢，直到芝麻夹心海...
我和我的室友们 我的大学四人间。我们宿舍四个都来自不同的地方，然而我们都在江苏读书。两个安徽，一个浙江，我来自湖北。一直想把我们之间的事情站在我的角度写出来。我也不认同自己是多么完美，毕竟人无完人。 先说浙江的吧。她是我们4个之中最聪明的。可能因为她成绩好，在宿舍里有一种她...
在面向对象开发中，经常遇到多个类间传值，总结起来即正向传值（A—&B）（属性传值），反向传值（A&—B）（利用对象，使用TargetAction，使用协议代理，使用系统自带的Block，使用自定义Block），双向传值(A&—&B)（使用NSUserDefaults进行数据...
公正司法，一直以来是人们关注的热点。但是，在议论、维权、行权过程中，如何正确地言行举止，恐怕思考者不多。绝大多数人秉持的是“事不关已，高高挂起”心态，少数好事者也不过借故 “喷”几句了事，甚至跟风 “以讹传讹”。 其实，建设法治中国，促进司法公正，每个公民都不应是“旁观者”...后使用快捷导航没有帐号？
只需一步，快速开始
请完成以下验证码
请完成以下验证码
主题帖子荣誉
成熟鱼友Ⅰ, 积分 536, 距离下一级还需 64 积分
成熟鱼友Ⅰ, 积分 536, 距离下一级还需 64 积分
查看: 822|回复: 2
& 累计签到：338 天连续签到：1 天
马上注册加入鱼C，享用更多服务吧^_^
才可以下载或查看，没有帐号？
本帖最后由 andalousie 于
12:36 编辑
这个是我们程序与算法综合课程设计的一道题。叫做数独游戏。
源代码
#include &iostream&
#include &fstream&
#include &cstdlib&
#include &ctime&
#include &algorithm&
static const bitfield maskMax = 512;
static const bitfield allSet = 511;
enum difficulty { EASY, MEDIUM, DIFFICULT, EVIL, DEFAULT };
// Returns the size of the set
static unsigned bitCount(bitfield bits)
{
& & unsigned result = 0;
& & bitfield mask = 1;
& & while(mask != maskMax)
& & {
& && &&&if (bits & mask)
& && && && &result++;
& && &&&mask *= 2;
& & }
// Returns a bitfield representing {num}
static inline bitfield bitFor(unsigned num)
{
& & return 1 && (num - 1);
}
class BlankList
{
public:
& & BlankList()
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &rows[i] = cols[i] = allS
& && &&&for (unsigned i = 0; i & 3; ++i)
& && && && &for (unsigned j = 0; j & 3; ++j)
& && && && && & blocks[i][j] = allS
& & }
& & void elim(unsigned i, unsigned j, unsigned n)
& & {
& && &&&bitfield bit = bitFor(n);
& && &&&rows[i] &= ~
& && &&&cols[j] &= ~
& && &&&blocks[i/3][j/3] &= ~
& & }
& & void cancel(unsigned i, unsigned j, unsigned n)
& & {
& && &&&bitfield bit = bitFor(n);
& && &&&rows[i] |=
& && &&&cols[j] |=
& && &&&blocks[i/3][j/3] |=
& & }
& & bitfield possible(unsigned i, unsigned j)
& & {
& && &&&return rows[i] & cols[j] & blocks[i/3][j/3];
& & }
private:
& & bitfield rows[9], cols[9];
& & bitfield blocks[3][3];
};
class Board
{
public:
& & Board()
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && && & matrix[i][j] = 0;
& & }
& & Board(unsigned seed)
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && && & matrix[i][j] = 0;
& && &&&std::srand(seed);
& && &&&_random_fill();
& & }
& & void set(unsigned row, unsigned col, unsigned val)
& & {
& && &&&matrix[row][col] =
& && &&&if (matrix[row][col])
& && && && &Blank.elim(row, col, val);
& & }
& & unsigned unset(unsigned row, unsigned col)
& & {
& && &&&unsigned val = matrix[row][col];
& && &&&if (val)
& && && && &Blank.cancel(row, col, val);
& && &&&matrix[row][col] = 0;
& && &&&
& & }
& & bitfield mask_check(unsigned i, unsigned j, bitfield mask)
& & {
& && &&&return Blank.possible(i, j) &
& & }
& & bitfield house_check(bitfield possible, unsigned i, unsigned j)
& & {
& && &&&unsigned row_base = i / 3 * 3;
& && &&&unsigned col_base = j / 3 * 3;
& && &&&for (unsigned row = row_ row & row_base + 3; ++row)
& && && && &for (unsigned col = col_ col & col_base + 3; ++col)
& && && && &{
& && && && && & if ((row == i && col == j) || matrix[row][col])
& && && && && && &&&
& && && && && & possible &= ~Blank.possible(row, col);
& && && && &}
& && &&&
& & }
& & bitfield rl_check(bitfield tricky, unsigned i, unsigned j)
& & {
& && &&&bitfield row_hidden = allS
& && &&&bitfield col_hidden = allS
& && &&&for (unsigned row = 0; row & 9; ++row)
& && && && &if (!matrix[row][j] && row != i)
& && && && && & col_hidden &= ~Blank.possible(row, j);
& && &&&for (unsigned col = 0; col & 9; ++col)
& && && && &if (!matrix[i][col] && col != j)
& && && && && & row_hidden &= ~Blank.possible(i, col);
& && &&&return tricky & (row_hidden | col_hidden);
& & }
& & void hidden_fill()
& & {
& && &&&
& && &&&do
& && &&&{
& && && && &again =
& && && && &for (unsigned i = 0; i & 9; ++i)
& && && && &{
& && && && && & for (unsigned j = 0; j & 9; ++j)
& && && && && & {
& && && && && && &&&if (matrix[i][j])
& && && && && && &&&bitfield possible = Blank.possible(i, j);
& && && && && && &&&if (bitCount(possible) == 1)
& && && && && && &&&{
& && && && && && && && &set(i, j, numFor(possible));
& && && && && && && && &again =
& && && && && && && && &
& && && && && && &&&}
& && && && && && &&&bitfield tricky = house_check(possible, i, j);
& && && && && && &&&if (bitCount(tricky) == 1)
& && && && && && &&&{
& && && && && && && && &set(i, j, numFor(tricky));
& && && && && && && && &again =
& && && && && && && && &
& && && && && && &&&}
& && && && && && &&&tricky = rl_check(tricky, i, j);
& && && && && && &&&if (bitCount(tricky) == 1)
& && && && && && &&&{
& && && && && && && && &set(i, j, numFor(tricky));
& && && && && && && && &again =
& && && && && && && && &
& && && && && && &&&}
& && && && && & }
& && && && &}
& && &&&}
& && &&&while (again);
& & }
& & unsigned remaining()
& & {
& && &&&unsigned count = 0;
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && && & if (!matrix[i][j])
& && && && && && &&&++
& && &&&
& & }
& & bool findMin(unsigned& row, unsigned& col)
& & {
& && &&&bool found =
& && &&&unsigned count = 10;
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & if (!matrix[i][j] &&
& && && && && && && && &bitCount(Blank.possible(i, j)) & count)
& && && && && & {
& && && && && && &&&count = bitCount(Blank.possible(i, j));
& && && && && && &&&row =
& && && && && && &&&col =
& && && && && && &&&found =
& && && && && & }
& && && && &}
& && &&&
& & }
& & bool backtrack(unsigned depth)
& & {
& && &&&unsigned row,
& && &&&if (!findMin(row, col))
& && && && &if (!depth)
& && && && && &
& && && && &else
& && && && && &
& && &&&// Iterate through the possible values this cell could have
& && &&&unsigned num = 1;
& && &&&bitfield mask = bitFor(num);
& && &&&while (mask != maskMax)
& && &&&{
& && && && &if (mask_check(row, col, mask))
& && && && &{
& && && && && & set(row, col, num);
& && && && && & if (backtrack(depth-1))
& && && && && && &&&
& && && && && & unset(row, col);
& && && && &}
& && && && &// Advance to the next number
& && && && &mask *= 2;
& && && && &num++;
& && &&&}
& && &&&
& & }
& & unsigned value(unsigned i, unsigned j)
& & {
& && &&&return matrix[i][j];
& & }
& & bool assert(unsigned i, unsigned j, unsigned val)
& & {
& && &&&return matrix[i][j] ==
& & }
& & void print_board(std::ostream & out)
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & out && matrix[i][j] && & &;
& && && && &}
& && && && &out && std::
& && &&&}
& & }
private:
& & unsigned matrix[9][9];
& & BlankList B
& & static unsigned numFor(bitfield bit)
& & {
& && &&&unsigned num = 0;
& && &&&while (bit)
& && &&&{
& && && && &bit &&= 1;
& && && && &++
& && &&&}
& && &&&
& & }
& & bool _fill(bool is_big, unsigned place,
& && && && && &unsigned num, bitfield usable = allSet)
& & {
& && &&&if (is_big)
& && &&&{
& && && && &if (num == 10)
& && && && && &
& && && && &if (place == 9)
& && && && && & return _fill(is_big, 0, num + 1);
& && &&&}
& && &&&if (place == 9)
& && && && &
& && &&&static unsigned look_up[] =
& && &&&{
& && && && &0,&&1,&&2,
& && && && &9,&&10, 11,
& && && && &18, 19, 20
& && &&&};
& && &&&static unsigned base[] =
& && &&&{
& && && && &0,&&3,&&6,
& && && && &27, 30, 33,
& && && && &54, 57, 60
& && &&&};
& && &&&
& && &&&bitfield usable_blocks = allS
& && &&&while (usable_blocks)
& && &&&{
& && && && &while (true)
& && && && &{
& && && && && & block = std::rand() % 9;
& && && && && & if (usable_blocks & bitFor(block + 1))
& && && && && && &&&
& && && && &}
& && && && &usable_blocks &= ~bitFor(block + 1);
& && && && &if (bitFor(block + 1) & usable)
& && && && &{
& && && && && & unsigned loc = base[block] + look_up[place];
& && && && && & unsigned row = loc / 9, col = loc % 9;
& && && && && & if (!matrix[row][col] &&
& && && && && && && && &(bitFor(num) & Blank.possible(row, col)))
& && && && && & {
& && && && && && &&&set(row, col, num);
& && && && && && &&&usable &= ~bitFor(block + 1);
& && && && && && &&&if (_fill(is_big, place + 1, num, usable))
& && && && && && && && &
& && && && && && &&&unset(row, col);
& && && && && && &&&usable |= bitFor(block + 1);
& && && && && & }
& && && && &}
& && &&&}
& && &&&
& & }
& & void _random_fill()
& & {
& && &&&for (unsigned i = 1; i &= 4; ++i)
& && && && &_fill(false, 0, i);
& && &&&while (true)
& && && && &if (_fill(true, 0, 5))
& && && && && &
& & }
};
class Holes
{
public:
& & Holes(Board & board)
& && &&&: puzzle(board)
& & {}
& & void digHoles(difficulty level)
& & {
& && &&&static unsigned look_up[] =
& && &&&{
& && && && &0,&&1,&&2,
& && && && &9,&&10, 11,
& && && && &18, 19, 20
& && &&&};
& && &&&static unsigned base[] =
& && &&&{
& && && && &0,&&3,&&6,
& && && && &27, 30, 33,
& && && && &54, 57, 60
& && &&&};
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &unsigned array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
& && && && &unsigned diff = _random_by_level(level);
& && && && &std::random_shuffle(array, array + 9);
& && && && &for (unsigned j = 0; j & ++j)
& && && && &{
& && && && && & unsigned loc = base[i] + look_up[array[j]];
& && && && && & unsigned row = loc / 9, col = loc % 9;
& && && && && & _valid_dig(row, col, level);
& && && && &}
& && &&&}
& & }
& & Board& to_play()
& & {
& && &&&
& & }
private:
& & B
& & unsigned _random_by_level(difficulty level)
& & {
& && &&&unsigned random = 5;
& && &&&switch (level)
& && &&&{
& && &&&case EASY:
& && && && &random = std::rand() % 2 + 4;
& && && && &
& && &&&case MEDIUM:
& && && && &random = std::rand() % 3 + 5;
& && && && &
& && &&&case DIFFICULT:
& && && && &random = std::rand() % 4 + 5;
& && &&&case EVIL:
& && && && &random = std::rand() % 4 + 6;
& && && && &
& && &&&default:
& && && && &
& && &&&}
& && &&&
& & }
& & void _valid_dig(unsigned i, unsigned j, difficulty level)
& & {
& && &&&unsigned val = puzzle.unset(i, j);
& && &&&for (unsigned num = 1; num &= 9; ++num)
& && &&&{
& && && && &if (num != val &&
& && && && && && &&&puzzle.mask_check(i, j, bitFor(num)))
& && && && &{
& && && && && & Board bd =
& && && && && & bd.set(i, j, num);
& && && && && & bd.hidden_fill();
& && && && && & if (bd.backtrack(bd.remaining()))
& && && && && & {
& && && && && && &&&puzzle.set(i, j, val);
& && && && && && &&&
& && && && && & }
& && && && &}
& && &&&}
& & }
};
class Sudoku
{
public:
& & Sudoku(const char * name, bool play = false)
& && &&&: in(name)
& & {
& && &&&unsigned num = 0;
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & in &&
& && && && && & _board.set(i, j, num);
& && && && &}
& && &&&}
& && &&&_board.print_board(std::cout);
& && &&&_answer = _
& && &&&if (_solve())
& && &&&{
& && && && &if (!play)
& && && && &{
& && && && && & std::cout && &The answer is:& && std::
& && && && && & _answer.print_board(std::cout);
& && && && &}
& && &&&}
& && &&&else
& && && && &std::cout && &The sudoku is not solvable!& && std::
& & }
& & Sudoku(difficulty level, std::ostream & out)
& & {
& && &&&generate(level, out);
& & }
& & void generate(difficulty level, std::ostream & out)
& & {
& && &&&_answer = Board(static_cast&unsigned&(std::time(0)));
& && &&&Holes game(_answer);
& && &&&game.digHoles(level);
& && &&&_board = game.to_play();
& && &&&_board.print_board(out);
& & }
& & void play(unsigned& row, unsigned& col, unsigned& val)
& & {
& && &&&if (_board.mask_check(row, col, bitFor(val)))
& && && && &if (_answer.assert(row, col, val))
& && && && &{
& && && && && & _board.set(row, col, val);
& && && && && & system(&cls&);
& && && && && & _board.print_board(std::cout);
& && && && &}
& && && && &else
& && && && && & std::cout && &You've chosen the wrong number.\n&;
& && &&&else
& && && && &std::cout && &Your play violated the rules.\n&;
& & }
& & bool is_complete()
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && && & if (!_answer.assert(i, j, _board.value(i, j)))
& && && && && && &&&
& && &&&
& & }
private:
& & std::
& & Board _
& & Board _
& & bool _solve()
& & {
& && &&&_answer.hidden_fill();
& && &&&if (_answer.backtrack(_answer.remaining()))
& && && && &
& && &&&else
& && && && &
& & }
};
int main()
{
& & char mode = 0;
& & std::cout && &Input puzzle file (I) or Generate one (G): &;
& & std::cin &&
& & if (mode == 'I')
& & {
& && &&&char file[100];
& && &&&
& && &&&std::cout && &Please specify the file: &;
& && &&&std::cin &&
AM:
& && &&&std::cout && &Automatically (A) solve it or Manually (M): &;
& && &&&std::cin &&
& && &&&if (mode == 'A')
& && && && &flag =
& && &&&else if (mode == 'M')
& && && && &flag =
& && &&&else
& && &&&{
& && && && &std::cout && &Invalid Input!\n&;
& && && && &goto AM;
& && &&&}
& && &&&system(&cls&);
& && &&&Sudoku puzzle(file, flag);
& && &&&if (flag)
& && &&&{
& && && && &unsigned row, col,
& && && && &while (!puzzle.is_complete())
& && && && &{
& && && && && & std::cout && &Enter a position and a number (i, j, num): &;
& && && && && & std::cin && row && col &&
& && && && && & puzzle.play(row, col, val);
& && && && &}
& && && && &std::cout && &You have completed the puzzle.& && std::
& && &&&}
& & }
& & else if (mode == 'G')
& & {
& && &&&std::cout && &Which Level: Easy (E) Medium (M) Difficult(D) Evil(U) &;
& && &&&std::cin &&
& && &&&
& && &&&
& && &&&switch (mode)
& && &&&{
& && &&&case 'E':
& && && && &level = EASY;
& && && && &
& && &&&case 'M':
& && && && &level = MEDIUM;
& && && && &
& && &&&case 'D':
& && && && &level = DIFFICULT;
& && && && &
& && &&&case 'U':
& && && && &level = EVIL;
& && && && &
& && &&&default:
& && && && &level = DEFAULT;
& && && && &
& && &&&}
SP:
& && &&&std::cout && &Save it to a file (S) or Play now (P): &;
& && &&&std::cin &&
& && &&&if (mode == 'S')
& && && && &flag =
& && &&&else if (mode == 'P')
& && && && &flag =
& && &&&else
& && &&&{
& && && && &std::cout && &Invalid Input!\n&;
& && && && &goto SP;
& && &&&}
& && &&&if (flag)
& && &&&{
& && && && &system(&cls&);
& && && && &Sudoku puzzle(level, std::cout);
& && && && &unsigned row, col,
& && && && &while (!puzzle.is_complete())
& && && && &{
& && && && && & std::cout && &Enter a position and a number (i, j, num): &;
& && && && && & std::cin && row && col &&
& && && && && & puzzle.play(row, col, val);
& && && && &}
& && && && &std::cout && &You have completed the puzzle.& && std::
& && &&&}
& && &&&else
& && &&&{
& && && && &std::ofstream ofs(&Sudoku.out&);
& && && && &Sudoku puzzle(level, ofs);
& && && && &std::cout && &Saved as Sudoku.out& && std::
& && &&&}
& & }
& & system(&pause&);
}复制代码可执行文件
(8.63 KB, 下载次数: 0)
07:50 上传
点击文件名下载附件
& 累计签到：338 天连续签到：1 天
（1） 需求和规格说明在一个9×9的大正方形中，包含9个3×3的小正方形。如图4所示。可以看到，其每行、每列、每个小正方形，都有9个空格。要求只用1到9这些数字，填满大正方形中所有的81个空格，同时满足：（1）在每列的9个空格中分别填入1到9，且每个数字在此列中只能出现一次；（2）在每行的9个空格中分别填入1到9，且每个数字在此行中只能出现一次；（3）在每个小正方形的9个空格中分别填入1到9，且每个数字在此正方形中只能出现一次；游戏一开始会给定了某些空格的值。参加游戏的人根据这些已知的值以及上面的约束条件，推理出剩余的空格的值。（2） 设计根据上述需求，采用unsigned类型进行存储，并且通过简单的位运算来获取对应的格子上可填入的数字。有两个基本类：BlankList和Board，分别用来获取数独上空白位置可填入的数字，以及对一个数独棋盘的一系列操作。另外，还有一个作为用户接口的类Sudoku，提供初始化数独、生成数独、以及数独求解的操作；一个Holes类，用来给已经生成的完全数独进行“挖洞”，以生成真正的数独。由于各个类的功用和数据相同成分不多，因此我采用的是潜入对象的做法，而没有使用继承。除了少数需要全局使用的变量和函数意外，数据基本都封装在各个类里面。在参考网上一些代码的基础上，我自己特别补充了hidden_fill方法，个人认为可以一定程度缩小解空间，所以引入了此方法对数独中naked single类型、hiddensingle类型、还有full house类型的确定解进行了筛查。之后再进行回溯进行求解。生成棋盘则是采用了回溯的方法，而不是采用Las Vegas的随机方法，旨在使完全数独生成更加随机化。属性和方法定义& &类名& &
对应行可填数
对应列可填数
对应房子可填数
elim(unsigned, unsigned,&&unsigned)
在增添数据时，从可填数中除去该数字
cancel(unsigned, unsigned,&&unsigned)
在删除数据时，从可填数中增添该数字
possible(unsigned,&&unsigned)
返回对应格子的可填数（在只考虑行、列、房子不冲突的情况下）
matrix[9][9]
9*9格子的二维数组
嵌入的BlankList对象，用于存储可填数
构造函数，用于已存在的数独
Board(unsigned)
传入随机数种子的构造函数，用于生成新的完全数独
set(unsigned, unsigned, unsigned)
用于设置一个格子上的值
unset(unsigned, unsigned)
用于取消设置一个格子的值，并返回取消的值
mask_check(unsigned,&&unsigned, bitfield mask)
检查mask代表的数字中可填的
house_check(bitfield,&&unsigned, unsigned)
从possible里筛选出需要填的格子意外同一个房子中，其他未填格子中都不可能的数
rl_check(bitfield,&&unsigned unsigned)
从tricky里筛选出对应行或对应列中，其他未填格子中都不可能的数
hidden_fill()
填入可以确定的值
remaining()
未填的格子数量
findMin(unsigned&, unsigned&)
查找可填数数量最少的格子
backtrack(unsigned)
value(unsigned, unsigned)
(i, j)格子中的值
assert(unsigned, unsigned,&&unsigned)
确认(i, j)中的值是否为val
print_board(std::ostream&&&)
输出整个数独
_fill(bool, unsigned,&&unsigned, bitfield)
完全数独的填充，针对填入数大小决定是否回溯到上一个数
_random_fill()
递归完全数独填充，调用_fill函数
嵌入的Board对象
digHoles(difficulty)
“挖洞”操作
返回挖洞结束的数独
_random_by_level(difficulty)
根据难度随机生成每个房子里挖洞的数目
_valid_dig(unsigned,&&unsigned, difficulty)
只挖有效的洞（要求挖完剩下的是有唯一解的数独）
std::ifstream
输入文件流
正在使用的数独
当前数独的答案
Sudoku(const char *, bool)
输入文件的构造函数
Sudoku(difficulty, std::ostream &)
自动产生数独的构造函数
generate(difficulty, std::ostream &)
产生一个给定难度的数独
play(unsigned&,unsigned&, unsigned&)
玩家输入对应位置数值
is_complete()
确认是否正确完成
& 累计签到：338 天连续签到：1 天
本帖最后由 andalousie 于
16:12 编辑
新的测试代码，部分。
class Board
{
public:
& & Board()
& && &&&: remains(81)
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & matrix[i][j] = 0;
& && && && && & memory[i][j] = allS
& && && && &}
& & }
& & Board(unsigned seed)
& && &&&: remains(81)
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & matrix[i][j] = 0;
& && && && && & memory[i][j] = allS
& && && && &}
& && &&&std::srand(seed);
& && &&&_random_fill();
& & }
& & void set(unsigned row, unsigned col, unsigned val, bool advanced = false)
& & {
& && &&&matrix[row][col] =
& && &&&if (matrix[row][col])
& && &&&{
& && && && &Blank.elim(row, col, val);
& && && && &--
& && &&&}
& && &&&if (advanced)
& && && && &_update(row, col);
& & }
& & unsigned unset(unsigned row, unsigned col)
& & {
& && &&&unsigned val = matrix[row][col];
& && &&&if (val)
& && &&&{
& && && && &Blank.cancel(row, col, val);
& && && && &++
& && &&&}
& && &&&matrix[row][col] = 0;
& && &&&
& & }
& & bitfield mask_check(unsigned i, unsigned j, bitfield mask)
& & {
& && &&&return Blank.possible(i, j) & mask & memory[i][j];
& & }
& & bitfield house_check(unsigned i, unsigned j, bool advanced = false)
& & {
& && &&&bitfield house_hidden = allS
& && &&&unsigned row_base = i / 3 * 3;
& && &&&unsigned col_base = j / 3 * 3;
& && &&&for (unsigned row = row_ row & row_base + 3; ++row)
& && && && &for (unsigned col = col_ col & col_base + 3; ++col)
& && && && &{
& && && && && & if ((row == i && col == j) || matrix[row][col])
& && && && && && &&&
& && && && && & house_hidden &= advanced ? ~memory[row][col] : ~Blank.possible(row, col);
& && && && &}
& && &&&return house_
& & }
& & bitfield row_check(unsigned i, unsigned j, bool advanced = false)
& & {
& && &&&bitfield row_hidden = allS
& && &&&for (unsigned col = 0; col & 9; ++col)
& && && && &if (!matrix[i][col] && col != j)
& && && && && & row_hidden &= advanced ? ~memory[i][col] : ~Blank.possible(i, col);
& && &&&return row_
& & }
& & bitfield col_check(unsigned i, unsigned j, bool advanced = false)
& & {
& && &&&bitfield col_hidden = allS
& && &&&for (unsigned row = 0; row & 9; ++row)
& && && && &if (!matrix[row][j] && row != i)
& && && && && & col_hidden &= advanced ? ~memory[row][j] : ~Blank.possible(row, j);
& && &&&return col_
& & }
& & bitfield decide(bitfield & possible, bitfield & house,
& && && && && && &&&bitfield & row,& && &bitfield & col)
& & {
& && &&&if (bitCount(possible) == 1)
& && && && &
& && &&&bitfield check1 = possible &
& && &&&if (bitCount(check1) == 1)
& && && && &return check1;
& && &&&bitfield check2 = possible &
& && &&&if (bitCount(check2) == 1)
& && && && &return check2;
& && &&&bitfield check3 = possible &
& && &&&if (bitCount(check3) == 1)
& && && && &return check3;
& && &&&bitfield check = check1 & check2;
& && &&&if (bitCount(check) == 1)
& && && && &
& && &&&check = check1 & check3;
& && &&&if (bitCount(check) == 1)
& && && && &
& && &&&check = check2 & check3;
& && &&&if (bitCount(check) == 1)
& && && && &
& && &&&check &= check1;
& && &&&if (bitCount(check) == 1)
& && && && &
& && &&&return 0;
& & }
& & void hidden_fill()
& & {
& && &&&
& && &&&do
& && &&&{
& && && && &again =
& && && && &for (unsigned i = 0; i & 9; ++i)
& && && && &{
& && && && && & for (unsigned j = 0; j & 9; ++j)
& && && && && & {
& && && && && && &&&if (matrix[i][j])
& && && && && && &&&bitfield possible = Blank.possible(i, j);
& && && && && && &&&bitfield house = house_check(i, j);
& && && && && && &&&bitfield row = row_check(i, j);
& && && && && && &&&bitfield col = col_check(i, j);
& && && && && && &&&bitfield to_check = decide(possible, house, row, col);
& && && && && && &&&if (to_check)
& && && && && && &&&{
& && && && && && && && &set(i, j, numFor(to_check));
& && && && && && && && &again =
& && && && && && &&&}
& && && && && & }
& && && && &}
& && &&&}
& && &&&while (again);
& & }
& & bitfield candidate_check(unsigned i, unsigned j)
& & {
& && &&&bitfield row_locked(0), col_locked(0), row_i(0), col_j(0);
& && &&&unsigned row_base = i / 3 * 3;
& && &&&unsigned col_base = j / 3 * 3;
& && &&&unsigned total_count = 0;
& && &&&for (unsigned row = row_ row & row_base + 3; ++row)
& && &&&{
& && && && &if (row == i)
& && && && &{
& && && && && & for (unsigned col = col_ col & col_base + 3; ++col)
& && && && && & {
& && && && && && &&&if (matrix[row][col])
& && && && && && && && &
& && && && && && &&&row_i |= memory[row][col];
& && && && && & }
& && && && &}
& && && && &else
& && && && &{
& && && && && & for (unsigned col = col_ col & col_base + 3; ++col)
& && && && && & {
& && && && && && &&&if (matrix[row][col])
& && && && && && && && &
& && && && && && &&&row_locked |= memory[row][col];
& && && && && && &&&++total_
& && && && && & }
& && && && &}
& && &&&}
& && &&&if (total_count && total_count == bitCount(row_locked))
& && && && &memory[i][j] &= ~row_
& && &&&bitfield pointing = row_i & ~row_
& && &&&if (pointing)
& && && && &for (unsigned col = 0; col & 9; ++col)
& && && && &{
& && && && && & if (matrix[i][col] || (col &= col_base && col & col_base + 3))
& && && && && && &&&
& && && && && & memory[i][col] &= ~
& && && && &}
& && &&&total_count = 0;
& && &&&for (unsigned col = col_ col & col_base + 3; ++col)
& && &&&{
& && && && &if (col == j)
& && && && &{
& && && && && & for (unsigned row = row_ row & row_base + 3; ++row)
& && && && && & {
& && && && && && &&&if (matrix[row][col])
& && && && && && && && &
& && && && && && &&&col_j |= memory[row][col];
& && && && && & }
& && && && &}
& && && && &else
& && && && &{
& && && && && & for (unsigned row = row_ row & row_base + 3; ++row)
& && && && && & {
& && && && && && &&&if (matrix[row][col])
& && && && && && && && &
& && && && && && &&&col_locked |= memory[row][col];
& && && && && && &&&++total_
& && && && && & }
& && && && &}
& && &&&}
& && &&&if (total_count && total_count == bitCount(col_locked))
& && && && &memory[i][j] &= ~col_
& && &&&pointing = col_j & ~col_
& && &&&if (pointing)
& && && && &for (unsigned row = 0; row & 9; ++row)
& && && && &{
& && && && && & if (matrix[row][j] || (row &= row_base && row & row_base + 3))
& && && && && && &&&
& && && && && & memory[row][j] &= ~
& && && && &}
& && && && && & for (unsigned col = 0; col & 9; ++col)
& && && && && & {
& && && && && && && && &if (matrix[i][col] || (col &= col_base && col & col_base + 3))
& && && && && && && && && && &&&
& && && && && && && && &row_i &= ~memory[i][col];
& && && && && & }
& && && && && & if (row_i)
& && && && && & {
& && && && && && && && &for (unsigned r = row_ r & row_base + 3; ++r)
& && && && && && && && && && &&&for (unsigned c = col_ c & col_base + 3; ++c)
& && && && && && && && && && &&&{
& && && && && && && && && && && && && & if (r == i || matrix[r][c])
& && && && && && && && && && && && && && && && &
& && && && && && && && && && && && && & memory[r][c] &= ~row_i;
& && && && && && && && && && &&&}
& && && && && & }
& && && && && & for (unsigned row = 0; row & 9; ++row)
& && && && && & {
& && && && && && && && &if (matrix[row][j] || (row &= row_base && row & row_base + 3))
& && && && && && && && && && &&&
& && && && && && && && &col_j &= ~memory[row][j];
& && && && && & }
& && && && && & if (col_j)
& && && && && & {
& && && && && && && && &for (unsigned r = row_ r & row_base + 3; ++r)
& && && && && && && && && && &&&for (unsigned c = col_ c & col_base + 3; ++c)
& && && && && && && && && && &&&{
& && && && && && && && && && && && && & if (c == j || matrix[r][c])
& && && && && && && && && && && && && && && && &
& && && && && && && && && && && && && & memory[r][c] &= ~col_j;
& && && && && && && && && && &&&}
& && && && && & }
& && &&&return memory[i][j];
& & }
& & void advanced_fill()
& & {
& && &&&
& && &&&
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && && & if (!matrix[i][j])
& && && && && && &&&memory[i][j] &= Blank.possible(i, j);
& && &&&do
& && &&&{
& && && && &again =
& && && && &sum& &= 0;
& && && && &for (unsigned i = 0; i & 9; ++i)
& && && && && & for (unsigned j = 0; j & 9; ++j)
& && && && && && &&&sum += memory[i][j];
& && && && &for (unsigned i = 0; i & 9; ++i)
& && && && &{
& && && && && & for (unsigned j = 0; j & 9; ++j)
& && && && && & {
& && && && && && &&&if (matrix[i][j])
& && && && && && &&&bitfield possible = candidate_check(i, j);
& && && && && && &&&//print_possible();
& && && && && && &&&bitfield house = house_check(i, j, true);
& && && && && && &&&bitfield row = row_check(i, j, true);
& && && && && && &&&bitfield col = col_check(i, j, true);
& && && && && && &&&bitfield to_check = decide(possible, house, row, col);
& && && && && && &&&if (to_check)
& && && && && && && && &set(i, j, numFor(to_check), true);
& && && && && & }
& && && && &}
& && && && &for (unsigned i = 0; i & 9; ++i)
& && && && && & for (unsigned j = 0; j & 9; ++j)
& && && && && && &&&sum -= memory[i][j];
& && && && &if (sum) again =
& && &&&}
& && &&&while (again);
& & }
& & unsigned remaining()
& & {
& && &&&
& & }
& & bool findMin(unsigned& row, unsigned& col)
& & {
& && &&&bool found =
& && &&&unsigned count = 10;
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & if (!matrix[i][j] && (bitCount(Blank.possible(i, j)
& && && && && && && && && && && && && & & memory[i][j])) & count)
& && && && && & {
& && && && && && &&&count = bitCount(Blank.possible(i, j) & memory[i][j]);
& && && && && && &&&row =
& && && && && && &&&col =
& && && && && && &&&found =
& && && && && & }
& && && && &}
& && &&&
& & }
& & bool backtrack(unsigned depth)
& & {
& && &&&unsigned row,
& && &&&if (!findMin(row, col))
& && && && &if (!depth)
& && && && && &
& && && && &else
& && && && && &
& && &&&// Iterate through the possible values this cell could have
& && &&&unsigned num = 1;
& && &&&bitfield mask = bitFor(num);
& && &&&while (mask != maskMax)
& && &&&{
& && && && &if (mask_check(row, col, mask))
& && && && &{
& && && && && & set(row, col, num);
& && && && && & if (backtrack(depth-1))
& && && && && && &&&
& && && && && & unset(row, col);
& && && && &}
& && && && &// Advance to the next number
& && && && &mask *= 2;
& && && && &num++;
& && &&&}
& && &&&
& & }
& & unsigned value(unsigned i, unsigned j)
& & {
& && &&&return matrix[i][j];
& & }
& & bool assert(unsigned i, unsigned j, unsigned val)
& & {
& && &&&return matrix[i][j] ==
& & }
& & void print_possible()
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & output && memory[i][j] && & &;
& && && && &}
& && && && &output && std::
& && &&&}
& && &&&output && std::
& & }
& & void print_board(std::ostream & out)
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & out && matrix[i][j] && & &;
& && && && &}
& && && && &out && std::
& && &&&}
& && &&&out && std::
& & }
private:
& & unsigned matrix[9][9];
& & bitfield memory[9][9];
& &
& & BlankList B
& & static unsigned numFor(bitfield bit)
& & {
& && &&&unsigned num = 0;
& && &&&while (bit)
& && &&&{
& && && && &bit &&= 1;
& && && && &++
& && &&&}
& && &&&
& & }
& & void _update(unsigned row, unsigned col)
& & {
& && &&&unsigned row_base = row / 3 * 3;
& && &&&unsigned col_base = col / 3 * 3;
& && &&&unsigned r,
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &if (!matrix[row][i])
& && && && && & memory[row][i] &= Blank.possible(row, i);
& && && && &if (!matrix[i][col])
& && && && && & memory[i][col] &= Blank.possible(i, col);
& && && && &r = row_base + i / 3;
& && && && &c = col_base + i % 3;
& && && && &if (r != row && c != col && !matrix[r][c])
& && && && && & memory[r][c] &= Blank.possible(r, c);
& && &&&}
& & }
& & bool _fill(bool is_big, unsigned block, unsigned num)
& & {
& && &&&if (is_big)
& && &&&{
& && && && &if (num == 10)
& && && && && &
& && && && &if (block == 9)
& && && && && & return _fill(is_big, 0, num + 1);
& && &&&}
& && &&&if (block == 9)
& && && && &
& && &&&static unsigned look_up[] =
& && &&&{
& && && && &0,&&1,&&2,
& && && && &9,&&10, 11,
& && && && &18, 19, 20
& && &&&};
& && &&&static unsigned base[] =
& && &&&{
& && && && &0,&&3,&&6,
& && && && &27, 30, 33,
& && && && &54, 57, 60
& && &&&};
& && &&&
& && &&&bitfield available = allS
& && &&&while (available)
& && &&&{
& && && && &while (true)
& && && && &{
& && && && && & place = std::rand() % 9;
& && && && && & if (available & bitFor(place + 1))
& && && && && && &&&
& && && && &}
& && && && &available &= ~bitFor(place + 1);
& && && && &unsigned loc = base[block] + look_up[place];
& && && && &unsigned row = loc / 9, col = loc % 9;
& && && && &if (!matrix[row][col] &&
& && && && && && &&&(bitFor(num) & Blank.possible(row, col)))
& && && && &{
& && && && && & set(row, col, num);
& && && && && & if (_fill(is_big, block + 1, num))
& && && && && && &&&
& && && && && & unset(row, col);
& && && && &}
& && &&&}
& && &&&
& & }
& & void _random_fill()
& & {
& && &&&for (unsigned i = 1; i &= 5; ++i)
& && && && &_fill(false, 0, i);
& && &&&if (!_fill(true, 0, 6))
& && && && && && && && &std::cout && &Error& && std::
& & }
};
class Holes
{
public:
& & Holes(Board & board)
& && &&&: puzzle(board)
& & {}
& & void digHoles(difficulty level)
& & {
& && &&&static unsigned look_up[] =
& && &&&{
& && && && &0,&&1,&&2,
& && && && &9,&&10, 11,
& && && && &18, 19, 20
& && &&&};
& && &&&static unsigned base[] =
& && &&&{
& && && && &0,&&3,&&6,
& && && && &27, 30, 33,
& && && && &54, 57, 60
& && &&&};
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &unsigned array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
& && && && &unsigned diff = _random_by_level(level);
& && && && &std::random_shuffle(array, array + 9);
& && && && &for (unsigned j = 0; j & ++j)
& && && && &{
& && && && && & unsigned loc = base[i] + look_up[array[j]];
& && && && && & unsigned row = loc / 9, col = loc % 9;
& && && && && & _valid_dig(row, col, level);
& && && && &}
& && &&&}
& & }
& & Board& to_play()
& & {
& && &&&
& & }
private:
& & B
& & unsigned _random_by_level(difficulty level)
& & {
& && &&&unsigned random = 5;
& && &&&switch (level)
& && &&&{
& && &&&case EASY:
& && && && &random = std::rand() % 7 + 3;
& && && && &
& && &&&case MEDIUM:
& && && && &random = std::rand() % 5 + 3;
& && && && &
& && &&&case DIFFICULT:
& && && && &random = std::rand() % 5 + 4;
& && && && &
& && &&&case EVIL:
& && && && &random = std::rand() % 5 + 5;
& && && && &
& && &&&default:
& && && && &
& && &&&}
& && &&&
& & }
& & void _valid_dig(unsigned i, unsigned j, difficulty level)
& & {
& && &&&unsigned val = puzzle.unset(i, j);
& && && && && & if (level == EASY)
& && && && && & {
& && && && && && && && &Board bd =
& && && && && && && && &bd.hidden_fill();
& && && && && && && && &if (bd.remaining())
& && && && && && && && &{
& && && && && && && && && && &&&puzzle.set(i, j, val);
& && && && && && && && && && &&&
& && && && && && && && &}
& && && && && & }
& && &&&for (unsigned num = 1; num &= 9; ++num)
& && &&&{
& && && && &if (num != val &&
& && && && && && &&&puzzle.mask_check(i, j, bitFor(num)))
& && && && &{
& && && && && & Board bd =
& && && && && & bd.set(i, j, num);
& && && && && & bd.hidden_fill();
& && && && && && && && && && &&&bd.advanced_fill();
& && && && && & if (bd.backtrack(bd.remaining()))
& && && && && & {
& && && && && && &&&puzzle.set(i, j, val);
& && && && && && &&&
& && && && && & }
& && && && &}
& && &&&}
& & }
};
class Sudoku
{
public:
& & Sudoku(const char * name, bool play = false)
& & {
& && &&&std::ifstream in(name);
& && &&&unsigned num = 0;
& && &&&for (unsigned i = 0; i & 9; ++i)
& && &&&{
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && &{
& && && && && & in &&
& && && && && & _board.set(i, j, num);
& && && && &}
& && &&&}
& && &&&_board.print_board(std::cout);
& && &&&_answer = _
& && &&&/*& && &&&if (_solve())
& && && && && & {
& && && && && && &&&if (!play)
& && && && && && &&&{
& && && && && && && && &std::cout && &The answer is:& && std::
& && && && && && && && &_answer.print_board(std::cout);
& && && && && && &&&}
& && && && && & }
& && && && && & else
& && && && && && &&&std::cout && &The sudoku is not solvable!& && std::*/
& && &&&solve();
& & }
& & Sudoku(difficulty level, std::ostream & out)
& & {
& && &&&generate(level, out);
& & }
& & void generate(difficulty level, std::ostream & out)
& & {
& && &&&_answer = Board(static_cast&unsigned&(std::time(0)));
& && && && && & while (true)
& && && && && & {
& && && && && && && && &Holes game(_answer);
& && && && && && && && &game.digHoles(level);
& && && && && && && && &Board bd = game.to_play();
& && && && && && && && &bd.hidden_fill();
& && && && && && && && &if (level & EASY && !bd.remaining())
& && && && && && && && && && &&&
& && && && && && && && &bd.advanced_fill();
& && && && && && && && &if (level & MEDIUM && !bd.remaining())
& && && && && && && && && && &&&
& && && && && && && && &if (level & DIFFICULT && bd.remaining() & 30)
& && && && && && && && && && &&&
& && && && && && && && &_board = game.to_play();
& && && && && && && && &
& && && && && & }
& && &&&_board.print_board(out);
& & }
& & void play(unsigned& row, unsigned& col, unsigned& val)
& & {
& && &&&if (_board.mask_check(row, col, bitFor(val)))
& && && && &if (_answer.assert(row, col, val))
& && && && &{
& && && && && & _board.set(row, col, val);
& && && && && & system(&cls&);
& && && && && & _board.print_board(std::cout);
& && && && &}
& && && && &else
& && && && && & std::cout && &You've chosen the wrong number.\n&;
& && &&&else
& && && && &std::cout && &Your play violated the rules.\n&;
& & }
& & bool is_complete()
& & {
& && &&&for (unsigned i = 0; i & 9; ++i)
& && && && &for (unsigned j = 0; j & 9; ++j)
& && && && && & if (!_answer.assert(i, j, _board.value(i, j)))
& && && && && && &&&
& && &&&
& & }
private:
& & Board _
& & Board _
& & bool _solve()
& & {
& && &&&_answer.hidden_fill();
& && &&&if (_answer.backtrack(_answer.remaining()))
& && && && &
& && &&&else
& && && && &
& & }
& & void solve()
& & {
& && &&&//std::ofstream out(&Sudoku.out&);
& && &&&_answer.hidden_fill();
& && &&&_answer.advanced_fill();
& && && && && & _answer.backtrack(_answer.remaining());
& && &&&_answer.print_board(std::cout);
& & }
};复制代码
小甲鱼强烈推荐
给我一节课的时间，帮你从繁琐的工作中解脱出来！
- - - - - - - - - - - -
极客Python，新课程！！
特效不会给你基本工资，但却能让你升职加薪
- - - - - - - - - - - -
有备无患，念念不忘
移动客户端下载（未启用）
微信公众号
Powered by
Copyright &
&&& All Rights Reserved.}