tag:blogger.com,1999:blog-8243961069707831485.post3479200312224205044..comments2017-02-17T15:42:53.560+01:00Comments on Zamboch: Cube21 Silver edition - database of all solutionsPavel Šavarahttps://plus.google.com/111035739517412605958noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-8243961069707831485.post-85535837315763475102007-11-29T13:43:00.000+01:002007-11-29T13:43:00.000+01:00I didn't get the idea why you are proposing Needle...I didn't get the idea why you are proposing Needleman-Wunsch, this is for aligning sequences, right ? For normalization ? We need exact match not just close.<BR/><BR/>With the Dynamic programming, I believe that I did exactly that. Precomputed first level and reused it for second level and so on. But I'm not theory expert.Pavel Šavarahttp://www.blogger.com/profile/02673125542713538726noreply@blogger.comtag:blogger.com,1999:blog-8243961069707831485.post-70465509929813050882007-11-29T12:30:00.000+01:002007-11-29T12:30:00.000+01:00have you considered the needleman-wunsch-algorithm...have you considered the needleman-wunsch-algorithm or any other algorithm of graph theory and dynamic programming? you shouldn't neet more that linear space for this problem. see all-shortest-paths-problem...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8243961069707831485.post-75323740501001020212007-11-29T01:36:00.000+01:002007-11-29T01:36:00.000+01:00Of course, what I suggested is only an algorithm t...Of course, what I suggested is only an algorithm to solve a particular scrambled state.<BR/><BR/>If you really want to build the database of all solutions, then it doesn't help.Igorhttp://www.blogger.com/profile/16177148151031666504noreply@blogger.comtag:blogger.com,1999:blog-8243961069707831485.post-43032945540183953722007-11-29T01:23:00.000+01:002007-11-29T01:23:00.000+01:00Well, the point is that you don't have to build le...Well, the point is that you don't have to build levels 7-12.<BR/><BR/>It should be much less work (by several factors of magnitude) to only compute levels 1-6, and you'd need much less storage for the precomputed values.<BR/><BR/>By the way, if you don't know the maximum depth, you can still use bidirectional search. Search from the solution and the scrambled state in parallel (switch between the searches after each move), and terminate when one search reaches a state that has already been visited by the other search.Igorhttp://www.blogger.com/profile/16177148151031666504noreply@blogger.comtag:blogger.com,1999:blog-8243961069707831485.post-77919624612198766952007-11-29T00:09:00.000+01:002007-11-29T00:09:00.000+01:00Hmmm, I wasn't sure that there is only 12 levels b...Hmmm, I wasn't sure that there is only 12 levels before I reached all configurations, so now - why not use levels 7-12 when I already built them ? There is normalization as you described it, I call it minimalization and it's done on index of permutations.Pavel Šavarahttp://www.blogger.com/profile/02673125542713538726noreply@blogger.comtag:blogger.com,1999:blog-8243961069707831485.post-11966718628610646022007-11-28T23:44:00.000+01:002007-11-28T23:44:00.000+01:00I only read over your posting briefly, but there i...I only read over your posting briefly, but there is an interesting optimization that your solution does not seem to take advantage of.<BR/><BR/>It is called bidirectional search. Basically, if you know that a solution is always reachable within 12 steps, you search say 7 steps from the solution, and store all reachable states, as well as how many moves did you need to reach each of them.<BR/><BR/>Then, to find a solution for a particular cube state, you just have to search 5 steps from that state, and you are guaranteed to find a state reachable from the solution.<BR/><BR/>(By the way, if in your state representation multiple states are the "solution" - say because of rotations - you can either search from all of them, or do some normalization, e.g. by fixing one of the pieces.)Igor Ostrovskyhttp://www.igoro.comnoreply@blogger.com