题目描述

在n×n方针里输入1，2，…，n*n，要求填成蛇形。例如，n=4时方阵为：



上面的方针中，多余的空格只是为了便于观察规律，不必严格输出。n<=8。

题目分析

首先看到方针先要明白题目要求具体是从哪里开始，即“蛇头”在哪，最后要看明白“蛇尾”在哪。


如图，整个蛇形填数的具体步骤已经明白，仅仅只是不断重复这个步骤，填数到最后就好。

设（x,y）为当前填数的位置坐标，则一开始的“蛇头”位置则为（0，n-1），想到用二维数组表示成a[0][n-1].（位置是在右上角，由于是数组，所以是第0行，第n-1列），知道了这些，则按照如图的箭头所示开始向下走。但是这个蛇是盘着身体的，朝一个方向走总要有个头,所以需要判断是否越界。

有一个很好的方法就是“预判”，以第一步为例：

首先预判断 x+1<n,不需要管y的值，因为y表示的是列数，没有修改。预判到最后一个，是会理解为当前方向的下一步的坐标为（x+1，y），只需一个"!a[x+1][y]"即可。其本身的位置没有变，只是进行了前面所说的“预判”。当判断未越界时，系统接着按此方向走，如果越界，则停止此步骤。
#include<stdio.h>
#include<string.h>
#define max 21
int a[max][max];
int main()
{
	int bot=0;
	int n,x,y;
	scanf_s("%d", &n);
	memset(a, 0, sizeof(a));//初始化数组，将数组a清零，它在string.h中定义
	bot = a[x = 0][y = n - 1] = 1;//将bot和”蛇头“初始化为1
	while (bot < n*n) 
	{
		while (x < n - 1 && !a[x + 1][y])	a[++x][y] = ++bot;//向下走，判断是否满足条件且不越界
		while (y - 1 >= 0 && !a[x][y - 1])	a[x][--y] = ++bot;
		while (x - 1 >= 0 && !a[x - 1][y])	a[--x][y] = ++bot;
		while (y < n - 1 && !a[x][y + 1])	a[x][++y] = ++bot;
	}
	for (x = 0; x < n; x++) {
		for (y = 0; y < n; y++)
			printf("%3d", a[x][y]); 
		printf("\n");
	}
	system("pause");
	return 0;
}

    
　　数独是一种源自18世纪末的瑞士，后在美国、日本得以发展的数字游戏。
    九宫数独盘面是个九宫，每一宫又分为九个小格（如图）。
    九阶标准数独题目，是要求解题者从1到9的9个数字中选择一个数字填到图中的空格里，使得从1到9 的9个数字在它的每一行、每一列和每一个九宫（指用粗线框住的3×3的区域）里都仅仅出现一次。即
    在9×9的格子中，用1到9共9个阿拉伯数字填满整个格子，要求符合：
一，1，2，……，8，9的9个数字在每一行各自独居一格，位置不限；
二，1，2，……，8，9的9个数字在每一列各自独居一格，位置不限；
三，9个3×3的小九宫里，1，2，……，8，9的9个数字各自独居一格，位置不限。
因为1，2，……，8，9的每个数字在各行、各列以及小九宫中各自独居一格，只能出现一次，所以起名“数独”。
    在八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1，2，……，8，9的数字。使1—9每个数字在每一行、每一列和每一宫中都只出现一次。这种游戏全面考验做题者观察能力和推理能力，虽然玩法简单，但数字排列方式却千变万化，所以不少教育者认为数独是训练头脑的绝佳方式。
现在已经有专著出版，网上也有介绍各种解题的技巧。但是九宫数独是最简单的，入门不难，可以自学成才，在探索中只有乐趣。
    感兴趣的朋友可以参考严德人先生编著的《竞技数独》一书，那里详细讲解了数独的各种解题原则，和采用这些解题原则表示的解题过程，并随书赠送有包含20000道题目和解题软件的光盘。
 

9


3


6


7


8


4


5


2


1


1


5


2


9


3


6


7


8


4


4


7


8


1


5


2


9


3


6


6


9


3


4


7


8


1


5


2


2


1


5


6


9


3


4


7


8


8


4


7


2


1


5


6


9


3


3


6


9


8


4


7


2


1


5


5


2


1


3


6


9


8


4


7


7


8


4


5


2


1


3


6


9
 

 
     
 
 
 
 
 
 
 
 
 
 
http://blog.sina.com.cn/s/blog_539fcb960100m0w4.html

转载于:https://www.cnblogs.com/tupx/archive/2012/04/22/2465234.html

    

                    

Sudoku Solver 题解
题目描述

