JAVA代码—算法基础：数独问题（Sodoku Puzzles）
JAVA代码—算法基础：数独问题（Sodoku Puzzles）
数独问题（Sodoku Puzzles）
数独游戏（日语：数独 すうどく）是一种源自18世纪末的瑞士的游戏，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。
拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。 数独的玩法逻辑简单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。
基本术语
单元格和值
一个数独谜题通常包含有9x9=81个单元格，每个单元格仅能填写一个值。对一个未完成的数独题，有些单元格中已经填入了值，另外的单元格则为空，等待解题者来完成。
行和列
习惯上，横为行，纵为列，在这里也不例外。行由横向的9个单元格组成，而列由纵向的9个单元格组成。很明显，整个谜题由9行和9列组成。
例如：一行的情况
例如：一列的情况
例如：一个完整的方形
接下来看问题：
原问题链接：https://leetcode.com/problems/valid-sudoku/description/
问题描述：判断一个数独游戏是否合法。数独当前可以是部分填充，未填充部分用’.’代替。
有效地数独并不是指该游戏是否有解，而仅仅判断当前填充是否有效。
问题分析
判断数独是否有效，对于当前填充的数字，可以依次检查：
- 对于大九宫格来说，每一行，每一列不能有重复的数字。如果有重复的数字，就不是数独。
- 对于每个小九宫格来说，不能有重复的数字。如果有重复的数字，就不是数独。
算法设计
0 => 0, 1 => 3, 2 => 6
3 => 0, 4 => 3, 5 => 6
6 => 0, 7 => 3, 8 => 6
x = (i % 3) * 3
0 => 0, 1 => 0, 2 => 0
3 => 3, 4 => 3, 5 => 3
6 => 6, 7 => 6, 8 => 6
y = i / 3 * 3
public class Solution {
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i < 9; i++) {
if(!isValid(board, i, i, 0, 8) || !isValid(board, 0, 8, i, i) || !isValid(board, i / 3 * 3, i / 3 * 3 + 2, i % 3 * 3, i % 3 * 3 + 2)) return false;
}
return true;
}
public boolean isValid(char[][] board, int xStart, int xEnd, int yStart, int yEnd) {
HashSet<Integer> set = new HashSet<Integer>();
for(int x = xStart; x <= xEnd; x++) {
for(int y = yStart; y <= yEnd; y++) {
if(board[x][y] != '.' && !set.add(board[x][y] - '0')) return false;
}
}
return true;
}
}
