data_structures_algorithms/sudoku_solver.py at main · HmonWutt/data_structures_algorithms · GitHub

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
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
board_2=[[".",".",".",".",".",".",".",".","."],[".","9",".",".","1",".",".","3","."],[".",".","6",".","2",".","7",".","."],[".",".",".","3",".","4",".",".","."],["2","1",".",".",".",".",".","9","8"],[".",".",".",".",".",".",".",".","."],[".",".","2","5",".","6","4",".","."],[".","8",".",".",".",".",".","1","."],[".",".",".",".",".",".",".",".","."]]
def sudoku_solver(board):
    if not is_empty(board):
        print_board(board)
        return True
    length = len(board)
    for row in range(length):
        for col in range(length):
            if is_cell_empty(board,row,col):

                for num in range(1,length+1):
                    if is_valid(num,board,row,col):
                        board[row][col] = str(num)
                        if sudoku_solver(board):
                            return True
                        board[row][col] = "."
                return False


    return False

def is_empty(board):
    is_empty = False
    for row in range(len(board)):
        for col in range(len(board)):
            if board[row][col] == ".":
                return True
    return is_empty
def is_cell_empty(board,row,col):
    return board[row][col] =="."

def is_valid(num,board,row,col):
    for r in range(len(board)):
        if board[r][col]==str(num):
            return False

    for c in range(len(board)):
        if board[row][c]==str(num):
            return False

    r = (row//3 )*3
    c = (col//3) *3
    for rr in range(r,r+3):
        for cc in range(c,c+3):
            if board[rr][cc] == str(num):
                return False
    return True


def print_board(board):
    for row in board:
        print(row)
    print()

sudoku_solver(board_2)