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;
}
}