Zeven miljoen uur rekenen aan de sudoku

Gary McGuire en zijn collega's aan de School of Mathematics van de Universiteit van Dublin hebben aangetoond dat een 9 x 9 sudoku pas een unieke oplossing kan hebben als er vooraf minimaal 17 cijfers zijn gegeven. Een sudoku waarvan 16 cijfers bekend zijn kan meer dan één oplossing hebben.

McGuire wilde de vraag beantwoorden welk aantal cijfers minimaal nodig is om een unieke sudoku te verkrijgen. Er werd verwacht dat het om minimaal 17 cijfers zou gaan, maar het bewijs daarvoor ontbreekt. Ook McGuire heeft dat bewijs niet geleverd, maar is gewoon gaan uitproberen. Hij bedacht een aantal rekenmethoden om het rekenwerk binnen de perken te houden, maar had desalniettemin 7 miljoen processoruren nodig op een groot aantal hex-core processoren in Dublin. Het rekenen duurde bijna een jaar en was voltooid in december 2011. Er werd daarbij geen 16-cijfer sudoku gevonden die slechts één oplossing heeft.

 

Download hier het verslag van McGuire's onderzoek (pdf, 40 pagina's)

En voor wie wil narekenen: hier de broncode van controleprogramma

Lees ook het artikel ‘Vergeet de sudoku met maar 16 cijfers' in de Volkskrant