即求解数独游戏。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。1
如：上图中则有一个例子。
题解
这题出现在算法类题目里我还是很惊讶的，不过看到了，就顺手做了下。
利用唯一余数法，即用格位去找唯一可填数字，格位唯一可填数字称为唯余解（Naked Single）。若找不到唯余解，则随意选择一个数字进行深度搜索，并记录当前状态以便回溯。时间复杂度很高，应该是O(b^d)。b为可选解，d为盘面的空位数。但由于存在唯余解，大多数情况下b = 1，所以很快就能得到结果。
代码
#define n 9
#define POS2(i, j) ((i) * n + (j))
#define POS3(i, j) ((i) * nsquare + (j))
#define POS(i, j, k) (POS3(i, POS2(j, k)))
#define COMPOSE(i, j) (((i) << 16) | (j))
#define VAIN ('.') // 46

char* used; 

class Solution {
public:
    bool operator()(int a, int b) const {
        int va = used[POS2(a >> 16, a & 0xFFFF)], vb = used[POS2(b >> 16, b & 0xFFFF)];
        return va > vb || (va == vb && a < b);
    }
    void solveSudoku(vector<vector<char>>& board) {
        if (board.empty() || board.size() != board[0].size())
            return;
        // n = board.size();
        int nsqrt = sqrt(n), nsquare = n * n, nm = nsquare * (n + 1) * sizeof(char);
        used = (char*)malloc(nm);
        memset(used, 0, nm);
        for (int i = n; i--; ) {
            vector<char>& vi = board[i];
            for (int j = n; j--; ) {
                if (vi[j] != VAIN) {
                    int ct = vi[j] - '0';
                    int row = i / nsqrt * nsqrt, col = j / nsqrt * nsqrt;
                    for (int k = row + nsqrt; --k >= row; )
                        for (int kk = col + nsqrt; --kk >= col; ) {
                            int t2 = POS2(k, kk), t3 = POS3(ct, t2);
                            if (used[t3])
                                continue;
                            used[t3] = 1;
                            ++used[t2];
                        }
                    for (int k = 0; k < row; ++k) {
                        int t2 = POS2(k, j), t3 = POS3(ct, t2);
                        if (used[t3])
                            continue;
                        used[t3] = 1;
                        ++used[t2];
                    }
                    for (int k = row + nsqrt; k < n; ++k) {
                        int t2 = POS2(k, j), t3 = POS3(ct, t2);
                        if (used[t3])
                            continue;
                        used[t3] = 1;
                        ++used[t2];
                    }
                    for (int k = 0; k < col; ++k) {
                        int t2 = POS2(i, k), t3 = POS3(ct, t2);
                        if (used[t3])
                            continue;
                        used[t3] = 1;
                        ++used[t2];
                    }
                    for (int k = col + nsqrt; k < n; ++k) {
                        int t2 = POS2(i, k), t3 = POS3(ct, t2);
                        if (used[t3])
                            continue;
                        used[t3] = 1;
                        ++used[t2];
                    }
                }
            }
        }
        
        std::set<int, Solution> next;
        for (int i = n; i--; ) {
            vector<char>& vi = board[i];
            for (int j = n; j--; )
                if (vi[j] == VAIN)
                    next.insert(COMPOSE(i, j));
                else
                    used[POS2(i, j)] = 9;
        }
        std::vector<std::pair<int, char*>> stack;
        NextLoop:
        for (std::set<int, Solution>::iterator it = next.begin(); it != next.end(); it = next.begin()) {
            int ct = 0, i = *it >> 16, j = *it & 0xFFFF, t2 = POS2(i, j);
            if (used[t2] > 8) {
                GoBack:
                free(used);
                used = stack.back().second;
                ct = stack.back().first;
                stack.pop_back();
                next.clear();
                for (int i = n; i--; )
                    for (int j = n; j--; )
                        if (used[POS2(i, j)] != 9) {
                            next.insert(COMPOSE(i, j));
                            board[i][j] = VAIN;
                        }
                it = next.begin();
                i = *it >> 16; j = *it & 0xFFFF; t2 = POS2(i, j);
            }
            while (++ct <= n)
                if (!used[POS3(ct, t2)]) {
                    if (used[t2] < 8) {
                        char* tmp = (char*)malloc(nm);
                        memcpy(tmp, used, nm);
                        stack.push_back(std::pair<int, char*>(ct, tmp));
                    }
                    board[i][j] = ct + '0';
                    used[t2] = 9;
                    next.erase(it);
                    int row = i / nsqrt * nsqrt, col = j / nsqrt * nsqrt;
                    for (int k = row + nsqrt; --k >= row; )
                        for (int kk = col + nsqrt; --kk >= col; ) {
                            int t2 = POS2(k, kk), t3 = POS3(ct, t2);
                            if (used[t2] == 9 || used[t3])
                                continue;
                            next.erase(COMPOSE(k, kk));
                            used[t3] = 1;
                            ++used[t2];
                            next.insert(COMPOSE(k, kk));
                        }
                    for (int k = 0; k < row; ++k) {
                        int t2 = POS2(k, j), t3 = POS3(ct, t2);
                        if (used[t2] == 9 || used[t3])
                            continue;
                        next.erase(COMPOSE(k, j));
                        used[t3] = 1;
                        ++used[t2];
                        next.insert(COMPOSE(k, j));
                    }
                    for (int k = row + nsqrt; k < n; ++k) {
                        int t2 = POS2(k, j), t3 = POS3(ct, t2);
                        if (used[t2] == 9 || used[t3])
                            continue;
                        next.erase(COMPOSE(k, j));
                        used[t3] = 1;
                        ++used[t2];
                        next.insert(COMPOSE(k, j));
                    }
                    for (int k = 0; k < col; ++k) {
                        int t2 = POS2(i, k), t3 = POS3(ct, t2);
                        if (used[t2] == 9 || used[t3])
                            continue;
                        next.erase(COMPOSE(i, k));
                        used[t3] = 1;
                        ++used[t2];
                        next.insert(COMPOSE(i, k));
                    }
                    for (int k = col + nsqrt; k < n; ++k) {
                        int t2 = POS2(i, k), t3 = POS3(ct, t2);
                        if (used[t2] == 9 || used[t3])
                            continue;
                        next.erase(COMPOSE(i, k));
                        used[t3] = 1;
                        ++used[t2];
                        next.insert(COMPOSE(i, k));
                    }
                    goto NextLoop;
                }
            goto GoBack;
        }
        for (free(used); stack.size(); stack.pop_back())
            free(stack.back().second);
    }

};
总结
主要应用了深度搜索思想。
 百度百科 数独。 ↩

  

