{"id":858,"date":"2012-01-08T16:22:02","date_gmt":"2012-01-08T21:22:02","guid":{"rendered":"http:\/\/blog.carlrobitaille.org\/?p=858"},"modified":"2012-01-08T16:25:03","modified_gmt":"2012-01-08T21:25:03","slug":"mathematician-claims-breakthrough-in-sudoku-puzzle","status":"publish","type":"post","link":"https:\/\/blog.carlrobitaille.org\/?p=858","title":{"rendered":"Mathematician claims breakthrough in Sudoku puzzle"},"content":{"rendered":"<p><a href=\"http:\/\/www.nature.com\/news\/mathematician-claims-breakthrough-in-sudoku-puzzle-1.9751\">nature.com: Via: Mathematician claims breakthrough in Sudoku puzzle. Puzzles must have at least 17 clues to have a valid solution.<\/a><\/p>\n<p><a href=\"http:\/\/idle.slashdot.org\/story\/12\/01\/08\/1845258\/lower-limit-found-for-sudoku-puzzle-clues\">slashdot.org: Lower Limit Found For Sudoku Puzzle Clues<\/a><\/p>\n<blockquote><p>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\u20139 according to certain rules.<\/p>\n<p>Gary McGuire of University College Dublin shows in a proof posted online on 1 January1 that the minimum number of clues \u2014 or starting digits \u2014 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.<\/p><\/blockquote>\n<blockquote><p>\n\u201cThe approach is reasonable and it\u2019s plausible. I\u2019d say the attitude is one of cautious optimism,\u201d 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.\n<\/p><\/blockquote>\n<blockquote><p>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. \u201cThe only realistic way to do it was the brute force approach,\u201d 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.<\/p><\/blockquote>\n<p><a href=\"http:\/\/www.math.ie\/McGuire_V1.pdf\">Papier en format PDF<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <a href=\"https:\/\/blog.carlrobitaille.org\/?p=858\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,15],"tags":[],"class_list":["post-858","post","type-post","status-publish","format-standard","hentry","category-mathematiques","category-programmation"],"_links":{"self":[{"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=\/wp\/v2\/posts\/858","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=858"}],"version-history":[{"count":3,"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=\/wp\/v2\/posts\/858\/revisions"}],"predecessor-version":[{"id":860,"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=\/wp\/v2\/posts\/858\/revisions\/860"}],"wp:attachment":[{"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=858"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=858"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.carlrobitaille.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=858"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}