原题链接:http://oj.leetcode.com/problems/valid-sudoku/这道题是Sudoku
Solver的一个子问题,在解数独的时候我们需要验证当前数盘是否合法。其实思路比较简单,也就是用brute force。对于每一行,每一列,每个九宫格进行验证,总共需要27次验证,每次看九个元素。所以时间复杂度就是O(3*n^2),
n=9。代码如下:
public boolean isValidSudoku(char[][] board) {
if(board==null || board.length!=9 || board[0].length!=9)
return false;
for(int i=0;i<9;i++)
{
boolean[] map = new boolean[9];
for(int j=0;j<9;j++)
{
if(board[i][j] != '.')
{
if(map[(int)(board[i][j]-'1')])
{
return false;
}
map[(int)(board[i][j]-'1')] = true;
}
}
}
for(int j=0;j<9;j++)
{
boolean[] map = new boolean[9];
for(int i=0;i<9;i++)
{
if(board[i][j] != '.')
{
if(map[(int)(board[i][j]-'1')])
{
return false;
}
map[(int)(board[i][j]-'1')] = true;
}
}
}
for(int block=0;block<9;block++)
{
boolean[] map = new boolean[9];
for(int i=block/3*3;i<block/3*3+3;i++)
{
for(int j=block%3*3;j<block%3*3+3;j++)
{
if(board[i][j] != '.')
{
if(map[(int)(board[i][j]-'1')])
{
return false;
}
map[(int)(board[i][j]-'1')] = true;
}
}
}
}
return true;
}
这道题其实没有什么好的算法,基本上就是遍历去检查,实现上就是数组的操作,属于Sudoku
Solver的subroutine,但是在Sudoku
Solver中实现上又可以进行优化,没必要每次检查整个board,只需要看当前加进去的数就可以,有兴趣的朋友可以看看哈。
分享到:
相关推荐
react-native-smart-sortable-sudoku-grid, 一个智能可以排序的数独网格,用于响应原生应用程序 react-native-smart-sortable-sudoku-grid 一个智能可以排序的数独网格,用于响应原生应用程序。 用JS编写跨平台支持...
Sudoku-Unity-main(20019-2021)火影数独游戏
Sudoku-Unity-main(20019-2021)火影数独游戏(打包)
ufo2mstar-SuDoku-Solver-archive-refs-heads-master.zip
sudoku-solver-源码.rar
sudoku-A.exe
python库。资源全名:Trivial_Sudoku-2.0-py2-none-any.whl
Algorithm-Sudoku-Generator.zip,用改进的高效回溯算法编写的C 数独谜题生成器。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Sudoku-九宫格-数独matlab代码,matlab需要嵌入凸优化CVX工具包
Sudoku-九宫格-数独matlab代码(含CVX工具包)
Algorithm-Sudoku-Solver.zip,一套应用程序,完全用C 编写,解决、验证和生成数独题!,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Sudoku-Sudoku
npm install --save @mattflow/sudoku-solver 或者 yarn add @mattflow/sudoku-solver 简单用法 接受一个字符串或由81个元素组成的数组,其中0表示一个空框。 返回包含已解决难题的字符串。 var solve = require...
数位之和leetcode ...sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which exists once/twice... - count
sudoku example 做leetcode37的时候看到的解数独的非常棒的方法。在简单回溯的基础上还加上了限制条件,会更快。主要参考 . 自己在main里面加上了一点从txt里读写,这样可以自己敲进去题目然后得到答案,比只是...
solving Sudoku puzzle by artificial bee colony algorithm
Sudoku verilog game for fpga. it solve sudoku.
Valid Sudoku 数组 遍历 Sudoku Solver 深度优先遍历 回溯 先检查后修改 Group Anagrams 排序 unordered_map Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree ...
sudoku-reactjs