Body: <p>Can we solve an <span class="math-container">$8 \times 8$</span> 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 <span class="math-container">$n \times n$</span> that can be solved normally (e.g. with a Google's colab instance)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T22:32:20.307Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T22:54:10.033Z
Comments.Text: actually both questions
Comments.UserDisplayName: sudofix
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T22:57:20.407Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T22:59:40.477Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T23:09:40.583Z
Comments.Text: 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
Comments.UserDisplayName: sudofix
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T23:11:06.357Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T23:12:31.687Z
Comments.Text: ok, i'll do that
Comments.UserDisplayName: sudofix
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-04T17:30:42.270Z
Comments.Text: 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
Comments.UserDisplayName: nikos
Tags: <algorithm><search><hill-climbing><local-search>
Title: Can we solve an $8 \times 8$ sliding puzzle using hill climbing?
UserDisplayName: sudofix
ThreadText: # Can we solve an $8 \times 8$ sliding puzzle using hill climbing?
  
  (Asked by: username_0 on 2020-06-03)
  
  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)?
  
  **Tags:** algorithm, search, hill-climbing, local-search
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: actually both questions  
  > **username_1**: 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.  
  > **username_1**: 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.  
  > **username_0**: 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  
  > **username_1**: 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.  
  > **username_0**: ok, i'll do that  
  > **username_2**: 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  
  
  ---
  
  ## 0 answers
  
  