Sudoku dengan Constraint Propagation
Constraint propagation adalah teknik penyelesaian masalah batasan (CSP) yang mempersempit kandidat nilai tiap sel dengan menghapus digit yang bertentangan dengan sel tetangga (baris, kolom, dan kotak). Ketika sebuah sel hanya menyisakan satu kandidat, nilai tersebut dikunci, yang kemudian memicu eliminasi berikutnya. Visualisasi menampilkan grid Sudoku dengan konflik yang ditandai dan sel yang terkunci hingga papan terselesaikan.
Mesin penyelesai teka-teki Sudoku atau penjadwalan otomatis yang harus memenuhi banyak batasan sekaligus.
Constraint Propagation menyelesaikan Sudoku dengan mempersempit kandidat tiap sel, dan ketika hanya tersisa satu kandidat nilainya dikunci.
- ·Memahami arti kandidat nilai dan batasan (constraint) tiap sel
- ·Menjelaskan efek berantai saat satu sel terkunci
- ·Menerapkan propagasi batasan untuk mempersempit ruang jawaban
- ·Tiap sel kosong punya daftar kandidat angka yang mungkin
- ·Hapus kandidat yang bentrok dengan angka di baris, kolom, dan kotak
- ·Bila sebuah sel hanya menyisakan satu kandidat, kunci nilainya
- ·Penguncian itu memicu eliminasi kandidat pada sel tetangga
- ·Ulangi sampai papan terselesaikan atau tak ada lagi yang bisa dipersempit
- ·Grid 2D
- ·Logika himpunan
- ·Mesin penyelesai Sudoku otomatis di aplikasi ponsel
- ·Penjadwalan otomatis yang harus memenuhi banyak batasan sekaligus
- ·Menyusun jadwal piket kelas agar tak ada bentrok
Kompleksitas Cepat untuk kasus mudah; sulit bisa perlu backtracking tambahan