Implementation of Strategies for Solving Constraint Satisfaction Problems

Abstract

This thesis investigates the different strategies for solving constraint satisfaction problems. The basic properties of constraint satisfaction problems are discussed. The different types of constraints are given. The constraint graph and cryptarithmetic constraint satisfaction problems are discussed. Such search techniques as backtracking search, local search, and constraint propagation for solving constraint satisfaction problems are presented. The forward checking in constraint satisfaction problems is used. Some constraint satisfaction problems such as map-coloring problem, cryptarithmetic problem, n-queens problems and Sudoku problem are solved. Keywords: Constraint satisfaction problem, Constraint graph, Backtracking search, n-queens problem, Local search, Constraint propagation, Forward checking

ÖZ: Bu tez kısıtlama memnuniyeti sorunlarını çözmek için farklı stratejiler araştırıyor. Ayrıca, kısıtlama memnuniyeti problemlerinin temel özellikleri tartışılır. Bunun yanında, kısıtlamaların farklı türleri verilmiştir. Kısıtlama grafiği ve cryptarithmetic kısıtlama memnuniyeti sorunları tartışılır. Geriye arama, yerel arama ve kısıtlama memnuniyeti problemlerinin çözümü için kısıtlama yayılma gibi arama teknikleri sunulmuştur. Kısıtlama memnuniyeti problemlerinde ileri kontrol yöntemi kullanılır. Harita renklendirme problemi, cryptarithmetic problemi, n-vezir problemi gibi bazı kısıtlama memnuniyeti problemleri ve Sudoku problemi çözülür. Anahtar Kelimeler: Kısıtlama memnuniyeti sorunu, Kısıtlama grafiki, Geri İzleme arama, n-vezir problemi, Yerel arama, Kısıtlama yayılımı, İleri kontrol