精华内容
下载资源
问答
  • 问题简介:给定个大小9*9的二维数组,输入部分数字,其它字符用’.‘代替,要求完成剩余数字的计算即字符’.‘处 数独的要求: 1.每个数字1-9必须在每行中恰好出现次 2.每个数字1-9必须在每列中恰好出现次 3.数字...

    Sudoku Solver

    问题简介:给定一个大小9*9的二维数组,输入部分数字,其它字符用’.‘代替,要求完成剩余数字的计算即字符’.‘处
    数独的要求:
    1.每个数字1-9必须在每行中恰好出现一次
    2.每个数字1-9必须在每列中恰好出现一次
    3.数字1-9中的每一个必须在网格的9个3×3子框中的每一个中恰好出现一次
    举例:
    输入:
    [
    [“5”,“3”,".",".",“7”,".",".",".","."],
    [“6”,".",".",“1”,“9”,“5”,".",".","."],
    [".",“9”,“8”,".",".",".",".",“6”,"."],
    [“8”,".",".",".",“6”,".",".",".",“3”],
    [“4”,".",".",“8”,".",“3”,".",".",“1”],
    [“7”,".",".",".",“2”,".",".",".",“6”],
    [".",“6”,".",".",".",".",“2”,“8”,"."],
    [".",".",".",“4”,“1”,“9”,".",".",“5”],
    [".",".",".",".",“8”,".",".",“7”,“9”]
    ]
    即:
    在这里插入图片描述
    结果:填充未完成的部分,即红色数字位置
    在这里插入图片描述
    解法一:
    利用递归的思路,逐个填充原字符’.'处的数字,当填充每个数字时进行判断,判断填充的数字是否有效,直到递归所有字符

    class Solution {
        public void solveSudoku(char[][] board) {
            solve(board, 0, 0);
        }
        boolean solve(char[][] board, int i, int j) {
            if (i == 9) return true;
            if (j >= 9) return solve(board, i + 1, 0);
            if (board[i][j] == '.') {
                for (int k = 1; k <= 9; ++k) {
                    board[i][j] = (char)(k + '0');
                    if (isValid(board, i , j)) {
                        if (solve(board, i, j + 1)) return true;
                    }
                    board[i][j] = '.';
                }
            } else {
                return solve(board, i, j + 1);
            }
            return false;
        }
        boolean isValid(char[][] board, int i, int j) {
            for (int col = 0; col < 9; ++col) {
                if (col != j && board[i][j] == board[i][col]) return false;
            }
            for (int row = 0; row < 9; ++row) {
                if (row != i && board[i][j] == board[row][j]) return false;
            }
            for (int row = i / 3 * 3; row < i / 3 * 3 + 3; ++row) {
                for (int col = j / 3 * 3; col < j / 3 * 3 + 3; ++col) {
                    if ((row != i || col != j) && board[i][j] == board[row][col]) return false;
                }
            }
            return true;
    }
    }
    

    小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海

    展开全文
  • 对于给出的数字二维数组,要求每行每列的数字不能重复。 二、实现代码: <?php /* 数独求解程序 * Created on 2017-4-18 * */ class Sudoku { var $matrix; function __construct($arr = null) { if ($...
  • Java 实现完成数独

    2011-03-30 19:42:00
    这几天想了数独算法,以下是Java实现版本。import java.util.Scanner; public class Sodoku ...//存储数独数据,二维数组 System.out.println("Please enter a puzzle."); Scanner input=new Sca

    这几天想了一个数独算法,以下是Java实现版本。

     

     


    展开全文
  • 数独游戏-C语言实现

    2020-06-29 15:44:24
    数独游戏 目标 写一个数独游戏,有以下功能...随机产生一个长度为9的一维数组,元素是随机产生的1到9的不同数字。 比如为root = [1, 4, 3, 5, 6 ,7, 8 ,9, 2]. 先获得一个填满的九宫格accord。 假如九宫格accord的第

    数独游戏-C语言实现

    目标

    写一个数独游戏,有以下功能:

    1:能随机产生题目并给出答案。

    2:求解输入的题目并输出答案。

    实现说明

    参照百度百科等资料可以知道求解数独的主要算法是:1.通过行、列和宫格确定可填数字。2.所有可行数字逐一填入得到结果。本程序求解数独部分也采用这样的算法。而生成题目的算法是:

    1. 随机产生一个长度为9的一维数组,元素是随机产生的1到9的不同数字。

    比如为root = [1, 4, 3, 5, 6 ,7, 8 ,9, 2].

    1. 先获得一个填满的九宫格accord。
    2. 假如九宫格accord的第一行为[6, 4, 5, 7, 3, 9, 8, 1, 2], 则可获得的九宫格squa的第一行第一列元素这样产生:看accord对应元素为6,则看root中6后一位的数为7,则所求数字为7。以此类推。
    3. 根据难度随机去除一定数量的空格则得到了随机产生的数独题目。

    下面介绍本程序的主要难点和创新点:

    1. 解数独的递归法。首先要定义一个检查函数judge用于判断某个数字在某个位置是否合适,进而根据找到的递归头即至最后一个位置后,分是否为0两种情况,否则,继续递归。

    2. 随机产生1到9之间的数。由于编译器自带函数rand会出现元素不变的确点,所以使用系统时间为种子,并引入全局变量index,使得时间差加大,避免固定不变。

    3. 定义各种函数简化程序。本程序定义了fprintf用于打印九宫格,定义reRank来获取元素在数组中位置等,简化了程序。

    结果

    下面是分别选择1(产生题目)和2(计算数独)后的结果图:

    在这里插入图片描述

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z0w8LVZw-1593416471669)(fig2.png)]

    代码:

    语言: C

    //期末实验报告-简单的数独计算器
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h> 
    long index = 0;    //全局变量index是保证每次产生的随机元素随机性
    void main()
    {
        void solve(int squa[9][9], int num); 
        void fprintf(int squa[9][9]);
        int reRank(int root[9], int numb);
        int myRand(int range);
        int squa[9][9], accord[9][9]={   //定义用于生成数独的参照数组
            {6, 4, 5, 7, 3, 9, 8, 1, 2},
            {2, 1, 8, 6, 4, 5, 9, 7, 3},
            {7, 3, 9, 2, 8, 1, 6, 4, 5},
            {5, 9, 6, 3, 7, 4, 2, 8, 1},
            {4, 8, 7, 5, 1, 2, 3, 6, 9},
            {3, 2, 1, 8, 9, 6, 7, 5, 4},
            {9, 5, 3, 4, 6, 7, 1, 2, 8},
            {8, 7, 2, 1, 5, 3, 4, 9, 6},
            {1, 6, 4, 9, 2, 8, 5, 3, 7}
            };
        int root[9], answ[9][9]; //定义用于生成数组的一维数组和临时数组
        int i, j, k, p = 0;
        int row;
        int choose, rtemp, diff; //分别定义选择变量,难度
        char result;
        printf("———请选择*1*生成一个数独——*2*计算一个数独———\n");
        scanf("%d", &choose);
    //**************选择1生成一个填好的数独****************************
        //根据生成数独题目算法先存入一个数独
        if(1 == choose)
        { //产生范围为1-9的一维数组root
          for(i = 0; i < 9; i++)
          {
              root[i] = myRand(9);
          }
          for(i = 0; i < 9; i++)
          {
                for(j = 0; j < i; j++)
                {
                    if(root[i]==root[j]) //使root中元素各不相同
                    root[i] = myRand(9);
                }
          }
          //随机产生完整九宫格
          for(i=0;i<9;i++)
          {
             for(j=0;j<9;j++)
             {
                row = reRank(root,accord[i][j]);
                squa[i][j] = root[(row+1)%9];
             }
          }
          for (i = 0; i < 9; i++)
          {
             for (j = 0; j < 9; j++)
             {
                answ[i][j] = squa[i][j];
             }
          }
          //根据不同难度需求处理数组
          printf("————请选择难度等级:1(低级)--2(中级)--3(高级)————\n");
          scanf("%d", &diff);
          if(diff==1)               //难度为低级时有30个空格
          {
                for(k=0; k<20;)//; k++)
                {
                     i = myRand(9)-1;
                     j = myRand(9)-1;
                     if(squa[i][j] != 0)
                     {
                      squa[i][j] = 0;
                      k++;
                     }        
                }
          }
          else if(diff==2)          //难度为中级时有50个空格
          {  
                for(k=0; k<30;)
                {
                     i = myRand(9)-1;
                     j = myRand(9)-1;
                     if(squa[i][j] != 0)
                     {
                      squa[i][j] = 0;
                      k++;
                     }        
                }
          }
          else if(diff==3)            //难度为中级时有70个空格
          {
                for(k=0; k<60;)
                {
                     i = myRand(9)-1;
                     j = myRand(9)-1;
                     if(squa[i][j] != 0)
                     {
                      squa[i][j] = 0;
                      k++;
                     }        
                }
          }
          printf("************题目如下(0表示空格)****************\n");
          fprintf(squa);
          printf("——————Enter键显示答案——————");
          fflush(stdin);           //除去缓存影响
          scanf("%c", &result);
          if(result == 10)
              fprintf(answ);
        }
    //**************选择2输入并计算一个数独**************************** 
        else
        {
          //*******输入题目***********************************
          printf("*********请输入题目(空缺以0代替)**********");
          printf("\n******||1*2*3*4*5*6*7*8*9\n");
          for (i = 0; i < 9; i++)
          {
             printf("******%d:", i + 1);
             for (j = 0; j < 9; j++)
             {
                scanf("%d", &squa[i][j]);
             }
          }
          solve(squa, 0);    //调用函数计算结果
        }
    }
     
    //定义函数可以产生随机产生1-9的数
    int myRand(int range) 
    {
        srand((unsigned)time( NULL ) + index);
        index++;
         return rand()%range + 1;     
    }
    
    //定义函数可以在root中根据元素找位置
    int reRank(int root[9], int numb)
    {    
        int i; 
        for(i = 0; i < 9; i++)
        {
            if(root[i] == numb)
            return i;
        }
    }
    
    //解决的第一步:判断空缺处可填数字的judge函数
    int judge(int squa[9][9], int m, int n, int posb)
    {
        int num, gridi, gridj;              
        int gi = m / 3 * 3, gj = n / 3 * 3;   //计算元素的宫格位置
        for (num = 0; num < 9; num++)         //根据行元素判断
        {
            if (squa[m][num] == posb)
                return 0;
        }
        for (num = 0; num < 9; num++)          //根据列元素判断
        {
            if (squa[num][n] == posb)
                return 0;
        }
        //根据宫格元素判断
        for (gridi = gi; gridi < gi + 3; gridi++)
        {
            for (gridj = gj; gridj < gj + 3; gridj++)
            {
                if (squa[gridi][gridj] == posb)
                    return 0;
            }
        }
        return 1;
    }
    
    //定义递归函数solve求得一种结果
    void solve(int squa[9][9], int num)
    {   
        void fprintf(int squa[9][9]);
        int posb;
        int i, j, value;
        int magic[9][9];//定义临时数组
        int sm,sn;
        sm=num/9;      //计算元素行数
        sn=num%9;      //计算元素列数
        //将squa中元素赋给magic
        for (i = 0; i < 9; i++)
        {
            for (j = 0; j < 9; j++)
            {
                magic[i][j] = squa[i][j];
            }
        }
        //判断位置处元素非0
        if (magic[sm][sn] != 0)  
        {
            if (sm == 8 && sn == 8) //递归头
            {
                printf("————————参考结果————————\n");
                fprintf(magic);
            }
            else
            {
                solve(magic, num+1);
            }
        }
        else //判断位置处元素为0
        {
            for (posb = 1; posb <= 9; posb++)
            {   //根据判断函数返回值决定是否赋值
                value = judge(magic, sm, sn, posb);
                if (value)
                {
                    magic[sm][sn] = posb;
                    if (sm == 8 && sn == 8) //递归头
                    {
                        printf("————————参考结果————————\n");
                        fprintf(magic);    
                    }
                    else
                    {
                        solve(magic, num+1);
                    }
                    magic[sm][sn] = 0;
                }
            }
        }
    
    }
    
    //打印数组结果函数fprintf的定义
    void fprintf(int squa[9][9])
    { 
      int i,j;
      for (i = 0; i < 9; i++)
            {
                    for (j = 0; j < 9; j++)
                    {   
                         printf("%d ", squa[i][j]);
                        if ((j == 2) || (j == 5)) //换列时加空格
                        printf(" ");
                    }
                    printf("\n");
                    if ((i == 2) || (i == 5))     //换行时加换行符
                    {
                        printf("\n");
                    }
            }            
    }
    
    展开全文
  • C语言实现数独解题程序

    万次阅读 2015-01-31 22:46:45
    用最暴力的递归方式在所有可能的空间中寻找数独的解法。试了一下,不管多难的数独都能在1s内找到所有答案,所以也没有采取更智能的算法进行优化,如加入人的逻辑.../*数独维数组*/ int g_s[9][9] = {  {0,4,0,7,0,

    用最暴力的递归方式在所有可能的空间中寻找数独的解法。试了一下,不管多难的数独都能在1s内找到所有答案,所以也没有采取更智能的算法进行优化,如加入人的逻辑推理算法。

    这里只是把一种最笨的方法分享出来,只是感叹现在的计算机运算能力太强大了。源码如下:


    #include <stdio.h>
    #include <stdlib.h>

    /*数独二维数组*/
    int g_s[9][9] = {    
    {0,4,0,7,0,0,0,0,0},
    {9,2,0,0,0,0,6,0,7},
    {8,3,0,0,0,5,4,0,0},
    {0,1,0,0,0,3,0,0,0},
    {0,0,0,2,0,1,0,0,0},
    {0,0,0,5,0,0,0,4,0},
    {0,0,4,9,0,0,0,7,1},
    {3,0,5,0,0,0,0,9,4},
    {0,0,0,0,0,8,0,6,0}
    };

    /*打印当前数独状态*/
    int prt()
    {
        int i = 0;
        int j = 0;
        for(i = 0;i < 9;i++)
        {
            for(j = 0;j < 9;j++)
            {
                printf("%d ",g_s[i][j]);
            }
            printf("\n");
        }

        getchar();
    }

    /*获取一个位置当前所有可能的解*/
    int get_all_num(int i,int j,int a[9])
    {
        int s[9] = {1,2,3,4,5,6,7,8,9};
        int row,col,k;

        /*删除当前行中已出现的值*/
        for(col = 0;col < 9;col++)
        {
            k = g_s[i][col];
            if(k != 0)
            {
                s[k-1] = 0;
            }
        }

        /*删除当前列中已出现的值*/
        for(row = 0;row < 9;row++)
        {
            k = g_s[row][j];
            if(k != 0)
            {
                s[k-1] = 0;
            }
        }

        /*删除当前九宫格中已出现的值*/
        row = (i/3)*3;
        col = (j/3)*3;
        for(i = row;i < (row+3);i++)
        {
            for(j = col;j < (col+3);j++)
            {
                k = g_s[i][j];
                if(k != 0)
                {
                    s[k-1] = 0;
                }
            }
        }

        i = 0;
        for(k = 0;k < 9;k++)
        {
            if(s[k] != 0)
            {
                a[i] = s[k];
                i++;
            }
        }
        
        return i;
    }

    /*判断当前行是否合法*/
    int check_row(int i,int num)
    {
        int j = 0;
        for(j = 0;j < 9;j++)
        {
            if(g_s[i][j] == num)
            {
                return 0;
            }
        }
        
        return 1;
    }

    /*判断当前列是否合法*/
    int check_col(int j,int num)
    {
        int i = 0;
        for(i = 0;i < 9;i++)
        {
            if(g_s[i][j] == num)
            {
                return 0;
            }
        }

        return 1;
            
    }

    /*判断当前九宫格是否合法*/
    int check_block(int i,int j,int num)
    {
        int row = (i/3)*3;
        int col = (j/3)*3;
        int k = 0;
        int l = 0;
        
        for(k = row;k < (row+3);k++)
        {
            for(l = col;l < (col+3);l++)
            {
                if(g_s[k][l] == num)
                {
                    return 0;
                }
            }
        }
        

        return 1;
    }

    /*尝试一个解*/
    int try_one(int i,int j,int num)
    {
        if(check_row(i,num) && check_col(j,num) &&
            check_block(i,j,num))
        {
            g_s[i][j] = num;
            //prt();
            return 1;
        }

        return 0;
    }

    /*获取下一个要填空的位置*/
    int get_next(int *pi,int *pj)
    {
        int i = *pi;
        int j = *pj;
        int r = i;
        int c = 0;
        j++;

        for(;r < 9;r++)
        {
            for(c = j;c < 9;c++)
            {
                if(g_s[r][c] == 0)
                {
                    *pi = r;
                    *pj = c;
                    return;
                }
            }
            j = 0;
        }

        if(r == 9)
        {
            return 0;
        }

        *pi = r;
        *pj = c;
        return 1;

    }

    /*找到一个解*/
    void finish()
    {
        printf("\n find a solution: \n");
        prt();
    }

    /*处理一个位置*/
    int do_one(int i,int j)
    {
        int row = i;
        int col = j;
        int n = 0;
        int k = 0;
        int a[9] = {0};
        
        /*当前位置有解,下一个位置*/
        if(g_s[row][col] != 0)
        {
            /*获取下一个无解的位置*/
            if(get_next(&row,&col))
            {
                /*对一下个位置递归操作*/
                do_one(row,col);
            }
            /*都有解了,成功*/
            else
            {
                finish();
            }

            /*当前位置有解,直接回溯*/
            return;
        }

        /*当前位置无解*/
        else
        {
            /*获取当前位置的所有可能解*/
            n = get_all_num(i,j,a);
            
            for(k = 0;k < n;k++)
            {
                /*尝试所有可能的解,这里是重复操作,就不改了*/
                if(try_one(i,j,a[k]))
                {
                    row = i;
                    col = j;
                    /*此位置找到合适的了,下一个*/
                    if(get_next(&row,&col))
                    {    
                        do_one(row,col);
                    }
                    /*当前位置已有解且没有下一个了,结束*/
                    else
                    {
                        finish();
                    }
                }
            }

            /*要向前回溯,则这个位置找到的解无效,回溯前清0*/
            g_s[i][j] = 0;
            //prt();
            return;
        }

        
    }

    int main()
    {
        do_one(0,0);

        return 0;

    }


    展开全文
  • 数独,用java实现

    2021-02-06 21:56:38
    程序调用readSolutionO方法来读取数独的解决方案,并且返回个表示数独网格的二维数组。isValid(grid)方法通过检査每个值是否都是从1到9的数字以及每个网格中值是否都是有效的,来确认网格中是否放入了正确的值...
  • 目前只有两个解法,对一般的数独题均能应付。从sudoku up2010上不同难度...1.[文件] sudoku.py~5KB 下载(70)# _*_ coding = utf-8 _*_def gather_col_row(row, col, sudoku):"""收集二维数组sudoku(mxm)中元素(row...
  • 数独规则 数独游戏,经典的为9×9=81个单元格组成的九宫格,同时也形成了3×3=9个小九宫格,要求在81个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复。...只用了个二维数组存储数独
  • 数独问题(工具)

    2016-12-05 22:58:00
    输入数独(用二维数组表示),求出数独的解。 效果图: 实现原理: DFS搜索遍历。 二维数组储存数据。 源代码: #include<iostream> #include<cstring> #include<cstring&...
  • JavaScript开发数独游戏(二)

    千次阅读 2018-09-24 00:16:35
    创建的方式有很多种,但是我们最终要定位到每一个单元格中,这里用行作为第一维数组由9个数组组成,每个数组作为第二维。 先用函数生成行数组,如下: function makeRow(v = 0) { const array = new Array(9); ...
  • 数独计算小程序开发(

    千次阅读 2009-12-22 15:46:00
    前些日子,女朋友给了我数独游戏,弄了好久没弄出来。计算量有点大,于是就想通过编程来计算了,就做了这么个东西来玩玩。... 说说实现吧,数独的数据信息的是记录在个二维数组中的。每个元素为如下数
  • 数独的编程求解

    2020-03-19 16:53:16
    个9*9的二维数组存储九宫格内数据,而每个格子的数据用个二进制表示。这里我采用了10位二进制,最低位作为候选数和已解数的标志,1标志其为候选数,0为已解数。其它9位表示1-9。例如1000000000表示已解数9,...
  • 数独自动计算工具

    2015-06-24 17:21:29
    数独算法说明:用三个二维数组记录数独每个点的状态,SD(i, j)显示数值,也是真实数值(1到9)。ST(i, j)状态,1可由用户输入,2是题目给定的,不能改。SY(i, j)这符串,记录每个点中可能的值。 1、在进行自动计算...
  • 数独暴力猜解

    2019-02-11 11:13:00
    思路 验证已填格子是否合法,非法则回 false 选个空格子,如果没有空格子则返回 true 对空格子进行填数,依次尝试 1-9 ...使用 9 x 9 的二维数组存储所有格子 每个格子维护个可填数的 mask,采用 bitmap 方式...
  • 自动计算数独VB源码

    2015-06-28 12:38:41
    数独算法说明:用三个二维数组记录数独每个点的状态,SD(i, j)显示数值,也是真实数值(1到9)。ST(i, j)状态,1可由用户输入,2是题目给定的,不能改。SY(i, j)字符串,记录每个点中可能的值。 1、在进行自动计算...
  • 软件工程基础——个人项目——数独(5) 生成终局的完善 1.生成终局时,加入2,3;...将move数组设为二维数组,每行对应个移动量的情况,共72行。 将原代码中move的使用方式: num[i][j] = num[0][(j +...
  • 题目要求: 输入个代表数独的字符型二维数组,里面元素是’.'说明没有填上,判断这个数组代表的数独是否是合法状态。 解题思路 implement 1 使用个字符型hashSet,每次遇到个非`'.'`元素c就存储个字符串格式...
  • 在数组维数的选择上,我选择了用一维数组实现。 分析 其实暴力算法求解的实际是,将求解数组的思路,整合成代码,通过代码告诉计算机,让计算机按我们的想法来工作。 首先,9*9数独的规则是,每行九个数各不相同,每...
  • LEETCODE 36. Valid Sudoku

    2017-05-23 21:55:52
    个9维数组,存放每个数字是不是出现过,按列、行、小格遍历 另种解法: 分别用三个数组,第个数组放着某个数字在某列是否出现过;第二个数组放着某个数字在某行是否出现过;第三个数组放着某个数字在...
  • C语言解数独

    2020-02-03 23:29:00
    数独种数学演算的逻辑游戏。玩家需要根据9×9盘面上...二维数组 实现方法: 通过回溯法确定每个位置上的正确数字 输入样例: 1 ? 6 ? 2 ? ? ? 3 ? 9 ? ? ? ? ? 8 2 ? ? 3 8 ? ? 1 6 ? ? 1 4 6 ? ? ? ? ? ? ? ...
  • 题目要求: 跟上题差不多,输入个代表数独的字符二维数组,找出这个数独的正确解。 解题思路 这题时很经典的数独的回溯解法,对于数独中的元素来说,每次输入个可能解,个试如果错误就排除这个答案然后...
  • 题目: 根据9*9盘面上的已知数字,推出所有剩余空格的数字,并满足每行、每列、每个粗线宫内的数字均含1~9且...对于同一行、同一列的重复判断,只需要用两个二维数组表示某个数是否在该行出现。而对小格子...
  • LeetCode解题总结

    2018-10-09 16:02:19
    7.3 在二排序数组中查找给定值 7.4 在旋转有序数组中查找最小值 7.4.1 数组无重复 7.4.2 数组有重复 7.5 在旋转排序数组中查找指定数字 8. 暴力枚举法 8.1 求集合的子集 8.2 集合的全排列 8.3 在指定树中选择进行...
  • 03.实现 Sunday 匹配 04.大数打印 05.验证回文串(125) 06.KMP 精讲 07.旋转字符串(796) 08.最后个单词的长度(58) 二叉树 01.最大深度与DFS(104) 02.层次遍历与BFS(102) 03.BST与其验证(98) 04.BST 的查找(700) ...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

一维数组实现数独