[HackTheBox] Sudoking-writeup

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.

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 |
+-------+-------+-------+

pythonで実装します(ChatGPTが)

def parse_input():
    import sys
    board = []
    for line in sys.stdin:
        line = line.strip()
        if line.startswith('+') or not line:
            continue
        row = []
        for ch in line.split():
            if ch == '|':
                continue
            if ch == '.':
                row.append(0)
            else:
                row.append(int(ch))
        board.append(row)
    return board

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

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

def print_board(board):
    for i in range(9):
        if i % 3 == 0:
            print("+-------+-------+-------+")
        row = ""
        for j in range(9):
            if j % 3 == 0:
                row += "| "
            row += str(board[i][j]) + " "
        row += "|"
        print(row)
    print("+-------+-------+-------+")

if __name__ == "__main__":
    board = parse_input()
    if solve(board):
        print_board(board)