課題 · アルゴリズム初級 Python ·

Valid Sudoku

A partially filled 9×9 Sudoku board is given as 9 strings of 9 characters, each a digit 1–9 or "." for an empty cell. Return True if no row, no column and no 3×3 box contains the same digit twice. The board doesn't have to be solvable.

シグネチャ

def valid_sudoku(board: list[str]) -> bool:

入力例

valid_sudoku(['53..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])  # -> True
valid_sudoku(['83..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])  # -> False

その他、入力値が非公開の6個の非公開テストおよび制限時間付きの0個の大規模入力テストがあります。モデルへの課題は英語で出題されます。

#1DeepSeek V4 Pro 0423正解 · 8 / 8 件のテストにパス回答時間 5.7 秒 · 実行時間 6 ms · $0.0006

✓	valid_sudoku(['53..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 True	<1 ms
✓	valid_sudoku(['83..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 False	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms

コード

def valid_sudoku(board: list[str]) -> bool:
    # Check rows
    for row in board:
        seen = 0
        for ch in row:
            if ch == '.':
                continue
            d = int(ch)
            mask = 1 << d
            if seen & mask:
                return False
            seen |= mask

    # Check columns
    for c in range(9):
        seen = 0
        for r in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch)
            mask = 1 << d
            if seen & mask:
                return False
            seen |= mask

    # Check 3x3 boxes
    for box_r in range(0, 9, 3):
        for box_c in range(0, 9, 3):
            seen = 0
            for r in range(box_r, box_r + 3):
                for c in range(box_c, box_c + 3):
                    ch = board[r][c]
                    if ch == '.':
                        continue
                    d = int(ch)
                    mask = 1 << d
                    if seen & mask:
                        return False
                    seen |= mask

    return True

#1OpenAI GPT-6 Luna正解 · 8 / 8 件のテストにパス回答時間 1.8 秒 · 実行時間 8 ms · $0.0001

✓	valid_sudoku(['53..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 True	<1 ms
✓	valid_sudoku(['83..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 False	<1 ms

✓ 1 ms✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms

コード

def valid_sudoku(board: list[str]) -> bool:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9

    for r, line in enumerate(board):
        for c, ch in enumerate(line):
            if ch == ".":
                continue
            bit = 1 << (ord(ch) - ord("1"))
            box = (r // 3) * 3 + c // 3
            if rows[r] & bit or cols[c] & bit or boxes[box] & bit:
                return False
            rows[r] |= bit
            cols[c] |= bit
            boxes[box] |= bit
    return True

#1MiniMax M3.1 Flash正解 · 8 / 8 件のテストにパス回答時間 805 ms · 実行時間 8 ms · $0.0001

✓	valid_sudoku(['53..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 True	<1 ms
✓	valid_sudoku(['83..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 False	<1 ms

✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms

コード

def valid_sudoku(board: list[str]) -> bool:
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9

    for r, row in enumerate(board):
        for c, ch in enumerate(row):
            if ch == ".":
                continue
            bit = 1 << (ord(ch) - ord("1"))
            b = (r // 3) * 3 + c // 3
            if (rows[r] | cols[c] | boxes[b]) & bit:
                return False
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit

    return True

#1Anthropic Claude Opus 5.5正解 · 8 / 8 件のテストにパス回答時間 2.7 秒 · 実行時間 8 ms · $0.0056

✓	valid_sudoku(['53..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 True	<1 ms
✓	valid_sudoku(['83..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'])期待値 False	2 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms

コード

def valid_sudoku(board: list[str]) -> bool:
    seen = set()
    add = seen.add
    for i in range(9):
        row = board[i]
        bi = (i // 3) * 3
        for j in range(9):
            c = row[j]
            if c == '.':
                continue
            r = (0, i, c)
            k = (1, j, c)
            b = (2, bi + j // 3, c)
            if r in seen or k in seen or b in seen:
                return False
            add(r)
            add(k)
            add(b)
    return True

トークンコスト: $0.0065 · 対戦の進行と評価方法について →