I am sure everyone has seen Sudoku puzzles: \u00a0it was quite a fad a few years ago. \u00a0The puzzle begins with an 9×9 grid, partially filled with numbers from 1 to 9 (the “givens”). \u00a0The goal is to complete the grid so that that every row, column, and the nine 3×3 subgrids in the corners and center all contain the numbers 1 through 9 with no missing and none repeated. \u00a0There was a time in my life where I loved Sudoku puzzles. \u00a0I had to give them up when I started to dream solely in Sudoku.<\/p>\n
The puzzles can be difficult or easy depending on straightforward it is to deduce missing values. \u00a0A grid with many \u00a0givens tends to be very easy, since there are few choices for missing values (though there can be hard problems with many givens and easy ones with few). \u00a0If too few values are filled in, however, the solution may not be unique, and it is a fundamental precept of puzzle-creators that the solution must be unique. \u00a0So, how many givens are needed to ensure uniqueness? It has been known for a long time that there exist problems with 17 givens that lead to unique solutions.<\/p>\n
Gary McGuire,\u00a0Bastian Tugemann,\u00a0Gilles Civario of University College Dublin proved this result is the best possible: \u00a0there is no problem with 16 givens with a unique solution. \u00a0They do this in a very interesting way: \u00a0they did an exhaustive search. \u00a0Given the number of possible solutions, it is surprising that exhaustive search works, but they were clever in organizing the search, and had access to a ridiculous amount of computational power. \u00a0This combination let them run through all the choices. \u00a0They didn’t find a 16, therefore there is not a sixteen!<\/p>\n
Fascinating work, and a sign of how fast computing can change how we look at research problems. \u00a0Technology Review<\/em>\u00a0has an article on this<\/a>; \u00a0the technical report is at arXiv<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":" I am sure everyone has seen Sudoku puzzles: \u00a0it was quite a fad a few years ago. \u00a0The puzzle begins with an 9×9 grid, partially filled with numbers from 1 to 9 (the “givens”). \u00a0The goal is to complete the grid so that that every row, column, and the nine 3×3 subgrids in the corners … Continue reading “16 Clue Sudokus”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45,46],"tags":[],"class_list":["post-1591","post","type-post","status-publish","format-standard","hentry","category-recreation","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1591","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1591"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1591\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1591"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1591"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1591"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}