That was joke? I never heard of any dancing links :)
the algorithm in more detail
let the grid by n rows m columns
covered[n][m]=0
go(x,y) {
if(y==n) return 1;
if(x==m) return go(0,y+1);
if(covered[y][x]) return go(x+1,y);
now consider all rotations of all remaining pentominoes.
Each have unique top most and then leftmost pixel. {
try if pentomino does not intersects with cowered array
if(no) {
fill covered
remove pentomino from remainning set
return value+=go(x+1,y);
undo steps above
//maybe here is possibility to increase algorithm speed by using
some links to next uncovered tiles
}
move consideration to next type of pentomin
}
}
public static int main(wtf ...) {
go(0,0);
}
there is one to one corespondency between solutions and vectors of subsets
of permutations of used pentominos+rotations, and the algorithm never
generates the same vector twice
On Wed, Nov 26, 2008 at 9:27 PM, Geoffrey Summerhayes <[EMAIL PROTECTED]>wrote:
>
> On Nov 26, 1:40 pm, "Miroslav Balaz" <[EMAIL PROTECTED]> wrote:
> >
> > It is too slow, i replied with better solution , bu i dont know how this
> > forum works.
> >
>
> I was looking for comments on correctness, not efficency.
> As I said, it can be improved. By quite a bit, actually.
>
> As for your 'better solution', if you are referring to the one
> paragraph blurb on row-major order, there's not enough
> information there to judge what your algorithm would look
> like in the end, let alone judge speed in comparison.
>
> Personally, I'd probably replace the cover function with Knuth's
> dancing links algorithm.
>
> ----
> Geoff
>
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
