JAVA代碼—算法基礎：數獨問題（Sodoku Puzzles）

數獨問題（Sodoku Puzzles）

數獨游戲（日語：數獨 すうどく）是一種源自18世紀末的瑞士的游戲，后在美國發展、并在日本得以發揚光大的數學智力拼圖游戲。
拼圖是九宮格（即3格寬×3格高）的正方形狀，每一格又細分為一個九宮格。在每一個小九宮格中，分別填上1至9的數字，讓整個大九宮格每一列、每一行的數字都不重復。 數獨的玩法邏輯簡單，數字排列方式千變萬化。不少教育者認為數獨是鍛煉腦筋的好方法。

基本術語

單元格和值

一個數獨謎題通常包含有9x9=81個單元格，每個單元格僅能填寫一個值。對一個未完成的數獨題，有些單元格中已經填入了值，另外的單元格則為空，等待解題者來完成。

行和列

習慣上，橫為行，縱為列，在這里也不例外。行由橫向的9個單元格組成，而列由縱向的9個單元格組成。很明顯，整個謎題由9行和9列組成。

例如：一行的情況

例如：一列的情況

例如：一個完整的方形

接下來看問題：

原問題鏈接：https://leetcode.com/problems/valid-sudoku/description/

問題描述：判斷一個數獨游戲是否合法。數獨當前可以是部分填充，未填充部分用’.’代替。
有效地數獨并不是指該游戲是否有解，而僅僅判斷當前填充是否有效。

問題分析

判斷數獨是否有效，對于當前填充的數字，可以依次檢查：

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