leetcode 36. Valid Sudoku
问题描述
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'. A partially filled sudoku which is valid.Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
问题分析
本问题主要是判断这个数独目前是否符合数独需要的三条规则，即行列，方框内是否是1~9，但是并不需要判断这个数独是否可解。我们可以直接将行列方框内的数分别用hashset存取 如果一旦出现添加某元素已存在的情况直接返回false即可，直到所有都添加完后还是没有冲突则表明当前数独是成立的。
java代码实现
import java.util.HashSet;
/**
* @Author: LiuYafei
* @Date: 2017/10/31
* @Time: 20:38
* @Description:
*/
public class ValidSudoku {
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i < 9; i++ ) {
HashSet<Character> rows = new HashSet<>();
HashSet<Character> columns = new HashSet<>();
HashSet<Character> cube = new HashSet<>();
for(int j = 0; j < 9; j++ ) {
if (board[i][j] != '.' && !rows.add(board[i][j])) {
return false;
}
if (board[j][i] != '.' && !columns.add(board[j][i])) {
return false;
}
//r和c控制cube的左上角坐标
int r = 3 * (i / 3);
int c = 3 * (i % 3);
if(board[r + j / 3][c + j % 3] != '.' && !cube.add(board[r + j / 3][c + j % 3])) {
return false;
}
}
}
return true;
}
}
leetcode 37. Sudoku Solver
问题描述
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution. A sudoku puzzle...
问题分析
这道题在上一题的基础上直接让编写程序来解这个数独，为此我还手工完成了这个数独（原来真的没有玩过几次数独，突然发现数独挺好玩的，可能荒废了好久的数学细胞又在作祟哈哈哈）。解法的话利用回溯法，简称不达到目的不回头，一出现问题就回头。这个算法的重点在于找好回溯点。话不多说看代码。
java代码
public class SudokuSolver {
public static void solveSudoku(char[][] board) {
if (board == null || board.length == 0) {
return;
}
solve(board);
}
public static boolean solve(char[][] board) {
for(int i=0; i < board.length; i++) {
for (int j=0; j< board[0].length;j++) {
if(board[i][j] == '.') {
for(char c = '1'; c <= '9'; c++) {
if(isVaild(board, i, j, c)) {
board[i][j] = c;
if(solve(board)) {
return true;
}
else {
board[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
}
public static boolean isVaild (char[][] board, int row, int col, char c) {
for(int i=0;i<9;i++) {
if(board[i][col] != '.' && board[i][col] == c) {
return false;
}
if(board[row][i] != '.' && board[row][i] == c) {
return false;
}
if(board[3*(row/3) + i/3][3 * (col / 3) + i % 3] != '.' && board[3*(row/3) + i/3][3 * (col / 3) + i % 3] == c) {
return false;
}
}
return true;
}
public static void main(String[] args) {
char[][] bo = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
SudokuSolver.solveSudoku(bo);
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
System.out.print(bo[i][j] + ",");
}
System.out.println();
}
}
}
在第一次写的时候出现少一个等号，坑了我好久，最后一步步调试才找到，以后更加认真写判断条件，不能想当然。数独真的挺好玩的！！！
转载于:https://www.cnblogs.com/lyf722/p/7766855.html
相关资源：JAVA上百实例源码以及开源项目
