Sudoku Solver

分手后的思念是犯贱 2023-06-09 13:28 17阅读 0赞

# Sudoku Solver #

### 文章目录 ###

*  Sudoku Solver
 *   *  题目
     *  分析
     *  代码如下

## 题目 ##

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1.  Each of the digits `1-9` must occur exactly once in each row.
2.  Each of the digits `1-9` must occur exactly once in each column.
3.  Each of the the digits `1-9` must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character `'.'`.

**Note:**

1.  The given board contain only digits `1-9` and the character `'.'`.
2.  You may assume that the given Sudoku puzzle will have a single unique solution.
3.  The given board size is always `9x9`.

## 分析 ##

这道题就是给你一个数独（会空出一些格子），然后要求你根据数独的规则（不了解数独的自行网上查找），推断出这个空格子应该填什么。

题目将会给出一个`char`类型的`9x9`的二维数组，该数组包含数字`1 - 9`和字符`.`（表示空格）。然后要求你根据数独的规则填充这个给出的二维数组。

**数独的规则**：每一行，每一类，每个九宫格都不能有相同的数字。

这道题直接使用DFS求解即可。  
首先，寻找出那些没有数字的位置并把它们记录下来。  
然后使用DFS，对每个没有数字地位置从1到9进行尝试。直到能够把所有地空格填满而且没有冲突为止。

## 代码如下 ##

class Solution { 
        public void solveSudoku(char[][] board) { 
        	int[] empty = new int[81];
        	int empty_count = 0;
        	// 寻找出没有数字地位置
        	for (int i = 0; i < 9; i++) { 
        		for (int j = 0; j < 9; j++) { 
        			if (board[i][j] == '.') { 
        				empty[empty_count] = i * 9 + j;
        				empty_count++;
        			}
        		}
        	}
            // DFS求解
        	boolean flag = false;
        	for (int i = 0; i < 9; i++) { 
        		flag = DFS((char)('1' + i), board, empty, empty_count, 0);
        		if (flag) { 
        			return;
        		}
        	}
        }
        
        private boolean DFS(char target, char[][] board, int[] empty, int empty_count, int empty_index) { 
        	int row = empty[empty_index] / 9;
        	int col = empty[empty_index] % 9;
        	if (checkTarget(target, board, row, col)) {   // 该数字满足要求
        		board[row][col] = target;
    // empty_index++;
        		if (empty_index + 1== empty_count) {   // 如果所有空都被填满
        			return true;
        		} else { 
        			boolean flag = false;
        			for (int i = 0; i < 9; i++) { 
        				// 填下一个空格，尝试['1', ..., '9']
        				flag = DFS((char)(i + '1'), board, empty, empty_count, empty_index + 1);
        				if (flag) { 
        					return flag;
        				}
        			}
        			// 下一个空格没有符合要求的，回退
        			board[row][col] = '.';
        			return flag;
    			}
        	} else { 
        		return false;
    		}
        }
        
        private boolean checkTarget(char target, char[][] board, int row, int col) { 
        	return checkRow(target, row, board) &&
        			checkCol(target, col, board) && checkCell(target, row / 3, col / 3, board);
        }
        
        private static boolean checkRow(char target, int row, char[][] board) { 
        	for (int i = 0; i < 9; i++) { 
        		if (board[row][i] == target) { 
        			return false;
        		}
        	}
        	return true;
        }
        
        private static boolean checkCol(char target, int col, char[][] board) { 
        	for (int i = 0; i < 9; i++) { 
        		if (board[i][col] == target) { 
        			return false;
        		}
        	}
        	return true;
        }
        
        private static boolean checkCell(char target, int x, int y, char[][] board) { 
        	int row = x * 3;
        	int col = y * 3;
        	for (int i = row; i < row + 3; i++) { 
        		for (int j = col; j < col + 3; j++) { 
        			if (board[i][j] == target) { 
        				return false;
        			}
        		}
        	}
        	return true;
        }
    }