Geekly articles weekly

Mencari si pembunuh di Prolog

Setiap hari Minggu di perusahaan kami sudah biasa mengatur kuis yang menyenangkan, ini salah satunya.

Teka-teki


Untuk menemukan pembunuh Tn. Boddy, Anda perlu mencari tahu di mana setiap orang berada dan senjata apa yang ada di ruangan itu. Petunjuk tersebar di seluruh kuis (Anda tidak dapat menjawab pertanyaan pertama sampai Anda membaca semuanya).

  • Pertama, bayangkan tersangka. Ada tiga pria (George, John, Robert) dan tiga wanita (Barbara, Christina, Yolanda). Setiap orang berada di ruang terpisah (kamar mandi, ruang makan, dapur, ruang tamu, dapur, kantor). Senjata mencurigakan ditemukan di setiap kamar (tas, senjata api, gas, pisau, racun, tali). Pertanyaan: siapa yang ditemukan di dapur?
  • Tip 1. Dengan seorang pria di dapur tidak ada tali, atau pisau, atau tas. Senjata itu bukan senjata api. Pertanyaan: Senjata apa yang ditemukan di dapur?

  • Petunjuk 2. Barbara berada di ruang belajar atau di kamar mandi, dan Yolanda berada di salah satu dari dua kamar yang disebutkan. Kamar apa yang ditemukan Barbara?
  • Tip 3. Pria dengan tas itu bukan Barbara atau George, dan dia tidak di kamar mandi atau di ruang makan. Siapa yang punya tas itu?
  • Tip 4. Seorang wanita dengan tali ditemukan di kantor. Siapa itu
  • Tip 5. Senjata di ruang tamu adalah milik John atau George. Senjata apa di ruang tamu?
  • Tip 6. Tidak ada pisau di ruang makan. Di mana pisau itu?
  • Petunjuk 7. Yolanda tidak di kantor atau di dapur dengan senjata yang sesuai untuk kamar-kamar ini. Senjata apa yang dimiliki Yolanda?
  • Tip 8. George menemukan senjata api. Kamar yang mana?
  • Ditemukan bahwa Tuan Boddy dibunuh dengan gas di pantry. Tersangka di ruangan itu adalah seorang pembunuh. Siapa ini?

Saya berangkat dengan teka-teki seperti itu (sebenarnya dari hampir semua teka-teki). Mereka bisa membutuhkan waktu berjam-jam refleksi, tetapi Prolog selalu datang untuk menyelamatkan! Mari kita lihat bagaimana ini membantu untuk menyelesaikan masalah seperti untuk alasan.

Prolog 101


Instal SWI-Prolog


~> swipl Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6) Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- write('Hello, World!'). Hello, World! true. ?- write('Hello,'), nl, write('world'). Hello, world true. ?- X is 3*4 + 2. X = 14.

  • swipl - Prolog interpreter
  • write disebut functor, dan representasi write/1 berarti bahwa dibutuhkan 1 argumen (konsep yang sama di Erlang dan Elixir untuk menambahkan jumlah argumen ke nama fungsi)
  • nl digunakan untuk mencetak baris baru
  • urutan perintah dipisahkan oleh koma, yang juga menggantikan operator DAN
  • operator penugasan diikuti oleh ekspresi matematika
  • variabel ditulis dalam huruf kapital X , bukan x

Basis pengetahuan


Inti dari Prolog adalah menyatakan fakta, menyusun fakta dan memintanya.

Membuat file hello.pl :

 friend(john, julia). friend(john, jack). friend(julia, sam). friend(julia, molly). loves(john, julia). loves(julia, sam). loves(sam, julia). male(brad). male(john). male(jim). male(alfred). female(marry). child(brad, alfred). child(john, jim). child(john, marry).

  • kami menggunakan [hello]. untuk memuat [hello]. : perhatikan titik di akhir
  • listing mencantumkan semua fakta di basis pengetahuan

 ?- [hello]. % hello compiled 0.00 sec, 3 clauses true. ?- listing(friend). friend(john, julia). friend(john, jack). friend(julia, sam). friend(julia, molly). true. ?- listing(loves). loves(john, julia). loves(julia, sam). loves(sam, julia). true.

