# Αρχές Γλωσσών Προγραμματισμού (εργαστήριο 8)

### 13/5/2021 & 20/5/2021

:::danger
Η συγκεκριμένη σελίδα μπορεί να χρησιμοποιηθεί για ερωτήσεις στην ώρα του μαθήματος.
:::

## Περιεχόμενο μαθήματος

Δηλωτικός προγραμματισμός - Κλήση επιλυτών για επίλυση "δύσκολων" προβλημάτων.

* [SWI-Prolog CLPFD](https://www.swi-prolog.org/man/clpfd.html)
* [ORTools by Google](https://developers.google.com/optimization)

## Πρόγραμμα μαθήματος

| Ώρα | Θέμα |
| --- | ---- |
|10:10-10:20| Η βιβλιοθήκη [CLPFD](https://www.swi-prolog.org/man/clpfd.html) της SWI-Prolog |
|10:20-10:30| Απλά παραδείγματα χρήσης της βιβλιοθήκης CLPFD |
|10:30-10:40| [Άσκηση 1](#Άσκηση-1) Χρωματισμός χάρτη με τη βιβλιοθήκη CLPFD της SWI-Prolog |
|10:40-11:00| Επίλυση προβλημάτων κατασκευάζοντας μοντέλα και καλώντας επιλυτές μέσω του λογισμικού OR-Tools |
|11:00-11:10| Διάλειμμα |
|10:10-11:20| Ο επιλυτής προγραμματισμού με περιορισμούς του OR-Tools |
|11:20-11:30| [Άσκηση 2](#Άσκηση-2) Επίλυση κρυπταριθμητικού παζλ με τον CP solver του OR-Tools |
|11:40-11:50| Σύντομη αναφορά στον επιλυτή CP-SAT |
|11:40-12:00| [Άσκηση 3](#Άσκηση-3) Επίλυση του προβλήματος των N-βασιλισσών με τον CP solver και με τον CP-SAT solver του OR-Tools|
|>12:00| [Άσκηση 4](#Άσκηση-4) Διαχωρισμός ειδών για μεταφορά |

### Άσκηση 1

**Χρωματισμός χάρτη με τη βιβλιοθήκη CLPFD της SWI-Prolog**

Δίνεται ένας χάρτης και ζητείται ο χρωματισμός του με 4 ή αν γίνεται με λιγότερα χρώματα υπό τον περιορισμό ότι περιοχές που συνορεύουν δεν πρέπει να χρωματίζονται το ίδιο χρώμα. Δείτε τον κώδικα που δίνεται για τον χρωματισμό της Αυστραλίας.

[colouring_australia.pl](https://github.com/chgogos/dituoi_agp/blob/main/pl/prolog/clpfd/colouring_australia.pl)

Τροποποιήστε τον κώδικα έτσι ώστε να επιτυγχάνει χρωματισμό του ακόλουθου χάρτη. Χρησιμοποιήστε τον κώδικα https://pastebin.com/37aCpZP9.

Πηγή: www.mathsisfun.com

Δείτε και το [The Power of Prolog: Map Coloring with Prolog](https://www.youtube.com/watch?v=6XD7vBbywMc)

### Άσκηση 2

**Επίλυση κρυπταριθμητικού παζλ με τον CP solver του OR-Tools**

Εγκαταστήστε το OR-Tools στην Python με την ακόλουθη εντολή.

$ pip install ortools

Δείτε τον ακόλουθο κώδικα για την επίλυση ενός κρυπταριθμητικού παζλ με τοn CP-Solver του OR-Tools.

[cryptarithmetic.ipynb](https://github.com/chgogos/dituoi_agp/blob/main/tools/ortools/cryptarithmetic.ipynb)

Τροποποιήστε τον κώδικα έτσι ώστε να επιλύει το ακόλουθο κρυπταριθμητικό παζλ.

   SEND
+  MORE
= MONEY

### Άσκηση 3

**Επίλυση του προβλήματος των N-βασιλισσών με τον CP solver και με τον CP-SAT solver του OR-Tools**

Δίνεται ο ακόλουθος κώδικας για την επίλυση του προβλήματος των N-βασιλισσών.

[nqueens.ipynb](https://github.com/chgogos/dituoi_agp/blob/main/tools/ortools/nqueens.ipynb)

Πόσο χρόνο απαιτεί στον υπολογιστή σας η εύρεση μιας λύσης για ένα ταμπλό μεγέθους 25Χ25 με τον CP επιλυτή και πόσο χρόνο με τον CP-SAT επιλυτή; Για ταμπλό ακόμα μεγαλύτερου μεγέθους;

### Άσκηση 4

**Διαχωρισμός ειδών**

Ένας ζωολογικός κήπος θέλει να μεταφέρει με τρία κλουβιά τα παρακάτω είδη ζώων. Πως θα χωριστούνε με την χρήση του OR-Tools χωρίς κάποιο είδος να κινδυνεύει από κάποιον θηρευτή του.

[foodweb.ipynb](https://github.com/chgogos/dituoi_agp/blob/main/tools/ortools/foodweb.ipynb)


Ποιό από τα προηγούμενα προβλήματα σας θυμίζει;

---

:::info
* Πάντα, κάνετε ερωτήσεις στο κάτω μέρος του εγγράφου, ακριβώς πάνω από εδώ
:::