ABSTRAKSI: Didalam dunia nyata banyak sekali persoalan yang bisa dimodelkan sebagai constraint satisfaction problem (CSP) seperti penjadwalan, penugasan dan sebagainya. Agar pencarian solusi lebih efisien maka perlunya suatu engine yang dapat menyelesaikan persoalan ini.
Tugas akhir ini menganalisis dan mengimplementasikan sebuah engine CSP dengan menggunakan algoritma depth-first search (DFS) with backtrack dan heuristic most contraining variable guna menigkatkan kinerja dari teknik pencarian backtracking. Engine yang dihasilkan hanya dapat variable bertipe string, domain bertipe string atau integer dan constraint berjenis unary dan Binary.
Heuristic Most Constraining Variable dalam membantu menigkatkan kinerja pencarian dengan teknik backtraking sangat baik diterapkan pada persoalan dimana semua variable memiliki domain yang sama dan didukung suatu constraint yang optimal sebagai fungsi pembatas.
Kata Kunci : constraint, constraint satisfaction problem, backtrack, most contraining variable.ABSTRACT: In the real world there are many problems can be modeling as constraint satisfaction problem (CSP) for example scheduling, tasking etc. to improve efficience for searching the solution then needed CSP’s engine to solve this problem.
This final task is analyzing and implementating an engine of CSPs by Using depth-first search (DFS) algorithm with backtrack and heuristic most contrining variable to acquire the best performance of backtracking searching technic. Engine that produced from this technic only use in string variable, string or integer domain and constraint with unary and binary type.
Heuristic most contrining variable in helping to increase searching performance with backtracking very well applied in problem where every variable have same domain and support with constraint that has optimal boundary function.Keyword: constraint, constraint satisfaction problem, backtrack, most contraining variable.