BacktrackingLanjutFase E–FE1E5

Sudoku Backtracking

Algoritma ini menyelesaikan Sudoku dengan mengisi sel kosong satu per satu menggunakan backtracking. Untuk tiap sel, ia mencoba angka kandidat yang valid (tidak melanggar aturan baris, kolom, dan kotak), lalu lanjut ke sel berikutnya; bila buntu, angka dihapus dan dicoba nilai lain. Visualisasi menampilkan penempatan valid dan proses menghapus angka saat backtrack hingga seluruh grid terisi benar.

Contoh kasus

Mesin penyelesai teka-teki Sudoku otomatis pada aplikasi ponsel yang memvalidasi dan mengisi papan pengguna.

Silabus

Sudoku Backtracking mengisi sel kosong satu per satu dengan angka valid, dan menghapusnya untuk mencoba nilai lain saat menemui jalan buntu.

Tujuan Belajar

·Memahami aturan validitas angka pada baris, kolom, dan kotak
·Menjelaskan cara backtracking mundur saat tidak ada angka valid
·Menerapkan backtracking untuk menyelesaikan papan Sudoku

Cara Kerja

·Cari sel kosong pertama pada papan
·Coba isi dengan angka kandidat yang tidak melanggar aturan
·Bila valid, lanjut mengisi sel kosong berikutnya secara rekursif
·Bila buntu (tak ada angka valid), hapus angka dan coba nilai lain
·Ulangi maju-mundur sampai seluruh grid terisi dengan benar

Prasyarat

·Backtracking
·Grid 2D

Contoh Nyata

·Fitur auto-solve pada aplikasi Sudoku di ponsel
·Memvalidasi dan mengisi papan Sudoku buatan pengguna
·Generator teka-teki yang memastikan puzzle punya solusi

Kompleksitas Eksponensial pada kasus terburuk, dipangkas oleh aturan validitas