Labb L2: Korsord

I den här uppgiften ska du konstruera ett Prolog-program som konstruerar ett enkelt korsord givet en lista med ord. Korsordet har en mycket enkel struktur:

D	I	T	C	H
O		U		O
D	I	T	O	R
G		O		E
E	A	R	L	Y

Laborationen ska ge dig övning i Prologprogrammering och låta dig använda ''generate-and-test'' som lösningsmetod.

Hjälpmedel

Du har två ordlistor att arbeta med.

• /info/progp10/prolog/litenordlista.pl. Använd denna för testning. Listan har 16 ord.
• /info/progp10/prolog/storordlista.pl. Denna lista har 2737 ord, så använd inte den förrän du vet att ditt program fungerar.

Om du använder AFS utanför Nada så använder du prefixet "/afs/nada.kth.se/" för sökvägarna ovan. Eller klickar på länkarna...

Uppgifter

1. Skriv ett predikat solve_crossword/2 som tar som indata en lista med strängar (dvs listor av ASCII-koder) om fem tecken och unifierar passande ord med en struktur som representar ett korsord. Du ska använda generera-och-testa för denna uppgift.
2. Skriv predikatet write_crossword/1 som skriver ut korsordet på ett snyggt sätt. Tips: Använd predikatet format/2. Exempel:
   | ?- X="KTH", format(X, []).
   KTH
   X = [75,84,72] ?
   
   Även predikatet nl kan vara bra att ha. Vad gör det?

   Så här ska din session kunna se ut:

   | ?- words(X), solve_crossword(X, C), write_crossword(C).
   DITCH
   O U O
   DITTO
   G O E
   EARLY
   
   C = [[68,73,84,67,72],[79,32,85,32,79],...
   X = [[68,73,83,84,82],[68,73,84,67,72],...
   

   Tips

   • Det duger inte att permutera listan av ord tills att en lösning hittas! Det ska gå att lösa detta problem i rimlig tid.
   • Hur ska du representera ett korsord? Det kan vara lämpligt att ha parametrar för de enskilda bokstäverna i korsordet.
   • Listan som binds till X tar lätt över skärmen, så det kan vara bra att kapsla in det ovanstående till ett predikatet crossword(C) som bara ger dig korsordet och "döljer" den långa ordlistan.

3. Bokstavsvikter

   Vikterna är tagna från Scrabble.

   Vikt	Bokstäver
   1	E, A, I, O, N, R, T, L, S, U
   2	D, G
   3	B, C, M, P
   4	F, H, V, W, Y
   5	K
   8	J, X
   9	Q, Z

   Skriv ett predikat word_weight/2 som räknar ut vikten på ett ord genom summera de ingående bokstävernas vikt. Bokstavsvikten tas från tabellen här intill.

   Ditt predikat behöver bara arbeta med versaler.

   Vid redovisning ska du kunna visa upp denna interaktion:

   | ?- word_weight("LASSE", W).
   
   W = 5 ? ;
   
   no
   | ?- word_weight("KTH", W).
   
   W = 10 ? ;
   
   no
   

4. Skriv predikatet require_min_weight(+Words,+Weight,-FewerWords) som unifierar FewerWords med en lista som innehåller de ord från Words vars vikt är minst Weight.

   Av effektivitetsskäl ska du använda snitt på väl valt ställe: när det är avgjort att ett ord har tillräcklig vikt ska koden inte undersöka alternativet att inte ta med ordet.

   | ?- Words=["LASSE", "KTH", "LTH"], require_min_weight(Words,10, Ut).
   
   Ut = [[75,84,72]]
   Words = [[76,65,83,83,69],[75,84,72],[76,84,72]]
   
   yes
   

5. Skriv predikatet better_crossword/2 som tar en minimivikt Wsom första parameter och returnerar ett korsord i den andra parametern som bara använder ord med vikt W eller bättre.

   Vid redovisning: Vilken är den högsta vikten som ger dig ett korsord?