数独（sudoku）盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
明白了原理之后就很简单了，首先我们在代码里生成一个9x9的二维数组。如下图所示，因为第1、第5、第9宫格之间是没有关联的，只需要保证这三个宫格之中都包含1到9的数字就只可以了，所以我们可以生成3组1-9的数字，分别将3组数字打乱顺序后填入蓝色格式，如下图所示。
接着我们只需要遍历每个个格子，排除不可填的数字之后，随机给它填入一个数字，如果发现当前格子没有可填的值，则退回去上一个格子，将此格子原有的值排除后再重新选一个新的值填入，如果发现也没有合适的值，再退一个格子....在不停的重复这个过程之后，就可以得到一个正确的数独矩阵，这里用到了深度优先算法和回溯算法。
以下为示例代码：
import random
import math

matrix = []


# 生成一个随机的数组
def get_random_unit():
    _num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    random.shuffle(_num_list)
    return _num_list


def print_grid(arr):
    for i in range(9):
        print(arr[i])


def get_row(row):
    row_arr = []
    for v in matrix[row]:
        if v == 0:
            continue
        row_arr.append(v)
    return row_arr


def get_col(col):
    col_arr = []
    for i in range(9):
        val = matrix[i][col]
        if val == 0:
            continue
        col_arr.append(matrix[i][col])
    return col_arr


def get_block(num):
    col_arr = []
    seq = num % 3
    col_end = 9 if seq == 0 else seq * 3
    row_end = int(math.ceil(num / 3) * 3)
    for i in range(row_end - 3, row_end):
        for j in range(col_end - 3, col_end):
            val = matrix[i][j]
            if val != 0:
                col_arr.append(matrix[i][j])
    return col_arr


def get_block_seq(row, col):
    col_seq = int(math.ceil((col + 0.1) / 3))
    row_seq = int(math.ceil((row + 0.1) / 3))
    return 3 * (row_seq - 1) + col_seq


def get_enable_arr(row, col):
    avail_arr = get_random_unit()
    seq = get_block_seq(row, col)
    block = get_block(seq)
    row = get_row(row)
    col = get_col(col)
    unable_arr = list(set(block + row + col))
    for v in unable_arr:
        if v in avail_arr:
            avail_arr.remove(v)
    return avail_arr


def main():
    can_num = {}
    count = 0
    # 初始化一个9行9列的数组
    for i in range(9):
        matrix.append([0] * 9)

    num_list = get_random_unit()
    for row in range(3):
        for col in range(3):
            matrix[row][col] = num_list.pop(0)

    num_list = get_random_unit()
    for row in range(3, 6):
        for col in range(3, 6):
            matrix[row][col] = num_list.pop(0)

    num_list = get_random_unit()
    for row in range(6, 9):
        for col in range(6, 9):
            matrix[row][col] = num_list.pop(0)

    box_list = []
    for row in range(9):
        for col in range(9):
            if matrix[row][col] == 0:
                box_list.append({'row': row, 'col': col})

    i = 0
    while i < len(box_list):
        count += 1
        position = box_list[i]
        row = position['row']
        col = position['col']
        key = '%dx%d' % (row, col)
        if key in can_num:
            enable_arr = can_num[key]
        else:
            enable_arr = get_enable_arr(row, col)
            can_num[key] = enable_arr

        if len(enable_arr) <= 0:
            i -= 1
            if key in can_num:
                del (can_num[key])
            matrix[row][col] = 0
            continue
        else:
            matrix[row][col] = enable_arr.pop()
            i += 1

    print_grid(matrix)
    print(count)


if __name__ == "__main__":
    main()