这是我的数独程序，可惜不会图形界面
本帖最后由 andalousie 于 2014-7-9 12:36 编辑这个是我们程序与算法综合课程设计的一道题。叫做数独游戏。
源代码
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
typedef unsigned bitfield;
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;
}
return result;
}
// 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 = cols = allSet;
for (unsigned i = 0; i < 3; ++i)
for (unsigned j = 0; j < 3; ++j)
blocks = allSet;
}
void elim(unsigned i, unsigned j, unsigned n)
{
bitfield bit = bitFor(n);
rows &= ~bit;
cols &= ~bit;
blocks &= ~bit;
}
void cancel(unsigned i, unsigned j, unsigned n)
{
bitfield bit = bitFor(n);
rows |= bit;
cols |= bit;
blocks |= bit;
}
bitfield possible(unsigned i, unsigned j)
{
return rows & cols & blocks;
}
private:
bitfield rows, cols;
bitfield blocks;
};
class Board
{
public:
Board()
{
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
matrix = 0;
}
Board(unsigned seed)
{
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
matrix = 0;
std::srand(seed);
_random_fill();
}
void set(unsigned row, unsigned col, unsigned val)
{
matrix = val;
if (matrix)
Blank.elim(row, col, val);
}
unsigned unset(unsigned row, unsigned col)
{
unsigned val = matrix;
if (val)
Blank.cancel(row, col, val);
matrix = 0;
return val;
}
bitfield mask_check(unsigned i, unsigned j, bitfield mask)
{
return Blank.possible(i, j) & mask;
}
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_base; row < row_base + 3; ++row)
for (unsigned col = col_base; col < col_base + 3; ++col)
{
if ((row == i && col == j) || matrix)
continue;
possible &= ~Blank.possible(row, col);
}
return possible;
}
bitfield rl_check(bitfield tricky, unsigned i, unsigned j)
{
bitfield row_hidden = allSet;
bitfield col_hidden = allSet;
for (unsigned row = 0; row < 9; ++row)
if (!matrix && row != i)
col_hidden &= ~Blank.possible(row, j);
for (unsigned col = 0; col < 9; ++col)
if (!matrix && col != j)
row_hidden &= ~Blank.possible(i, col);
return tricky & (row_hidden | col_hidden);
}
void hidden_fill()
{
bool again;
do
{
again = false;
for (unsigned i = 0; i < 9; ++i)
{
for (unsigned j = 0; j < 9; ++j)
{
if (matrix) continue;
bitfield possible = Blank.possible(i, j);
if (bitCount(possible) == 1)
{
set(i, j, numFor(possible));
again = true;
continue;
}
bitfield tricky = house_check(possible, i, j);
if (bitCount(tricky) == 1)
{
set(i, j, numFor(tricky));
again = true;
continue;
}
tricky = rl_check(tricky, i, j);
if (bitCount(tricky) == 1)
{
set(i, j, numFor(tricky));
again = true;
continue;
}
}
}
}
while (again);
}
unsigned remaining()
{
unsigned count = 0;
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
if (!matrix)
++count;
return count;
}
bool findMin(unsigned& row, unsigned& col)
{
bool found = false;
unsigned count = 10;
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
{
if (!matrix &&
bitCount(Blank.possible(i, j)) < count)
{
count = bitCount(Blank.possible(i, j));
row = i;
col = j;
found = true;
}
}
return found;
}
bool backtrack(unsigned depth)
{
unsigned row, col;
if (!findMin(row, col))
if (!depth)
return true;
else
return false;
// 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))
return true;
unset(row, col);
}
// Advance to the next number
mask *= 2;
num++;
}
return false;
}
unsigned value(unsigned i, unsigned j)
{
return matrix;
}
bool assert(unsigned i, unsigned j, unsigned val)
{
return matrix == val;
}
void print_board(std::ostream & out)
{
for (unsigned i = 0; i < 9; ++i)
{
for (unsigned j = 0; j < 9; ++j)
{
out << matrix << " ";
}
out << std::endl;
}
}
private:
unsigned matrix;
BlankList Blank;
static unsigned numFor(bitfield bit)
{
unsigned num = 0;
while (bit)
{
bit >>= 1;
++num;
}
return num;
}
bool _fill(bool is_big, unsigned place,
unsigned num, bitfield usable = allSet)
{
if (is_big)
{
if (num == 10)
return true;
if (place == 9)
return _fill(is_big, 0, num + 1);
}
if (place == 9)
return true;
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
};
unsigned block;
bitfield usable_blocks = allSet;
while (usable_blocks)
{
while (true)
{
block = std::rand() % 9;
if (usable_blocks & bitFor(block + 1))
break;
}
usable_blocks &= ~bitFor(block + 1);
if (bitFor(block + 1) & usable)
{
unsigned loc = base + look_up;
unsigned row = loc / 9, col = loc % 9;
if (!matrix &&
(bitFor(num) & Blank.possible(row, col)))
{
set(row, col, num);
usable &= ~bitFor(block + 1);
if (_fill(is_big, place + 1, num, usable))
return true;
unset(row, col);
usable |= bitFor(block + 1);
}
}
}
return false;
}
void _random_fill()
{
for (unsigned i = 1; i <= 4; ++i)
_fill(false, 0, i);
while (true)
if (_fill(true, 0, 5))
break;
}
};
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 < diff; ++j)
{
unsigned loc = base + look_up];
unsigned row = loc / 9, col = loc % 9;
_valid_dig(row, col, level);
}
}
}
Board& to_play()
{
return puzzle;
}
private:
Board puzzle;
unsigned _random_by_level(difficulty level)
{
unsigned random = 5;
switch (level)
{
case EASY:
random = std::rand() % 2 + 4;
break;
case MEDIUM:
random = std::rand() % 3 + 5;
break;
case DIFFICULT:
random = std::rand() % 4 + 5;
case EVIL:
random = std::rand() % 4 + 6;
break;
default:
break;
}
return random;
}
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 = puzzle;
bd.set(i, j, num);
bd.hidden_fill();
if (bd.backtrack(bd.remaining()))
{
puzzle.set(i, j, val);
return;
}
}
}
}
};
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 >> num;
_board.set(i, j, num);
}
}
_board.print_board(std::cout);
_answer = _board;
if (_solve())
{
if (!play)
{
std::cout << "The answer is:" << std::endl;
_answer.print_board(std::cout);
}
}
else
std::cout << "The sudoku is not solvable!" << std::endl;
}
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)))
return false;
return true;
}
private:
std::ifstream in;
Board _board;
Board _answer;
bool _solve()
{
_answer.hidden_fill();
if (_answer.backtrack(_answer.remaining()))
return true;
else
return false;
}
};
int main()
{
char mode = 0;
std::cout << "Input puzzle file (I) or Generate one (G): ";
std::cin >> mode;
if (mode == 'I')
{
char file;
bool flag;
std::cout << "Please specify the file: ";
std::cin >> file;
AM:
std::cout << "Automatically (A) solve it or Manually (M): ";
std::cin >> mode;
if (mode == 'A')
flag = false;
else if (mode == 'M')
flag = true;
else
{
std::cout << "Invalid Input!\n";
goto AM;
}
system("cls");
Sudoku puzzle(file, flag);
if (flag)
{
unsigned row, col, val;
while (!puzzle.is_complete())
{
std::cout << "Enter a position and a number (i, j, num): ";
std::cin >> row >> col >> val;
puzzle.play(row, col, val);
}
std::cout << "You have completed the puzzle." << std::endl;
}
}
else if (mode == 'G')
{
std::cout << "Which Level: Easy (E) Medium (M) Difficult(D) Evil(U) ";
std::cin >> mode;
difficulty level;
bool flag;
switch (mode)
{
case 'E':
level = EASY;
break;
case 'M':
level = MEDIUM;
break;
case 'D':
level = DIFFICULT;
break;
case 'U':
level = EVIL;
break;
default:
level = DEFAULT;
break;
}
SP:
std::cout << "Save it to a file (S) or Play now (P): ";
std::cin >> mode;
if (mode == 'S')
flag = false;
else if (mode == 'P')
flag = true;
else
{
std::cout << "Invalid Input!\n";
goto SP;
}
if (flag)
{
system("cls");
Sudoku puzzle(level, std::cout);
unsigned row, col, val;
while (!puzzle.is_complete())
{
std::cout << "Enter a position and a number (i, j, num): ";
std::cin >> row >> col >> val;
puzzle.play(row, col, val);
}
std::cout << "You have completed the puzzle." << std::endl;
}
else
{
std::ofstream ofs("Sudoku.out");
Sudoku puzzle(level, ofs);
std::cout << "Saved as Sudoku.out" << std::endl;
}
}
system("pause");
}可执行文件
（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的随机方法，旨在使完全数独生成更加随机化。属性和方法定义
类名
成员类别
类型
成员名
描述
BlankList
属性
bitfield
rows
对应行可填数
bitfield
cols
对应列可填数
bitfield
blocks
对应房子可填数
方法
void
elim(unsigned, unsigned,unsigned)
在增添数据时，从可填数中除去该数字
void
cancel(unsigned, unsigned,unsigned)
在删除数据时，从可填数中增添该数字
bitfield
possible(unsigned,unsigned)
返回对应格子的可填数（在只考虑行、列、房子不冲突的情况下）
Board
属性
unsigned
matrix
9*9格子的二维数组
BlankList
Blank
嵌入的BlankList对象，用于存储可填数
方法
Board()
构造函数，用于已存在的数独
Board(unsigned)
传入随机数种子的构造函数，用于生成新的完全数独
void
set(unsigned, unsigned, unsigned)
用于设置一个格子上的值
bool
unset(unsigned, unsigned)
用于取消设置一个格子的值，并返回取消的值
bitfield
mask_check(unsigned,unsigned, bitfield mask)
检查mask代表的数字中可填的
bitfield
house_check(bitfield,unsigned, unsigned)
从possible里筛选出需要填的格子意外同一个房子中，其他未填格子中都不可能的数
bitfield
rl_check(bitfield,unsigned unsigned)
从tricky里筛选出对应行或对应列中，其他未填格子中都不可能的数
void
hidden_fill()
填入可以确定的值
unsigned
remaining()
未填的格子数量
bool
findMin(unsigned&, unsigned&)
查找可填数数量最少的格子
bool
backtrack(unsigned)
回溯求解
unsigned
value(unsigned, unsigned)
(i, j)格子中的值
bool
assert(unsigned, unsigned,unsigned)
确认(i, j)中的值是否为val
void
print_board(std::ostream&)
输出整个数独
unsigned
numFor()
bool
_fill(bool, unsigned,unsigned, bitfield)
完全数独的填充，针对填入数大小决定是否回溯到上一个数
void
_random_fill()
递归完全数独填充，调用_fill函数
Holes
属性
Board
puzzle
嵌入的Board对象
方法
void
digHoles(difficulty)
“挖洞”操作
Board
to_play
返回挖洞结束的数独
unsigned
_random_by_level(difficulty)
根据难度随机生成每个房子里挖洞的数目
void
_valid_dig(unsigned,unsigned, difficulty)
只挖有效的洞（要求挖完剩下的是有唯一解的数独）
Sudoku
属性
std::ifstream
in
输入文件流
Board
_board
正在使用的数独
Board
_answer
当前数独的答案
方法
Sudoku(const char *, bool)
输入文件的构造函数
Sudoku(difficulty, std::ostream &)
自动产生数独的构造函数
void
generate(difficulty, std::ostream &)
产生一个给定难度的数独
void
play(unsigned&,unsigned&, unsigned&)
玩家输入对应位置数值
bool
is_complete()
确认是否正确完成
bool
_solve()
求解过程
本帖最后由 andalousie 于 2014-7-11 16:12 编辑
新的测试代码，部分。
class Board
{
public:
Board()
: remains(81)
{
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
{
matrix = 0;
memory = allSet;
}
}
Board(unsigned seed)
: remains(81)
{
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
{
matrix = 0;
memory = allSet;
}
std::srand(seed);
_random_fill();
}
void set(unsigned row, unsigned col, unsigned val, bool advanced = false)
{
matrix = val;
if (matrix)
{
Blank.elim(row, col, val);
--remains;
}
if (advanced)
_update(row, col);
}
unsigned unset(unsigned row, unsigned col)
{
unsigned val = matrix;
if (val)
{
Blank.cancel(row, col, val);
++remains;
}
matrix = 0;
return val;
}
bitfield mask_check(unsigned i, unsigned j, bitfield mask)
{
return Blank.possible(i, j) & mask & memory;
}
bitfield house_check(unsigned i, unsigned j, bool advanced = false)
{
bitfield house_hidden = allSet;
unsigned row_base = i / 3 * 3;
unsigned col_base = j / 3 * 3;
for (unsigned row = row_base; row < row_base + 3; ++row)
for (unsigned col = col_base; col < col_base + 3; ++col)
{
if ((row == i && col == j) || matrix)
continue;
house_hidden &= advanced ? ~memory : ~Blank.possible(row, col);
}
return house_hidden;
}
bitfield row_check(unsigned i, unsigned j, bool advanced = false)
{
bitfield row_hidden = allSet;
for (unsigned col = 0; col < 9; ++col)
if (!matrix && col != j)
row_hidden &= advanced ? ~memory : ~Blank.possible(i, col);
return row_hidden;
}
bitfield col_check(unsigned i, unsigned j, bool advanced = false)
{
bitfield col_hidden = allSet;
for (unsigned row = 0; row < 9; ++row)
if (!matrix && row != i)
col_hidden &= advanced ? ~memory : ~Blank.possible(row, j);
return col_hidden;
}
bitfield decide(bitfield & possible, bitfield & house,
bitfield & row, bitfield & col)
{
if (bitCount(possible) == 1)
return possible;
bitfield check1 = possible & house;
if (bitCount(check1) == 1)
return check1;
bitfield check2 = possible & row;
if (bitCount(check2) == 1)
return check2;
bitfield check3 = possible & col;
if (bitCount(check3) == 1)
return check3;
bitfield check = check1 & check2;
if (bitCount(check) == 1)
return check;
check = check1 & check3;
if (bitCount(check) == 1)
return check;
check = check2 & check3;
if (bitCount(check) == 1)
return check;
check &= check1;
if (bitCount(check) == 1)
return check;
return 0;
}
void hidden_fill()
{
bool again;
do
{
again = false;
for (unsigned i = 0; i < 9; ++i)
{
for (unsigned j = 0; j < 9; ++j)
{
if (matrix) continue;
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 = true;
}
}
}
}
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_base; row < row_base + 3; ++row)
{
if (row == i)
{
for (unsigned col = col_base; col < col_base + 3; ++col)
{
if (matrix)
continue;
row_i |= memory;
}
}
else
{
for (unsigned col = col_base; col < col_base + 3; ++col)
{
if (matrix)
continue;
row_locked |= memory;
++total_count;
}
}
}
if (total_count && total_count == bitCount(row_locked))
memory &= ~row_locked;
bitfield pointing = row_i & ~row_locked;
if (pointing)
for (unsigned col = 0; col < 9; ++col)
{
if (matrix || (col >= col_base && col < col_base + 3))
continue;
memory &= ~pointing;
}
total_count = 0;
for (unsigned col = col_base; col < col_base + 3; ++col)
{
if (col == j)
{
for (unsigned row = row_base; row < row_base + 3; ++row)
{
if (matrix)
continue;
col_j |= memory;
}
}
else
{
for (unsigned row = row_base; row < row_base + 3; ++row)
{
if (matrix)
continue;
col_locked |= memory;
++total_count;
}
}
}
if (total_count && total_count == bitCount(col_locked))
memory &= ~col_locked;
pointing = col_j & ~col_locked;
if (pointing)
for (unsigned row = 0; row < 9; ++row)
{
if (matrix || (row >= row_base && row < row_base + 3))
continue;
memory &= ~pointing;
}
for (unsigned col = 0; col < 9; ++col)
{
if (matrix || (col >= col_base && col < col_base + 3))
continue;
row_i &= ~memory;
}
if (row_i)
{
for (unsigned r = row_base; r < row_base + 3; ++r)
for (unsigned c = col_base; c < col_base + 3; ++c)
{
if (r == i || matrix)
continue;
memory &= ~row_i;
}
}
for (unsigned row = 0; row < 9; ++row)
{
if (matrix || (row >= row_base && row < row_base + 3))
continue;
col_j &= ~memory;
}
if (col_j)
{
for (unsigned r = row_base; r < row_base + 3; ++r)
for (unsigned c = col_base; c < col_base + 3; ++c)
{
if (c == j || matrix)
continue;
memory &= ~col_j;
}
}
return memory;
}
void advanced_fill()
{
bool again;
unsigned sum;
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
if (!matrix)
memory &= Blank.possible(i, j);
do
{
again = false;
sum = 0;
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
sum += memory;
for (unsigned i = 0; i < 9; ++i)
{
for (unsigned j = 0; j < 9; ++j)
{
if (matrix) continue;
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;
if (sum) again = true;
}
while (again);
}
unsigned remaining()
{
return remains;
}
bool findMin(unsigned& row, unsigned& col)
{
bool found = false;
unsigned count = 10;
for (unsigned i = 0; i < 9; ++i)
for (unsigned j = 0; j < 9; ++j)
{
if (!matrix && (bitCount(Blank.possible(i, j)
& memory)) < count)
{
count = bitCount(Blank.possible(i, j) & memory);
row = i;
col = j;
found = true;
}
}
return found;
}
bool backtrack(unsigned depth)
{
unsigned row, col;
if (!findMin(row, col))
if (!depth)
return true;
else
return false;
// 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))
return true;
unset(row, col);
}
// Advance to the next number
mask *= 2;
num++;
}
return false;
}
unsigned value(unsigned i, unsigned j)
{
return matrix;
}
bool assert(unsigned i, unsigned j, unsigned val)
{
return matrix == val;
}
void print_possible()
{
for (unsigned i = 0; i < 9; ++i)
{
for (unsigned j = 0; j < 9; ++j)
{
output << memory << " ";
}
output << std::endl;
}
output << std::endl;
}
void print_board(std::ostream & out)
{
for (unsigned i = 0; i < 9; ++i)
{
for (unsigned j = 0; j < 9; ++j)
{
out << matrix << " ";
}
out << std::endl;
}
out << std::endl;
}
private:
unsigned matrix;
bitfield memory;
unsigned remains;
BlankList Blank;
static unsigned numFor(bitfield bit)
{
unsigned num = 0;
while (bit)
{
bit >>= 1;
++num;
}
return num;
}
void _update(unsigned row, unsigned col)
{
unsigned row_base = row / 3 * 3;
unsigned col_base = col / 3 * 3;
unsigned r, c;
for (unsigned i = 0; i < 9; ++i)
{
if (!matrix)
memory &= Blank.possible(row, i);
if (!matrix)
memory &= Blank.possible(i, col);
r = row_base + i / 3;
c = col_base + i % 3;
if (r != row && c != col && !matrix)
memory &= Blank.possible(r, c);
}
}
bool _fill(bool is_big, unsigned block, unsigned num)
{
if (is_big)
{
if (num == 10)
return true;
if (block == 9)
return _fill(is_big, 0, num + 1);
}
if (block == 9)
return true;
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
};
unsigned place;
bitfield available = allSet;
while (available)
{
while (true)
{
place = std::rand() % 9;
if (available & bitFor(place + 1))
break;
}
available &= ~bitFor(place + 1);
unsigned loc = base + look_up;
unsigned row = loc / 9, col = loc % 9;
if (!matrix &&
(bitFor(num) & Blank.possible(row, col)))
{
set(row, col, num);
if (_fill(is_big, block + 1, num))
return true;
unset(row, col);
}
}
return false;
}
void _random_fill()
{
for (unsigned i = 1; i <= 5; ++i)
_fill(false, 0, i);
if (!_fill(true, 0, 6))
std::cout << "Error" << std::endl;
}
};
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 < diff; ++j)
{
unsigned loc = base + look_up];
unsigned row = loc / 9, col = loc % 9;
_valid_dig(row, col, level);
}
}
}
Board& to_play()
{
return puzzle;
}
private:
Board puzzle;
unsigned _random_by_level(difficulty level)
{
unsigned random = 5;
switch (level)
{
case EASY:
random = std::rand() % 7 + 3;
break;
case MEDIUM:
random = std::rand() % 5 + 3;
break;
case DIFFICULT:
random = std::rand() % 5 + 4;
break;
case EVIL:
random = std::rand() % 5 + 5;
break;
default:
break;
}
return random;
}
void _valid_dig(unsigned i, unsigned j, difficulty level)
{
unsigned val = puzzle.unset(i, j);
if (level == EASY)
{
Board bd = puzzle;
bd.hidden_fill();
if (bd.remaining())
{
puzzle.set(i, j, val);
return;
}
}
for (unsigned num = 1; num <= 9; ++num)
{
if (num != val &&
puzzle.mask_check(i, j, bitFor(num)))
{
Board bd = puzzle;
bd.set(i, j, num);
bd.hidden_fill();
bd.advanced_fill();
if (bd.backtrack(bd.remaining()))
{
puzzle.set(i, j, val);
return;
}
}
}
}
};
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 >> num;
_board.set(i, j, num);
}
}
_board.print_board(std::cout);
_answer = _board;
/* if (_solve())
{
if (!play)
{
std::cout << "The answer is:" << std::endl;
_answer.print_board(std::cout);
}
}
else
std::cout << "The sudoku is not solvable!" << std::endl;*/
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())
continue;
bd.advanced_fill();
if (level > MEDIUM && !bd.remaining())
continue;
if (level > DIFFICULT && bd.remaining() < 30)
continue;
_board = game.to_play();
break;
}
_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)))
return false;
return true;
}
private:
Board _board;
Board _answer;
bool _solve()
{
_answer.hidden_fill();
if (_answer.backtrack(_answer.remaining()))
return true;
else
return false;
}
void solve()
{
//std::ofstream out("Sudoku.out");
_answer.hidden_fill();
_answer.advanced_fill();
_answer.backtrack(_answer.remaining());
_answer.print_board(std::cout);
}
};
页:
[1]