{"id":3809,"date":"2015-06-12T07:38:42","date_gmt":"2015-06-12T07:38:42","guid":{"rendered":"http:\/\/www.lifeandnews.com\/articles\/?p=3809"},"modified":"2016-09-02T23:36:48","modified_gmt":"2016-09-02T23:36:48","slug":"totally-addicted-to-apps-difficulty-makes-candy-crush-so-sweet","status":"publish","type":"post","link":"https:\/\/www.lifeandnews.com\/articles\/totally-addicted-to-apps-difficulty-makes-candy-crush-so-sweet\/","title":{"rendered":"Totally addicted to apps: difficulty makes Candy Crush so sweet"},"content":{"rendered":"

Toby Walsh<\/a>, NICTA<\/a><\/em><\/p>\n

It\u2019s been said that in a city, you\u2019re never more than two metres<\/a> away from a rat. But it seems more likely that you\u2019re never more than two metres from someone playing the puzzle game Candy Crush Saga<\/a>.<\/p>\n

One possible reason that Candy Crush is so addictive has been revealed in my recent proof<\/a> which shows that it is a mathematically hard puzzle to solve, thus joining the ranks of puzzles such as Minesweeper<\/a>, Sudoku<\/a> and Tetris<\/a> which have also been proved to be mathematically hard to solve.<\/p>\n

Candy Crush is currently the most popular game<\/a> on Facebook and it\u2019s been downloaded and installed more than half a billion times. Its developer, King.com Ltd<\/a>, is soon to list on the New York Stock Exchange in an initial public offering predicted<\/a> to value the company at more than US$5 billion.<\/p>\n

That\u2019s not bad for a simple game of swapping candies to form chains of three or more identical candies.<\/p>\n

So how do we go about proving that a puzzle such as Candy Crush is hard to solve? What makes noughts and crosses easy, but Candy Crush hard?<\/p>\n

Deduction from reduction<\/h2>\n

To prove that Candy Crush is hard, we need to call upon one of the most important and beautiful concepts in the whole of computer science: the idea of a problem reduction<\/a>. This is the idea of mapping one problem into another. Or as computer scientists like to say, you reduce one problem into another.<\/p>\n

\"\"<\/a>
JuhaOnTheRoad\/Flickr<\/a>, CC BY-NC-SA<\/a><\/span><\/figcaption><\/figure>\n

Now, if the problem you started with was hard, then the problem you map into must be at least as hard. The second problem can\u2019t be easier as you can solve the first problem with a program that can solve the second. And if you can show the reverse, that the second problem can be reduced to the first, then the two problems are equally as hard.<\/p>\n

In the case of Candy Crush, we started with the most famous class of computationally hard problems \u2013 problems in a class called \u201cNon-deterministic Polynomial-time\u201d (NP<\/a>). This class contains all the problems that computer scientists believe are on the boundary between hard and easy.<\/p>\n

Beneath NP, we have the problem class P that contains all the easy problems such as sorting a list or finding a record in a database. The time it takes for an efficient computer program to solve such problems is small, even in the worst case.<\/p>\n

Mathematically, the runtime (the length of time a program takes to run) is a polynomial<\/a> (consisting just of terms multiplied together) of the size of the problem.<\/p>\n

Above NP, we have really hard problems. There are even problems above NP for which there is no computer program which is guaranteed to stop and return an answer. You may wait for ever and still not have an answer.<\/p>\n

NP, on the other hand, is right at the boundary between easy and hard. Within NP, we have many challenging problems such as the problem of routing trucks to deliver parcels, rostering staff in a hospital, or scheduling classes in a school. Any of these problems can be reduced to any other of these problems. They\u2019re all equally as hard as each other.<\/p>\n

\"\"<\/a>
MIT-Libraries\/Flickr<\/a>, CC BY-ND<\/a><\/span><\/figcaption><\/figure>\n

The best computer program that we have for any problem in NP has a runtime that grows dramatically as we increase the size of the problem.<\/p>\n

On my desktop computer, I have a program that takes a few hours to find the optimal routing for ten trucks and demonstrate that this was the best that can be possibly achieved.<\/p>\n

But for 100 trucks, the same program would take more than the lifetime of the universe. Mathematically, the runtime of my program is an exponential of the size of the problem.<\/p>\n

Deciding between \u2018easy\u2019 and \u2018hard\u2019 is, um, hard<\/h2>\n

Surprisingly, while computer scientists believe problems in NP are on the boundary between easy and hard, they don\u2019t actually know on which side they are.<\/p>\n

The best computer programs we have take exponential time to solve problems in NP. But we don\u2019t know if there\u2019s some exotic algorithm out there that will solve problems in NP efficiently\u00a0\u2013\u00a0and by efficiently, we mean in polynomial time.<\/p>\n

In fact, this is one of the most important open problems in mathematics today, the famous P=NP<\/a> question. The Clay Mathematics Institute<\/a> has even offered a US$1 million prize for the answer to this question. The prize<\/a> remains unclaimed since it was first offered in 2000.<\/p>\n

The idea of problem reduction is central to the P=NP question. If we did find an algorithm that could solve any problem in NP efficiently then, by exploiting the idea of problem reduction, we could solve all problems in NP efficiently. The world would be a very different place if this ever happened.<\/p>\n

On the plus side, we\u2019d be able to go about our lives more efficiently, routing trucks, timetabling flights, and rostering staff to save money, but the absence of efficient algorithms to do various tasks such as crack codes is also required to keep our passwords and bank accounts secure.<\/p>\n

\"\"<\/a>
Symic\/Flickr<\/a>, CC BY-SA<\/a><\/span><\/figcaption><\/figure>\n

Hard candy<\/h2>\n

Anyway, let\u2019s go back to Candy Crush. To show that Candy Crush is a hard problem, we could reduce from any problem in NP. But to make life simple, we start from the granddaddy of all problems in NP: finding a solution to a logical formula.<\/p>\n

Mathematically, this is called the satisfiability problem<\/a>. You will have solved such a problem if you ever tackled a logic puzzle. You have to decide which propositions to make true, and which to make false, in order to satisfy some logical formulae.<\/p>\n

We created a collection of candies where the player has choices as to which chains to create. And these choices have knock-on effects that mirror exactly the knock-on effects of the choices in deciding which propositions in a logical formula to make true.<\/p>\n

\"\"<\/a>
faseextra\/Flickr<\/a>, CC BY-SA<\/a><\/span><\/figcaption><\/figure>\n

We also showed the reverse \u2013\u00a0that is, you can reduce a Candy Crush problem to satisfying a logical formula. Hence, Candy Crush is no harder than any of the problems in NP. Candy Crush is equally as hard as solving all the other problems in NP.<\/p>\n

If we had an efficient way to play Candy Crush, the we would have an efficient way to route trucks, roster staff or schedule classes. Equally, if we had an efficient way to way to route trucks, roster staff, or schedule classes then we would have an efficient way to play Candy Crush. That\u2019s the power of a problem reduction.<\/p>\n

So, next time you fail to solve a Candy Crush board in the given number of swaps, you can console yourself with the knowledge that it was a mathematically hard problem to solve. Just as hard, in fact, as the staff rostering problem your boss actually wanted you to solve instead of playing Candy Crush.<\/p>\n

Finally, there\u2019s an intriguing possibility that may appeal to Candy Crush addicts. Can we profit from the millions of hours humans spend solving Candy Crush problems? By exploiting the idea of a problem reduction, perhaps we can hide some practical computational problems within these puzzles?<\/p>\n

\"The<\/p>\n

Toby Walsh<\/a> is Professor, Research Group Leader, Optimisation Research Group at NICTA<\/a>.<\/p>\n

This article was originally published on The Conversation<\/a>.
\nRead the original article<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Toby Walsh, NICTA It\u2019s been said that in a city, you\u2019re never more than two metres away from a rat. But it seems more likely that you\u2019re never more than two metres from someone playing the puzzle game Candy Crush Saga. One possible reason that Candy Crush is so addictive has been revealed in my […]<\/p>\n","protected":false},"author":40,"featured_media":7722,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[28],"tags":[],"_links":{"self":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/3809"}],"collection":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/users\/40"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/comments?post=3809"}],"version-history":[{"count":2,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/3809\/revisions"}],"predecessor-version":[{"id":7723,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/3809\/revisions\/7723"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/media\/7722"}],"wp:attachment":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/media?parent=3809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/categories?post=3809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/tags?post=3809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}