Sudoku Solver-蒲公英云

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:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
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:

The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
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;
    }
}