• Fandekasp 8 years ago + 3 comments

    After comparing different heuristics, I found that the best performance was given by this cost function

    steps_from_start + manhattan_dist + sqrt(nb_misplaced)
    
    • steps_from_start: length of path taken until current state
    • manhattan_dist: distance between each cell's position versus end position.
    • nb_misplaced: number of tiles incorrectly placed

    Solved in 20 moves after finding 667 states and navigating through 396 of them.

    Add Reply Preview cancel

    Sorry, you do not have a permission to answer to this question.

    • Fandekasp 8 years ago + 0 comments

      Played with matplotlib to generate a video solver for the sliding blocks:
      img

      https://youtu.be/XG5ZE11vFvc

      Add Reply Preview cancel

      Sorry, you do not have a permission to answer to this question.

      • tiberiu_iancu 7 years ago + 1 comment

        I used this formula but with or without sqrt(nb_misplaced) I still miss test 5

        Add Reply Preview cancel

        Sorry, you do not have a permission to answer to this question.

        • phychessics 4 years ago + 0 comments

          I have the same problem. All the test cases have passed except the Game 5. I do not know why. (Game number changes but always one case fails.)

          Add Reply Preview cancel

          Sorry, you do not have a permission to answer to this question.

        • schiebermc 7 years ago + 0 comments

          Is h(s) = (manhattan_dist + sqrt(nb_misplaced)) admissable??? I don't think adding the sqrt(nb_misplaced) is necessary, or even efficacious past the constrainted tests we have.

          Add Reply Preview cancel

          Sorry, you do not have a permission to answer to this question.

        1. Challenge Walkthrough
          Let's walk through this sample challenge and explore the features of the code editor.1 of 6
        2. Review the problem statement
          Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
        3. Choose a language
          Select the language you wish to use to solve this challenge.3 of 6
        4. Enter your code
          Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
        5. Test your code
          You can compile your code and test it for errors and accuracy before submitting.5 of 6
        6. Submit to see results
          When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
        1. Check your score