Permintaan Fakta


Setelah menyatakan fakta di basis pengetahuan, kita bisa melangkah lebih jauh dan mengajukan pertanyaan tentang kebenaran fakta, serta kesimpulan apa yang bisa diambil darinya.

 ?- friend(john, julia). true . ?- friend(john, jack). true. ?- loves(john, julia). true. ?- loves(john, sam). false.

Kita bisa membuat pertanyaan yang lebih rumit. Misalnya, siapa yang berteman dengan John atau yang mencintai Julia.

 ?- friend(john, Who). Who = julia ; Who = jack. 

 ?- listing(child). child(brad, alfred). child(john, jim). child(john, mary). true. ?- child(john, X). X = jim ; X = mary.

Apakah John ada di zona persahabatan?


Kami telah menjalin persahabatan John dengan Julia ( friend(john, julia) ), tetapi untuk Prolog ini tidak berarti bahwa Julia berteman dengan John: Anda perlu menambahkan friend(julia, john) fakta lain friend(julia, john) . Kami juga telah mengindikasikan siapa yang memiliki anak dan jelas tidak ingin menggandakan kode, secara terpisah menunjukkan orang tua dari setiap anak. Kami tidak ingin menulis sesuatu seperti

 child(brad, alfred). child(john, jim). child(john, mary). parent(alfred, brad). parent(jim, john). parent(mary, john).

Prolog membantu menghindari duplikasi dengan aturan kesimpulan logis:

 rule :- stmt1, stmt2,...

Aturannya benar jika semua pernyataan internal benar (terdaftar dan secara logis dilipat dengan koma).

 friend(X, Y) :- friend(Y,X). parent(X, Y) :- child(Y,X). father(X, Y) :- child(Y,X), male(X). mother(X, Y) :- child(Y,X), female(X). friendzoned(X) :- loves(X, Y), \+ loves(Y,X).

  • friend(X,Y) berlaku untuk friend(Y,X )
  • parent(X,Y) benar ketika child(Y,X)
  • father(X,Y) benar dengan male(X) parent(X,Y) dan male(X) - male(X)
  • mother(X,Y) benar ketika parent(X,Y) dan female(X)
  • friendzoned(X) benar jika X mencintai SOMEONE Y dan Y tidak menyukai X (perhatikan variabel tersembunyi Y?)

 ?- friend(julia, john). true . ?- male(jim). true. ?- parent(jim,X). X = john. ?- father(jim, X). X = john. ?- mother(X, john). X = marry. ?- mother(marry,X). X = john. ?- mother(marry, john). true. ?- loves(julia, X). X = sam. ?- friendzoned(julia). false. ?- friendzoned(john). true.

Ok, sekarang kita memiliki semua pengetahuan yang diperlukan. Mari kita berlatih mewarnai peta.

Pewarnaan kartu


Mari kita mulai dengan masalah matematika yang terkenal. Diperlukan tidak ada area yang berdekatan memiliki warna yang sama.



Karena itu, alasannya harus seperti itu, kami punya tiga hal:

  1. Variabel adalah area yang ingin kita beri warna: A, B, C, D, E.
  2. Domain - rentang nilai yang dapat ditetapkan ke variabel: merah, biru, hijau.
  3. Batasannya adalah bahwa area yang berdekatan tidak boleh memiliki warna yang sama.

Domain


Tetapkan domain wilayah kami (merah, hijau, biru).

 color(red). color(green). color(blue).

Itu saja.

Kami meminta solusi


 colorify(A,B,C,D,E) :- color(A), color(B), color(C), color(D), color(E), \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.

Di sini kita mendefinisikan solusi sebagai aturan yang colorify dengan lima variabel A, B, C, D, E, dan di dalam aturan tersebut kita menetapkan warna domain (merah, biru, hijau) untuk variabel dan mengatur batasan bahwa A tidak sama dengan B, tidak sama dengan C ... dan dll.

