Sudoking

DESCRIPTION

Welcome to the SudoKing challenge! In this task, your objective is to write a program that solves a given Sudoku puzzle.

Challenge Description:

You will receive an incomplete Sudoku puzzle as input. Your program must solve the puzzle and output the completed Sudoku grid. The input and output will be formatted with box separators to clearly delineate the 3x3 subgrids. Ensure that your output matches the required format exactly, including the box separators and line breaks. Note: You only need to print the correctly solved Sudoku puzzle. Do not include any additional text or debugging information in your output.

Example
Input
+-------+-------+-------+
| . . 1 | 2 7 5 | . 9 6 |
| 8 5 . | 6 . 3 | 4 . . |
| . . . | . 1 4 | 3 . 2 |
+-------+-------+-------+
| . 3 . | . . . | 7 . . |
| . 2 8 | 3 . . | 9 6 . |
| . 7 . | 9 2 . | 1 . 5 |
+-------+-------+-------+
| . . . | . 4 . | . . 1 |
| 9 . 5 | . . . | 2 4 3 |
| 4 . 7 | . 3 . | . . . |
+-------+-------+-------+
Output

+-------+-------+-------+
| 2 4 1 | 2 7 5 | 8 9 6 |
| 8 5 6 | 6 4 3 | 4 1 2 |
| 7 9 3 | 5 1 4 | 3 8 2 |
+-------+-------+-------+
| 5 3 2 | 1 8 9 | 7 6 4 |
| 6 2 8 | 3 5 7 | 9 6 1 |
| 4 7 9 | 9 2 6 | 1 3 5 |
+-------+-------+-------+
| 3 6 8 | 4 4 2 | 5 7 1 |
| 9 1 5 | 7 6 8 | 2 4 3 |
| 4 8 7 | 2 3 1 | 6 5 9 |
+-------+-------+-------+

SOLUTION

def parse_input():
    import sys
    grid = []

    # Read each line from standard input
    for line in sys.stdin:
        line = line.strip()

        # Skip border lines like '+-------+'
        if line.startswith("+"):
            continue

        # Parse lines that contain actual Sudoku values
        if "|" in line:
            row = []

            # Extract values between '|' separators
            for part in line.split("|")[1:-1]:
                # Convert '.' to 0 (empty cell), digits to int
                for val in part.strip().split():
                    row.append(0 if val == '.' else int(val))
            grid.append(row)

    return grid


def is_valid(board, row, col, num):
    # Check if the number exists in the current row or column
    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False

    # Check the 3x3 subgrid
    startRow, startCol = 3 * (row // 3), 3 * (col // 3)
    for i in range(startRow, startRow + 3):
        for j in range(startCol, startCol + 3):
            if board[i][j] == num:
                return False

    return True


def solve_sudoku(board):
    # Backtracking algorithm to solve Sudoku
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                # Try placing digits 1 through 9
                for num in range(1, 10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num  # Tentatively assign

                        if solve_sudoku(board):  # Recursive call
                            return True

                        board[row][col] = 0  # Backtrack

                return False  
    return True  


def print_board(board):
    # Generate sudoku board 
    for i in range(9):
        if i % 3 == 0:
            print("+-------+-------+-------+")
        for j in range(9):
            if j % 3 == 0:
                print("|", end=" ")
            print(board[i][j], end=" ")
        print("|")
    print("+-------+-------+-------+")


sudoku_board = parse_input()         
solve_sudoku(sudoku_board)         
print_board(sudoku_board)