文档章节

验证数独 Valid Sudoku

叶枫啦啦
 叶枫啦啦
发布于 2017/09/04 10:33
字数 981
阅读 16
收藏 0

问题:Determine if a Sudoku is valid, according to: Here are three rules: 

Each row must have the numbers 1-9 occuring just once.

Each column must have the numbers 1-9 occuring just once.

And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

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.

解决:

① 本题是验证一个数独(不一定是完整的,空白的元素用"."来代替)是否是正确的。

九宫格的规则为:

  1. 每一行只能出现1~9一次;
  2. 每一列只能出现1~9一次;
  3. 每个3×3子区域只能出现1~9一次(子区域之间没有交叉,也就是一共有9个子区域)

因为只需要判断已经填入的数字是否合法,那么需要判断每行每列以及每个9宫格的数字是否有重复,很自然的联想到HashSet,因为每个Set里面的元素是不能相同的。顺着这个思路,那么我们为行、列及九宫格各设置9个Hashset元素的数组,每次进行判断即可

class Solution { //34ms
    public boolean isValidSudoku(char[][] board) {
        HashSet[] row = new HashSet[9];
        HashSet[] col = new HashSet[9];
        HashSet[] cell = new HashSet[9];
        for (int i = 0;i < 9 ;i ++ ) {
            row[i] = new HashSet<Character>();
            col[i] = new HashSet<Character>();
            cell[i] = new HashSet<Character>();
        }
        for (int i = 0;i < 9 ;i ++ ) {
            for (int j = 0;j < 9 ;j ++ ) {
                if(board[i][j] != '.'){
                    if(row[i].contains(board[i][j]) || 
                        col[j].contains(board[i][j]) ||
                        cell[3 * (i / 3) + j / 3].contains(board[i][j]))//不能使用add方法判断

                        return false;
                    else{
                        row[i].add(board[i][j]);
                        col[j].add(board[i][j]);
                        cell[3 * (i / 3) + j / 3].add(board[i][j]);
                    }
                }
            }
        }
        return true;
    }
}

② 更详细一点的解法。

本题难点在于表示第i个九宫格每个格点的坐标。
观察行号规律:
第0个九宫格:000111222; 第1个九宫格:000111222; 第2个九宫格:000111222;
第3个九宫格:333444555; 第4个九宫格:333444555; 第5个九宫格:333444555;
第6个九宫格:666777888; 第7个九宫格:666777888; 第8个九宫格:666777888;
可见对于每三个九宫格行号增3;对于单个九宫格,每三个格点行号增1。
因此第i个九宫格的第j个格点的行号可表示为i / 3 * 3 + j / 3
观察列号规律:
第0个九宫格:012012012; 第1个九宫格:345345345; 第2个九宫格:678678678;
第3个九宫格:012012012; 第4个九宫格:345345345; 第5个九宫格:678678678;
第6个九宫格:012012012; 第7个九宫格:345345345; 第8个九宫格:678678678;
可见对于下个九宫格列号增3,循环周期为3;对于单个九宫格,每个格点行号增1,周期也为3。
周期的数学表示就是取模运算mod。
因此第i个九宫格的第j个格点的列号可表示为i % 3 * 3 + j % 3

public class Solution{//29ms
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character> set = new HashSet<Character>();
        // 验证每行
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {

                if (board[i][j] == '.')
                    continue;
                if (! set.add(board[i][j]))
                    return false;
            }
            set.clear();
        }
        // 验证每列
        for (int j = 0; j < 9; j ++) {
            for (int i = 0; i < 9; i ++) {

                if (board[i][j] == '.')
                    continue;
                if (! set.add(board[i][j]))
                    return false;
            }
            set.clear();
        }
        // 验证每个子九宫格
        for (int k = 0; k < 9; k ++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i ++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j ++)
{
                    if (board[i][j] == '.')
                        continue;
                    if (! set.add(board[i][j]))
                        return false;
                }
            }
            set.clear();
        }
        return true;
    }
}

③ 进化版。。。。。

public class Solution {//28ms
    public boolean isValidSudoku(char[][] board) {
        int[] row = new int[9];
        int[] col = new int[9];
        int[] region = new int[9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int mask = 1 << board[i][j] - '1';
                    int k = (i / 3) * 3 + j / 3;
                    if ((row[i] & mask) > 0 || (col[j] & mask) > 0 
                        || (region[k] & mask) > 0) {
                        return false;
                    } else {
                        row[i] |= mask;
                        col[j] |= mask;
                        region[k] |= mask;
                    }
                }
            }
        }
        return true;
    }
}
 

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
验证数独棋盘

原题   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 charact......

一贱书生
2016/12/14
68
0
【Leetcode】【中等】【36. 有效的数独】【JavaScript】

题目描述 36. 有效的数独 判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-...

孙达
10/03
0
0
用react-native实现一个数独游戏(总结)

前言 最近用react-native做了一个数独游戏的app,到今天基本功能已经全都完成并打包在真机上测试了,这里总结一下开发过程中的一些问题和实现的思路。 环境和平台选择 项目上读取的接口是我自...

TokenYang
2017/12/20
0
0
shenxgan/sudoku

数独生成与求解 记得第一次写数独的算法的时候是在大学期间,那时候闲来无事;在手机上玩着数独游戏,看着自己解不出来的题,想着是不是折腾折腾数独,写出一个求解数独的算法出来。 想到就做...

shenxgan
2017/04/28
0
0
JAVA代码—算法基础:数独问题(Sodoku Puzzles)

数独问题(Sodoku Puzzles) 数独游戏(日语:数独 すうどく)是一种源自18世纪末的瑞士的游戏,后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。 拼图是九宫格(即3格宽×3格高)的...

seagal890
2018/03/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

python学习10.04:Python list列表使用技巧及注意事项

前面章节介绍了很多关于 list 列表的操作函数,细心的读者可能会发现,有很多操作函数的功能非常相似。例如,增加元素功能的函数有 append() 和 extend(),删除元素功能的有 clear()、 remo...

太空堡垒185
27分钟前
4
0
新手插画学习的方法?教你如何自学?

插画学习的方法?教你如何自学? 从小喜欢画一些漫画头像随笔画,但是其实没有基础。个人偏好小清新手绘风的插画(如下图),每每看到都希望自己能画出这样的作品。 我其实很想说画这种美术功...

huihuajiaocheng
32分钟前
4
0
面试题

1、实现clone();

gtandsn
43分钟前
5
0
CentOS 7 部署 tesseract-ocr

官方地址 github yum-config-manager --add-repo https://download.opensuse.org/repositories/home:/Alexander_Pozdnyakov/CentOS_7/ 若提示 yum-config-manager: command not found 执行以......

阿白
44分钟前
3
0
JAVA比较器中comparator的使用

一个专用的比较器Comparator Comparator是一个专用的比较器,当一个不支持自比较或者自比较函数不能满足要求时,可写一个比较器来完成两个对象之间大小的比较。Comparator体现了一种策略模式...

daxiongdi
44分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部