One of my younger relatives showed me this curious puzzle (called "IQ Blox") while I was staying at their place. The premise is as follows: there's a leaflet included with the puzzle listing over a hundred "guides", which are initial positions of the white border bits ("walls") and colored pieces. From there you have to completely fill the board with the remaining pieces.
The leaflet claims there is only one solution for each guide. I was wondering if there's some specific math behind this puzzle. For example, if we represent it as a graph, there's this algorithm that, in combination with that algorithm, gives us all board configurations.
So, the question is:
How does one generate all the guides for a given set of pieces and walls, while also guaranteeing that there's one, and only one, solution? Or am I overthinking this, and it's simply bruteforced?
Thought, the search space seems quite large to me. A quick google search didn't reveal anything. Also, I'm not sure if this question would be more appropriate for Puzzles Stackexchange.
Thank you.
Just eye-balling that puzzle, I really don't think brute-forcing this is much of a problem for a computer (or even a human!). The board is of limited size, there are a limited number of pieces, and all pieces are of size 4 or 5. Thus, given the placement of three wall pieces (and if you watch the video, you'll see that some puzzles place all 4 white pieces), the number of possible placements of each of the pieces is already quite limited, even if we take rotation and mirroring (i.e. flipping them over) into account.
Just to see this for yourself, just consider the puzzle with the three white walls pieces placed as given in that image, and think of where the yellow 'U' piece can go. You'll find that there are really not a lot of options (also note that due to their symmetry, flipping the 'U' piece does not help, just as it doesn't help for the 'W' and 'T' pieces. And rotating the 'S' piece 180 degrees does not help either ...)
Moreover, after placing just one or two pieces, it will rule out possible positions for the remaining pieces even more quickly. Thus, I believe that even a completely dumb brute-force search algorithm will very quickly get to dead ends as it places the pieces, and should thus be able to cover the whole search space fairly quickly.
Of course, we can add some further intelligence to this algorithm as well. For example, placing the 'U' piece in 4-9-15-21-16 creates an isolated 'island' of size 2: 5-10 ... and that of course means that this is not going to work given that all pieces are of size 4 or 5. Indeed, creating any island with size smaller than 4 means you have reached a dead end.
You could even check for islands of size 6 or 7, or any number that you cannot form by the size 4 and 5 pieces (e.g. 11 or 16 (yes, 16 also works since there are only three pieces of size 4)) but I believe a brute force algorithm that just checks for islands smaller than 4 will already be highly, highly efficient.
Indeed, in the puzzle as shown, the yellow U piece creates such islands in every of its already limited number of positions except for one. Thus, we can figure out the correct location of the U piece almost immediately, and from there, the rest will be very straightforward as well.
And as if that is not already enough, yet another thing that you can do is to try to figure out how chunks of puzzle pieces are forced (you effectively do some of this already when identifying islands). For example, we know that 5 and 10 will always have to belong to the same piece. Moreover, once you place the white walls, a bunch more of those connections are forced. And, once you place a puzzle piece, more connections are forced.
Consider, for example, what happens when we place the white walls as from the image shown on the website, and we place the green piece in 12-17-22-23-28:
Now, this is one of the few locations that the green piece can go without creating an island smaller than 4. However, immediately we can see that (because of the white walls) 2 and 7 need to be connected but (because of the green piece), 11, 6, and 1 need to be connected as well ... and 1 will need to be connected to 7 .. thus forcing a piece of size 5 ... of a shape that does not exist. So, we know that the green piece does not go here.
Adding this further bit of intelligence to the brute force search algorithm might make it even more efficient yet, though I am not sure, since merely checking for islands of size smaller than 4 might already make it very, very fast. Indeed, every bit of intelligence you add will slow down the basic loop, and so there is always this interesting trade-off between the number of loops you have to go through and how long it takes to pass through each loop (this is also why I think that checking for dead-end islands of size greater than 4 may not increase the efficiency either).
Anyway, I hope that at this point I have you convinced that a brute force algorithm should have no problem at all covering the whole search space. I truly think a brute force algorithm that checks for islands of size less than 4 will complete the search in a fraction of a second. But even without any further intelligence at all, I believe a totally dumb brute force algorithm will already be able to check for uniqueness in a fairly short time.
One final thought. Near the end of the video, you'll see that for some of the puzzles only one white piece is placed on the board. Now, having only one white piece would obviously increase the number of ways to place individual pieces significantly, and a brute force algorithm would slow down considerably. However, it actually confirms a suspicion I have: with this board and puzzle pieces, there are probably a fairly limited number of solutions to place all pieces in the board, period.
That is, even without any white wall pieces placed on the board at all, I bet that the number of solutions is fairly small (maybe a couple of hundred?). Thus, if you just brute force and get a complete list of all those completely unconstrained solutions (and you have to do this just once), then creating any new puzzle would be a snap: place some white pieces, and go through your already created list of unconstrained solutions to see if there is exactly one solution from that list that is compatible with the placed white pieces. This would probably take the time to verify that some set-up has a unique solution down to less than 1 microsecond.