tag:blogger.com,1999:blog-6753769565491687768.post8152712645736147993..comments2019-06-25T08:05:11.117+02:00Comments on Tomasz Nurkiewicz around Java and concurrency: Brute-forcing a seemingly simple number puzzlenurkiewiczhttp://www.blogger.com/profile/05938011050162061962noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-6753769565491687768.post-4253534838774983712018-10-05T12:27:48.307+02:002018-10-05T12:27:48.307+02:00Really enjoyed this post! So much I made my own ve...Really enjoyed this post! So much I made my own version of it.<br />I did manage to find a solution by starting 1 in the corner:<br /><br />+-----------------------+<br />| 1 49 22 2 17 23 3 9 24 4 |<br />| 88 46 19 32 40 13 26 6 14 27 |<br />| 21 34 42 48 35 8 16 29 37 10 |<br />| 44 50 89 45 18 31 39 12 25 5 |<br />| 87 47 20 33 41 67 36 7 15 28 |<br />| 96 91 43 51 90 82 52 30 38 11 |<br />| 77 72 94 78 75 60 79 68 61 58 |<br />| 86 100 97 83 55 66 63 56 53 64 |<br />| 95 92 76 71 93 81 70 59 80 69 |<br />| 98 73 85 99 74 84 54 65 62 57 |<br />+-----------------------+<br /><br />Nathan's approach was used, where all the possible moves from the current cell were being tested recursively. <br /><br />Its made in processing, to more easily visualize the results. code: <br />https://github.com/TomRoozendaal/processing-projects/tree/master/gridPuzzle<br />Unknownhttps://www.blogger.com/profile/05901333599786072809noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-81002694408573732872018-10-04T21:10:52.051+02:002018-10-04T21:10:52.051+02:00I couldn't help it - I found some free time an...I couldn't help it - I found some free time and had to try it.<br /><br />Turns out, if you use this heuristic, there is no need to recurse at all. The algorithm never reaches a dead end. You can see my solution (in Perl) here:<br /><br />https://github.com/greg-kennedy/100Hops<br /><br />Thanks for the puzzle, fun to play with on an otherwise boring day.Greg Kennedyhttps://www.blogger.com/profile/10730868092902552857noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-26948045966695750122018-10-04T10:59:14.965+02:002018-10-04T10:59:14.965+02:00You can easily construct Hamilton paths without an...You can easily construct Hamilton paths without any structure by hand. You just need to know one trick. If you have a path a-b-c-d-e-f and c is connected to f, then a-b-c-f-e-d is also a path. You can use this operation to move the end points of your path until they neighbour unfilled vertices and you can increase the length of your path. Just choose an operation which gets the end closer to unfilled vertex and if there are no such operation, just wander randomly. I constructed countless knight tours using this approach while I couldn't construct a single one before I discovered this trick.Unknownhttps://www.blogger.com/profile/04613219667357782049noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-48693102532379607622018-10-04T05:57:40.317+02:002018-10-04T05:57:40.317+02:00This sounds a lot like the Knight's Tour probl...This sounds a lot like the Knight's Tour problem. I wonder if you could apply the same heuristic that helps brute force solutions there...<br /><br />Create another 10x10 board. Each cell is then pre-filled with the number of "potential" moves reachable from that square. So for example, the corners have 3 escapes, while central squares have a full 8.<br /><br />Each time you visit a node, set its value to 0, and also update each potential (unvisited) hop from here, by decrementing the value in that cell. Then, recurse, but try your next hop in order of the lowest potential first.<br /><br />The goal here is to avoid creating unreachable cells, by ensuring that each one is visited in order of "least able to be reached" and getting those out of the way first.<br /><br />Added bonus: see if you can do a "perfect tour" by landing your final square within one hop of your initial square (a complete cycle).Greg Kennedyhttps://www.blogger.com/profile/10730868092902552857noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-40055527422023311742018-10-04T01:47:41.729+02:002018-10-04T01:47:41.729+02:00This comment has been removed by the author.rcortyhttps://www.blogger.com/profile/14727989507772001629noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-35376366164097209272018-10-03T21:11:14.826+02:002018-10-03T21:11:14.826+02:00Why not start at the third row and first column, s...Why not start at the third row and first column, solve it such that you end in the center square and then repeat this for all four quadrants? But not sure there exists such solution :)MatevÅ¾https://www.blogger.com/profile/11522649136113631601noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-74811435270151361272018-10-03T19:39:31.983+02:002018-10-03T19:39:31.983+02:00Well you really don't have to do the work, you...Well you really don't have to do the work, you could use the computer to pre-define it...anonymoushttps://www.blogger.com/profile/12995282086326826054noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-31321652304439822382018-10-03T16:30:12.629+02:002018-10-03T16:30:12.629+02:00You're working to hard. Let the computer do t...You're working to hard. Let the computer do the work. Its not like it has better things to do...Tyson Zwickerhttps://www.blogger.com/profile/13947319212122351757noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-16780764265679161212018-10-03T15:51:18.030+02:002018-10-03T15:51:18.030+02:00Oops. I just saw that my suggestion was also prov...Oops. I just saw that my suggestion was also provided in the linked stackexchange problem.<br />Unknownhttps://www.blogger.com/profile/01704275218389858364noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-51027875921322862682018-10-03T15:44:46.943+02:002018-10-03T15:44:46.943+02:00This may get out of the realm of "brute forci...This may get out of the realm of "brute forcing," but what if you divide the grid into four 5x5 boards, and, since the moves are valid in any orientation, solve for starting in the top left corner, and solving 5x5 such that move #25 ends in a position from which it can jump to the first row, sixth column (the starting point of the top right 5x5). Then solve for 5x5 where move #25 ends on the sixth row, fifth column (top right of the next square). Then use that same solutions, but rotated 90% to solve the bottom right quadrant, ending in position to jump to the bottom right of the bottom left quadrant and then use the same solution (rotated again) to solve the bottom left. Assuming there is a solution for those two boards, you are reducing the complexity from (100^2) * (8^100) to something slightly higher than 2 * (25^2) * (8^25). (Higher because of the constraint on the endpoint)Unknownhttps://www.blogger.com/profile/01704275218389858364noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-55700471740729440662018-10-03T15:09:53.256+02:002018-10-03T15:09:53.256+02:00Indeed, that sounds like a valid optimization!Indeed, that sounds like a valid optimization!Tomasz Nurkiewiczhttps://www.blogger.com/profile/05938011050162061962noreply@blogger.comtag:blogger.com,1999:blog-6753769565491687768.post-65987703327616050052018-10-03T15:06:47.275+02:002018-10-03T15:06:47.275+02:00Note: I am only a hack programmer (in the bad sens...Note: I am only a hack programmer (in the bad sense, not the good sense!)<br /><br />Question: Wouldn't it have made more sense to pre-define every possible move from each square up front rather then keep doing it over and over? Each square on the board would have an array of 8 valid moves (some of which would be null). Then you simply loop through the array for the current square and there is no need to determine direction and calculate which is the next square, you just go to the next memory address.<br /><br />Looks like an interesting problem for me to try in Python. NATHAN SPITZERhttps://www.blogger.com/profile/17542900944392275022noreply@blogger.com