华为机试-044-困难-HJ44.数独（Sudoku）_python hj44 sudoku

---

一、描述

• 描述
  问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。

例如：
输入

输出

数据范围：输入一个 9*9 的矩阵

1.1、输入描述

• 包含已知数字的9X9盘面数组[空缺位以数字0表示]

1.2、输出描述

• 完整的9X9盘面数组

二、示例

2.1、示例1

输入：

0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1
1
2
3
4
5
6
7
8
9

输出：

5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1
1
2
3
4
5
6
7
8
9

三、答案（java）

3.1、方法一 ：回溯法解数独

package com.tzq.hwod;

import java.util.Scanner;

//注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[][] board = new int[9][9];
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				board[i][j] = in.nextInt();
			}
		}
		solveSudoku(board);
		// 输出二维矩阵
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 8; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.println(board[i][8]);// 换行，每一行的最后一个数字
		}
	}

	public static boolean solveSudoku(int[][] board) {
		// 「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
		// 一行一***定下来之后，递归遍历这个位置放9个数字的可能性！」
		for (int i = 0; i < 9; i++) { // 遍历行
			for (int j = 0; j < 9; j++) { // 遍历列
				if (board[i][j] != 0) { // 跳过原始数字
					continue;
				}
				for (int k = 1; k <= 9; k++) { // (i, j) 这个位置放k是否合适
					if (isValidSudoku(i, j, k, board)) {
						board[i][j] = k;// 将k放在（i，j）
						if (solveSudoku(board)) { // 如果找到合适一组立刻返回
							return true;
						}
						board[i][j] = 0;// 回溯
					}
				}
				// 9个数都试完了，都不行，那么就返回false
				return false;
				// 因为如果一行一***定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
				// 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
			}
		}
		// 遍历完没有返回false，说明找到了合适棋盘位置了
		return true;
	}

	/**
	 * 判断棋盘是否合法有如下三个维度: 同行是否重复 同列是否重复 9宫格里是否重复
	 */
	public static boolean isValidSudoku(int row, int col, int val, int[][] board) {
		// 同行是否重复
		for (int i = 0; i < 9; i++) {
			if (board[row][i] == val) {
				return false;
			}
		}
		// 同列是否重复
		for (int j = 0; j < 9; j++) {
			if (board[j][col] == val) {
				return false;
			}
		}
		// 9宫格里是否重复
		int startRow = (row / 3) * 3;
		int startCol = (col / 3) * 3;
		for (int i = startRow; i < startRow + 3; i++) {
			for (int j = startCol; j < startCol + 3; j++) {
				if (board[i][j] == val) {
					return false;
				}
			}
		}
		return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

四、答案（python 3）

4.1、方法一

#!/usr/bin/python
# -*- coding: UTF-8 -*-


class Solution:

    def isValue(self, board, x, y):
        # 检查已经填入的坐标是否和列中有的元素相等
        for i in range(9):
            if i != x and board[i][y] == board[x][y]:
                return False
        # 检查已经填入的坐标是否和行中有的元素相等
        for j in range(9):
            if j != y and board[x][j] == board[x][y]:
                return False

        # 检查每个正方形是否符合（粗线框内只有1~9）
        m, n = 3*(x // 3), 3*(y // 3)  # 这里求出的是3x3网格的左上角的坐标
        for i in range(3):
            for j in range(3):
                if(i+m != x or j+n != y) and board[i+m][j+n] == board[x][y]:
                    return False

        return True

    def dfs(self, board):

        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    for k in '123456789':  # 从里面选择一个
                        board[i][j] = int(k)
                        if self.isValue(board, i, j) and self.dfs(board):
                            return True
                        # 回溯
                        board[i][j] = 0
                    # 都不行，说明上次的数字不合理
                    return False
        # 全部便利完，返回True
        return True

while True:
    try:
        board = []
        for i in range(9):
            row = list(map(int, input().split()))
            board.append(row)

        s = Solution()
        s.dfs(board)

        for i in range(9):
            board[i] = list(map(str, board[i]))
            print(' '.join(board[i]))
    except:
        break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56