## Small puzzle game

User projects written in or related to FreeBASIC.
fbfan
Posts: 27
Joined: Oct 17, 2008 12:32
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:
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
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
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:
funny,nice game !
congrats. !
Posts: 2149
Joined: May 24, 2007 22:10
Location: The Netherlands
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...