Algorithm for solving 3d puzzle

I guess the no-homework policy would apply to this thread. Anyway, just start with a simple depth-first search. If you write it right it should be fast enough and you won't need fancy algorithms.

This is an interesting problem.

The key here seems to be that due to the various orientations and positions of the blocks, a depth first search might take very long....yeah, looking at the possible positions its pretty nasty.

I guess I shouldn't give you the whole genetic algorithm solution, but here are a few tips to help you on your way.

1. You probably don't need to use a binary coded GA. Since you have a fixed number of blocks, your chromosome or candidate solution will just be a combination of the blocks in a certain combination of orientations/positions.

2. Your fitness function can simply be, given a combination of block orientations, how many cubes overlap and how many stick out of the 4x4x4 boundary. The goal of course is to reduce it to 0.

3. Mutation should be pretty straight forward as you can simply randomly choose an orientation for a block.

4. Crossover shouldn't be tough once you get the above stuff to fall into place.

5. Remember, these are only ideas, you may need to hack them a bit as you learn more about the problem.

As for other approaches, there is one that comes to mind. You can read up on Tabu Search. Using the same fitness as above, you can probably get tabu search to work. You might even try simulated annealing too.

Just another tip, don't be afraid to hybridize. Good hybrid algorithms may sometimes work better than the original.

There are too many combinations for a depth first search. I'll give the genetic algorithm a try. Thanks for the help.

A suggestion:
I think Depth First Search might be quite feasible, you just need to make it clever about optimizations.

You may have opportunities to Early Out Reject on many of the Depth Search branches.
For example.... if the placement of a new piece 'cuts off' an empty cube by itself (so it is surrounded by either walls or filled spaces), this configuration must be bad since there will never be a way to fill in that empty space. -this idea can be extended, so instead of finding a 'island' of a single empty cube, also watch for clusters of empty cubes that are smaller than the smallest available piece. (in terms of bounding dimensions)

I'd also, when Depth Searching, Only search positions for new pieces where they are Touching previous pieces. That should lower the possible branches by quite a lot! It does not exclude the search from visiting all possible Valid configurations, its just a nice way to help avoid repeating yourself. Plus checking configs where the new piece touches the previous ones also increases the chances of finding the above mentioned 'cut off' empty cubes.

