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!
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.