专栏首页Petrichor的专栏leetcode: 37. Sudoku Solver

leetcode: 37. Sudoku Solver

Problem

# Write a program to solve a Sudoku puzzle by filling the empty cells.
# 
# Empty cells are indicated by the character '.'.
# 
# You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

AC

class Solution():
    def solveSudoku(self, board):
        def solver(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == ".":
                        for k in range(1, 10):
                            board[i][j] = str(k)
                            if isValid(board, i, j) and solver(board):
                                return True
                            board[i][j] = "."
                        return False
            return True

        def isValid(board, x, y):
            for i in range(9):
                if (i != x and board[i][y] == board[x][y]) or (i != y and board[x][i] == board[x][y]):
                    return False
            for i in range((x//3)*3, (x//3)*3+3):
                for j in range((y//3)*3, (y//3)*3+3):
                    if (i != x or j != y) and board[i][j] == board[x][y]:
                        return False
            return True

        solver(board)


if __name__ == '__main__':
    board = [[".",".","9","7","4","8",".",".","."],
             ["7",".",".",".",".",".",".",".","."],
             [".","2",".","1",".","9",".",".","."],
             [".",".","7",".",".",".","2","4","."],
             [".","6","4",".","1",".","5","9","."],
             [".","9","8",".",".",".","3",".","."],
             [".",".",".","8",".","3",".","2","."],
             [".",".",".",".",".",".",".",".","6"],
             [".",".",".","2","7","5","9",".","."]]
    Solution().solveSudoku(board)
    assert board == [["5","1","9","7","4","8","6","3","2"],
                     ["7","8","3","6","5","2","4","1","9"],
                     ["4","2","6","1","3","9","8","7","5"],
                     ["3","5","7","9","8","6","2","4","1"],
                     ["2","6","4","3","1","7","5","9","8"],
                     ["1","9","8","5","2","4","3","6","7"],
                     ["9","7","5","8","6","3","1","2","4"],
                     ["8","3","2","4","9","1","7","5","6"],
                     ["6","4","1","2","7","5","9","8","3"]]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 79. Word Search

    JNingWei
  • leetcode: 36. Valid Sudoku

    JNingWei
  • 源码安装

    JNingWei
  • Swift 有效的数独 - LeetCode

    判断一个数独是否有效,根据:Sudoku Puzzles - The Rules。 (数独规则: 每一行不能有重复的数字;每一列不能有重复的数字;将数独框划分...

    韦弦zhy
  • leetcode419. Battleships in a Board

    假设有一个2D板,在板上用X表示战舰,已知板上任意两个战舰体之间一定会用.隔开,因此不会出现两个X相邻的情况。现在要求用O(N)的时间复杂度和O(1)的空间复杂...

    眯眯眼的猫头鹰
  • python 实现 2048 游戏 (二)

    上一篇文章中,我们梳理了实现简易版 2048 游戏的基本知识,这篇文章将介绍如何实现各个模块。换句话说,上一次我们确定了旅行的目的地,这一次就让我们自由畅行在山...

    用户2870857
  • leetcode: 79. Word Search

    JNingWei
  • 如此大手笔的个人投资,董明珠这份对造车的执着会得到回报吗?

    镁客网
  • LNMP环境配置SSL证书最简单教程

    用户1700948
  • 2018最新区块链白皮书大全

    用户1408045

扫码关注云+社区

领取腾讯云代金券