Java教程

牛客华为机试HJ44

本文主要是介绍牛客华为机试HJ44,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题传送门

1. 题目描述

2. Solution

1、思路
从上到下,从左到右遍历,每个空位置。在第一个空位置,随便填一个合法的数字,递归在填充后续空位置。如果,期间出现没有数字可以填的话,就回退到上一个位置,换下一个数字,继续。

import sys

if sys.platform != "linux":
    file_in = open("input/HJ44.txt")
    sys.stdin = file_in

board = [list(map(int, line.strip().split())) for line in sys.stdin]


def is_valid(board, row, col, num):
    block_row = (row // 3) * 3
    block_col = (col // 3) * 3
    for i in range(9):
        if board[i][col] == num or board[row][i] == num or board[block_row + i // 3][block_col + i % 3] == num:
            return False
    return True


def solve(board, row, col):
    for i in range(row, 9):
        for j in range(col, 9):
            if board[i][j] != 0:
                continue
            for num in range(1, 10):
                if is_valid(board, i, j, num):
                    board[i][j] = num
                    if solve(board, i, j + 1):
                        return True
                    board[i][j] = 0
            return False
        col = 0
    return True


def main():
    solve(board, 0, 0)
    for rows in board:
        for row in rows:
            print(row, end=" ")
        print()


if __name__ == '__main__':
    main()
这篇关于牛客华为机试HJ44的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!