精华内容
下载资源
问答
  • 蛇形填数问题

    2018-11-06 22:25:45
    题目描述 n×n方针输入1,2,…,n*n,要求填成蛇形。...如,整个蛇形填数的具体步骤已经明白,仅仅只是不断重复这个步骤,填数到最后就好。 设(x,y)为当前填数的位置坐标,则一开始的“蛇头...

    题目描述
    在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;
    }
    
    展开全文
  • 九宫数独简介(转)

    2019-10-04 18:48:32
    九阶标准数独题目,是要求解题者从1到9的9个数字中选择一个数字图中空格里,使得从1到9 的9个数字它的每一行、每一列和每一个九宫(指用粗线框住的3×3的区域)里都仅仅出现一次。即 9×9的格子中,用1到...

      数独是一种源自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

    2017-10-19 02:15:21
    这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,其他的空格入1-9的数字。使1-9每个数字每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。1 如:上图中则有一个例子。 题解 这题...
        

    Sudoku Solver 题解


    题目描述

    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);
        }
    
    };

    总结

    主要应用了深度搜索思想。


    1. 百度百科 数独
    展开全文
  • 这八十一格给出一定的已知数字和解题条件,利用逻辑和推理,其他的空格入1-9的数字。使1-9每个数字每一行、每一列和每一宫都只出现一次,所以又称“九宫格”。明白了原理之后就很简单了,首先我们...

    数独(sudoku)盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。

    明白了原理之后就很简单了,首先我们在代码里生成一个9x9的二维数组。如下图所示,因为第1、第5、第9宫格之间是没有关联的,只需要保证这三个宫格之中都包含1到9的数字就只可以了,所以我们可以生成3组1-9的数字,分别将3组数字打乱顺序后填入蓝色格式,如下图所示。

    ad0bddc84ea60511b0df4f95502fb232.png
    9x9 矩阵

    接着我们只需要遍历每个个格子,排除不可填的数字之后,随机给它填入一个数字,如果发现当前格子没有可填的值,则退回去上一个格子,将此格子原有的值排除后再重新选一个新的值填入,如果发现也没有合适的值,再退一个格子....在不停的重复这个过程之后,就可以得到一个正确的数独矩阵,这里用到了深度优先算法和回溯算法。

    以下为示例代码:

    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()
    展开全文
  • 这八十一格给出一定的已知数字和解题条件,利用逻辑和推理,其他的空格入1-9的数字。使1-9每个数字每一行、每一列和每一宫都只出现一次,所以又称“九宫格”。明白了原理之后就很简单了,首先我们...
  • 这八十一格给出一定的已知数字和解题条件,利用逻辑和推理,其他的空格入1-9的数字。使1-9每个数字每一行、每一列和每一宫都只出现一次,所以又称“九宫格”。明白了原理之后就很简单了,首先我们...
  • 凫山抽奖软件

    2013-01-25 15:52:55
    4、此奖每次抽取人数 最多一次可抽取20人, 比如:图中例子,优秀奖的奖品为“现金5000元” 每次抽取人数为一人。 奖项设置 设置了优秀奖抽取次数为一次,所以此次抽奖活动共抽取优秀奖一名。 B:图片、音乐...
  • excel的使用

    2012-11-25 17:06:01
    一单元格内入“*”或“~”等符号,然后单击此单元格,向右拖动鼠标,选中横向若干单元格,单击“格式”菜单,选中“单元格”命令,弹出的“单元格格式”菜单,选择“对齐”选项卡,水平对齐下拉列表...
  • Quartus_II使用教程

    热门讨论 2012-11-26 23:20:43
    memory设计图中,双击空白处,输入cdu16(名称为刚才自行设计模块的文件名) 就可以调出自己打包的芯片,也可以双击后project中点选,如图10. 图10 电路设计完成后,就是此编译了,如果前面点选了别的...
  • 代码语法错误分析工具pclint8.0

    热门讨论 2010-06-29 07:00:09
    选项间要以空格分开,lint命令一定要小写,并且紧跟/*或//后面,不能有空格。如果 选项由类似于操作符和操作的部分组成,例如-esym(534, printf, scanf, operat or new),其中最后一个选项是operator new,...
  • 软件多个TAG空格为分隔符号(原为,号)28.添加软件时, 选择"软件分类" 时 增加 选完一级选二级/选完二级选三级的功能, 改变了原来从众多分类选择一个分类的方式, 提高效率.29.软件页面增加对软件提交/发布者的...
  • 一共9行,每行9个整数(每个0—9的范围内),表示一个尚未满的数独方格,未满的空格用“0”表示。每两个数字之间用一个空格隔开。 【输出】 输出文件sudo.out共1行。 输出可以得到的靶形数独的最高分数。...
  • 打开修改—>修改代码列表,弹出的窗口(如图所示),“代码”和“修改”就是输入RAW码的地方(图中的A、B)。不同的是:前者是批量输入,后者是单个输入,具体方法初级教程已有,就不再说了。  至于删除,...
  • 2009达内SQL学习笔记

    2010-02-10 19:46:58
    处理SQL语句时,其中所有的空格都被忽略(空格只用来分开单词,连续多个空格当一个用)。 SQL语句可以一行上写出,建议多行写出,便于阅读和调试。 多条SQL语句必须以分号分隔。多数DBMS不需要单条SQL语句后...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    10. 顺序存储结构,有时也存储数据结构元素之间的关系。( )【华南理工大学 2002 一、2 (1分)】 11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( )【上海海运学院 1999 一、1(1分)】 12....
  • 入门学习Linux常用必会60个命令实例详解doc/txt

    千次下载 热门讨论 2011-06-09 00:08:45
    Linux ,设备名称通常都存在/dev。这些设备名称的命名都是有规则的,可以用“推理”的方式把设备名称找出来。例如,/dev/hda1这个 IDE设备,hd是Hard Disk(硬盘)的,sd是SCSI Device,fd是Floppy Device(或是...
  • 2、[Client] 增加内挂自动挂机功能,游戏按F12呼出内挂,设置挂机技能项,按Ctrl+L开启或关闭挂机 3、[Client] 修正合成功能引数据包太大导致功能失效的错误 4、[Client] 修正剑侠界面人物名字位置错误 5、[M2...
  • 达内 coreJava 习题答案

    2010-02-10 19:49:01
    其中a为1至9之的一个,项也要可以指定。 import java.util.Scanner; class Multinomial{ public static void main(String[] args){ int a; //定义输入的 a int howMany; //定义最后的一项有多少个数字 ...
  • LINGO软件的学习

    2009-08-08 22:36:50
    LINGO,只有初始部分给出的集属性值以后的求解可更改。这与前面并不矛盾,初始部分是LINGO求解器的需要,并不是描述问题所必须的。 2.3.2 定义派生集 为了定义一个派生集,必须详细声明: •集的名字 •...
  • Ghost 8.3 系统备份软件

    2009-11-13 10:29:50
    然后 ->Dump From Client->rtitions->More Options-> auto start 的 client 中填入 50(如果你要同时复制50台)->accept client 就算完成了,当你的工作站达到50台时,server就自动传送*.gho 文件。...
  • Ghost 8.3 Enterprise

    2009-04-15 13:32:08
    然后 ->Dump From Client->rtitions->More Options-> auto start 的 client 中填入 50(如果你要同时复制50台)->accept client 就算完成了,当你的工作站达到50台时,server就自动传送*.gho 文件。...
  • php高级开发教程说明

    2008-11-27 11:39:22
    阅读的时候,为了理解文章的含义,你的大脑必须分析从你的眼睛获得的信息,识别 出重要的部分,然后把这些部分译成正确的代码。这个分析过程分两步执行:形式分析和逻辑 分析。首先通过检查文章的可视结构来执行...
  • AutoLISP学习导引.pdf

    2015-07-18 22:45:17
    AutoCAD能提供的多种程序设计界面,AutoLISP是最容易入门及精通的程序语言。当更新到更高级版本的环境下,用AutoLISP编写的程序几乎不需任何改动即可直接使用。本书以单元方式逐步引导你使用AutoLISP解决日常...
  • 093《Search to Play the Song》浏览器随时听我想听的歌~(周杰伦的也行) 092《Copyfish Free OCR Software》自动截图识别网页的文字 091《FasterChrome》鼠标悬停预加载链接让你的Chrome起飞 090《拒绝...
  • PT80-NEAT开发指南v1.1

    2014-06-24 18:38:34
    NEAT 开 发 指南 文档 适用于 PT80 系列 移动数据终端 版本记录 版本号 版本描述 发布日期 V 1.0 初始版本。 2012-04-12 V1.1 修改前三章内容 2012-09-25 目录 第一章 关于本手册.....................................
  • Mysql 甲骨文 是个开源的数据库server,可运行多种平台, 特点是响应速度特别快,主要面向小企业 小型企业 PostgreSQL 号称“世界上最先进的开源数据库“,可以运行多种平台下,是tb级数据库,而且性能也很...
  • printf("请输入字符个(空格间隔):"); scanf("%d",&n); int i; int *w=NULL; w=(int*)malloc(n*sizeof(int)); printf("请依次输入权值(空格间隔):"); for(i=0;i;i++){ scanf("%d",w+i); }...
  • 精易模块[源码] V5.15

    2015-03-21 22:03:37
    5、修正“类_APIHOOK->取地址”当安装时不后缀,而取地址填写后无法获取已安装地址BUG,感谢易友【@ChongZi】反馈。 6、修正“窗口_枚举所有子窗口”当过滤类名输入空符号或一段空文本后无法枚举的BUG,感谢易友...

空空如也

空空如也

1 2
收藏数 31
精华内容 12
关键字:

在图中空格里填数