BacktrackingLanjutFase E–FE1E5

SUDOKU BACKTRACK

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Backtracking
·Grid 2D

Real-World Uses

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

Complexity Eksponensial pada kasus terburuk, dipangkas oleh aturan validitas