Can we solve an $8 \times 8$ sliding puzzle using a random-restart hill climbing technique (steepest-ascent)? If yes, how much computing power will this need? And what is the maximum $n \times n$ that can be solved normally (e.g. with a Google's colab instance)?

  • $\begingroup$ Hi and welcome to AI SE! It's not clear to me if you're interested in answers that describe how this puzzle can be solved with hill climbing or if you're more interested in knowing the computational resources needed to solve it. $\endgroup$
    – nbro
    Jun 3 '20 at 22:32
  • $\begingroup$ actually both questions $\endgroup$
    – sudofix
    Jun 3 '20 at 22:54
  • $\begingroup$ Well, hill climbing is an iterative algorithm, so you can run it just for a few iterations without going out of memory or time, if that's your concern. Of course, this doesn't mean that you will find the right solution. Right now, I don't want to try to answer your question formally (because I would need to think about it a little bit more), but, to give you some guidance, how would you represent a solution in the search space? And what would be a neighbour of a solution? These are questions that you need to answer in order to solve your problem with hill climbing. $\endgroup$
    – nbro
    Jun 3 '20 at 22:57
  • $\begingroup$ If you want to know more about hill climbing, I think that page 39 of the book Clever Algorithms: Nature-Inspired Programming Recipes is your best bet. $\endgroup$
    – nbro
    Jun 3 '20 at 22:59
  • $\begingroup$ ok, i know i abou hill climbing but it's just i wrote a program to solve the problem i stated, and the program won't finish, and i did some calculations which showed that it would take years finding the solution, for example , 8 x 8 is 64 , so the search space actually would the factorial of 64 which is enormous! , so i need to make sure that's the case and i'm not doing anything wrong $\endgroup$
    – sudofix
    Jun 3 '20 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.