Puzzle Solver

Last week I posted a new project to Github. It’s called Puzzle Solver. It is a very basic breadth first search solver for board puzzles.

I have a few puzzles from Israel that have the theme of placing tiles on a board in a specific way. I wanted to try and write a program to solve these types of puzzles. It is a bit more complicated than just a recursive search as tiles can be rotated.

The program only solves for the puzzle listed below, but eventually I want to get it to solve arbitrary puzzles by only requiring the pieces, the board size, and a function indicting “valid state”

Example

(Source: www.thinkinggames.com)

The solution from running the program yielded 4 solutions:

``````Starting
Solution # 1 =
Place [["Star","Bull","Tria"]] at position 0,0
Place [["Yell"],["Tria"],["Squig"]] at position 3,0
Place [["Squig"],["Star"],["Yell"]] at position 4,0
Place [["Squig","Yell","Bull"]] at position 0,1
Place [["Bull"],["Yell"],["Tria"]] at position 0,2
Place [["Tria","Star"]] at position 1,2
Place [["Star","Squig","Bull"]] at position 1,3
Place [["Tria"],["Bull"]] at position 4,3
Place [["Squig","Yell","Star"]] at position 1,4

[ [ 'Star', 'Bull', 'Tria', 'Yell', 'Squig' ],
[ 'Squig', 'Yell', 'Bull', 'Tria', 'Star' ],
[ 'Bull', 'Tria', 'Star', 'Squig', 'Yell' ],
[ 'Yell', 'Star', 'Squig', 'Bull', 'Tria' ],
[ 'Tria', 'Squig', 'Yell', 'Star', 'Bull' ] ]

Solution # 2 =
Place [["Star","Bull","Tria"]] at position 0,0
Place [["Squig"],["Tria"],["Yell"]] at position 3,0
Place [["Yell"],["Star"],["Squig"]] at position 4,0
Place [["Squig","Yell","Bull"]] at position 0,1
Place [["Bull"],["Yell"],["Tria"]] at position 0,2
Place [["Tria","Star"]] at position 1,2
Place [["Star","Squig","Bull"]] at position 1,3
Place [["Tria"],["Bull"]] at position 4,3
Place [["Squig","Yell","Star"]] at position 1,4

[ [ 'Star', 'Bull', 'Tria', 'Squig', 'Yell' ],
[ 'Squig', 'Yell', 'Bull', 'Tria', 'Star' ],
[ 'Bull', 'Tria', 'Star', 'Yell', 'Squig' ],
[ 'Yell', 'Star', 'Squig', 'Bull', 'Tria' ],
[ 'Tria', 'Squig', 'Yell', 'Star', 'Bull' ] ]

Solution # 3 =
Place [["Star"],["Bull"],["Tria"]] at position 0,0
Place [["Squig"],["Yell"],["Bull"]] at position 1,0
Place [["Bull","Yell","Tria"]] at position 2,0
Place [["Tria"],["Star"]] at position 2,1
Place [["Star"],["Squig"],["Bull"]] at position 3,1
Place [["Squig"],["Yell"],["Star"]] at position 4,1
Place [["Yell","Tria","Squig"]] at position 0,3
Place [["Squig","Star","Yell"]] at position 0,4
Place [["Tria","Bull"]] at position 3,4

[ [ 'Star', 'Squig', 'Bull', 'Yell', 'Tria' ],
[ 'Bull', 'Yell', 'Tria', 'Star', 'Squig' ],
[ 'Tria', 'Bull', 'Star', 'Squig', 'Yell' ],
[ 'Yell', 'Tria', 'Squig', 'Bull', 'Star' ],
[ 'Squig', 'Star', 'Yell', 'Tria', 'Bull' ] ]

Solution # 4 =
Place [["Bull"],["Tria"]] at position 0,0
Place [["Tria"],["Yell"],["Bull"]] at position 1,0
Place [["Squig","Yell","Star"]] at position 2,0
Place [["Star","Squig","Bull"]] at position 2,1
Place [["Squig"],["Star"],["Yell"]] at position 0,2
Place [["Tria","Star"]] at position 2,2
Place [["Yell"],["Tria"],["Squig"]] at position 4,2
Place [["Squig","Yell","Bull"]] at position 1,3
Place [["Star","Bull","Tria"]] at position 1,4

[ [ 'Bull', 'Tria', 'Squig', 'Yell', 'Star' ],
[ 'Tria', 'Yell', 'Star', 'Squig', 'Bull' ],
[ 'Squig', 'Bull', 'Tria', 'Star', 'Yell' ],
[ 'Star', 'Squig', 'Yell', 'Bull', 'Tria' ],
[ 'Yell', 'Star', 'Bull', 'Tria', 'Squig' ] ]

------
Found 4 solutions in 1.259 seconds (595885 iterations)...
``````

Possible Improvements

The algorithm could possibly be improved to prevent symmetric attempts from being attempted again.

The project is currently hard coded for a specific puzzle game, but without much effort it should be able to be abstracted out as an object with overridable functions to specify the board size, pieces, and a “isValid” function which returns true or false on whether the search should continue.

Redbox Movies with IMDB and Rotten Tomato Ratings Mobile App

My latest mobile project is Redbox Movies Reviewed. The application lists Redbox movies sorted by IMDB and Rotten Tomato ratings.

Annoying to Very Annoying Newsletter Practices

I really… really hate newsletters from websites I don’t want them from. What I hate even more is the unsubscribing process that websites employ. It’s like cancelling a gym membership.

My flow of frustration in the unsubscribing process. Some websites employ a Hotel California approach in newsletters – you can check out any time you’d like but you can never leave.

Is it unreasonable for me to demand that I shouldn’t have to log in to a website to unsubscribe from their email list?

Migrated server

Sorry everyone for recent downtime. Just changed servers…

Looks like the wordpress importer decided not to import all the comments… Great.

In other news, I’ve launched a new word game for IPhone, IPad, and Android.