LeetCode:Valid Sudoku,Sudoku Solver(数独游戏)

时间:2022-09-25 17:52:41
Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

LeetCode:Valid Sudoku,Sudoku Solver(数独游戏)

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

注意到题目中说的,只要当前已经填充的数字是合法的就可以,不一定要这个数独是有解.(下面说的九宫格都是指3*3的网格)

因此只需要判断9*9网格的每一行、每一列、9个小九宫格是否合法。即如果在每一行、每一列、每个9个小九宫格内,某个数字重复出现了,当前数独就是不合法的。                                 本文地址

网上很多解法是:行、列、九宫格、分三个两重循环来分别判断是否合法。其实只需要一个两重循环即可

需要注意的是:如果把九宫格按照行从0开始标号,那么数字board[i][j] 位于第 i/3*3+j/3 个九宫格内

class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int rowValid[10] = {0};//用于判断某一行是否合法,对于行来说这个数组可以重复使用
int columnValid[9][10] = {0};//用于判断某一列是否合法
int subBoardValid[9][10] = {0};//用于判断某一个九宫格是否合法
for(int i = 0; i < 9; i++)
{
memset(rowValid, 0, sizeof(rowValid));
for(int j = 0; j < 9; j++)
if(board[i][j] != '.')
{
if(!checkValid(rowValid, board[i][j]-'0') ||
!checkValid(columnValid[j], board[i][j]-'0') ||
!checkValid(subBoardValid[i/3*3+j/3], board[i][j]-'0'))
return false;
}
}
return true;
}
bool checkValid(int vec[], int val)
{
if(vec[val] == 1)return false;
vec[val] = 1;
return true;
}
};

针对上面的算法,还可以优化空间。上面的算法中,在双重循环时,我们默认了第一重循环表示矩阵的行、第二重循环表示矩阵的列。可以换一种思路:

  • 在检测行是否合法时,i 表示矩阵的行,j 表示矩阵的列;
  • 检测列是否合法时,i 表示矩阵的列,j 表示矩阵的行;
  • 检测九宫格是否合法时,i 表示九宫格的标号,j 表示九宫格里的每个元素(只是我们需要根据i、j定位相应的元素到原来的矩阵:第 i 个九宫格里面的第 j 个元素在原矩阵的第 3*(i/3) + j/3 行,第 3*(i%3) + j%3)列,“/” 表示整数除法)
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int rowValid[10] = {0};//用于判断某一行是否合法
int columnValid[10] = {0};//用于判断某一列是否合法
int subBoardValid[10] = {0};//用于判断某一个九宫格是否合法
for(int i = 0; i < 9; i++)
{
memset(rowValid, 0, sizeof(rowValid));
memset(columnValid, 0, sizeof(columnValid));
memset(subBoardValid, 0, sizeof(subBoardValid));
for(int j = 0; j < 9; j++)
{
if(!checkValid(rowValid, board[i][j]-'0') ||
!checkValid(columnValid, board[j][i]-'0') ||
!checkValid(subBoardValid, board[3*(i/3) + j/3][3*(i%3) + j%3]-'0'))
return false;
}
}
return true;
}
bool checkValid(int vec[], int val)
{
if(val < 0)return true;//对应的是字符‘.’
if(vec[val] == 1)return false;
vec[val] = 1;
return true;
}
};

以上的基础上,当然我们还可以用bitmap来更加压缩空间


Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

LeetCode:Valid Sudoku,Sudoku Solver(数独游戏)

A sudoku puzzle...

LeetCode:Valid Sudoku,Sudoku Solver(数独游戏)

...and its solution numbers marked in red.

这种类型的游戏一般回溯法来解决,设置某个空格时,如果该空格无论设置什么数字都无法达到合法状态,那么回溯重新设置上一个空格,详细见代码注释

class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
if(board[i][j] != '.')
fill(i, j, board[i][j] - '0');
solver(board, 0);
} bool solver(vector<vector<char> > &board, int index)
{// 0 <= index <= 80,index表示接下来要填充第index个格子
if(index > 80)return true;
int row = index / 9, col = index - 9*row;
if(board[row][col] != '.')
return solver(board, index+1);
for(int val = '1'; val <= '9'; val++)//每个为填充的格子有9种可能的填充数字
{
if(isValid(row, col, val-'0'))
{
board[row][col] = val;
fill(row, col, val-'0');
if(solver(board, index+1))return true;
clear(row, col, val-'0');
}
}
board[row][col] = '.';//注意别忘了恢复board状态
return false;
} //判断在第row行col列填充数字val后,是否是合法的状态
bool isValid(int row, int col, int val)
{
if(rowValid[row][val] == 0 &&
columnValid[col][val] == 0 &&
subBoardValid[row/3*3+col/3][val] == 0)
return true;
return false;
} //更新填充状态
void fill(int row, int col, int val)
{
rowValid[row][val] = 1;
columnValid[col][val] = 1;
subBoardValid[row/3*3+col/3][val] = 1;
} //清除填充状态
void clear(int row, int col, int val)
{
rowValid[row][val] = 0;
columnValid[col][val] = 0;
subBoardValid[row/3*3+col/3][val] = 0;
}
private:
int rowValid[9][10];//rowValid[i][j]表示第i行数字j是否已经使用
int columnValid[9][10];//columnValid[i][j]表示第i列数字j是否已经使用
int subBoardValid[9][10];//subBoardValid[i][j]表示第i个小格子内数字j是否已经使用
};

