Small puzzle game

User projects written in or related to FreeBASIC.
fbfan
Posts: 27
Joined: Oct 17, 2008 12:32

Postby fbfan » Jun 26, 2011 12:38

badidea could you briefly explain the solving algorithm?, im very interested
Destructosoft
Posts: 88
Joined: Apr 03, 2011 3:44
Location: Inside the bomb
Contact:

Postby Destructosoft » Jun 26, 2011 19:20

If it helps, the commercial version of this game in the 1980s was called Pythagoras, and Solomon Golomb the famous mathematician published a book in the 1960s called "Polyominoes" which mentioned it and other similar games and their solvability. (Seems long out of print, sadly, so I can't link to a purchasable copy.)
Richard
Posts: 3030
Joined: Jan 15, 2007 20:44
Location: Australia

Postby Richard » Jun 26, 2011 21:07

I can...
It was Hardcover. Charles Scribner's Sons,. 1965. Now reprinted, Softcover:

Title: Polyominoes. Author: Solomon W. Golomb
Softcover, ISBN 0691024448 Publisher: Princeton University Press, 1996
Used, very good, clean and straight, Usually ships in 1-2 business days Aust$18.05
http://www.bookfinder.com/search/?ac=sl ... 20packings
dodicat
Posts: 6687
Joined: Jan 10, 2006 20:30
Location: Scotland

Postby dodicat » Jun 26, 2011 21:52

Nicely done badidea
28 seconds on two X 3000Mhz dual cores.(no -exx) for the solutions.
I've only got a quadro graphics card which probably accounts for the speed lack.
And, I didn't realize that -exx switch slowed things down so much.
I'll keep it switched off awhile.
Cheers.
Mihail_B
Posts: 271
Joined: Jan 29, 2008 11:20
Location: Romania
Contact:

Postby Mihail_B » Aug 22, 2011 5:21

funny,nice game !
congrats. !
badidea
Posts: 2149
Joined: May 24, 2007 22:10
Location: The Netherlands

Postby badidea » Aug 23, 2011 14:57

badidea could you briefly explain the solving algorithm?, im very interested

Let me have a look at my own code, already more then a year since I posted this...

The main solver function is solve, this is a recursive function.
- It tries to place a piece at all possible locations and at all possible orientations. (function solver_testShape)
- If it fits the piece is placed. (function solver_setShape)
- Then it check for 'strange' gaps: Empty places with a area not dividable by 5. (function checkBadGap)
- If all OK, the solve function is called again (recursively) for the next piece.

The trick for speed is to prevent going to deep in the recursive path if this path will never lead to a solution. the function checkBadGap is not very fast, but it does prevent a lot of these false paths.

Now, I go for a drink here at work...

Return to “Projects”

Who is online

Users browsing this forum: No registered users and 2 guests