Valid Sudoku ใน Python - ตรวจสอบ Sudoku ถูกต้องหรือไม่

สมมติว่าเรามีกระดาน Sudoku ขนาด 9x9 เราต้องตรวจสอบว่าถูกต้องหรือไม่ เฉพาะช่องที่กรอกแล้วเท่านั้นที่ต้องตรวจสอบตามกฎ:

• แต่ละแถวต้องมีตัวเลข 1-9 ไม่ซ้ำ
• แต่ละคอลัมน์ต้องมีตัวเลข 1-9 ไม่ซ้ำ
• แต่ละกล่อง 3x3 (ย่อย 9 กล่อง) ต้องมีตัวเลข 1-9 ไม่ซ้ำ

ตัวอย่าง Sudoku grid ที่ถูกต้อง:

ขั้นตอนการทำงาน

1. วนลูป i จาก 0 ถึง 8:
   • สร้าง dictionary ว่าง row, col, block
   • row_cube := 3 * (i // 3), col_cube := 3 * (i % 3)
   • วนลูป j จาก 0 ถึง 8:
     • ถ้า board[i][j] != '.' และอยู่ใน row คืน false
     • row[board[i][j]] := 1
     • ถ้า board[j][i] != '.' และอยู่ใน col คืน false
     • col[board[j][i]] := 1
     • rc := row_cube + j//3, cc := col_cube + j%3
     • ถ้า board[rc][cc] in block และไม่ใช่ '.' คืน false
     • block[board[rc][cc]] := 1
2. คืน true

ตัวอย่างโค้ด (Python)

class Solution(object):
    def isValidSudoku(self, board):
        for i in range(9):
            row = {}
            column = {}
            block = {}
            row_cube = 3 * (i // 3)
            column_cube = 3 * (i % 3)
            for j in range(9):
                if board[i][j] != '.' and board[i][j] in row:
                    return False
                row[board[i][j]] = 1
                if board[j][i] != '.' and board[j][i] in column:
                    return False
                column[board[j][i]] = 1
                rc = row_cube + j // 3
                cc = column_cube + j % 3
                if board[rc][cc] in block and board[rc][cc] != '.':
                    return False
                block[board[rc][cc]] = 1
        return True

ob1 = Solution()
print(ob1.isValidSudoku([
    ["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",".","."],
    [".",".",".",".",".","8",".",".","7","9"]
]))

อินพุต

[["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",".","."],[".",".",".",".",".","8",".",".","7","9"]]

เอาต์พุต

true