判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 1、数字 1-9 在每一行只能出现一次。 2、数字 1-9 在每一列只能出现一次。 3、数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字，空白格用 0 表示。 示例1： { 5 , 3 , 0 , 0 , 7 , 0 ,0 , 0 , 0 }, { 6 , 0 , 0 , 1 , 9 , 5 ,0 , 0 , 0 }, { 0 , 9 , 8 , 0 , 0 , 0 ,0 , 6 , 0 }, { 8 , 0 , 0 , 0 , 6 , 0 ,0 , 0 , 3 }, { 4 , 0 , 0 , 8 , 0 , 3 ,0 , 0 , 1 }, { 7 , 0 , 0 , 0 , 2 , 0 ,0 , 0 , 6 }, { 0 , 6 , 0 , 0 , 0 , 0 ,2 , 8 , 0 }, { 0 , 0 , 0 , 4 , 1 , 9 ,0 , 0 , 5 }, { 0 , 0 , 0 , 0 , 8 , 0 ,0 , 7 , 9 } 输出：true
示例2： { 8 , 3 , 0 , 0 , 7 , 0 ,0 , 0 , 0 }, { 6 , 0 , 0 , 1 , 9 , 5 ,0 , 0 , 0 }, { 0 , 9 , 8 , 0 , 0 , 0 ,0 , 6 , 0 }, { 8 , 0 , 0 , 0 , 6 , 0 ,0 , 0 , 3 }, { 4 , 0 , 0 , 8 , 0 , 3 ,0 , 0 , 1 }, { 7 , 0 , 0 , 0 , 2 , 0 ,0 , 0 , 6 }, { 0 , 6 , 0 , 0 , 0 , 0 ,2 , 8 , 0 }, { 0 , 0 , 0 , 4 , 1 , 9 ,0 , 0 , 5 }, { 0 , 0 , 0 , 0 , 8 , 0 ,0 , 7 , 9 } 输出：false 但由于位于第一列宫内有两个 8 存在, 因此这个数独是无效的。
思路： 9 * 9 划分成 3 * 3个方格 = 9行划分成3份行格，9列也划分成3份列格。
9行划分成3份行格 i / 3 ，确定是第几份行格。 如，第8行，8/3 = 2，第8行属于第2份行格（起始行为第0行）
9列也划分成3份列格 j / 3, 确定是第几份列格。 如，第5行，5/3 = 1，第8行属于第1份行格（起始行为第0行）
方格索引 9 * 9 划分成 3 * 3个方格，行格下标为i / 3，列格下标为j / 3，也就是[x，y]=[i/3 , j/3] 那么处于第几个方格就可以算出来了：x * 列格数 + y = i / 3 * 3 + j / 3
package com.loo;
import java.util.HashSet;
public class ValidSudo {
public static final int sudoLength = 9; public static void main(String[] args) { int[][] arr = new int[][] { { 5 , 3 , 0 , 0 , 7 , 0 ,0 , 0 , 0 }, { 6 , 0 , 0 , 1 , 9 , 5 ,0 , 0 , 0 }, { 0 , 9 , 8 , 0 , 0 , 0 ,0 , 6 , 0 }, { 8 , 0 , 0 , 0 , 6 , 0 ,0 , 0 , 3 }, { 4 , 0 , 0 , 8 , 0 , 3 ,0 , 0 , 1 }, { 7 , 0 , 0 , 0 , 2 , 0 ,0 , 0 , 6 }, { 0 , 6 , 0 , 0 , 0 , 0 ,2 , 8 , 0 }, { 0 , 0 , 0 , 4 , 1 , 9 ,0 , 0 , 5 }, { 0 , 0 , 0 , 0 , 8 , 0 ,0 , 7 , 9 } }; int[][] arr2 = new int[][] { { 8 , 3 , 0 , 0 , 7 , 0 ,0 , 0 , 0 }, { 6 , 0 , 0 , 1 , 9 , 5 ,0 , 0 , 0 }, { 0 , 9 , 8 , 0 , 0 , 0 ,0 , 6 , 0 }, { 8 , 0 , 0 , 0 , 6 , 0 ,0 , 0 , 3 }, { 4 , 0 , 0 , 8 , 0 , 3 ,0 , 0 , 1 }, { 7 , 0 , 0 , 0 , 2 , 0 ,0 , 0 , 6 }, { 0 , 6 , 0 , 0 , 0 , 0 ,2 , 8 , 0 }, { 0 , 0 , 0 , 4 , 1 , 9 ,0 , 0 , 5 }, { 0 , 0 , 0 , 0 , 8 , 0 ,0 , 7 , 9 } }; System.out.println(isValidSudo(arr)); System.out.println(isValidSudo(arr2)); }
public static boolean isValidSudo(int[][] board) { if (board == null || board.length != sudoLength || board[0].length != sudoLength) { System.out.println("isValidSudo Error!!!"); return false; } HashSet<Integer>[] rows = new HashSet[sudoLength]; HashSet<Integer>[] cols = new HashSet[sudoLength]; HashSet<Integer>[] boxes = new HashSet[sudoLength]; for (int i=0;i<sudoLength;i++) { rows[i] = new HashSet<Integer>(); cols[i] = new HashSet<Integer>(); boxes[i] = new HashSet<Integer>(); } for (int i=0;i<sudoLength;i++) { for (int j=0;j<sudoLength;j++) { int temp = board[i][j]; if (temp == 0) { continue; } if (rows[i].contains(temp) || cols[j].contains(temp) || boxes[(i/3)*3+j/3].contains(temp)) { return false; } rows[i].add(temp); cols[j].add(temp); boxes[(i/3)*3+j/3].add(temp); } } return true; }
}
