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 '.'
.
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.
A sudoku puzzle...
...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(数独游戏)的更多相关文章
-
Leetcode0037--Sudoku Solver 数独游戏
[转载请注明]http://www.cnblogs.com/igoslly/p/8719622.html 来看一下题目: Write a program to solve a Sudoku puzzl ...
-
[LeetCode] Valid Sudoku 验证数独
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be ...
-
LeetCode——Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be ...
-
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 ...
-
Steam 游戏 《Sudoku Universe(数独宇宙)》、《Sudoku Killer(数独杀手)》、《Sudoku Jigsaw(数独拼图)》数字位置解析 ---------C# 数独程序解析(2020年寒假小目标11)
日期:2020.02.11 博客期:151 星期二 今天,准备肝一个 C# 的数独读写工具(汇编语言也在努力学习命令方法中...),这三个游戏我早就买下了,一直放在 Steam 库里积灰,看着它的成就 ...
-
Steam 游戏 《Sudoku Universe(数独宇宙)》——[数独基本局分析]
日期:2020.02.12 博客期:152 星期三 老师给的任务都做完了,15篇博客也都写好了,剩下的几天居然还要每天写一篇~唉~为难我 PH ,剩下的几天就把 我的数独要义分享一下吧! 1.基本局规 ...
-
POJ 2676 - Sudoku - [蓝桥杯 数独][DFS]
题目链接:http://poj.org/problem?id=2676 Time Limit: 2000MS Memory Limit: 65536K Description Sudoku is a ...
-
乘风破浪:LeetCode真题_037_Sudoku Solver
乘风破浪:LeetCode真题_037_Sudoku Solver 一.前言 这次我们对于上次的模型做一个扩展并求解. 二.Sudoku Solver 2.1 问题 2.2 分析与解决 这道题 ...
-
android开发——数独游戏
最近研究了一下android,写了一个数独游戏,具体如下: 游戏界面需要重写一个ShuduView继承View, 然后自定义一个Dialog: 1.需要继承 Dialog 类, 2.并要定义一个有参构 ...
-
C语言学习 数独游戏
摘要:花了1周多时间学习了C语言,开始练手写解数独游戏的程序. C语言学习 数独游戏 作者:乌龙哈里 时间:2015-11-22 平台:Window7 64bit,TCC 0.9.26(x86-64 ...
随机推荐
-
JS魔法堂:再识instanceof
一.Breif 大家都知道instanceof一般就是用来检查A对象是否为B类或子类的实例.那问题是JS中没有类的概念更没有类继承的概念(虽然有构造函数),那么instanceof到底是怎样判断 ...
-
pymongo带认证连接mongo
import pymongo connection = pymongo.MongoClient("127.0.0.1") connection.database.authentic ...
-
JavaScript OOP 思想
JS的核心是对象 {}, new function(){}这种形式也是对象. http://www.nowamagic.net/librarys/veda/detail/241 整理一些网上的资料,供 ...
-
entOS查看系统信息-CentOS查看命令
一:查看cpu more /proc/cpuinfo | grep "model name" grep "model name" /proc/cpuinfo 如 ...
-
HDU 2045 不容易系列之(3)—— LELE的RPG难题 (递推)
题意:略. 析:首先是假设前n-2个已经放好了,那么放第 n 个时,先考虑一下第 n-1 放的是什么,那么有两种情况. 如果n-1放的是和第1个一样的,那么第 n 个就可以在n-2的基础上放2个,也就 ...
-
poj 1011 Sticks (DFS+剪枝)
Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 127771 Accepted: 29926 Descrip ...
-
hdu_1403_Longest Common Substring(后缀数组的应用)
题目链接:hdu_1403_Longest Common Substring 题意: 给你两个字符串,然你找最长的公共子串 题解: 后缀数组的经典应用,要找两个字符串的公共子串,那么就相当于找两个串的 ...
-
Docker 学习笔记
1. Docker 资源 英文资源 Docker 官网:https://www.docker.com/ Docker 官方文档:https://docs.docker.com/ Docker wind ...
-
从一个多项目Web工程看Eclipse如何导入Gradle项目
这里再次说一下为什么我们需要熟悉Gradle构建工具,主要原因就是很多开源项目现在都在改用Gradle作为构建工具.一部分的github上的示例代码也在用Gradle构建,如果还是只能用maven,那 ...
-
Path Creation and Path Painting
[Path Creation and Path Painting] Path creation and path painting are separate tasks. First you crea ...