Mathematician claims breakthrough in Sudoku puzzle

nature.com: Via: Mathematician claims breakthrough in Sudoku puzzle. Puzzles must have at least 17 clues to have a valid solution.

slashdot.org: Lower Limit Found For Sudoku Puzzle Clues

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.

Papier en format PDF

The seesaw magic book: the computational power of DNA molecules

Via: Cosmic Variance: DNA Takes Square Roots

Caltech researchers Lulu Qian and Erik Winfree have managed to coax 130 strands of DNA into performing what is unquestionably a calculation: taking the square root of a number. (Ars Technica post; Science paper behind paywall; open-access background paper.) Not a big number: we’re talking about four-digit binary numbers, so 15 at the biggest. And not very efficiently: with prodding, the calculation took eight hours. Moore’s Law isn’t really in danger here.

On est pas les seuls jambons

informationweek.com: Social Security Data Center Approaching Collapse

Via: slashdot.org: Social Security Information Systems Near Collapse

J’aurais pu ecrire qu’on etait aussi jambon que les autres, mais il me semble que notre perception est qu’au Quebec et/ou Canada, les couts de developpements informatiques sont astronomiques, pour ne pas dire ridicules/insenses/criminels/demoralisants/etc.

Mais on peut se consoler en regardant ailleurs, a defaut de se prendre en main et de regler les problemes! Bonne nouvelle, non? 😉

One of the biggest problems is the agency’s transition to a new data center, according to the report. The IG has characterized the replacement of the SSA’s National Computer Center (NCC) — built in 1979 — as the SSA’s “primary IT investment” in the next few years.

The agency has received more than $500 million so far to replace the outdated center, which is now so severely strained by an expanded workload over its time of operation that it may not be able to function by 2012, according to the report.

Mais bon, avec notre registre des armes a feu de 2G$, et le fait qu’on est 10 fois moins, ils ont encore des croutes a manger ces americains pour nous battre!

P.S. Mon estimation est que mon ordi a la maison pourrait gerer le registre des armes a feu sans probleme, mais aller dire ca aux compagnies qui ont empoche les 2G$….

Two-Dimensional Pathology: Befunge

scienceblogs.com: Two-Dimensional Pathology: Befunge

In Befunge, there’s a read-head that moves over the program. Each step, it executes the instruction under the head. But instead of just moving left or right, it can move left, right, up, or down. “>” is an instruction that tells the head to start moving to the right; “<" tells the head to start moving left; "^" means start moving up, and "v" means to start moving down. So, for example: >v
^<

Is a program that runs an infinite loop: the head will just cycle over those four characters. An even more interesting infinite loop (taken from the befunge documentation) is:

C’est rien, compare a l’autre exemple de code que vous retrouverai sur le site via le lien plus haut. Outch! :-)