Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

Re: Re: Pentominos Solver

by Lexicon (Chaplain)
on Sep 13, 2002 at 17:15 UTC ( #197662=note: print w/replies, xml ) Need Help??

in reply to Re: Pentominos Solver
in thread Pentominos Solver

The board is already kinda unidirectional, albeit in a hacked way. I figure the problem is already either optimally solved or runnable a couple orders of magnatude faster than my code, but researching it would take longer than writing my code, and it just wasn't that important of a project (although I am a math major, and would easily be distracted into researching that as it's own project :). Anyway, here are the three heuristics I used:
# If piece is efficiently placed, try the next pentomino # (tend to cluster them towards origin) if (!exceeds_hole_count($index)) { solve ($index+1); }
There are 9 holes in pentominos (I assume that's the mythical 12'th pentomino that you refer to). Clearly we better leave holes sparingly. The exact forumula relates the indexth of the pentomino to the indexth diagonal, namely that there are less than or equal to index holes up to and including the indexth diag.
($x, $y) = next_position_accross ( $x, $y ); # if the pentomino has run off the board, backup # and try again. (n_p_a returns (-1,-1) in this case if ($x < 0) { return } $SOLVE_COUNT++; # Start the piece well out onto the board if (($x+$y) < $index) { next };
A pentomino need never be in a diagonal less than it's index. Pentomino 1 starts in diagonal 2, for instance.
# Optimization by which piece never starts too far out on board. if (($x+$y) > (2*$index)) { print 'b'; next }; if ($y > $index) { print 'y'; return }; last;
And we keep them close to home in two ways. First, they need to stay within a radius of twice their index, and second they need never exceed the indexth row. This somewhat prevents reflection across the x-y plane. And now that I've thought about it some more, I have a glimmering of a far more elegant way to capture all that. But that's allright, I have other projects to work on. Back to your post, Regexps would have been super elegant. I'm off to check it out presently. Thanks!

Replies are listed 'Best First'.
Re: Re: Re: Pentominos Solver
by stefp (Vicar) on Sep 13, 2002 at 20:52 UTC
    A math major should know how to search the litterature. especially when the references are spelled out.
    12 pentominoes and a solved 3x20. Straight out from my obfuscation.
    xxxxx x xxx x xx x xx XX XXX x xxx x x xxxx xx xx x xxx x x x xxx x xx xxx xxxx x x x xxx _________________________________________________________ | __| |____________| |__ |___ ___| |________ | | | |__ ___| | _____| |__ | | ______| __|__| | |_____|__|_______|__|_________|__|__|__|________|________|

    -- stefp -- check out TeXmacs wiki

      Sometimes it's just more fun to solve things yourself. It's not rocket science or network security.

      I mean, hell, do ya think I wrote the Poker Probability Processor because I thought that was an effecient way to solve things? Ha! :)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://197662]
[stevieb]: ...has honed in my skills of recognizing sound
[stevieb]: All of the early members are coming out of the woodwork today :) Hey, planetscape
[Corion]: This cover version had so much promise but the singing is underwhelming :-/
[stevieb]: erix Thanks! I dislike remakes of songs usually, but my favourite remix of guitar/weeps is Jeff Healey. I'll take a listen to yours
[planetscape]: hi stevieb!
[stonecolddevin]: also hi Corion
[Corion]: stevieb: Yeah, but I don't follow guitar players enough... I never got Prince and I don't think I could recognize his play style. I can recognize Santana and Nile Rodgers, but that's about it, and not really deep knowledge I think ;)
[stevieb]: Jeff Healey cut of My guitar gently weeps
[stonecolddevin]: you don't recognize Prince. Prince tells you it's him.
[erix]: Alvin Lee (Ten Years After) played a jazzguitar ("Big Red"), a good warm sound

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (6)
As of 2017-06-22 21:33 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (531 votes). Check out past polls.