Games: map colouringGiochi: colorazione di mappe

Up to four solvers colour the same map side by side, each lane replaying, event by event, the trace of a real run on a relief of the map whose regions rise and take their colour as the solver assigns them, while the pegs on a region are the colours still possible. The lanes are CaDiCaL of SMS++, whose search SMS++ follows through its external propagator, and the solvers of aima-python: CDCL and DPLL on the same CNF, backtracking search with the most constrained variable first and either forward checking or maintained arc consistency, and the local searches min-conflicts and WalkSAT, and, on the minimum sum colouring (colour j costs j), HiGHS of SMS++ with its bound and incumbent; the instance is the constraint satisfaction problem of aima-python (one variable per region, one constraint of difference per border), which its MapColoringSAT translates into the CNF that the page computes in Python (Pyodide) and shows below.

Fino a quattro solutori colorano la stessa mappa affiancati, ogni corsia che ripete, evento per evento, la traccia di un'esecuzione reale su un rilievo della mappa le cui regioni si alzano e prendono il loro colore man mano che il solutore le assegna, mentre i pioli su una regione sono i colori ancora possibili. Le corsie sono CaDiCaL di SMS++, la cui ricerca SMS++ segue attraverso il suo propagatore esterno, e i solutori di aima-python: CDCL e DPLL sulla stessa CNF, la ricerca con backtracking che sceglie per prima la variabile più vincolata con forward checking o con la consistenza d'arco mantenuta, e le ricerche locali min-conflicts e WalkSAT, e, sulla colorazione a somma minima (il colore j costa j), HiGHS di SMS++ con il suo bound e l'incumbente; l'istanza è il problema di soddisfacimento di vincoli di aima-python (una variabile per regione, un vincolo di diversità per confine), che il suo MapColoringSAT traduce nella CNF che la pagina calcola in Python (Pyodide) e mostra più in basso.

The model the solvers readIl modello che i solutori leggono

CSP

CNF (MapColoringSAT, aima-python)

MILP rows (SATBlock)Righe MILP (SATBlock)