-
LeetCode第三十七题-实现数独
2019-05-14 12:02:58问题简介:给定一个大小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实现的数独求解问题示例
2021-01-20 01:37:56对于给出的数字二维数组,要求每行每列的数字不能重复。 二、实现代码: <?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.所有可行数字逐一填入得到结果。本程序求解数独部分也采用这样的算法。而生成题目的算法是:
- 随机产生一个长度为9的一维数组,元素是随机产生的1到9的不同数字。
比如为root = [1, 4, 3, 5, 6 ,7, 8 ,9, 2].
- 先获得一个填满的九宫格accord。
- 假如九宫格accord的第一行为[6, 4, 5, 7, 3, 9, 8, 1, 2], 则可获得的九宫格squa的第一行第一列元素这样产生:看accord对应元素为6,则看root中6后一位的数为7,则所求数字为7。以此类推。
- 根据难度随机去除一定数量的空格则得到了随机产生的数独题目。
下面介绍本程序的主要难点和创新点:
-
解数独的递归法。首先要定义一个检查函数judge用于判断某个数字在某个位置是否合适,进而根据找到的递归头即至最后一个位置后,分是否为0两种情况,否则,继续递归。
-
随机产生1到9之间的数。由于编译器自带函数rand会出现元素不变的确点,所以使用系统时间为种子,并引入全局变量index,使得时间差加大,避免固定不变。
-
定义各种函数简化程序。本程序定义了fprintf用于打印九宫格,定义reRank来获取元素在数组中位置等,简化了程序。
结果
下面是分别选择1(产生题目)和2(计算数独)后的结果图:
代码:
语言: 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的数字以及每个网格中值是否都是有效的,来确认网格中是否放入了正确的值... -
完成数独的算法 python_数独人工算法的python实现
2021-01-11 23:35:33目前只有两个解法,对一般的数独题均能应付。从sudoku up2010上不同难度...1.[文件] sudoku.py~5KB 下载(70)# _*_ coding = utf-8 _*_def gather_col_row(row, col, sudoku):"""收集二维数组sudoku(mxm)中元素(row... -
JavaScript遍历求解数独问题的主要思路小结
2020-11-24 11:33:10数独规则 数独游戏,经典的为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)
2020-01-19 00:42:07软件工程基础——个人项目——数独(5) 生成终局的完善 1.生成终局时,加入2,3;...将move数组设为二维数组,每一行对应一个移动量的情况,共72行。 将原代码中move的使用方式: num[i][j] = num[0][(j +... -
Leetcode1-100: 36. Valid Sudoku
2020-06-07 06:39:34题目要求: 输入一个代表数独的字符型二维数组,里面元素是’.'说明没有填上,判断这个数组代表的数独是否是合法状态。 解题思路 implement 1 使用一个字符型hashSet,每次遇到一个非`'.'`元素c就存储一个字符串格式... -
C语言||暴力算法解数独
2020-07-01 08:14:31在数组维数的选择上,我选择了用一维数组实现。 分析 其实暴力算法求解的实际是,将求解数组的思路,整合成代码,通过代码告诉计算机,让计算机按我们的想法来工作。 首先,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 ? ? ? ? ? ? ? ... -
Leetcode1-100: 37. Sudoku Solver
2020-06-07 06:52:46题目要求: 跟上一题差不多,输入一个代表数独的字符二维数组,找出这个数独的正确解。 解题思路 这题时很经典的数独的回溯解法,对于数独中的元素来说,每次输入一个可能解,一个一个试如果错误就排除这个答案然后... -
程序基本算法习题解析 根据9*9盘面上的已知数字,推出所有剩余空格的数字。
2018-12-25 15:25:56题目: 根据9*9盘面上的已知数字,推出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1~9且...对于同一行、同一列的重复判断,只需要用两个二维数组表示某一个数是否在该行出现。而对小格子... -
LeetCode解题总结
2018-10-09 16:02:197.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) ...
-
Glasterfs 分布式网络文件系统
-
PPTP_NNN 服务生产环境实战教程
-
MYSQL企业常用架构与调优经验分享
-
微动弹道导弹的动态RCS特性研究
-
Unity 热更新技术-ILRuntime
-
Amoeba 实现 MySQL 高可用、负载均衡和读写分离
-
在 Linux 上构建企业级 DNS 域名解析服务
-
用微服务spring cloud架构打造物联网云平台
-
项目管理工具与方法
-
图的遍历
-
php必不可少的开发工具CodeSniffer代码规范phpcs检测及phpcb
-
天池打卡
-
go刷题指北
-
php 浅谈相对路径与绝对路径(../ ./ / )
-
再谈球绑定:AWGN信道上二进制线性码性能评估的新仿真方法
-
Java学习日记 day1
-
jquery如何判断是否是数组元素
-
代管-源码
-
linux基础入门和项目实战部署系列课程
-
白话:java从入门到实战