5

I read in the Guardian about a puzzle given to 8-year old in Vietnam.

Enter the digits 1 to 9 into the following grid so that the equality holds

enter image description here

Now, given access to a computer, this can be solved easily in a minute or so. My python solution is 19 lines of codes (8 of which is indentation).

What I'm interested in is whether there is a general algorithm better than the brute force for solving problems such as this one. My code found 136 solutions out of 9! = 362,880 possible arrangements of 1-9. So, is there a strategy better than randomly finding a solution once in ~2403 (362,880/136) attempts. In other words, if you were given this problem in Putnam, how would you approach it.

edit: assume regular order of operations, i.e. the "snake" plays no role

scibuff
  • 661
  • 4
    Do the normal order of operations rules apply, or is it strictly following the operations in order of the path? I'm just not familiar with problems written in snake format! – Paul May 21 '15 at 12:43
  • It would surprise me, if there is anything better than brute force. The only operations where restrictions might be possible, are the divisons. – Peter May 21 '15 at 12:44
  • An algorithm really sounds interesting – Ilaya Raja S May 21 '15 at 12:46
  • The problem would be more attractive, if the solution would be unique. Of course, this would make the problem very difficult, if it must be solved by hand. – Peter May 21 '15 at 12:46
  • To be honest, I'm more interested in a possible way to approach it than speculating about the role of the snake ... – scibuff May 21 '15 at 13:00
  • @Shane "it feels like there should be a way to solve it backwards" D you mean something like Dynamic programming? – quapka May 21 '15 at 13:03
  • @quapka I was thinking more like something analogous to backward induction to find a subgame perfect Nash equilibrium -- my dumb economist brain would only turn to DP if the problem were infinite and I were looking for a fixed point, but perhaps there's a way to formulate this as such. With the new edit, that the snake doesn't define the order of operations, this now seems less likely to be fruitful. – Shane May 21 '15 at 13:05
  • @Paul According to the algorithm scibuff provided the operations evaluate by the priority as usual. Also it is stated in the Guardian article: following the order of operations - multiply first, then division, addition and subtraction last. – quapka May 21 '15 at 13:12
  • @Shane Citing the article again: UPDATE: For those who were stumped by the symbols, the colon “:” is the division sign. Now return to your workings... – quapka May 21 '15 at 13:16
  • @quapka Thanks. I did see those subsequently and hence deleted the comment. – Shane May 21 '15 at 13:21
  • @DavidK thanks, I searched but would have never guessed that title (or those tags) – scibuff May 21 '15 at 13:56

0 Answers0