There are many like it, but this one is mine.
A recursive search algorithm for finding all solutions of the IQ FIT puzzle.
And also solutions for the IQ Love puzzle, which has more complex geometric shapes.
The software should run on any linux type system with gcc and Python for some post processing.
-
Clone/download the repo.
git clone https://github.com/isohelio/puzzles -
Run make in the repo folder, which should produce output like this
> make clean all rm -f *.o *.obj *.exe *.stackdump gmon.out cc -O4 -DNDEBUG -Wall -march=native -fomit-frame-pointer -c -o iqfit.o iqfit.c gcc -o iqfit iqfit.o -O4 -DNDEBUG -Wall -march=native -fomit-frame-pointer -lm -
Run the software with no arguments to generate all the solutions to the puzzle that contain no unfilled spaces. This takes about 2 minutes.
> ./iqfit -
To capture the solutions into a file
> ./iqfit -o solutions.txt -
To see command line options
> ./iqfit -h
usage: iqfit [options]
solve problems from the iqfit puzzle
-g file configuration for the game (default: config/iqfit.json)
-p n print every n'th solution (default: 1000)
-t n terminate after the n'th solution (default: none)
-d show every step of solving the board (default: off)
-On optimisation level 0-4 (default: 10!)
-o file print all solutions to file (default: none)
-i file read solutions from the specified file (default: none)
-S file solve examples from the specified file (default: none)
-D abbrevs deactivate the pieces specified by their abbreviations (default: none)
-s only generate the non-symmetry related solutions
-h print this message
default behaviour is to enumerate all solutions, using all optimisations
-O0 disable all optimisations, and allow solutions that include gaps
-O1 generate all solutions that don't include any gaps
-O2 skip partial solutions that include 1, 2 or 3 size gaps
-O3 skip partial solutions that include some impossible shapes
-O4 skip partial solutions that include size 7 gaps
The IQFIT pieces and board are now specified in a .json configuration file. The configuration can be specified with the -g option. The default is for the original IQFIT game and is contained in config/iqfit.json. You can view the piece definitions in the configuration file.
Most of the colours are self explanatory but the blue colour names have been taken to coincide with the physical pieces rather than the instruction manual. The colours are specified in linux terminal escape code colour numbers.
{
"width": 10,
"height": 5,
"step": 1,
"pieces": [
{
"name": "red", "colour": "31", "abbreviation": "R", "rgb": "230,0,28",
"layout": [ [ "****",
"* *"],
[ " *",
"****"] ]
},
{
"name": "orange", "colour": "33", "abbreviation": "O", "rgb": "255,193,80",
"layout": [ [ " * *",
"****"],
[ " * ",
"****"] ]
},
{
"name": "yellow", "colour": "93", "abbreviation": "Y", "rgb": "255,255,160",
"layout": [ [ "* ",
"****"],
[ "** ",
"****"] ]
},
{
"name": "cyan", "colour": "96", "abbreviation": "C", "rgb": "0,201,255",
"layout": [ [ " * ",
"****"],
[ " ** ",
"****"] ]
},
{
"name": "lightblue", "colour": "94", "abbreviation": "b", "rgb": "0,182,255",
"layout": [ [ "* * ",
"****"],
[ " *",
"****"] ]
},
{
"name": "pink", "colour": "95", "abbreviation": "p", "rgb": "243,116,187",
"layout": [ [ " * ",
"****"],
[ " **",
"****"] ]
},
{
"name": "lightgreen", "colour": "92", "abbreviation": "g", "rgb": "194,205,90",
"layout": [ [ "* *",
"***"],
[ " *",
"***"] ]
},
{
"name": "blue", "colour": "34", "abbreviation": "B", "rgb": "0,84,202",
"layout": [ [ "* *",
"***"],
[ " * ",
"***"] ]
},
{
"name": "green", "colour": "32", "abbreviation": "G", "rgb": "0,100,100",
"layout": [ [ " * ",
"***"],
[ " **",
"***"] ]
},
{
"name": "purple", "colour": "35", "abbreviation": "P", "rgb": "47,0,156",
"layout": [ [ "** ",
"***"],
[ "* ",
"***"] ]
}
]
}
Partial solutions can be provided using a simple text file format, which consists of
- A title
- 5 lines of 10 characters using the piece abbreviations
- Unfilled positions can be indicated with a - or _ character
There are examples in the examples folder e.g.
STARTER-1
ggg-CCCCGG
gBg-RCCGGG
BB--RPYYYY
bBb-RPPP-Y
bbbbRR----
To solve the puzzle run
./iqfit -S examples/examples.txt -p 1
Output will look like this
Specify -o filename to capture the puzzle solutions to a text file.
Alternatively if the title line is longer than 50 characters it is interpreted as a single line solution format e.g.
RRRRgggObbRPYRgOOOObPPYYYYBBBbPPppGGGBCbppppGGCCCC
Total solutions without gaps
iqfit -p 1000
total solutions 301350, invalid solutions 57472
Total solutions with gaps
iqfit -O0 -p 1000
total solutions 6462189, invalid solutions 0
There are a maximum of 56 nodes available from the 10 pieces. Therefore the 50 holes in the puzzle can be solved by omitting one piece.
Puzzle pieces can be deactivated using the -D flag e.g. to solve the puzzle without the cyan (C) piece
./iqfit -DC -p1
This produces the following solutions.
The solutions can be captured in an output file, specified with the -o option.
The solutions are stored one per line, printed from the top left corner. The piece positions are indicated using the piece abbreviation. A few lines from the file are shown below
RRRRgggObbRPYRgOOOObPPYYYYBBBbPPppGGGBCbppppGGCCCC
RRRRgggObbRGGRgOOOObGGGppCCCCbYppppBCPPbYYYYBBBPPP
RRRRgggOBBRCCRgOOOOBCCCCbGGGBBYbbbbpGPPPYYYYppppPP
RRRRgggOBBRGGRgOOOOBGGGCCCCPBBppppCbYPPPppbbbbYYYY
RRRRgggObbRYYRgOOOObGYYYYppppbGGPPBBBpCbGGPPPBCCCC
RRRRgggObbRYYRgOOOObGYYYYppppbGGCCPPPpBbGCCCCPPBBB
RRRRgggObbRYYRgOOOObBYYYYppppbBBCCPPPpGbBCCCCPPGGG
RRRRCCCCGGRPPROCCBGGgPOOOObBBGgPYbbbbBppggYYYYpppp
The single solution per line format is convenient for working with the solutions in command line tools.
Most solution analyses are done with Python as it is mainly just reading the single line solution output files.
The image generation parts of this require the python png module which is installed with
pip install pypng
With the --image option you can generate a png of all the solutions in a file. The --columns option specifies how many solutions to put in one row.
The images are a bit hard to handle but are quite neat to look at. The images have one pixel per section of the piece. Unfilled pieces are shown with a light grey checker board pattern.
Note that the default Photo Viewer in Windows 11 will not display these images correctly. It insists on interpolating the colours as you zoom in. ImageGlass will display them correctly.
python iqfit.py --image --input solutions/solutions.txt \
--columns 500 --output solutions/solutions.png
Here is a section from the full solution set image.
The Python helper program can generate the start points with two or three pieces that have a unique solution
python iqfit.py --two --input solutions/solutions.txt \
--output solutions/two_piece_solutions.txt --dedup
The --dedup option deduplicates the output by removing one pair of each of the solutions that are related by 180° rotation of the board. There are 13789 puzzles with two pieces that generate a single solution. A small sample is shown below.
Use the --three option to generate all three piece puzzles that have a unique solution. There are 1209312 three piece solutions.
The unique solutions are generated by taking each solution in turn and replacing all piece names with _ apart from the two or three pieces that are being considered. The partial solutions are then sorted together and the ones that only occur once are output as a solution.
________B__CC____BB_CCCC____B_____________________ 1
___________CC____BBBCCCC____B_____________________ 1
___________CC_BBB___CCCCB_B_______________________ 1
_______C_________C_____B_B_CC____BBB_C____________ 1
____C_________CC_______BCC______BBC________B______ 1
The solutions are deduplicated by generating the rotated version of the solution, and only writing it if the initial version is alphabetically less then the rotated version. This works for both complete solutions and partial solutions.
The IQ Love puzzle is another puzzle from Smartgames which uses geometrical shapes to fill a heart outline.
To generate the solutions for this puzzle use
./iqfit -g config/iqlove_heart.json -O6 -p 1
Generation is rather slow as there are no acceleration options for this puzzle type. The puzzle is represented using the same grid approach as IQ Fit, but each cell in the puzzles is represented by a 2x2 grid. The half square pieces use one of the 2x2 cells and rule prevents placements that don't allow moves which put the pieces anywhere other than opposite on a diagonal (this is not well explained here).
New puzzles that have two or three starting pieces and lead to a single solution can be generated in the same way as for IQ Fit. A PDF can be generated of the solutions or the puzzle starting points.
./iqfit -g config/iqlove_heart.json -i /tmp/random.txt -P solutions/iqlove_heart_solutions_three_random.pdf -t 200 -r 5 -c 4
An example PDF is in the output foler.
Where random.txt is some random selection of puzzles from the overall solution file. This can be generated with e.g.
sort -R solutions/iqlove_heart_solutions_three.txt | head -20 > /tmp/random.txt
Here is a screenshot of some random puzzles
