![\"Case0\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2015\/12\/Case0.jpg\")
<\/a><\/p>\nIf it works out, one gets information about the number of mines in the eight nearest-neighbor spaces.\u00a0 If one is lucky, the information is enough to solve the puzzle outright.\u00a0 Case 1 is such a case.\u00a0 After one successful blind guess, the information available on the board was sufficient to get to the end stage where it is obvious how to solve the puzzle<\/p>\n
The two remaining mines need to go directly next to the \u20183\u2019 and the \u20184\u2019 and so the remaining two spaces can be explored without fear.<\/p>\n Sometimes, no amount of logic can save you and there is nothing to do but guess as in Case 2. \u00a0After the initial blind-guess the board looked like<\/p>\n Solving for the obvious spaces leads to the final configuration with two unexplored spaces and one remaining mine.\u00a0 No amount of deductive or inductive logic will save the day and a 50\/50 guess is required (for those who care, I guessed wrong).<\/p>\n Both of these cases have the luxury of being straightforward.\u00a0 The amount of thinking was kept to a minimum and the options were well understood (although not always successfully so).<\/p>\n The true complexity of the game becomes apparent in the in-between Case 3.\u00a0 After the blind guess and resolution of the easy spaces, the board looked like this:<\/p>\n There is no way to easily finish off the board but nor is the final solution up to chance.\u00a0 It is a matter of exploring possibilities.\u00a0 Since \u20181\u2019 spaces are easiest to deal with, let\u2019s focus on the line of three \u20181\u2019s found on the lower right.\u00a0 Let\u2019s tentatively mark the rightmost \u20181\u2019 as having a mine directly below it by placing a \u2018?\u2019 on the space.\u00a0 Making that assumption leads to a propagation of other possible mine spaces, each marked with a \u2018?\u2019, as shown below<\/p>\n The entire set of \u2018?\u2019s is consistent \u2013 that is to say, we don\u2019t have a contradiction anywhere.<\/p>\n Next suppose that we assume a mine just below the middle \u20181\u2019 on the row of three on the right.\u00a0 Putting a \u2018?\u2019 there leads to an inconsistency, since if there is a mine at the location of the \u2018?\u2019 there is no way to satisfy the \u20181\u2019 and \u20182\u2019that are next to each other.\u00a0 The red dot (which is photo-edited in since Minesweeper doesn\u2019t provide a marker for inconsistency) drives this point home.<\/p>\n Similar logic holds for putting the \u2018?\u2019 under the leftmost \u20181\u2019 and so the only consistent guess was the first one.\u00a0 Acting on that guess leads immediately to success.<\/p>\n The true complexity of Minesweeper becomes obvious upon reflection of what can happen when the field is bigger and the number of mines is increased.\u00a0 Each blind luck move at the beginning of the game can lead to numerous possible avenues to explore.\u00a0 Each \u2018?\u2019 placed on the board can spawn additional channels to explore; the difficulty can grow exponentially.<\/p>\n This argument is a plausible, heuristic one so there may be a tendency for the reader to respond \u2018But you really haven\u2019t proven it!\u2019.\u00a0 That is a point I am willing to concede \u2013 I haven\u2019t proven it \u2013 but someone has.<\/p>\n In the spring of 2000, mathematician Richard Kaye of Birmingham University was able to prove that Minesweeper is NP-Complete<\/a>.\u00a0 This means that Minesweeper is a decision problem (did you solve it or did you detonate), it is very hard to find a solution, and it is very easy to check the solution.\u00a0 He also went on to construct various logic gates in Minesweeper<\/a> and using these, proved, in 2007, that Minesweeper played on an infinite board with infinite mines (although fewer mines than spaces) is also Turing complete<\/a>.<\/p>\n So the next time someone chides you for wasting time playing Minesweeper, respectfully point out that you are not wasting time, you are researching one of the most important open questions in computer science.<\/p>\n","protected":false},"excerpt":{"rendered":" A couple of weeks ago, I explored the notion of computational complexity and how amazing amounts of complexity can show up in seemingly simple contexts.\u00a0 In the particular case examined,… Read more ><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-402","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/402","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=402"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/402\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=402"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=402"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=402"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n