Valid Sudoku

+10

Kamu mendapatkan papan Sudoku 9 × 9 sebagai board, berupa list yang terdiri dari 9 string dengan masing-masing 9 karakter, satu string untuk setiap baris. Setiap karakter adalah digit dari 1 hingga 9 atau . untuk sel kosong. Kembalikan true jika tidak ada digit yang muncul dua kali dalam satu baris, kolom, atau kotak 3 × 3, dan false jika tidak. Hanya sel yang terisi yang diperiksa: papan tidak harus dapat diselesaikan.

Fungsi

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 string yang masing-masing terdiri dari 9 karakter, satu per baris, menggunakan digit 1 sampai 9 dan . untuk sel kosong
Mengembalikanboolean: benar jika tidak ada baris, kolom, atau kotak 3 × 3 yang mengulang digit, salah jika tidak

Batasan

board.length == 9 dan board[i].length == 9
board[i][j] adalah digit dari 1 hingga 9 atau .
Papan mungkin mustahil diselesaikan, yang penting hanya pengulangan di antara sel yang sudah terisi.

Contoh

Input: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Output: true
Penjelasan: Baris 4, dihitung mulai dari 0, .74..89.3, memiliki angka 7, 4, 8, 9, dan 3 masing-masing satu kali, dan tidak ada satu pun dari 26 kelompok lainnya yang mengulang angka.

Input: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Output: false
Penjelasan: Baris 0 dan baris 7 sama-sama dimulai dengan 3, jadi kolom 0 berisi dua angka 3. Keduanya tidak berada di baris atau kotak yang sama, jadi hanya pemeriksaan kolom yang mendeteksinya.

Input: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Output: false
Penjelasan: 5 pada baris 0, kolom 8 dan 5 pada baris 2, kolom 7 tidak berada pada baris atau kolom yang sama, tetapi keduanya berada di kotak kanan atas, jadi jawabannya adalah false.

Pertanyaan lanjutan

Bagaimana cara memeriksa papan 16 × 16 dengan kotak 4 × 4 dan simbol 1 sampai 9 serta A sampai G? Menjadi seperti apa rumus kotaknya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap digit termasuk dalam tiga kelompok: barisnya, kolomnya, dan kotak 3 × 3-nya. Baris dan kolom mudah diindeks, kotak adalah tempat bug bersembunyi. Beri nomor kotak dari 0 sampai 8 dengan (r / 3) * 3 + c / 3, lalu satu kali melewati 81 sel akan memeriksa semua 27 kelompok.

Periksa setiap baris, kolom, dan kotak secara terpisah

Intuisi

Aturan ini menetapkan 27 kelompok: 9 baris, 9 kolom, dan 9 kotak. Kumpulkan sembilan sel dari setiap kelompok, lalu cari digit yang berulang dengan mengabaikan titik. Papan valid tepat ketika tidak ada kelompok yang memiliki digit berulang.

Penanda untuk setiap digit dapat menemukan pengulangan di antara sembilan sel. Setiap dari 81 sel dibaca sekali untuk masing-masing dari tiga kelompoknya: 243 pembacaan, jumlah pekerjaan yang tetap. Pada papan n × n, metode yang sama memerlukan O(n²).

Algoritma

Untuk i dari 0 sampai 8, kumpulkan baris i, kolom i, dan kotak i.
Kotak i memiliki sudut di baris 3 * (i / 3), kolom 3 * (i % 3); selnya yang ke-k berada k / 3 baris ke bawah dan k % 3 kolom ke kanan dari sudut tersebut.
Telusuri setiap kelompok dengan penanda seen baru, lewati titik. Jika digit sudah ditandai, kembalikan false.
Setelah semua 27 kelompok, kembalikan true.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

Satu kali pemindaian dengan tabel seen untuk setiap baris, kolom, dan kotak

Intuisi

Kunjungi setiap sel sekali dan ajukan ketiga pertanyaan sekaligus. Gunakan tiga tabel berukuran 9 × 9 untuk menyimpan penanda: seenRow[r][d] menyatakan bahwa digit d+1 sudah ada di baris r, sedangkan seenCol dan seenBox bekerja dengan cara yang sama.

Sel (r, c) termasuk dalam kotak (r / 3) * 3 + c / 3. Bagian pertama menentukan pita yang terdiri dari tiga kotak, sedangkan c / 3 menentukan kotak di dalam pita tersebut. Sel (4, 7) berada di kotak 1 * 3 + 2 = 5, yaitu kotak tengah-kanan.

Penanda yang sudah terpasang berarti digit tersebut berulang dalam kelompok itu. Setiap sel dibaca sekali dan tabel menyimpan 243 penanda: waktu dan memori tetap dalam kasus ini, O(n²) pada papan berukuran n × n.

Algoritma

Buat seenRow, seenCol, dan seenBox, masing-masing berukuran 9 × 9 dan semuanya bernilai false.
Untuk setiap sel yang terisi (r, c), tetapkan d sebagai digitnya dikurangi 1 dan b = (r / 3) * 3 + c / 3.
Jika seenRow[r][d], seenCol[c][d], atau seenBox[b][d] disetel, kembalikan false; jika tidak, setel ketiganya.
Setelah sel terakhir, kembalikan true.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Jebakan dan kasus tepi

Menghitung kotak dengan r / 3 + c / 3. Hasilnya hanya 0 sampai 4, jadi (0, 3) dan (3, 0) memiliki angka yang sama meskipun kotaknya berbeda, dan dua angka 7 di sana dilaporkan sebagai pengulangan.
Membagi dengan / dalam JavaScript, Python 3, atau Lua, yang menghasilkan 1.33 untuk 4 / 3. Bulatkan ke bawah.
Menganggap . sebagai nilai. Papan kosong, dengan sembilan titik di setiap baris, valid.
Mencoba menyelesaikan teka-teki. Baris 0 yang berisi 12345678. dengan angka 9 di bawahnya pada kolom 8 tidak mungkin diselesaikan, tetapi tidak ada angka yang berulang: true.
Melewatkan kotak-kotaknya. Kisi penuh dengan setiap baris bergeser satu tempat ke kiri dari baris di atasnya tidak memiliki pengulangan dalam baris atau kolom, sementara setiap kotak berisi angka yang berulang.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Valid Sudoku?

Papan selalu memiliki 81 sel, jadi kedua pendekatan berjalan dalam waktu O(1) dan menggunakan memori O(1). Untuk Sudoku n × n umum, pemeriksaan satu kali membaca setiap sel dari n² sel sekali dan menyimpan 3n² penanda: waktu dan memori O(n²).

Apakah papan Sudoku yang valid harus bisa diselesaikan?

Tidak. Valid di sini hanya berarti tidak ada digit yang berulang dalam satu baris, satu kolom, atau satu kotak 3 × 3 di antara sel yang terisi. Papan bisa lolos pemeriksaan itu dan tetap tidak memiliki solusi. Menentukan apakah papan dapat diselesaikan memerlukan pencarian seperti backtracking, yang merupakan masalah berbeda.

Apakah Valid Sudoku bisa diselesaikan dengan bit mask?

Ya. Beri setiap baris, kolom, dan kotak satu bilangan bulat, dengan bit d berarti digit d+1 sudah ditemukan. Untuk sel yang terisi, jika 1 << d menghasilkan nilai AND yang bukan nol dengan salah satu dari ketiga mask-nya, berarti digit tersebut berulang; jika tidak, lakukan OR ke ketiganya. Ini menggunakan 27 bilangan bulat, bukan 243 flag.

def isValidSudoku(board):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Output yang diharapkan

true