Sliding Numbers Puzzle

Hey,

I hope everyone is familiar with the number sliding puzzles. The numbers 1-N*N are scrabbled where N(dimension of grid) ranges from 4-10. The user needs to place the numbers in order after they have been scrambled. The number of empty spaces can range from 1 to N/2.

This project has certain requirements:

- Display the scrambled numbers.
- Allow the user to solve.
and
- Show the solution.

I have been working on this for sometime now but I can't seem to come up with a working algorithm that would solve the grid in a reasonable amount of time. Two empty spaces may be assumed since the grid may become unsolvable with only one empty space.

A push in the right direction would be greatly appreciated.

Thx,
Nomi

I'd have the user input either the tile-position or the tile-value that is to move, your choice. Tile-position would be the easiest. Then look for adjacent empty spots and if only 1, move the tile. If 2 or more, ask the user for the new tile-position.

Quote:

---

Originally Posted by WaltP

I'd have the user input either the tile-position or the tile-value that is to move, your choice. Tile-position would be the easiest. Then look for adjacent empty spots and if only 1, move the tile. If 2 or more, ask the user for the new tile-position.

---

Well allowing the user to play the game isnt that hard. What I am really having trouble with is showing the solution. It needs to be step by step instructions to solve the board in a minimal amount of time.

Calculate every move from the current board layout. Store them in an array with a pointer the the parent (current) layout. Move to the next layout in the array.

Check for final layout as you calculate each new board.

This will take time and memory. The more empty spaces, the more memory.

Well, do you want ONE solution, or the BEST solution? The algorithm and complexity is inherently different.

In any case: Wikipedia, which also links to a page containing a pretty good algorithm and a Java implementation. Hope you can figure it out from there.

Quote:

---

Originally Posted by jafet

Well, do you want ONE solution, or the BEST solution? The algorithm and complexity is inherently different.

In any case: Wikipedia, which also links to a page containing a pretty good algorithm and a Java implementation. Hope you can figure it out from there.

---

Im actually looking for the most efficient solution, but any solution would work right now. Thanks for the links. Im reading through them now.

I have finalized and cleaned up my code so everything but AI solve works. I cant seem to pen down the algorithm to solve it though. I sort of understand what needs to be done, but the complexity of the coding is scaring the crap out of me and I am making no significant progress.

Oh, that Java one was comparatively EASY -- simple recursion algorithm ;)

The BEST (shortest) solution is NP-Hard (read: will take a long long time to calculate), and I don't think the user will actually notice the difference between a "good" solution and the best one.

If you don't think you're up to the task, I think it's best to put all that code aside for now and go for something simpler first, just to get the hang of solving stuff.

Like this :)

Hey thanks a lot, I think I finally understand whats happening. I have a rough algorithm written down, I just need to code it now and see how it turns out.