Solving Puzzle using Simulated Annealing

Look at the Picture below

photo (1)

There are NxM square tiles – each edge of which is colored using a different color.

If 2 adjacent tiles have the same color facing each other – we add a point.

The problem is to Swap the tiles so that we get the maximum number of points. Swapping means that 1 tile is exchanged with another tile without changing the orientation of any of the tiles.

What is the best way to solve this problem.

I tried Simulated Annealing.

 

Here is the programmatic (python) solution to this.

Python code is available here

https://github.com/palsumitpal/sumitpython/blob/master/SimulatedAnnealingPuzzleSolve.py

With my solution – it approaches quite close to the maximum possible

The way to run the code is below

python SimulatedAnnealingPuzzleSolve.py 5 5 20000 Greedy

1st Param (int)- Rows in the Grid

2nd Param (int)- Cols in the Grid

3rd Param (int)- Number of Max Iterations to be done

4th Parameter (String)- Whether to choose the Greedy algorithm or generalized Simulated Annealing – Possible values – Greedy or Any other String ( which chooses Generalized Simulated Annealing )

The output of the program gives the final score – either when it 1 or 2 points from the max possible points or after the program terminates after the Max Number of Iterations.

It also prints in ( Color in Unix Console ) – the arrangement of the tiles.

Sample Output from a Unix Console ( cygwin / unix command prompt – you can see the colors)

On windows command prompt – you will only see the color codes

1 Block is represented as

-Y-

G-B

-R-

[cloudera@localhost code]$ python SimulatedAnnealingPuzzleSolve.py 5 5 20000 Greedy

Initial Pieces

-Y- -G- -R- -Y- -G-

G-B R-Y Y-G B-G Y-B

-R- -B- -B- -R- -R-

-Y- -Y- -Y- -R- -R-

R-G G-B G-R B-G G-B

-B- -R- -B- -Y- -Y-

-R- -B- -R- -R- -G-

B-G Y-G G-Y G-B B-R

-Y- -R- -B- -Y- -Y-

-B- -R- -G- -G- -Y-

Y-R G-Y B-Y R-Y G-B

-G- -B- -R- -B- -R-

-G- -G- -Y- -B- -Y-

B-R B-R R-B Y-R R-B

-Y- -Y- -G- -G- -G-

 

Max Possible Score Possible for GridSize(5,5) = 40

Initial State 13

Max achieved by Simulated Annealing with Steepest Ascent 34

Current Max State After Generalized Simulated Annealing

-Y- -G- -Y- -G- -G-

G-B B-R R-B B-R R-Y

-R- -Y- -G- -Y- -B-

-R- -Y- -G- -Y- -B-

Y-G G-B B-Y B-G Y-R

-B- -R- -R- -R- -G-

-B- -R- -R- -R- -G-

Y-G G-Y B-G G-Y Y-B

-R- -B- -Y- -B- -R-

-R- -B- -Y- -R- -R-

G-B Y-R R-B B-G G-B

-Y- -G- -G- -Y- -Y-

-Y- -G- -G- -Y- -Y-

G-B B-R R-Y G-R R-G

-R- -Y- -B- -B- -B-

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s