Raul Miller wrote: > I would be interested in knowing some sizes of your intermediate > data structures. > > For example, after pruning, how many initial possibilities do > you have, for each piece? (And, if you could characterize > similar information for each subsequent step in f, that > might also be interesting.) > > I don't know that I have any useful suggestions, but I also don't > know any details about what your code is already doing -- and > these numbers might tell me if you have covered the ground I > am familiar with. > In the table below, the (i,j)th entry is the number of pieces of shape j whose first cell is i, for i in i.10.
5 5 3 5 5 5 4 4 6 5 8 8 10 8 8 10 8 12 8 8 7 10 11 11 12 12 11 12 7 9 6 8 7 8 8 7 8 6 7 8 4 3 3 4 3 4 5 2 4 4 7 8 8 6 6 8 8 8 6 8 8 11 10 10 11 11 9 12 7 10 6 9 10 11 11 10 10 10 8 9 6 4 5 6 6 7 8 6 7 5 3 2 1 3 2 2 1 0 4 2 If a board had i as its first empty cell, I would extend it by all the pieces in row i, minus the columns corresponding to pieces already used. As you can see, this severely limits the possibilities: the total number of configurations of pieces of each type is 208 254 258 274 274 298 272 284 220 254 and considering all legal positions obtained by adding one more piece is prohibitive. Using breadth first search, I get the following: 1 47 955 7568 25196 96243 306466 875160 1268130 514304 2098 Here item i indicates the number of boards I am considering with i pieces. If I do it depth first, the maximum stack depth is 221. These numbers are tantalizingly small, and I hope to do considerably better in time than I am doing now. It would help if I could get jpm to work in 64-bit Linux. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
