网站首页设计注意,微信公众平台注册官网登录入口,WordPress资讯网站,静态网页设计作品欣赏JAVA代码—算法基础#xff1a;数独问题#xff08;Sodoku Puzzles#xff09; 数独问题#xff08;Sodoku Puzzles#xff09; 数独游戏#xff08;日语#xff1a;数独 すうどく#xff09;是一种源自18世纪末的瑞士的游戏#xff0c;后在美国发展、并在日本得以发扬… JAVA代码—算法基础数独问题Sodoku Puzzles 数独问题Sodoku Puzzles 数独游戏日语数独 すうどく是一种源自18世纪末的瑞士的游戏后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。 拼图是九宫格即3格宽×3格高的正方形状每一格又细分为一个九宫格。在每一个小九宫格中分别填上1至9的数字让整个大九宫格每一列、每一行的数字都不重复。 数独的玩法逻辑简单数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。 基本术语 单元格和值 一个数独谜题通常包含有9x981个单元格每个单元格仅能填写一个值。对一个未完成的数独题有些单元格中已经填入了值另外的单元格则为空等待解题者来完成。 行和列 习惯上横为行纵为列在这里也不例外。行由横向的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) {HashSetInteger set new HashSetInteger();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;}
} 完原文地址http://www.bieryun.com/2479.html
