Sto facendo ricerche sui quadrati, e ho pensato di usare risolutori di problemi di soddisfazione dei vincoli per dimostrare o confutare alcune congetture. Come semplice esempio di problema, considera il seguente compito:
Draw two green squares and two red squares, such that:
- All squares of the same color are interior-disjoint;
- All squares of different colors are interior-intersecting.
Per risolvere questo problema, ho scritto il seguente script nella lingua Minion . Per abbreviare il programma, ho utilizzato macro in stile C:
MINION 3
**VARIABLES**
// There are 2 red squares and 2 green squares.
// for every square, x and y are the south-west corner, and s is the side-length:
DISCRETE xred[2] {1..100}
DISCRETE yred[2] {1..100}
DISCRETE sred[2] {1..100}
DISCRETE xgrn[2] {1..100}
DISCRETE ygrn[2] {1..100}
DISCRETE sgrn[2] {1..100}
**CONSTRAINTS**
// The following macros handle intersection relations between squares.
// Let a and b be names of squares.
// intersect(a,b) defines constraints meaning "rectangle a intersects rectangle b".
// disjoint(a,b) defines constraints meaning "rectangle a does not intersect rectangle b".
// a and b interior-intersect, if ALL the following equalities hold:
// a.x + a.s > b.x
// b.x + b.s > a.x
// a.y + a.s > b.y
// b.y + b.s > a.y
#define intersect(a,b) \
watched-and({\
sumgeq([x##a,s##a,-1], x##b), \
sumgeq([x##b,s##b,-1], x##a), \
sumgeq([y##a,s##a,-1], y##b), \
sumgeq([y##b,s##b,-1], y##a)})
// a and b are interior-disjoint if they do not interior-intersect.
// We need a special macro for this because Minion does not support negation of constraints.
#define disjoint(a,b) \
watched-or({\
sumleq([x##a,s##a], x##b), \
sumleq([x##b,s##b], x##a), \
sumleq([y##a,s##a], y##b), \
sumleq([y##b,s##b], y##a)\
})
// Squares of the same color must be disjoint:
disjoint(red[0],red[1])
disjoint(grn[0],grn[1])
// Squares of the different colors must intersect:
intersect(red[0],grn[0])
intersect(red[0],grn[1])
intersect(red[1],grn[0])
intersect(red[1],grn[1])
**EOF**
Ho eseguito il risolutore utilizzando il seguente comando shell:
cpp myfile > myfile.tmp
minion myfile.tmp
Minion ha restituito il seguente risultato
Sol: 1 1
Sol: 1 4
Sol: 3 3
Sol: 1 3
Sol: 3 1
Sol: 2 4
leggi:
- red # 0 inizia a (1,1) con il lato 3;
- il rosso # 1 inizia a (1,4) con il lato 3;
- grn # 0 inizia da (1,3) con il lato 2;
- grn # 1 inizia a (3,1) con il lato 4;
Ecco come appare sull'aereo:
Ineffetti,iquadratidellostessocoloresonointerni-disgiuntimentreiquadratidicoloridiversisiintersecano!
(Naturalmentecisonomoltealtresoluzioni:Minionrestituiscelaprimasoluzionechetrova,cheèOKperlemieesigenze).
Oralemiedomandesono:
- Perprimacosa,utilizzolostrumentogiustoperl'attività?C'èunmodoperfareciòchehoappenafattosenzalanecessitàdidefinireesplicitamentecosasignifica"intersecare"?
- In secondo luogo, utilizzo correttamente la lingua di Minion?