tom's blog

Solving the puzzle
By tom, history, 10 years ago, In English

Hello Codeforces community,

Here is a problem: http://www.spoj.com/problems/SOLVING/

How would you solve it? I don't want to skew your view, so I just leave the question without mentioning my (apparently too slow) solution.

Thanks, tom

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Did you try using A-Star algorithm? I think search space is too big even for this algorithm but you can give it a try. Since optimal solution is not required you may use non-consistent heuristic to speed up the search.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Yes. My algorithm looks as follows:

    for every tile i from 1 to n*n-1
  go to tile i
  "bring" tile i near (manhattan distance <= 2) to the place it should be at
  run A* to put it there

    My heuristic is simple sum of manhattan distances between current point and destination point for tiles <= i.

    It works well except two last rows. Sometimes it takes a lot of time to finish them.

    → Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

My bad XDDDD, ignore, its stupid

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Look at the constraints, board can be up to 10x10

    → Reply