{"id":1302,"date":"2010-12-07T12:25:40","date_gmt":"2010-12-07T16:25:40","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1302"},"modified":"2010-12-07T12:25:40","modified_gmt":"2010-12-07T16:25:40","slug":"operations-research-sudoko-rogo-and-puzzles","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/12\/07\/operations-research-sudoko-rogo-and-puzzles\/","title":{"rendered":"Operations Research, Sudoko, Rogo, and Puzzles"},"content":{"rendered":"

A few years back, Sudoko became a craze with seemingly everyone spending their time solving these puzzles.\u00a0 The puzzle is quite simple:\u00a0 take a nine by nine grid, partially filled in with numbers from one to nine, and complete it so that every row, column, and non-overlapping 3×3 square contains the numbers one through nine exactly once each.\u00a0 While the grid contains numbers, there is no mathematics involved:\u00a0 using the letters a-i would work as well.\u00a0 But you can use mathematics (in the form of logic) to solve the puzzle.\u00a0 To solve these by hand, puzzlers quickly learn logical rules, from the simple (“If only one square is open in a row, then you know what number goes there”) to advanced (say, alternate pair exclusion<\/a>).\u00a0 One can even use the methods of operations research (say, constraint programming<\/a> or integer programming<\/a>) to solve Sudoko puzzles.\u00a0\u00a0 It does not seem to discourage human solvers to know that these techniques can solve any Sudoko problem in milliseconds.<\/p>\n

There is often a close relationship between puzzles and the methods of operations research, particularly networks or discrete mathematics.\u00a0 Finding a path in a maze is nothing more than a shortest path problem;\u00a0 “logic” puzzles (“Smith, Jones, and Robinson are (not respectively) a trucker, a fireman, and an engineer, who live in …”, followed by facts, leading to “What is the name of the engineer?”) can be handled through integer programming, and so on.\u00a0 People, for some reason, like to do combinatorial search in their spare time.<\/p>\n

Hamish Waterer<\/a>, with whom I shared an office in New Zealand and who is now at Newcastle in Australia, pointed out to me a puzzle that has even closer ties to operations research: Rogo<\/a>.\u00a0 In Rogo, the goal is to find a loop through a grid of fixed length that contains as many reward points as possible.\u00a0\u00a0\u00a0 So, for this example (taken from the Rogo site<\/a>)<\/p>\n

\"\"<\/a><\/p>\n

the goal in this example is to find a loop of no more than 12 steps that includes as many points as possible.\u00a0\u00a0 The loop must be a real loop:\u00a0 it must return where it started and can’t cross itself or double back. Steps can be either horizontal or vertical:\u00a0 they cannot be diagonal.\u00a0 The loop cannot include any of the black squares.\u00a0 Here is the solution:<\/p>\n

\"\"<\/a><\/p>\n

\n

Rogo was created by two faculty members<\/a> (Nicola Petty<\/a> and Shane Dye<\/a>)\u00a0 at the University of Canterbury in Christchurch, New Zealand.\u00a0 Not surprisingly, Nicola and Shane teach management science there:\u00a0 the problem has a very strong operations research flavor.\u00a0 This is a form of the Prize Collecting Traveling Salesman problem<\/a>, originally studied by my colleague Egon Balas<\/a> (in the regular PCTSP, there is a penalty for distance traveled:\u00a0 in Rogo, there is an upper bound).<\/p>\n

If you want to play around with this, you can get the iPhone (touch, pad, etc.) app.<\/a> Creating a solver would make a nice undergraduate project (and I suspect there are at least a few master’s theses and perhaps a doctoral dissertation on algorithmic aspects of creating and solving these).<\/p>\n","protected":false},"excerpt":{"rendered":"

A few years back, Sudoko became a craze with seemingly everyone spending their time solving these puzzles.\u00a0 The puzzle is quite simple:\u00a0 take a nine by nine grid, partially filled in with numbers from one to nine, and complete it so that every row, column, and non-overlapping 3×3 square contains the numbers one through nine … Continue reading “Operations Research, Sudoko, Rogo, and Puzzles”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,45],"tags":[],"class_list":["post-1302","post","type-post","status-publish","format-standard","hentry","category-blogs-and-web","category-recreation"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1302","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=1302"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1302\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1302"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1302"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}