\+ X=Y berarti X tidak sama dengan Y

Prolog akan terus menghasilkan nilai sampai menemukan opsi yang memenuhi aturan dengan pembatasan.

 ?- [mapcoloring] | . true. ?- colorify(A,B,C,D,E) | . A = red, B = D, D = green, C = E, E = blue ; A = red, B = D, D = blue, C = E, E = green ; A = green, B = D, D = red, C = E, E = blue ; A = green, B = D, D = blue, C = E, E = red ; A = blue, B = D, D = red, C = E, E = green ; A = blue, B = D, D = green, C = E, E = red 

 color(red). color(green). color(blue). colorify(A,B,C,D,E) :- color(A), color(B), color(C), color(D), color(E), \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.

... tapi kami tidak mewarnai gambar di sini, tetapi mencari pembunuhnya.

Pembunuhan itu


Pertama, bayangkan tersangka. Ada tiga pria (George, John, Robert) dan tiga wanita (Barbara, Christina, Yolanda). Setiap orang berada di ruang terpisah (kamar mandi, ruang makan, dapur, ruang tamu, dapur, kantor). Senjata mencurigakan ditemukan di setiap kamar (tas, senjata api, gas, pisau, racun, tali).

Siapa yang ditemukan di dapur?

Domain


Dari sini kita dapat menyimpulkan bahwa kita memiliki lima domain: man , woman , person atau tersangka, location dan weapons , dan variabel kita (A, B, C, D, E, F) harus mewakili baik orang, tempat, dan senjata dengan beberapa batasan yang akan diungkap di tips mendatang.

 man(george). man(john). man(robert). woman(barbara). woman(christine). woman(yolanda). person(X):- man(X). person(X):- woman(X). location(bathroom). location(dining). location(kitchen). location(livingroom). location(pantry). location(study). weapon(bag). weapon(firearm). weapon(gas). weapon(knife). weapon(poison). weapon(rope).

Aturan uniq_ppl menghasilkan nilai unik untuk variabel kami.

 uniq_ppl(A,B,C,D,E,F):- person(A), person(B), person(C), person(D), person(E), person(F), \+A=B, \+A=C, \+A=D, \+A=E, \+A=F, \+B=C, \+B=D, \+B=E, \+B=F, \+C=D, \+C=E, \+C=F, \+D=E, \+D=F, \+E=F.

Solusi


Kita mulai dengan mendefinisikan aturan seorang pembunuh dengan orang-orang unik di tempat-tempat dan orang-orang unik dengan senjata, dan sekarang akan menunjukkan hubungan antara orang-orang di tempat dengan mereka yang memiliki senjata

Harap dicatat bahwa kami masih memiliki enam tersangka.

Entri


 murderer(X) :- uniq_ppl(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study), uniq_ppl(Bag, Firearm, Gas, Knife, Poison, Rope),

Untuk dengan mudah berbicara tentang variabel, seperti kamar mandi, ruang makan, senjata api, gas, kami segera menentukan:

  • Kamar mandi - tersangka yang sama (pria atau wanita) di kamar mandi
  • Senjata api - tersangka yang sama (pria atau wanita) dengan senjata api
  • dan seterusnya ... Anda bisa membayangkannya sebagai kotak

Sekarang kami terus menambahkan batasan setelah koma terakhir dalam aturan murderer .

Kiat 1


Dengan seorang pria di dapur tidak ada tali, pisau atau tas. Senjata itu bukan senjata api. Senjata apa yang ditemukan di dapur?

 % 2. Clue 1: The man in the kitchen was not found with the rope, knife, or bag. % Which weapon, then, which was not the firearm, was found in the kitchen? man(Kitchen), \+Kitchen=Rope, \+Kitchen=Knife, \+Kitchen=Bag, \+Kitchen=Firearm,

Di sini kita mengatakan bahwa variabel Kitchen memenuhi fakta man (didefinisikan dalam domain kita), dan menyatakan bahwa tidak peduli siapa orangnya di dapur, dia tidak memiliki yang berikut: Rope , Knife , Bag , Firearm .

Petunjuk 2