Doing both of those at once makes the search more similar to what a human (me) would do when solving the puzzle - new peices contact old ones and 'islands' of empty space are avoided; so you basically try and Fill In space as compactly as possible.
If you want, you could even add in a 'gravity' effect when placing new pieces (first piece must touch bottom of cube, later peices must rest on previous ones), that should help cull the branches even more, and help to eliminate Symmetryies in the search (reduced to 1/6 the size I'd bet).
-hey if that approach works for a human... why not for the program as well?

Actually, what you guys are referring to is not exactly depth first search, its more like Backtracking search used for constraint satisfaction problems. It is not hard to implement as the origianl purpose was to cut down on futile branching. However, you still run into massive thrashing problems.

For example, after placing the 4th piece successfully, you start placing the 5th, but you iterate through all the possible positions and orientations of possible 5th pieces and find that nothing works, because of possible contraint violations down the line. So, you back track and replace the 4th piece. However, in reality, the problem may be that the 2nd piece wasn't right in the first place. But to realise that, the search must go through all possible 3rd, 4th and 5th piece combinations or more before coming back to change the second piece. So, in the current problem, if we've put in piece0 first, then piece1 second, and piece1 is in the wrong position, you won't know till you try combinations of the rest of the 10 pieces. So, assume that 3 more pieces is as far as the search goes before backtracking to change the second piece, you're still searching at least 192x48x216 possibilities and thats a minimum.

Probably the better way, if you really want to use backtracking style searches, is to use a weak-commitment search, which performs 2 - 10 times better than the best backtracking. But based on the size of the search space, that's still gonna take pretty long.

Sorry, I've sort of rambled on, but just wanted to point out the real downside to using backtracking style searches, since we are lookin at a search space of about 10^38 and pruning can only really go so far.

This is an NP-complete problem, so even in the best case it will not be very efficient. It is an example of the "3D bin packing problem" for arbitrary solids.

I would use backtracking with two improvements:
- Place the cross-shaped piece first, since it can only be put in essentially two places, and this will take care of all the symmetries in the solutions. Actually, I would consider these two options as separate puzzles and solve them separatelly.
- Divide the remaining 12 pieces in two groups of size k and 12-k. With the first group, generate all possible arrangements of the k pieces and store them in a fast data structure (a hash table is a good one to start with, which in many C++ compilers' STL implementations is provided as hash_set'). All you need to store is a 64-bit pattern of what blocks are occupied, and remember that you can't use the five cubes used by the cross-shaped piece. Now start with an empty cube again and use backtracking to find all arrangements of the 12-k pieces. At the end of the search, check your data structure to see if the remaining spaces can be filled exactly with the other k pieces. Set k to 5 or 6 if your memory can take it.

The idea of checking for isolated sections that can't possibly be filled with pieces (e.g., isolated single cubes) is probably too expensive to check. The idea of only placing pieces touching already-placed pieces is not going to reduce the branching factor much for this problem (the space to be filled is too small) and using a pre-established order for the pieces is probably faster.

Using the dancing-links idea that Knuth describes in his article is just a very smart implementation trick on backtracking, and it might be too much of a pain to implement, but you can try. It probably is faster.

Oh, and for the name depth-first search', this is exactly what this search is, if you consider the acyclic directed graph whose nodes are arrangements of a subset of the pieces and whose links represent the placement of an additional piece.

Quote:

I wouldn't really call this artificial intelligence but more like a really nice optimization trick, if you can get it to work.

I wouldn't call it AI either. I am just trying to solve a problem here, and I don't particularly care if you can call it AI or not.

Do you consider computer chess to be AI? A very similar trick is used there; databases are generated with all the exact scores for positions with only a few pieces left, and then they are queried during the search, whenever one of the branches happens to fall into a known endgame.

Quote:

Original post by alvaro I would use backtracking with two improvements: - Place the cross-shaped piece first, since it can only be put in essentially two places, and this will take care of all the symmetries in the solutions. Actually, I would consider these two options as separate puzzles and solve them separatelly. - Divide the remaining 12 pieces in two groups of size k and 12-k. With the first group, generate all possible arrangements of the k pieces and store them in a fast data structure (a hash table is a good one to start with, which in many C++ compilers' STL implementations is provided as hash_set'). All you need to store is a 64-bit pattern of what blocks are occupied, and remember that you can't use the five cubes used by the cross-shaped piece. Now start with an empty cube again and use backtracking to find all arrangements of the 12-k pieces. At the end of the search, check your data structure to see if the remaining spaces can be filled exactly with the other k pieces. Set k to 5 or 6 if your memory can take it. The idea of checking for isolated sections that can't possibly be filled with pieces (e.g., isolated single cubes) is probably too expensive to check. The idea of only placing pieces touching already-placed pieces is not going to reduce the branching factor much for this problem (the space to be filled is too small) and using a pre-established order for the pieces is probably faster. Using the dancing-links idea that Knuth describes in his article is just a very smart implementation trick on backtracking, and it might be too much of a pain to implement, but you can try. It probably is faster. Oh, and for the name depth-first search', this is exactly what this search is, if you consider the acyclic directed graph whose nodes are arrangements of a subset of the pieces and whose links represent the placement of an additional piece.

Its a nice idea, but then consider the space complexity involved. I'm not even sure if you can set your k to 3 or 4. Given the current problem, say we group the first 3 pieces together and generate all the possible combinations, which is 432x216x432 and then 64-bit entries, that's 8 bytes per entry. So, the required space would be 322,486,272 bytes, or about 307.5MB. Through in another piece and you'll be clear into the multi-GB region. Even if you store only the feasible ones, you'll still need to check 40 million entries and optimistically if only 1% are feasible, storing all combinations of 4 pieces would still require close to a GB of memory. The only possible implementation for this I can think of is dump everything to file then use the windows filemapping feature to map the whole file into virtual memory and then let the OS worry about the address paging.

Well, I wouldn't exactly say its not AI. In a sense it is because the field of AI involves all sorts of search algorithms, including depth first search. The key is the heuristic that's used to prune the possibility.

Quote:

Original post by WeirdoFu Its a nice idea, but then consider the space complexity involved. I'm not even sure if you can set your k to 3 or 4. Given the current problem, say we group the first 3 pieces together and generate all the possible combinations, which is 432x216x432 and then 64-bit entries, that's 8 bytes per entry. So, the required space would be 322,486,272 bytes, or about 307.5MB. Through in another piece and you'll be clear into the multi-GB region. Even if you store only the feasible ones, you'll still need to check 40 million entries and optimistically if only 1% are feasible, storing all combinations of 4 pieces would still require close to a GB of memory. The only possible implementation for this I can think of is dump everything to file then use the windows filemapping feature to map the whole file into virtual memory and then let the OS worry about the address paging.

I hadn't made any computations on how big the table would have to be. There are some tricks by which you can save some space. For instance, you could divide the data in 65536 data structures, indexing with the first two bytes. Those data structures now only have to contain 6 bytes per entry. In any case, there are more combinations than I had originally thought. 3 pieces is workable and 4 might be possible with a lot of RAM and effort (1 GB of RAM is fairly standard these days, and 4 is not unheard of).

Quote:

Original post by alvaro Quote: I wouldn't really call this artificial intelligence but more like a really nice optimization trick, if you can get it to work. I wouldn't call it AI either. I am just trying to solve a problem here, and I don't particularly care if you can call it AI or not. Do you consider computer chess to be AI? A very similar trick is used there; databases are generated with all the exact scores for positions with only a few pieces left, and then they are queried during the search, whenever one of the branches happens to fall into a known endgame.

I think the key word here is search. If the solution uses a search, it's AI. On the other hand, it is often said that once we solve an AI problem, it's not AI anymore. ...Maybe AI is in the eye of the beholder.

This is a problem that falls clearly within the realms of constraint satisfaction problems, which are a popular area of AI research. I would suggest that MILP (Mixed Integer Linear Programming) would be a good tool to tackle your problem. You'll find plenty of free software and literature for MILP on the web.

Good luck with it. 8)

Timkin

Quote:

Original post by Anonymous Poster Give simulated annealing a try. I think you will find it easier to implement than a GA. There should be plenty of papers available to point you in the right direction. I remember a lecture given by Rob Rutenbar @ CMU where they had a video of one of their place and route systems solving the exact problem you describe.

Yup, simulated annealing will be much easier to implement, considering its nothing more than a probabilistic hill climber. And of course, like every other probabilistic hill climber, you run into the nasty cooling schedule issue. What most research on simulated annealingdon't show half the time is all the various cooling schedules that are tested before they hit on one that does better. Of course, its the same with GAs as well. So, in the end, you win some and you lose some. It all boils down to heuristics, parameter settings, and the various choices you make during implementation. The crazy world of optimization.

Heck, even hill climbers have various issues involved, like do we do probabilistic restarts or do we do min conflict or something else.