Xref: utzoo sci.math:6585 comp.lang.prolog:1708 comp.ai:4047
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!amdahl!amdcad!crackle!prem
From: prem@crackle.amd.com (Prem Sobel)
Newsgroups: sci.math,comp.lang.prolog,comp.ai
Subject: Re: solving soma puzzles
Message-ID: <25492@amdcad.AMD.COM>
Date: 2 May 89 19:51:30 GMT
References: <336@edai.ed.ac.uk>
Sender: news@amdcad.AMD.COM
Reply-To: prem@crackle.amd.com (Prem Sobel)
Organization: Advanced Micro Devices, Inc. Sunnyvale CA
Lines: 48
Summary:
Expires:
Sender:
Followup-To:

In article <336@edai.ed.ac.uk> cam@edai.ed.ac.uk (Chris Malcolm) writes:
>I need fast methods of solving this kind of problem in a computer - I
>have a PROLOG program which does it, too slowly. [It is methods I'm
>interested in, not the relative virtues of programming languages].

At work some one had a 3x4x5 puzzle with 12 pieces of 5 cubies each. I started
to solve this by hand but it took me hours to get the first solution. When
I was told that there are 3940 solutions it was time for a computer
program.  It turns out that the pieces in this puzzle took the restriction
that one dimension of the three would always be one cubie thick.

The first approach was brute force: 12 pieces 24 orientations 60 positions
which is:

	(24*60)^12

combinations to try. This, takes much too long so had to add some more
intelligence to the program. The first step was add logic which removed
symmetries from the piece. For example the piece:

	##
	#
	##

has one axis of symmetry cutting the 24 orientations to 12, while the piece:

	 #
	###
	 #

has full symmetry and has only 3 orientations to try.

This was still not enough. The next step, observing how I solved the puzzle,
was to add logic to prune the search tree to eliminate placements which
create remaining holes either too small or unable to take any of the remaining
pieces. Any further, improvements to the program seemed to slow it down so
I stooped there. At this point it takes a SUN-4 28 minutes to get the first
solution and a 29000 with slow memory about 7 minutes.

If anyone is interested I can email them the program, it is fairly large
and is not the most commented C progarm I ever wrote, but it is bug free :)

By the way, it read a file which gives the shape descriptions. It is easy
to extend the program to change the size of the puzzle. It is slightly 
harder but not very to generalize it to take pieces which are not unit
thickness in one dimension.

Prem