Petunjuk 2. Barbara berada di ruang belajar atau di kamar mandi, dan Yolanda berada di salah satu dari dua kamar yang disebutkan. Kamar apa yang ditemukan Barbara?

Jadi, kita dapat mengatakan bahwa ada seorang woman di kantor dan di kamar mandi, Dan ini bukan Christina, dan kita juga mencoret opsi lain untuk Barbara dan Yolanda (dapur, ruang makan, ruang tamu, dapur).

 % % 3. Clue 2: Barbara was either in the study or the bathroom; Yolanda was in the other. % % Which room was Barbara found in? woman(Bathroom), woman(Study), \+christine=Bathroom, \+christine=Study, \+barbara=Dining, \+barbara=Kitchen, \+barbara=Livingroom, \+barbara=Pantry,

Kiat 3


Pria dengan tas itu bukan Barbara atau George, dan dia tidak di kamar mandi atau di ruang makan. Siapa yang punya tas itu?

 % % 4. Clue 3: The person with the bag, who was not Barbara nor George, was not in the bathroom nor the dining room. % % Who had the bag in the room with them? \+barbara=Bag, \+george=Bag, \+Bag=Bathroom, \+Bag=Dining,

Kiat 4


Seorang wanita dengan tali ditemukan di kantor. Siapa itu

 % % 5. Clue 4: The woman with the rope was found in the study. % % Who had the rope? woman(Rope), Rope=Study,

Kiat 5


Tip 5. Senjata di ruang tamu adalah milik John atau George. Senjata apa di ruang tamu?

 man in Livingroom Livingroom isn't robert % % 6. Clue 5: The weapon in the living room was found with either John or George. % % What weapon was in the living room? man(Livingroom), \+Livingroom=robert,

Kiat 6


Tidak ada pisau di ruang makan. Di mana pisau itu?

 % % 7. Clue 6: The knife was not in the dining room. % % So where was the knife? \+Knife=Dining,

Kiat 7


Petunjuk 7. Yolanda tidak ada di kantor atau di dapur. Senjata apa yang ada di kamar Yolanda?

 % % 8. Clue 7: Yolanda was not with the weapon found in the study nor the pantry. % % What weapon was found with Yolanda? \+yolanda=Pantry, \+yolanda=Study,

Tip 8


George menemukan senjata api.

 % % 9. Clue 8: The firearm was in the room with George. % % In which room was the firearm found? Firearm=george,

Kiat 9


Ditemukan bahwa Tuan Boddy dibunuh dengan gas di dapur. Tersangka di ruangan itu adalah seorang pembunuh. Siapa itu

 % % 10. It was discovered that Mr. Boddy was gassed in the pantry. The suspect found in that room was the murderer. % % Who, then, do you point the finger towards? Pantry=Gas, Pantry=X, write("KILLER IS :"), write(X), nl, writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope).

Cocokkan gas, dapur, dan pembunuh, kemudian gunakan write untuk write writeanswers .

 writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope):- write("Bathroom: "), write(Bathroom), nl, write("Dining: "), write(Dining), nl, write("Livingroom: "), write(Livingroom), nl, write("Pantry: "), write(Pantry), nl, write("Study: "), write(Study), nl, write("Kitchen: "), write(Kitchen), nl, write("Knife: "), write(Knife), nl, write("Gas: "), write(Gas), nl, write("Rope: "), write(Rope), nl, write("Bag: "), write(Bag), nl, write("Poison: "), write(Poison), nl, write("Firearm: "), write(Firearm), nl.

Siapa pembunuhnya?


  ?- [crime2]. true. ?- murderer(X). KILLER IS :christine Bathroom: yolanda Dining: george Livingroom: john Pantry: christine Study: barbara Kitchen: robert Knife: yolanda Gas: christine Rope: barbara Bag: john Poison: robert Firearm: george X = christine ;

Kode diterbitkan di sini . Mungkin bisa jauh lebih baik karena saya bukan ahli dalam Prolog :)

Source: https://habr.com/ru/post/id434172/

More articles:


All Articles