Implementation of Constraint Satisfaction Problem Approach for Solving the Zebra Puzzle with Prolog

Tri Bagus Kurniawan; Muhammad Risqi Nuryana; Resi Sujiwo Bijokangko

doi:10.32493/epic.v8i2.58721

Authors

Tri Bagus Kurniawan Universitas Mercu Buana
Muhammad Risqi Nuryana Universitas Katolik Indonesia Atma Jaya https://orcid.org/0009-0000-8676-5925
Resi Sujiwo Bijokangko Universitas Mercu Buana https://orcid.org/0009-0001-0383-1868

DOI:

https://doi.org/10.32493/epic.v8i2.58721

Keywords:

Constain Satifiscation Problem, Zebra Puzzle, Prolog, Knowledge Representation

Abstract

Constraint Satisfaction Problem (CSP) Is a fundamental concept in artificial intelligence used to solve combinatorial problems by satisfying a set of constraints. The Zebra Puzzle is a classical example that involves assigning attributes such as nationality, house color, pet, drink, and candy to five houses based on logical clues. This study aims to implement CSP techniques using the Prolog programming language to solve the Zebra Puzzle. The methodology includes classifying all relevant attributes, encoding constraints into Prolog predicates, and applying helper functions to represent adjacency and ordering relationships. The puzzle is modeled as a list of structured facts, and Prolog’s inference engine is used to derive consistent solutions. The program successfully assigns all attributes to the correct house positions. For example, the Englishman lives in the red house, the Spaniard owns the dog, and the Ukrainian drinks tea. The Norwegian lives in the first house and drinks water, while the Japanese owns the zebra. These results confirm the effectiveness of Prolog in solving structured logic puzzles using CSP. The study concludes that logic programming is a reliable tool for modeling and solving constraint-based problems. This implies broader applicability of CSP in intelligent systems.

References

Berman, S., McKeown, K., & Ray, B. (2024). Solving Zebra Puzzles Using Constraint-Guided Multi-Agent Systems (arXiv:2407.03956). arXiv. https://doi.org/10.48550/arXiv.2407.03956

Buscaroli, R., Chesani, F., Giuliani, G., Loreti, D., & Mello, P. (2023). A Prolog application for reasoning on maths puzzles with diagrams. Journal of Experimental & Theoretical Artificial Intelligence, 35(7), 1079–1099. https://doi.org/10.1080/0952813X.2022.2062456

Grohe, M., Guruswami, V., & Zivny, S. (2018). The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231) [Application/pdf]. 18 pages. https://doi.org/10.4230/DAGREP.8.6.1

Jamine, D. M. (2024). LOGIC PUZZLES: UPAYA MENINGKATKAN COMPUTATIONAL THINKING SISWA SMK MENGGUNAKAN MODEL PUZZLE-BASED LEARNING PADA MATERI ALGORITMA.

Jendreiko, C. (2024). Generative Logic: Teaching Prolog as Generative AI in Art and Design.

Körner, P., Leuschel, M., Barbosa, J., Costa, V. S., Dahl, V., Hermenegildo, M. V., Morales, J. F., Wielemaker, J., Diaz, D., Abreu, S., & Ciatto, G. (2022). Fifty Years of Prolog and Beyond. Theory and Practice of Logic Programming, 22(6), 776–858. https://doi.org/10.1017/S1471068422000102

Krokhin, A., & Opršal, J. (2022). An invitation to the promise constraint satisfaction problem. ACM SIGLOG News, 9(3), 30–59. https://doi.org/10.1145/3559736.3559740

Schrijvers, T., Berg, B. van den, & Riguzzi, F. (2023). Automatic Differentiation in Prolog (arXiv:2305.07878). arXiv. https://doi.org/10.48550/arXiv.2305.07878

Shah, K., Dikkala, N., Wang, X., & Panigrahy, R. (n.d.). Causal language modeling can elicit search and reasoning capabilities on logic puzzles.

Siti Masrichah. (2023). Ancaman Dan Peluang Artificial Intelligence (AI). Khatulistiwa: Jurnal Pendidikan dan Sosial Humaniora, 3(3), 83–101. https://doi.org/10.55606/khatulistiwa.v3i3.1860

SWISH -- prolog_tutorials.swinb. (n.d.). Retrieved November 18, 2025, from https://swish.swi-prolog.org/example/prolog_tutorials.swinb

Szomiu, R., & Groza, A. (2021). A Puzzle-Based Dataset for Natural Language Inference (arXiv:2112.05742). arXiv. https://doi.org/10.48550/arXiv.2112.05742

Thompson, S., Candon, K., & Vázquez, M. (2025). The Social Context of Human–Robot Interactions. Annual Review of Control, Robotics, and Autonomous Systems. https://doi.org/10.1146/annurev-control-030623-015506

White, C., Dooley, S., Roberts, M., Pal, A., Feuer, B., Jain, S., Shwartz-Ziv, R., Jain, N., Saifullah, K., Naidu, S., Hegde, C., LeCun, Y., Goldstein, T., Neiswanger, W., Goldblum, M., & Ai, A. (2024). LiveBench: A Challenging, Contamination-Free LLM Benchmark.

Wielemaker, J., Beek, W., Hildebrand, M., & van Ossenbruggen, J. (2021). ClioPatria: A SWI-Prolog Infrastructure for the Semantic Web.

Wielemaker, J., Lager, T., & Riguzzi, F. (2015). SWISH: SWI-Prolog for Sharing (arXiv:1511.00915). arXiv. https://doi.org/10.48550/arXiv.1511.00915

Wielemaker, J., Riguzzi, F., Kowalski, B., Lager, T., Sadri, F., & Calejo, M. (2020). Using SWISH to realise interactive web based tutorials for logic based languages. https://doi.org/10.1017/S1471068418000522

Yang, X., Chen, B., & Tam, Y.-C. (2024). Arithmetic Reasoning with LLM: Prolog Generation & Permutation (arXiv:2405.17893). arXiv. https://doi.org/10.48550/arXiv.2405.17893

ZebraPuzzles.com: New Zebra Puzzles Every Day. (n.d.). Retrieved November 12, 2025, from https://www.zebrapuzzles.com/

Zombori, Z., Urban, J., & Brown, C. E. (2020). Prolog Technology Reinforcement Learning Prover: (System Description). In N. Peltier & V. Sofronie-Stokkermans (Eds.), Automated Reasoning (Vol. 12167, pp. 489–507). Springer International Publishing. https://doi.org/10.1007/978-3-030-51054-1_33