JAVA代码—算法基础:数独问题(Sodoku Puzzles)

JAVA代码—算法基础:数独问题(Sodoku Puzzles)

JAVA代码—算法基础:数独问题(Sodoku Puzzles)

数独问题(Sodoku Puzzles)

数独游戏(日语:数独 すうどく)是一种源自18世纪末的瑞士的游戏,后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。
拼图是九宫格(即3格宽×3格高)的正方形状,每一格又细分为一个九宫格。在每一个小九宫格中,分别填上1至9的数字,让整个大九宫格每一列、每一行的数字都不重复。 数独的玩法逻辑简单,数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。

基本术语

单元格和值

一个数独谜题通常包含有9x9=81个单元格,每个单元格仅能填写一个值。对一个未完成的数独题,有些单元格中已经填入了值,另外的单元格则为空,等待解题者来完成。

行和列

习惯上,横为行,纵为列,在这里也不例外。行由横向的9个单元格组成,而列由纵向的9个单元格组成。很明显,整个谜题由9行和9列组成。

例如:一行的情况

JAVA代码—算法基础:数独问题(Sodoku Puzzles)

例如:一列的情况

JAVA代码—算法基础:数独问题(Sodoku Puzzles)

例如:一个完整的方形

JAVA代码—算法基础:数独问题(Sodoku Puzzles)

接下来看问题:

原问题链接:https://leetcode.com/problems/valid-sudoku/description/

问题描述:判断一个数独游戏是否合法。数独当前可以是部分填充,未填充部分用’.’代替。
有效地数独并不是指该游戏是否有解,而仅仅判断当前填充是否有效。

JAVA代码—算法基础:数独问题(Sodoku Puzzles)

问题分析

判断数独是否有效,对于当前填充的数字,可以依次检查:

  1. 对于大九宫格来说,每一行,每一列不能有重复的数字。如果有重复的数字,就不是数独。
  2. 对于每个小九宫格来说,不能有重复的数字。如果有重复的数字,就不是数独。

算法设计

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

(完)原文地址http://www.bieryun.com/2479.html

上一篇:jQuery事件代理


下一篇:C++求最大公约数与最小公倍数