1

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)?

sudofix
  • 11
  • 2
  • 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. – nbro Jun 03 '20 at 22:32
  • actually both questions – sudofix Jun 03 '20 at 22:54
  • 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. – nbro Jun 03 '20 at 22:57
  • If you want to know more about hill climbing, I think that page 39 of the book [Clever Algorithms: Nature-Inspired Programming Recipes](https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Clever%20Algorithms_%20Nature-Inspired%20Programming%20Recipes%20%5BBrownlee%202012-06-15%5D.pdf#page=51) is your best bet. – nbro Jun 03 '20 at 22:59
  • 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 – sudofix Jun 03 '20 at 23:09
  • Maybe you can edit your post to share with us your current ideas and calculations. Right now, as I said, I won't try to answer your question, but maybe later. – nbro Jun 03 '20 at 23:11
  • ok, i'll do that – sudofix Jun 03 '20 at 23:12
  • As you've discovered, using hill climbing is theoretically possible, but practically impossible. I remember using A* to solve this problem and it still took a long time -- even for a greedy sub-optimal solution – nikos Jun 04 '20 at 17:30

0 Answers0