gioco della domenica: Flood Fill

Conoscete il teorema dei quattro colori? Afferma che una mappa può sempre essere colorata usando quattro soli colori distinti, senza che due regioni dello stesso colore abbiano un tratto di confine in comune (un punto è permesso). Il teorema è stato enunciato nella seconda metà del secolo XIX, ma si dovette aspettare il 1977 per averne una dimostrazione… che richiede una quantità assurda di conti al computer.
Nel caso di Flood Fill non vi si chiede di dimostrare il teorema, ma semplicemente di colorare alcune mappe usando il minor numero di colori possibile. Purtroppo, anche se vengono assegnate delle stelle se si risparmiano colori, non ho visto da nessuna parte un modo per contare le stelle vinte e/o sapere se si poteva fare di meglio. Ad ogni buon conto, buona colorazione!
P.S.: il sito apre una finestra su http://www.paradoxide.com/ – ho dato un’occhiata al sorgente e mi pare setti solo Google Analytics, ma i paranoici potrebbero bloccare il sito e/o evitare di giocare.
(via Passion for Puzzles)

Ultimo aggiornamento: 2009-11-08 07:00

11 pensieri su “gioco della domenica: Flood Fill

  1. maxxfi

    Non so se c’e’ materia per scriverci un post di divulgazione matematica, ma mi piacerebbe leggere cosa ne pensi delle dimostrazioni di teoremi che usano ‘brute force’ al calcolatore, e del perche’ sono appunto accettate come dimostrazioni.

  2. Alex

    Per sapere se nu determinato livello e’ stato risolto col numero minimo di colori possibile basta selezionere “levels”.

  3. Barbara

    @maxxfi: le dimostrazioni al calcolatore sono come le altre: solo che invece di caso 1, caso 2, e caso 3, arrivano fino al caso 1500, e allora si preferisce far fare l’analisi caso-per-caso a un calcolatore.
    In altre parole: si dimostra che se tutte le carte nella lista delle 1500 (il numero è naturalmente tirato a caso) sono colorabili con quattro colori, allora tutte le carte sono colorabili con quattro colori; la verifica dei 1500 casi particolari viene poi svolta al calcolatore.
    I miei figli hanno passato un’ora a litigare davanti al computer per questo gioco, e posso scrivere questi commenti solo perché li ho spediti a fare i compiti con la forza.

  4. delio

    maxxfi, mettiamola così: per quanto ne so nessuno ha mai controllato effettivamente che i conti fatti al computer siano corretti. epperò due gruppi indipendenti di ricerca hanno prodotto due dimostrazioni (entrambe al computer) nel corso degli ultimi 30 anni, e in entrambi i casi il codice del computer era open-source, quindi chiunque è libero di trovare un errore (e infatti degli errorini sono stati trovati e corretti).
    la questione filosofica probabilmente si può riassumere nella domanda: da quando in qua in una dimostrazione matematica l’onere della prova spetta all’accusa (il lettore/referee) e non alla difesa (l’autore)? è un po’ perverso che solo perché la mia prova dura 5 stramiliardi di pagine nessuno mi possa dir niente.
    (è anche vero che parecchie dimostrazioni “manuali” sono ugualmente incomprensibili (perché troppo lunghe e complesse) per una tipica mente umana: l’esempio classico è il teorema di classificazione dei gruppi finiti, ma anche il teorema dei minori di robertson-seymour non scherza:
    http://en.wikipedia.org/wiki/Classification_of_finite_simple_groups
    http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem
    una riflessione un po’ provocatoria ma interessante su questi temi la puoi trovare in un libro di e.b. davies:
    http://books.google.de/books?id=mpwtwZ9pJg8C&dq=science+through+the+looking+glass+davies&source=gbs_navlinks_s)

  5. .mau.

    @maxxfi, @delio: alla fine ho scritto un pipponcino al riguardo, ma uscirà mercoledì perché sono pigro :-)

  6. maxxfi

    Ecco, infatti e’ la questione filosofica che mi lascia un po’ perplesso.
    Vabbe’ mi metto pigramente ad aspettare la pubblicazione del mercoledi’ :-)

  7. Barbara

    Niente come un paio di decenni di ricerca in matematica per far passare ogni interesse per la filosofia soggiacente. IMHO, ovviamente.

  8. .mau.

    @barbara: non avendo mai fatto ricerca in matematica, io posso permettermi questi lussi :-)

  9. delio

    barbara, un po’ hai ragione, ma la questione è molto terra terra: quando fai un corso di teoria dei grafi, lo chiami “teorema dei quattro colori” o “congettura dei quattro colori”? io opto per la prima, ma una scelta va fatta.

I commenti sono chiusi.