{"id":29923,"date":"2023-04-24T21:58:06","date_gmt":"2023-04-24T21:58:06","guid":{"rendered":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/"},"modified":"2023-04-24T21:58:07","modified_gmt":"2023-04-24T21:58:07","slug":"the-number-15-describes-the-secret-limit-of-an-infinite-grid","status":"publish","type":"post","link":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/","title":{"rendered":"The Number 15 Describes the Secret Limit of an Infinite Grid"},"content":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420\/#comments<\/a><\/br>
\nThe Number 15 Describes the Secret Limit of an Infinite Grid<\/br>
\n2023-04-24 21:58:06<\/br><\/p>\n

\n

For a first-year grad student who\u2019d roped a big-time professor into working on his pet problem, it was an unsettling discovery. \u201cI was horrified. I had basically been working for several months on a problem without realizing this, and even worse, I had made Marijn waste his time on it<\/em>!\u201d Subercaseaux wrote<\/a> in a blog post recapping their work.<\/p>\n

Heule, however, found the discovery of past results invigorating. It demonstrated that other researchers found the problem important enough to work on, and confirmed for him that the only result worth obtaining was to solve the problem completely.<\/p>\n

\u201cOnce we figured out there had been 20 years of work on the problem, that completely changed the picture,\u201d he said.<\/p>\n

Avoiding the Vulgar<\/strong><\/h2>\n

Over the years, Heule had made a career out of finding efficient ways to search among vast possible combinations. His approach is called SAT solving \u2014 short for \u201csatisfiability.\u201d It involves constructing a long formula, called a Boolean formula, that can have two possible results: 0 or 1. If the result is 1, the formula is true, and the problem is satisfied.<\/p>\n

For the packing coloring problem, each variable in the formula might represent whether a given cell is occupied by a given number. A computer looks for ways of assigning variables in order to satisfy the formula. If the computer can do it, you know it\u2019s possible to pack the grid under the conditions you\u2019ve set.<\/p>\n

Unfortunately, a straightforward encoding of the packing coloring problem as a Boolean formula could stretch to many millions of terms \u2014 a computer, or even a fleet of computers, could run forever testing all the different ways of assigning variables within it.<\/p>\n

\u201cTrying to do this brute force would take until the universe finishes if you did it na\u00efvely,\u201d Goddard said. \u201cSo you need some cool simplifications to bring it down to something that\u2019s even possible.\u201d<\/p>\n

Moreover, every time you add a number to the packing coloring problem, it becomes about 100 times harder, due to the way the possible combinations multiply. This means that if a bank of computers working in parallel could rule out 12 in a single day of computation, they\u2019d need 100 days of computation time to rule out 13.<\/p>\n

Heule and Subercaseaux regarded scaling up a brute-force computational approach as vulgar, in a way. \u201cWe had several promising ideas, so we took the mindset of \u2018Let\u2019s try to optimize our approach until we can solve this problem in less than 48 hours of computation on the cluster,\u2019\u201d Subercaseaux said.<\/p>\n

To do that, they had to come up with ways of limiting the number of combinations the computing cluster had to try.<\/p>\n

\u201c[They] want not just to solve it, but to solve it in an impressive way,\u201d said Alexander Soifer<\/a> of the University of Colorado, Colorado Springs.<\/p>\n

Heule and Subercaseaux recognized that many combinations are essentially the same. If you\u2019re trying to fill a diamond-shaped tile with eight different numbers, it doesn\u2019t matter if the first number you place is one up and one to the right of the center square, or one down and one to the left of the center square. The two placements are symmetric with each other and constrain your next move in exactly the same way, so there\u2019s no reason to check them both.<\/p>\n<\/div>\n

<\/br><\/br><\/br><\/p>\n

Uncategorized<\/br>
\n<\/br>
\nSource:https:\/\/www.quantamagazine.org\/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420\/#comments<\/a><\/br><\/br><\/p>\n","protected":false},"excerpt":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420\/#comments The Number 15 Describes the Secret Limit of an Infinite Grid 2023-04-24 21:58:06 For a first-year grad student who\u2019d roped a big-time professor into working on his pet problem, it was an unsettling discovery. \u201cI was horrified. I had basically been working for several months on a problem without realizing this, and even worse, […]<\/p>\n","protected":false},"author":1,"featured_media":29924,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","om_disable_all_campaigns":false,"pagelayer_contact_templates":[],"_pagelayer_content":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-29923","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"yoast_head":"\nThe Number 15 Describes the Secret Limit of an Infinite Grid - Science and Nerds<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"The Number 15 Describes the Secret Limit of an Infinite Grid - Science and Nerds\" \/>\n<meta property=\"og:description\" content=\"Source:https:\/\/www.quantamagazine.org\/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420\/#comments The Number 15 Describes the Secret Limit of an Infinite Grid 2023-04-24 21:58:06 For a first-year grad student who\u2019d roped a big-time professor into working on his pet problem, it was an unsettling discovery. \u201cI was horrified. I had basically been working for several months on a problem without realizing this, and even worse, […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/\" \/>\n<meta property=\"og:site_name\" content=\"Science and Nerds\" \/>\n<meta property=\"article:published_time\" content=\"2023-04-24T21:58:06+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-04-24T21:58:07+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp\" \/>\n\t<meta property=\"og:image:width\" content=\"1712\" \/>\n\t<meta property=\"og:image:height\" content=\"2280\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/webp\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/\",\"url\":\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/\",\"name\":\"The Number 15 Describes the Secret Limit of an Infinite Grid - Science and Nerds\",\"isPartOf\":{\"@id\":\"https:\/\/scienceandnerds.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp?fit=1712%2C2280&ssl=1\",\"datePublished\":\"2023-04-24T21:58:06+00:00\",\"dateModified\":\"2023-04-24T21:58:07+00:00\",\"author\":{\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\"},\"breadcrumb\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp?fit=1712%2C2280&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp?fit=1712%2C2280&ssl=1\",\"width\":1712,\"height\":2280},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/scienceandnerds.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"The Number 15 Describes the Secret Limit of an Infinite Grid\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/scienceandnerds.com\/#website\",\"url\":\"https:\/\/scienceandnerds.com\/\",\"name\":\"Science and Nerds\",\"description\":\"My WordPress Blog\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/scienceandnerds.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"caption\":\"admin\"},\"sameAs\":[\"https:\/\/scienceandnerds.com\"],\"url\":\"https:\/\/scienceandnerds.com\/author\/admin\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"The Number 15 Describes the Secret Limit of an Infinite Grid - Science and Nerds","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/","og_locale":"en_US","og_type":"article","og_title":"The Number 15 Describes the Secret Limit of an Infinite Grid - Science and Nerds","og_description":"Source:https:\/\/www.quantamagazine.org\/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420\/#comments The Number 15 Describes the Secret Limit of an Infinite Grid 2023-04-24 21:58:06 For a first-year grad student who\u2019d roped a big-time professor into working on his pet problem, it was an unsettling discovery. \u201cI was horrified. I had basically been working for several months on a problem without realizing this, and even worse, […]","og_url":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/","og_site_name":"Science and Nerds","article_published_time":"2023-04-24T21:58:06+00:00","article_modified_time":"2023-04-24T21:58:07+00:00","og_image":[{"width":1712,"height":2280,"url":"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp","type":"image\/webp"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/","url":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/","name":"The Number 15 Describes the Secret Limit of an Infinite Grid - Science and Nerds","isPartOf":{"@id":"https:\/\/scienceandnerds.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#primaryimage"},"image":{"@id":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp?fit=1712%2C2280&ssl=1","datePublished":"2023-04-24T21:58:06+00:00","dateModified":"2023-04-24T21:58:07+00:00","author":{"@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e"},"breadcrumb":{"@id":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#primaryimage","url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp?fit=1712%2C2280&ssl=1","contentUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp?fit=1712%2C2280&ssl=1","width":1712,"height":2280},{"@type":"BreadcrumbList","@id":"https:\/\/scienceandnerds.com\/2023\/04\/24\/the-number-15-describes-the-secret-limit-of-an-infinite-grid\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/scienceandnerds.com\/"},{"@type":"ListItem","position":2,"name":"The Number 15 Describes the Secret Limit of an Infinite Grid"}]},{"@type":"WebSite","@id":"https:\/\/scienceandnerds.com\/#website","url":"https:\/\/scienceandnerds.com\/","name":"Science and Nerds","description":"My WordPress Blog","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/scienceandnerds.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e","name":"admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","caption":"admin"},"sameAs":["https:\/\/scienceandnerds.com"],"url":"https:\/\/scienceandnerds.com\/author\/admin\/"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/04\/the-number-15-describes-the-secret-limit-of-an-infinite-grid_6446fb6ed5e11.webp?fit=1712%2C2280&ssl=1","_links":{"self":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/29923"}],"collection":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/comments?post=29923"}],"version-history":[{"count":1,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/29923\/revisions"}],"predecessor-version":[{"id":29925,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/29923\/revisions\/29925"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media\/29924"}],"wp:attachment":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media?parent=29923"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/categories?post=29923"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/tags?post=29923"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}