这是我的数独程序，可惜不会图形界面

andalousie

这个是我们程序与算法综合课程设计的一道题。叫做数独游戏。
源代码

#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[i] = cols[i] = allSet;
        for (unsigned i = 0; i < 3; ++i)
            for (unsigned j = 0; j < 3; ++j)
                blocks[i][j] = allSet;
    }

    void elim(unsigned i, unsigned j, unsigned n)
    {
        bitfield bit = bitFor(n);
        rows[i] &= ~bit;
        cols[j] &= ~bit;
        blocks[i/3][j/3] &= ~bit;
    }

    void cancel(unsigned i, unsigned j, unsigned n)
    {
        bitfield bit = bitFor(n);
        rows[i] |= bit;
        cols[j] |= bit;
        blocks[i/3][j/3] |= bit;
    }

    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] = val;
        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;
        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[row][col])
                    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][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()
    {
        bool again;
        do
        {
            again = false;
            for (unsigned i = 0; i < 9; ++i)
            {
                for (unsigned j = 0; j < 9; ++j)
                {
                    if (matrix[i][j]) 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[i][j])
                    ++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[i][j] &&
                        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[i][j];
    }
    bool assert(unsigned i, unsigned j, unsigned val)
    {
        return matrix[i][j] == val;
    }
    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::endl;
        }
    }
private:
    unsigned matrix[9][9];
    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[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))
                        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[i] + look_up[array[j]];
                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[100];
        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");
}

可执行文件 Sudoku.zip (8.63 KB, 下载次数: 1)

2014-6-28 07:50 上传

点击文件名下载附件

andalousie

（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[9]	对应行可填数
		bitfield	cols[9]	对应列可填数
		bitfield	blocks[9]	对应房子可填数
	方法	void	elim(unsigned, unsigned,  unsigned)	在增添数据时，从可填数中除去该数字
		void	cancel(unsigned, unsigned,  unsigned)	在删除数据时，从可填数中增添该数字
		bitfield	possible(unsigned,  unsigned)	返回对应格子的可填数（在只考虑行、列、房子不冲突的情况下）
Board	属性	unsigned	matrix[9][9]	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

新的测试代码，部分。

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] = allSet;
            }
    }
    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] = allSet;
            }

        std::srand(seed);
        _random_fill();
    }
    void set(unsigned row, unsigned col, unsigned val, bool advanced = false)
    {
        matrix[row][col] = val;
        if (matrix[row][col])
        {
            Blank.elim(row, col, val);
            --remains;
        }
        if (advanced)
            _update(row, col);
    }
    unsigned unset(unsigned row, unsigned col)
    {
        unsigned val = matrix[row][col];
        if (val)
        {
            Blank.cancel(row, col, val);
            ++remains;
        }
        matrix[row][col] = 0;
        return val;
    }
    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 = 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[row][col])
                    continue;
                house_hidden &= advanced ? ~memory[row][col] : ~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[i][col] && col != j)
                row_hidden &= advanced ? ~memory[i][col] : ~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][j] && row != i)
                col_hidden &= advanced ? ~memory[row][j] : ~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[i][j]) 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[row][col])
                        continue;
                    row_i |= memory[row][col];
                }
            }
            else
            {
                for (unsigned col = col_base; col < col_base + 3; ++col)
                {
                    if (matrix[row][col])
                        continue;
                    row_locked |= memory[row][col];
                    ++total_count;
                }
            }
        }
        if (total_count && total_count == bitCount(row_locked))
            memory[i][j] &= ~row_locked;
        bitfield pointing = row_i & ~row_locked;
        if (pointing)
            for (unsigned col = 0; col < 9; ++col)
            {
                if (matrix[i][col] || (col >= col_base && col < col_base + 3))
                    continue;
                memory[i][col] &= ~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[row][col])
                        continue;
                    col_j |= memory[row][col];
                }
            }
            else
            {
                for (unsigned row = row_base; row < row_base + 3; ++row)
                {
                    if (matrix[row][col])
                        continue;
                    col_locked |= memory[row][col];
                    ++total_count;
                }
            }
        }
        if (total_count && total_count == bitCount(col_locked))
            memory[i][j] &= ~col_locked;
        pointing = col_j & ~col_locked;
        if (pointing)
            for (unsigned row = 0; row < 9; ++row)
            {
                if (matrix[row][j] || (row >= row_base && row < row_base + 3))
                    continue;
                memory[row][j] &= ~pointing;
            }

                for (unsigned col = 0; col < 9; ++col)
                {
                        if (matrix[i][col] || (col >= col_base && col < col_base + 3))
                                continue;
                        row_i &= ~memory[i][col];
                }
                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[r][c])
                                                continue;
                                        memory[r][c] &= ~row_i;
                                }
                }

                for (unsigned row = 0; row < 9; ++row)
                {
                        if (matrix[row][j] || (row >= row_base && row < row_base + 3))
                                continue;
                        col_j &= ~memory[row][j];
                }
                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[r][c])
                                                continue;
                                        memory[r][c] &= ~col_j;
                                }
                }
        return memory[i][j];
    }
    void advanced_fill()
    {
        bool again;
        unsigned sum;
        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 = false;
            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]) 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[i][j];
            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[i][j] && (bitCount(Blank.possible(i, j)
                                        & memory[i][j])) < count)
                {
                    count = bitCount(Blank.possible(i, j) & memory[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[i][j];
    }
    bool assert(unsigned i, unsigned j, unsigned val)
    {
        return matrix[i][j] == val;
    }
    void print_possible()
    {
        for (unsigned i = 0; i < 9; ++i)
        {
            for (unsigned j = 0; j < 9; ++j)
            {
                output << memory[i][j] << " ";
            }
            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[i][j] << " ";
            }
            out << std::endl;
        }
        out << std::endl;
    }
private:
    unsigned matrix[9][9];
    bitfield memory[9][9];
    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[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)
                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[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))
                    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[i] + look_up[array[j]];
                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);
    }
};