本文共 3141 字，大约阅读时间需要 10 分钟。

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求解即可。

代码如下

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

转载地址：http://yibmb.baihongyu.com/