AutoSolve a 3x3 slider puzzle game

Page 1 of 1

7 Replies - 28080 Views - Last Post: 02 March 2010 - 05:42 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=153899&amp;s=c3d8e167f1fcb3cb914cb60e57d13a60&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 JorgenG

Reputation: 12
• Posts: 39
• Joined: 24-January 10

AutoSolve a 3x3 slider puzzle game

Posted 04 February 2010 - 08:25 AM

Hello all!

I have finished a little mini game. The game is a 3x3 slider puzzle. Like http://www.seasky.or...zle-game-1.html

In my game i have the numbers 1 - 8.

To represent the board i have a 2D array of Piece, which is an extension of JPanel. Each of these pieces have a storedValue integer. From 0 - 8, where 0 is the blank one.

I have been thinking a lot about this, and I think the best way to solve this might be using some kind of Tree structure, the problem is i have really low knowledge about how to use Trees to this purpose.

I tried using recursive methods but it didnt work the way i wanted it so i trashed it and started thinking new.

The methods i have to solve this is a method which tries to move a selected brick. This method checks if it is a valid move, and if it is, performs the move. This logic is working well. To shuffle the table i have a made a method that generates random moves until 100 validMoves have been performed. One way to do this could be by storing every move in an array, and just replay them, but that wouldnt be finding the "best" way to solve it.

If you just give me your first thoughts when reading about this problem that would be great. Just think how you wouldve solved it. If anyone wants any particular code just let me know, I just don't feel it is relevant when you know how the methods work. I am sorry if my explanation of this problem is poor, let me know how to improve and ill work on it :)

JorgenG

Is This A Good Question/Topic? 0

Replies To: AutoSolve a 3x3 slider puzzle game

#2 SwiftStriker00

• No idea why my code works

Reputation: 439
• Posts: 1,617
• Joined: 25-December 08

Re: AutoSolve a 3x3 slider puzzle game

Posted 04 February 2010 - 08:38 AM

Radom is never good when going about how to solve something. You had the right idea looking for the valid move, however theres a few things to do.

1) if you number the squares, 0-8. you want the 0 tile in (0,0),an the 8 tile in (3,3). So you can look at different "tactics" in the game to how to work a tile from any given position to its goal position

2) Depth First Search Is a good simple start to solving this

3) A* serach if you want to combine options 1 & 2

#3 JorgenG

Reputation: 12
• Posts: 39
• Joined: 24-January 10

Re: AutoSolve a 3x3 slider puzzle game

Posted 04 February 2010 - 08:56 AM

I see i might have been a bit unclear. In my current game, the user is the one who moves around on the tiles.

As of now the method isSolved returns true when the board looks like this:
Column: 0 1 2
Row 0: 1 2 3
Row 1: 4 5 6
Row 2: 7 8(0)

The random function is ONLY used to shuffle the board before the user starts solving it. So I did not use random in order to autosolve this.

The method i talk about is the actual method that moves around on the tiles with the correct game logic. Lets say we have the solved board in front of us and click on tile (2, 0) which has the value 7 then the value 8 moves to tile 2,2 and value 7 moves to value 2,1 and 2,0 has the value 0.

What i was talking about was using this method on a "copy" of the array to search and fin the quickes way to solve it. After the solution is found, I want it to have the "way" it went stored, so i can show the solution graphical.

I tried to use recursion by basically using two for loops, but i ended up clicking 0,0 and 0,1 tiles until it went to StackOverFlow. I will look further into Depth-first search, thanks for that.

#4 SwiftStriker00

• No idea why my code works

Reputation: 439
• Posts: 1,617
• Joined: 25-December 08

Re: AutoSolve a 3x3 slider puzzle game

Posted 04 February 2010 - 09:05 AM

Ya, there are two base searching algorithms that are used DFS (Depth) and BFS (Breadth Frist Search). The primary difference between them is Depth uses a stack and Breadth uses a queue. This means when searching a maze for example Depth will pick a path and take it as far as it can, then back track if its wrong. Breadth with go 1 step in every direction until it has the right path.

I think that DFS will be just a little bit more efficient but if you try both do let me know which was faster.

#5 baavgai

• Dreaming Coder

Reputation: 7150
• Posts: 14,892
• Joined: 16-October 07

Re: AutoSolve a 3x3 slider puzzle game

Posted 04 February 2010 - 10:34 AM

There's one real trick to any solution method: don't back track!

It's real easy to spin forever in something like this. You need some way to make sure you don't go where you've gone before. To this end, you need a puzzle object that can both by copied and compared.

#6 SwiftStriker00

• No idea why my code works

Reputation: 439
• Posts: 1,617
• Joined: 25-December 08

Re: AutoSolve a 3x3 slider puzzle game

Posted 04 February 2010 - 10:44 AM

baavgai Good point, I forgot to mention that. Im pretty sure its mentioned on the wiki I linked. But JorgenG, you are going to need to define a state of your puzzle (quite simply a 2d array will work), and if you've ever visited that place you should never go back, otherwise you will get an infinite loop

#7 JorgenG

Reputation: 12
• Posts: 39
• Joined: 24-January 10

Re: AutoSolve a 3x3 slider puzzle game

Posted 04 February 2010 - 01:58 PM

That should be fine, I already have the board consisting of a 2D array with objects in it, so adding the necessary components shouldn't be a problem. But is Tree's the way to go? I really don't have any knowledge about them, so if anyone have any good tutorials or tips I'd be happy.

Reputation:

Re: AutoSolve a 3x3 slider puzzle game

Posted 02 March 2010 - 05:42 AM

even just 3x3 in size, some puzzle take VERY long time to search. DFS usually spend alot more time, due to wrong direction search. For me, BFS is better, BUT you need some kind of
optimization to make it faster than human.

For example

0 8 7
6 5 4
3 2 1

W/O optimization, this one take 5 min! on my cpu (BFS). DFS is seem forever...