An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9X9 grid of squares with the numbers 1–9 according to certain rules.
Gary McGuire of University College Dublin shows in a proof posted online on 1 January1 that the minimum number of clues — or starting digits — needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given.
“The approach is reasonable and it’s plausible. I’d say the attitude is one of cautious optimism,” says Jason Rosenhouse, a mathematician at James Madison University in Harrisonburg, Virginia, and the co-author of a newly released book on the maths of Sudoku.
Having spent two years testing the algorithm, McGuire and his team used about 700 million CPU hours at the Irish Centre for High-End Computing in Dublin, searching through possible grids with the hitting-set algorithm. “The only realistic way to do it was the brute force approach,” says Gordon Royle, a mathematician at the University of Western Australian in Perth who had been working on the problem of counting 17 clue puzzles using different algorithms.
La discussion est tres drole et merite d’etre ecoutee meme si elle est longue et que vous n’apprendrai probablement pas grand chose de scientifique. La partie sur le film Titanic est un classique instantane 😉
Si comme moi vous avez eu des problemes dernierement avec kmix, cet article devrait vous interesser. Ca semble avoir regler les miens.
Regardless, I eventually figured a solution to the problem: Quit kmix. You may need to actually kill the program. Next move/delete/rename the folder ‘kmix’ in the folder ‘~/.kde/share/apps/. Restart kmix, and it will recreate a default ‘~/.kde/share/apps/kmix/’ folder with default settings.
“It’s absolutely astounding,” says Karl Battams of the Naval Research Lab in Washington DC. “I did not think the comet’s icy core was big enough to survive plunging through the several million degree solar corona for close to an hour, but Comet Lovejoy is still with us.”
Comet Lovejoy was discovered on Dec. 2, 2011, by amateur astronomer Terry Lovejoy of Australia. Researchers quickly realized that the new find was a member of the Kreutz family of sungrazing comets. Named after the German astronomer Heinrich Kreutz, who first studied them, Kreutz sungrazers are fragments of a single giant comet that broke apart back in the 12th century (probably the Great Comet of 1106). Kreutz sungrazers are typically small (~10 meters wide) and numerous. The Solar and Heliospheric Observatory sees one falling into the sun every few days.