620 - IL PUZZLE DA UN MILIONE DI DOLLARI

Sembra impossibile ma…

Se risolvi un problema di scacchi creato più di 150 anni fa ti porti a casa un milione di dollari. E’ il premio messo in palio dall’università scozzese di St Andrews per chi troverà la soluzione in chiave informatica del “Puzzle della regina”. La notizia della sfida è stata data dal Journal of Artificial Intelligence Research.

Il puzzle, ideato nel 1848 da Max Bezzel, nella sua versione base richiede di sistemare sulla scacchiera otto regine, una in ogni riga, in modo che non ci siano due regine nella stessa colonna, né nella stessa diagonale, quindi che nessuna regina sia in grado di attaccare l’altra. In questi termini, fu risolto già nel 1850 da Franz Nauck, e negli anni sono state trovate ben 92 soluzioni (72 delle quali dal famoso matematico Carl Friedrich Gauss).

Le cose si complicano quando si estende il problema a scacchiere con un maggior numero di caselle, e con analogo numero di regine. E non solo per il cervello umano. I più avanzati programmi informatici infatti non vanno oltre le scacchiere da mille caselle con mille regine. Oltre, non c’è computer in grado di gestire l’enorme numero di opzioni. O meglio, ai più complessi servirebbero migliaia di anni per elaborare i dati.

“Un programma che risolvesse velocemente questo puzzle – dice Ian Gent, professore informatico a St Andrews – sarebbe la soluzione per molti problemi del quotidiano, dai più banali come l’elaborazione del più grande gruppo di amici Facebook che non si conoscono tra loro, ai più importanti come la cifratura dei codici per mantenere al sicuro le nostre transazioni online».

Il puzzle delle regine è uno dei sette Millennium Prize Problem, i problemi più difficili che la matematica non ha ancora risolto. Che ora sono 6, perché di uno è già stata trovata la soluzione. Difficile ma non impossibile dunque. Se vi viene qualche idea telefonate al professor Gent. Lui ha già pronto l’assegno.