【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3800485.html

LeetCode:Valid Sudoku,Sudoku Solver(数独游戏)的更多相关文章

  1. Leetcode0037--Sudoku Solver 数独游戏

    [转载请注明]http://www.cnblogs.com/igoslly/p/8719622.html 来看一下题目: Write a program to solve a Sudoku puzzl ...

  2. &lbrack;LeetCode&rsqb; Valid Sudoku 验证数独

    Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be ...

  3. LeetCode——Valid Sudoku

    Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be ...

  4. POJ - 2676 Sudoku 数独游戏 dfs神奇的反搜

    Sudoku Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smalle ...

  5. Steam 游戏 《Sudoku Universe(数独宇宙)》、《Sudoku Killer(数独杀手)》、《Sudoku Jigsaw(数独拼图)》数字位置解析 ---------C&num; 数独程序解析(2020年寒假小目标11)

    日期:2020.02.11 博客期:151 星期二 今天,准备肝一个 C# 的数独读写工具(汇编语言也在努力学习命令方法中...),这三个游戏我早就买下了,一直放在 Steam 库里积灰,看着它的成就 ...

  6. Steam 游戏 《Sudoku Universe(数独宇宙)》——&lbrack;数独基本局分析&rsqb;

    日期:2020.02.12 博客期:152 星期三 老师给的任务都做完了,15篇博客也都写好了,剩下的几天居然还要每天写一篇~唉~为难我 PH ,剩下的几天就把 我的数独要义分享一下吧! 1.基本局规 ...

  7. POJ 2676 - Sudoku - &lbrack;蓝桥杯 数独&rsqb;&lbrack;DFS&rsqb;

    题目链接:http://poj.org/problem?id=2676 Time Limit: 2000MS Memory Limit: 65536K Description Sudoku is a ...

  8. 乘风破浪:LeetCode真题&lowbar;037&lowbar;Sudoku Solver

    乘风破浪:LeetCode真题_037_Sudoku Solver 一.前言 这次我们对于上次的模型做一个扩展并求解. 二.Sudoku Solver 2.1 问题 2.2 分析与解决     这道题 ...

  9. android开发——数独游戏

    最近研究了一下android,写了一个数独游戏,具体如下: 游戏界面需要重写一个ShuduView继承View, 然后自定义一个Dialog: 1.需要继承 Dialog 类, 2.并要定义一个有参构 ...

  10. C语言学习 数独游戏

    摘要:花了1周多时间学习了C语言,开始练手写解数独游戏的程序. C语言学习 数独游戏 作者:乌龙哈里 时间:2015-11-22 平台:Window7 64bit,TCC 0.9.26(x86-64 ...

随机推荐

  1. JS魔法堂:再识instanceof

    一.Breif    大家都知道instanceof一般就是用来检查A对象是否为B类或子类的实例.那问题是JS中没有类的概念更没有类继承的概念(虽然有构造函数),那么instanceof到底是怎样判断 ...

  2. pymongo带认证连接mongo

    import pymongo connection = pymongo.MongoClient("127.0.0.1") connection.database.authentic ...

  3. JavaScript OOP 思想

    JS的核心是对象 {}, new function(){}这种形式也是对象. http://www.nowamagic.net/librarys/veda/detail/241 整理一些网上的资料,供 ...

  4. entOS查看系统信息-CentOS查看命令

    一:查看cpu more /proc/cpuinfo | grep "model name" grep "model name" /proc/cpuinfo 如 ...

  5. HDU 2045 不容易系列之&lpar;3&rpar;—— LELE的RPG难题 (递推)

    题意:略. 析:首先是假设前n-2个已经放好了,那么放第 n 个时,先考虑一下第 n-1 放的是什么,那么有两种情况. 如果n-1放的是和第1个一样的,那么第 n 个就可以在n-2的基础上放2个,也就 ...

  6. poj 1011 Sticks (DFS&plus;剪枝)

    Sticks Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 127771   Accepted: 29926 Descrip ...

  7. hdu&lowbar;1403&lowbar;Longest Common Substring&lpar;后缀数组的应用&rpar;

    题目链接:hdu_1403_Longest Common Substring 题意: 给你两个字符串,然你找最长的公共子串 题解: 后缀数组的经典应用,要找两个字符串的公共子串,那么就相当于找两个串的 ...

  8. Docker 学习笔记

    1. Docker 资源 英文资源 Docker 官网:https://www.docker.com/ Docker 官方文档:https://docs.docker.com/ Docker wind ...

  9. 从一个多项目Web工程看Eclipse如何导入Gradle项目

    这里再次说一下为什么我们需要熟悉Gradle构建工具,主要原因就是很多开源项目现在都在改用Gradle作为构建工具.一部分的github上的示例代码也在用Gradle构建,如果还是只能用maven,那 ...

  10. Path Creation and Path Painting

    [Path Creation and Path Painting] Path creation and path painting are separate tasks. First you crea ...