Sage: Ticket #11379: Add Quantumino solver to sage/games
https://trac.sagemath.org/ticket/11379
<p>
Some code to solve the <a class="ext-link" href="http://familygamesamerica.com/mainsite/consumers/productview.php?pro_id=274&search=quantumino|"><span class="icon"></span>Quantumino Puzzle</a> (see also <a class="ext-link" href="http://www.youtube.com/watch?v=jX_VKzakZi8|"><span class="icon"></span>this video</a> on youtube).
</p>
<p>
<strong>Apply:</strong>
</p>
<ol><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11379/trac_11379_quantamino-sl.patch" title="Attachment 'trac_11379_quantamino-sl.patch' in Ticket #11379">trac_11379_quantamino-sl.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11379/trac_11379_quantamino-sl.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11379/trac_11379_corrections-sl-v2.patch" title="Attachment 'trac_11379_corrections-sl-v2.patch' in Ticket #11379">trac_11379_corrections-sl-v2.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11379/trac_11379_corrections-sl-v2.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11379/trac_11379_color_issue-sl.patch" title="Attachment 'trac_11379_color_issue-sl.patch' in Ticket #11379">trac_11379_color_issue-sl.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11379/trac_11379_color_issue-sl.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11379/trac_11379-reviewer-docs.patch" title="Attachment 'trac_11379-reviewer-docs.patch' in Ticket #11379">trac_11379-reviewer-docs.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11379/trac_11379-reviewer-docs.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11379/trac_11379_hole_bug-sl.patch" title="Attachment 'trac_11379_hole_bug-sl.patch' in Ticket #11379">trac_11379_hole_bug-sl.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11379/trac_11379_hole_bug-sl.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11379/trac_11379_2d_boundary-sl.patch" title="Attachment 'trac_11379_2d_boundary-sl.patch' in Ticket #11379">trac_11379_2d_boundary-sl.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11379/trac_11379_2d_boundary-sl.patch" title="Download"></a>
</li></ol>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11379
Trac 1.1.6rbeezerWed, 25 May 2011 20:02:38 GMT
https://trac.sagemath.org/ticket/11379#comment:1
https://trac.sagemath.org/ticket/11379#comment:1
<p>
I saw this demo'ed at Sage Days 30. It's really nice. I'll give the patch as look once it appears.
</p>
TicketslabbeWed, 25 May 2011 22:16:40 GMT
https://trac.sagemath.org/ticket/11379#comment:2
https://trac.sagemath.org/ticket/11379#comment:2
<p>
Just added the patch.
</p>
<p>
The file takes 80 seconds to test... so I still need to add some "long" doctest warnings...
</p>
<p>
Sébastien
</p>
TicketslabbeThu, 26 May 2011 20:03:40 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379_quantamino-sl.patch</em>
</li>
</ul>
TicketslabbeThu, 26 May 2011 20:03:56 GMTstatus changed
https://trac.sagemath.org/ticket/11379#comment:3
https://trac.sagemath.org/ticket/11379#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketslabbeThu, 26 May 2011 20:04:50 GMT
https://trac.sagemath.org/ticket/11379#comment:4
https://trac.sagemath.org/ticket/11379#comment:4
<p>
Takes now 17 seconds to test on my machine (35s with long test).
</p>
TicketrbeezerMon, 30 May 2011 05:00:36 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379-size-suggestion.patch</em>
</li>
</ul>
TicketrbeezerMon, 30 May 2011 05:03:54 GMTstatus changed
https://trac.sagemath.org/ticket/11379#comment:5
https://trac.sagemath.org/ticket/11379#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hi Sebastien,
</p>
<p>
Very nice - this is a lot of fun, and a great advertisement for the power of dancing links. Lots of little comments, I hope its not too much. Nothing very serious.
</p>
<ul><li> One doctest failure. I'm on 64-bit Linux - could 32-bit/64-bit be the cause?
<pre class="wiki">sage -t "devel/sage-main/sage/games/quantumino.py"
**********************************************************************
File "/sage/sage-4.7/devel/sage-main/sage/games/quantumino.py", line 193:
sage: hash(p)
Expected:
2059134902
Got:
6915256369230374838
**********************************************************************
</pre></li></ul><ul><li> Why does block number 8 (yellow) have a hole in the middle? See discussion below about <code>size</code>.
</li></ul><ul><li> Documentation looks good. I would have liked to see a bit more detail at the module level for a quickstart - more like for the <code>QuantuminoSolver</code> class-level documentation. Specifically:
<ul><li> Make it clearer that you will see the puzzle pieces in 3D with the <code></code>show_pentaminos()<code></code> command.
</li><li> Show how to get the list of the actual placements for a single solution. I wanted to do this once I had a solution since the <code>_repr_</code> was not as informative as my curiosity.
</li><li> Maybe a real quick overview of the classes: the pentamino and polyomino classes, the solution class, and the solver class.
</li></ul></li></ul><ul><li>I thought an interact would be fun. Checkboxes for the excluded piece, plus the ability to "explode" the solution via a slider. I'm <strong>not</strong> suggesting you write an interact, but a <code>size</code> argument as input to <code>show3d()</code> (for the solution) would make this possible. Patch attempts to do this, but it is not totally correct, at size below 0.50 the pieces start to fall apart into cubes. And the aside piece breaks up even earlier in my test. The hole in block number 8 behaves slightly differently. So as a suggestion: consider adding a <code>size</code> argument to pass from the solution <code>show3d()</code> down to each piece. But my patch is just a suggestion - it is not ready to use.
</li></ul><ul><li>Some of the lesser methods could use some improved documentation. In many cases, at least the first summary line, and/or the type of input. For example:
<ul><li>"Return the 3D polyomino defined by a set of 3d coordinates." It is not clear what "defined by" means here, maybe the coordinates are for the "bottommost" corner of each constituent cube.
</li><li>It is not clear what <span class="underline">sub</span> does without looking at the code. A one-line summary and an input list would be enough, I think.
</li></ul></li></ul><ul><li>I'm not sure upper-case is part of Python or Sage style for code. SPACE, COORD_TO_INT, and INT_TO_COORD look funny to my eye.
</li></ul><ul><li>I set up Sudoku puzzles with a "Sudoku" class. Then s = Sudoku(.....), followed by s.solve() gave an iterator over solutions. Would it be worth trying to mimic that approach for consistency? I'm not arguing that my approach was better - just first. <code>:-)</code>
</li></ul><p>
Minor editing
</p>
<ul><li>"needs to creates" should be "create"
</li><li>"where each pieces is used exactly once" should be "piece"
</li><li><code># Class QuantuminoSolultion</code> (misspelled in comment)
</li><li>I think even with the utf-8 header the consensus (rule?) has been straight ASCII in source files? Which I know even impacts your name. I wish it wasn't this way (maybe I'm wrong?). The trademark symmbol and bracketing on "think inside the box" for the game description would need adjustments.
</li><li> <code>#bug trac #11272</code> - can this go away?
</li><li> <code>#return G</code> (twice) - can these go away?
</li></ul><p>
As I said, lots of little stuff, which I hope does not look like too long a list. I've tried to keep it to suggestions so you have the latitude to approach it as you see fit. I'll be happy to stick with this review as you make revisions.
</p>
<p>
Rob
</p>
TicketrbeezerMon, 30 May 2011 05:07:43 GMT
https://trac.sagemath.org/ticket/11379#comment:6
https://trac.sagemath.org/ticket/11379#comment:6
<p>
One more comment I forgot:
</p>
<pre class="wiki">ss=quantumino_solver.get_solution(7, box=(3,3,9))
</pre><p>
seems to totally hang on my system - not even a Ctrl-C gets it back. Do I need to use a box of exactly volume 80? Was it unreasonable to expect a different result?
</p>
TicketslabbeWed, 01 Jun 2011 16:56:31 GMT
https://trac.sagemath.org/ticket/11379#comment:7
https://trac.sagemath.org/ticket/11379#comment:7
<p>
Hi Rob,
</p>
<p>
Thanks a lot for your good review. I almost done making the corrections. I also added a class Tiling Solver which replaces the puzzle solver function. This allows for more introspection (for instance looking at the rows passed to the DLX solver) and also comptute the number of solutions more efficiently. I have one question about your suggestion :
</p>
<blockquote class="citation">
<ul><li>I thought an interact would be fun. Checkboxes for the excluded piece, plus the ability to "explode" the solution via a slider. I'm <strong>not</strong> suggesting you write an interact, but a <code>size</code> argument as input to <code>show3d()</code> (for the solution) would make this possible. Patch attempts to do this, but it is not totally correct, at size below 0.50 the pieces start to fall apart into cubes. And the aside piece breaks up even earlier in my test. The hole in block number 8 behaves slightly differently. So as a suggestion: consider adding a <code>size</code> argument to pass from the solution <code>show3d()</code> down to each piece. But my patch is just a suggestion - it is not ready to use.
</li></ul></blockquote>
<p>
I don't understand what is meant by ""explode" the solution". Is this a slider which would bring the size of the cube from 0 to 1 ? It doesn't not seem that nice to me. I would rather suggest a slider which would go from one solution to the other, where we would see the pieces that are removed and added, etc. Or maybe even an animation of it. I am almost done doing it: I have the iterator of partial solutions. I only need to know how to make a Jmol animation of 3D Graphics object or maybe an animation of Tachyon images.
</p>
<p>
Sébastien
</p>
TicketslabbeWed, 01 Jun 2011 19:42:48 GMTdescription changed
https://trac.sagemath.org/ticket/11379#comment:8
https://trac.sagemath.org/ticket/11379#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=8">diff</a>)
</li>
</ul>
TicketslabbeWed, 01 Jun 2011 19:46:43 GMTstatus changed
https://trac.sagemath.org/ticket/11379#comment:9
https://trac.sagemath.org/ticket/11379#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<blockquote class="citation">
<p>
I don't understand what is meant by ""explode" the solution".
</p>
</blockquote>
<p>
Ok, now I understand. I needed to try it ! It is true that it helps to change the size of the small cubes. Because of conflicts, I had to reload your patch (but could not erase yours) so I renamed it. Hence, your patch apply over my second patch.
</p>
<p>
I think I was able to answer all of your comments. Needs review!
</p>
<p>
Sébastien
</p>
TicketslabbeWed, 01 Jun 2011 19:49:17 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379-size-suggestion-updated.patch</em>
</li>
</ul>
<p>
Applies over the correction patch.
</p>
TicketrbeezerThu, 02 Jun 2011 02:47:37 GMT
https://trac.sagemath.org/ticket/11379#comment:10
https://trac.sagemath.org/ticket/11379#comment:10
<p>
I had a bit of time to look through the patch. Looks great! I still need to do a thorough test of the new features and all, so will try to get to that soon.
</p>
<p>
Would Franco let you bring the real physical puzzle to Seattle for SD 31?
</p>
<p>
Rob
</p>
TicketslabbeThu, 02 Jun 2011 18:19:50 GMT
https://trac.sagemath.org/ticket/11379#comment:11
https://trac.sagemath.org/ticket/11379#comment:11
<blockquote class="citation">
<p>
Would Franco let you bring the real physical puzzle to Seattle for SD 31?
</p>
</blockquote>
<p>
Sure! I'll ask. And will try not to forget it!
</p>
<p>
Sébastien
</p>
TicketmariahFri, 03 Jun 2011 17:44:48 GMTcomponent changed
https://trac.sagemath.org/ticket/11379#comment:12
https://trac.sagemath.org/ticket/11379#comment:12
<ul>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>misc</em>
</li>
</ul>
TicketslabbeTue, 14 Jun 2011 08:21:14 GMTstatus changed
https://trac.sagemath.org/ticket/11379#comment:13
https://trac.sagemath.org/ticket/11379#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I have been working on it again yesterday. I will update the patches again quite soon. Do not review until then.
</p>
<p>
Sebastien
</p>
TicketrbeezerTue, 14 Jun 2011 15:48:59 GMTdescription changed; keywords, reviewer set
https://trac.sagemath.org/ticket/11379#comment:14
https://trac.sagemath.org/ticket/11379#comment:14
<ul>
<li><strong>keywords</strong>
<em>sd31</em> added
</li>
<li><strong>reviewer</strong>
set to <em>Rob Beezer</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=14">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11379#comment:13" title="Comment 13">slabbe</a>:
</p>
<blockquote class="citation">
<p>
I have been working on it again yesterday. I will update the patches again quite soon. Do not review until then.
</p>
</blockquote>
<p>
Thanks - ready whenever you are (I think!).
</p>
TicketslabbeWed, 15 Jun 2011 00:35:21 GMT
https://trac.sagemath.org/ticket/11379#comment:15
https://trac.sagemath.org/ticket/11379#comment:15
<p>
Great. So I will upload the patches later tonight! I still have some cleaning to make.
</p>
TicketslabbeWed, 15 Jun 2011 09:42:28 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379_corrections-sl.patch</em>
</li>
</ul>
<p>
Applies over my first patch
</p>
TicketslabbeWed, 15 Jun 2011 10:00:42 GMTstatus, description, summary changed
https://trac.sagemath.org/ticket/11379#comment:16
https://trac.sagemath.org/ticket/11379#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=16">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Add Quantamino solver to sage/games</em> to <em>Add Quantumino solver to sage/games</em>
</li>
</ul>
<p>
Ok, so I just re-uploaded the correction patch. The size suggestion patch as been folded into that correction patch. So only two patches are needed to be applied (the one that has already been reviewed and the correction patch).
</p>
<p>
So, compared to what has already been reviewed, I did a bunch of improvements: I created a new file <code>sage/combinat/tiling.py</code> and moved the polyomino class into it. Also, I created a new class called <code>TilingSolver</code> which solves the general problem of Tiling a box by polyomino. This class replaces the old function <code>general_puzzle_solver</code> which I might misspell. The <code>TilingSolver</code> class allows to do more introspection like getting the rows passed to the DLX solver and count them. One can also get the DLX Solver. I managed to write the <code>Polyomino</code> and <code>TilingSolver</code> abstract enough so that they can be defined in any dimension. Ploting works when the dimension is 2 or 3. I also added parameters to allow (or not) reflections and rotations and whether the pieces can be reused or not.
</p>
<p>
There is still one issue mentionned in the review that I did not fixed. The holes in the polyomino. Maybe tomorrow we can think about a efficient way to fix this?
</p>
<p>
Question: Should I use Pentomino like Donald Knuth does or Pentamino like the game Quantumino calls the pieces? Which is best?
</p>
<p>
Good night!
</p>
TicketslabbeWed, 15 Jun 2011 15:37:04 GMTdescription changed
https://trac.sagemath.org/ticket/11379#comment:17
https://trac.sagemath.org/ticket/11379#comment:17
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=17">diff</a>)
</li>
</ul>
TicketslabbeWed, 15 Jun 2011 16:40:05 GMTdescription changed
https://trac.sagemath.org/ticket/11379#comment:18
https://trac.sagemath.org/ticket/11379#comment:18
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=18">diff</a>)
</li>
</ul>
<p>
In a new patch I just uploaded which applies on top of two others, I fixed a color issue for when pieces are reusable. Sorry, I had the idea for the fix when I woke up. Now, I stop working on it!
</p>
TicketslabbeThu, 16 Jun 2011 01:15:41 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379_color_issue-sl.patch</em>
</li>
</ul>
<p>
Applies over the correction patch.
</p>
TicketslabbeThu, 16 Jun 2011 01:17:12 GMT
https://trac.sagemath.org/ticket/11379#comment:19
https://trac.sagemath.org/ticket/11379#comment:19
<p>
Ok, so I can't stop working on it apparently. I added the possibility of making an animation. I also fixed the problem that showed up during my quick demo.
</p>
<p>
Needs review!
</p>
TicketrbeezerMon, 11 Jul 2011 03:24:36 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379-reviewer-docs.patch</em>
</li>
</ul>
TicketrbeezerMon, 11 Jul 2011 03:26:39 GMTdescription changed
https://trac.sagemath.org/ticket/11379#comment:20
https://trac.sagemath.org/ticket/11379#comment:20
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=20">diff</a>)
</li>
</ul>
<p>
Sebastien,
</p>
<p>
Sorry to be so tardy on this one. Really just one "issue" that I think needs attention.
</p>
<p>
Made a reviewer patch: Changed some module and class links in documentation to be active, fixed a couple minor English language things. Do <strong>not</strong> list me as an author for these.
</p>
<p>
The animations are great. Can you do something to mark the end (like a few blank frames, for maybe a half-second)? It goes so fast, it is hard to tell where the start is and where the end is.
</p>
<p>
Related Questions:
</p>
<ol><li> Pentamino 8 (a yellow one) still has a hole in it. Not a big deal, but perhaps a symptom of something that should be done more carefully?
</li><li> I feel bad to bring this up, since I suggested it. The "size" parameter works fine for 0.5 < size < 1.0. Proably size > 1.0 should raise an error. Below size=0.5 the puzzle pieces seem to break into lots of individual cubes. Also the hole in piece 8 seems to change according to size. So I wonder if these first two items are related.
</li><li> In the 3D puzzle in the tiling module documentation, there are again holes in the pieces.
</li><li> Maybe each cube of a piece needs to be shrunk and translated, relative to some anchor point (the "corner" closest to the origin?). I have not looked carefully enough to know if this what needs to be done.
</li></ol><p>
Rob
</p>
TicketslabbeTue, 19 Jul 2011 17:30:11 GMTstatus changed
https://trac.sagemath.org/ticket/11379#comment:21
https://trac.sagemath.org/ticket/11379#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hi Rob,
</p>
<blockquote class="citation">
<p>
Sorry to be so tardy on this one. Really just one "issue" that I think needs attention.
</p>
</blockquote>
<p>
No problem!
</p>
<blockquote class="citation">
<p>
Made a reviewer patch: Changed some module and class links in documentation to be active, fixed a couple minor English language things. Do <strong>not</strong> list me as an author for these.
</p>
</blockquote>
<p>
Good, thanks for those fixes! Is there a problem with one of the fixes ? Because there is a symbol tilde <code>~</code> that appears in front of one of the class path.
</p>
<pre class="wiki">:class:`~sage.combinat.tiling.TilingSolver`
</pre><blockquote class="citation">
<p>
The animations are great. Can you do something to mark the end (like a few blank frames, for maybe a half-second)? It goes so fast, it is hard to tell where the start is and where the end is.
</p>
</blockquote>
<p>
The delay between frames and the number of iterations are arguments of the method show (see <code>animate??</code>). I would keep the animation function as is, but add an exemple in the doctest of how to change those parameters and add blank frames at the end. What do you think?
</p>
<blockquote class="citation">
<ol><li> Pentamino 8 (a yellow one) still has a hole in it. Not a big deal, but perhaps a symptom of something that should be done more carefully?
</li></ol></blockquote>
<p>
Ok. I will think about it. Let me find a solution which will be better than the "cube in the middle" I am using up to now. Maybe using Simplicial Complexes of cubes, I could get the exact boundary of the piece? I take a look at it and comes back with a fix soon.
</p>
<p>
Sébastien
</p>
TicketrbeezerTue, 19 Jul 2011 17:54:12 GMT
https://trac.sagemath.org/ticket/11379#comment:22
https://trac.sagemath.org/ticket/11379#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11379#comment:21" title="Comment 21">slabbe</a>:
</p>
<blockquote class="citation">
<p>
No problem!
</p>
</blockquote>
<p>
Good. We just need to finish this before you become a father. ;-)
</p>
<pre class="wiki">:class:`~sage.combinat.tiling.TilingSolver`
</pre><p>
The tilde should suppress the <code>sage.combinat.tiling</code> prefix in the output. Don't remember just why I did it that way there (I'm sure I had a reason at the time!) - but you should feel free to adjust it if you would rather have the fully-qualified name.
</p>
<blockquote class="citation">
<p>
The delay between frames and the number of iterations are arguments of the method show (see <code>animate??</code>). I would keep the animation function as is, but add an exemple in the doctest of how to change those parameters and add blank frames at the end. What do you think?
</p>
</blockquote>
<p>
Perfect.
</p>
<blockquote class="citation">
<p>
Ok. I will think about it. Let me find a solution which will be better than the "cube in the middle" I am using up to now. Maybe using Simplicial Complexes of cubes, I could get the exact boundary of the piece? I take a look at it and comes back with a fix soon.
</p>
</blockquote>
<p>
Maybe if each piece had a center, or maybe a center of a bounding box, or something like that. Then you could shrink into the center. Seems like you work off a corner right now, but again, I have not studied it very carefully. If the size parameter becomes too much trouble, feel free to drop it, but I think fixing this will fix a variety of other things, like the hole in piece 8.
</p>
TicketslabbeWed, 20 Jul 2011 18:32:07 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379_hole_bug-sl.patch</em>
</li>
</ul>
<p>
Applies over the precedent patches.
</p>
TicketslabbeWed, 20 Jul 2011 19:06:17 GMTstatus changed; author set
https://trac.sagemath.org/ticket/11379#comment:23
https://trac.sagemath.org/ticket/11379#comment:23
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Sébastien Labbé</em>
</li>
</ul>
<p>
I just uploaded a new patch which applies over the precedent ones.
</p>
<blockquote class="citation">
<p>
The animations are great. Can you do something to mark the end (like a few blank frames, for maybe a half-second)? It goes so fast, it is hard to tell where the start is and where the end is.
</p>
</blockquote>
<p>
I added a paragraph saying (copied from the animate doc string) :
</p>
<pre class="wiki"> The ``show`` function takes arguments to specify the delay between
frames (measured in hundredths of a second, default value 20) and
the number of iterations (default value 0, which means to iterate
forever). To iterate 4 times with half a second between each frame::
sage: a.show(delay=50, iterations=4) # optional
</pre><p>
I also fixed the methods <code>dlx_common_prefix_solutions</code> and <code>dlx_incremental_solutions</code> which were broken. That was maybe the reason why the animations were going so fast... So now, the following animation looks better and not too fast even with default parameters of the method show :
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> <span class="kn">from</span> <span class="nn">sage.combinat.tiling</span> <span class="kn">import</span> Polyomino<span class="p">,</span> TilingSolver
sage<span class="p">:</span> y <span class="o">=</span> Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">2</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">3</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">2</span><span class="p">,</span><span class="mi">1</span><span class="p">)],</span> color<span class="o">=</span><span class="s">'cyan'</span><span class="p">)</span>
sage<span class="p">:</span> T <span class="o">=</span> TilingSolver<span class="p">([</span>y<span class="p">],</span> box<span class="o">=</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">10</span><span class="p">),</span> reusable<span class="o">=</span><span class="bp">True</span><span class="p">,</span> reflection<span class="o">=</span><span class="bp">True</span><span class="p">)</span>
sage<span class="p">:</span> a <span class="o">=</span> T<span class="o">.</span>animate<span class="p">(</span><span class="s">'incremental'</span><span class="p">)</span>
sage<span class="p">:</span> a
Animation <span class="k">with</span> <span class="mi">123</span> frames
sage<span class="p">:</span> a<span class="o">.</span>show<span class="p">()</span>
</pre></div></div><blockquote class="citation">
<ol><li> Maybe each cube of a piece needs to be shrunk and translated, relative to some anchor point (the "corner" closest to the origin?).
</li></ol></blockquote>
<p>
Ok. So I implemented this solution (translation to origin, shrinked, translated back) and changed show2d and show3d methods accordingly. For the Quantumino, it looks great. The yellow pentamino number 8 do not have a hole anymore :
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> <span class="kn">from</span> <span class="nn">sage.games.quantumino</span> <span class="kn">import</span> show_pentaminos
sage<span class="p">:</span> show_pentaminos<span class="p">()</span>
</pre></div></div><p>
Also, using size<0.5 does not create disconnected cubes :
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> <span class="kn">from</span> <span class="nn">sage.games.quantumino</span> <span class="kn">import</span> QuantuminoSolver
sage<span class="p">:</span> s <span class="o">=</span> QuantuminoSolver<span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="o">.</span>solve<span class="p">()</span><span class="o">.</span>next<span class="p">()</span>
sage<span class="p">:</span> s<span class="o">.</span>show3d<span class="p">(</span>size<span class="o">=</span><span class="mf">0.3</span><span class="p">)</span>
</pre></div></div><p>
Although, I can not say that the proposed solution is perfect and always better than the precedent one. In the example below, there are no holes anymore which is good. But, the space between each piece is not uniform and it is even hard to find a size which will avoid the pieces to touch each other without being to far from each other:
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> <span class="kn">from</span> <span class="nn">sage.combinat.tiling</span> <span class="kn">import</span> Polyomino<span class="p">,</span> TilingSolver
sage<span class="p">:</span> L <span class="o">=</span> <span class="p">[]</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)]))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)]))</span>
sage<span class="p">:</span> T <span class="o">=</span> TilingSolver<span class="p">(</span>L<span class="p">,</span> <span class="p">(</span><span class="mi">8</span><span class="p">,</span><span class="mi">8</span><span class="p">),</span> reflection<span class="o">=</span><span class="bp">True</span><span class="p">)</span>
sage<span class="p">:</span> solution <span class="o">=</span> T<span class="o">.</span>solve<span class="p">()</span><span class="o">.</span>next<span class="p">()</span>
sage<span class="p">:</span> G <span class="o">=</span> <span class="nb">sum</span><span class="p">([</span>piece<span class="o">.</span>show2d<span class="p">(</span>size<span class="o">=</span><span class="mf">0.85</span><span class="p">)</span> <span class="k">for</span> piece <span class="ow">in</span> solution<span class="p">],</span> Graphics<span class="p">())</span>
sage<span class="p">:</span> G<span class="o">.</span>show<span class="p">(</span>aspect_ratio<span class="o">=</span><span class="mi">1</span><span class="p">)</span>
</pre></div></div><p>
What do you think?
</p>
<p>
Sébastien
</p>
TicketslabbeWed, 20 Jul 2011 19:07:24 GMTdescription changed
https://trac.sagemath.org/ticket/11379#comment:24
https://trac.sagemath.org/ticket/11379#comment:24
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=24">diff</a>)
</li>
</ul>
TicketslabbeWed, 20 Jul 2011 20:15:34 GMTdescription changed
https://trac.sagemath.org/ticket/11379#comment:25
https://trac.sagemath.org/ticket/11379#comment:25
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=25">diff</a>)
</li>
</ul>
<p>
I don't know how to speak to the buildbot. Maybe the commas between patches name are needed? I am trying.
</p>
<p>
More info is here : <a class="ext-link" href="http://wiki.sagemath.org/buildbot"><span class="icon"></span>http://wiki.sagemath.org/buildbot</a>
</p>
TicketslabbeWed, 20 Jul 2011 20:34:42 GMT
https://trac.sagemath.org/ticket/11379#comment:26
https://trac.sagemath.org/ticket/11379#comment:26
<p>
Or maybe the information must be put in a comment instead of above in the description :
</p>
<p>
For the patchbot:
</p>
<p>
Apply trac_11379_quantamino-sl.patch, trac_11379_corrections-sl.patch, trac_11379_color_issue-sl.patch, trac_11379-reviewer-docs.patch, trac_11379_hole_bug-sl.patch
</p>
TicketslabbeFri, 22 Jul 2011 17:46:00 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379_2d_boundary-sl.patch</em>
</li>
</ul>
<p>
Applies over the precedent patches.
</p>
TicketslabbeFri, 22 Jul 2011 17:48:59 GMTdescription changed
https://trac.sagemath.org/ticket/11379#comment:27
https://trac.sagemath.org/ticket/11379#comment:27
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=27">diff</a>)
</li>
</ul>
<p>
For the patchbot:
</p>
<p>
Apply trac_11379_quantamino-sl.patch, trac_11379_corrections-sl.patch, trac_11379_color_issue-sl.patch, trac_11379-reviewer-docs.patch, trac_11379_hole_bug-sl.patch, trac_11379_2d_boundary-sl.patch
</p>
TicketslabbeFri, 22 Jul 2011 18:01:27 GMT
https://trac.sagemath.org/ticket/11379#comment:28
https://trac.sagemath.org/ticket/11379#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11379#comment:23" title="Comment 23">slabbe</a>:
</p>
<blockquote class="citation">
<p>
Although, I can not say that the proposed solution is perfect and always better than the precedent one.
</p>
</blockquote>
<p>
I change the way to show 2d polyomino. First, I reverted its drawing as it was before. Second, I added a boundary line. Thirdly, I made the edge between adjacent points smaller than before. This way, holes are more esthetic and natural : we accept them more easily.
</p>
<p>
You can see the result with this example :
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> <span class="kn">from</span> <span class="nn">sage.combinat.tiling</span> <span class="kn">import</span> Polyomino<span class="p">,</span> TilingSolver
sage<span class="p">:</span> L <span class="o">=</span> <span class="p">[]</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)],</span> <span class="s">'yellow'</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)],</span> <span class="s">"black"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)],</span> <span class="s">"gray"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)],</span><span class="s">"cyan"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">)],</span><span class="s">"red"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)],</span><span class="s">"blue"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)],</span><span class="s">"green"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)],</span><span class="s">"magenta"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)],</span><span class="s">"orange"</span><span class="p">))</span>
sage<span class="p">:</span> L<span class="o">.</span>append<span class="p">(</span>Polyomino<span class="p">([(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">),(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)],</span><span class="s">"pink"</span><span class="p">))</span>
sage<span class="p">:</span> T <span class="o">=</span> TilingSolver<span class="p">(</span>L<span class="p">,</span> <span class="p">(</span><span class="mi">8</span><span class="p">,</span><span class="mi">8</span><span class="p">),</span> reflection<span class="o">=</span><span class="bp">True</span><span class="p">)</span>
sage<span class="p">:</span> solution <span class="o">=</span> T<span class="o">.</span>solve<span class="p">()</span><span class="o">.</span>next<span class="p">()</span>
sage<span class="p">:</span> G <span class="o">=</span> <span class="nb">sum</span><span class="p">([</span>piece<span class="o">.</span>show2d<span class="p">()</span> <span class="k">for</span> piece <span class="ow">in</span> solution<span class="p">],</span> Graphics<span class="p">())</span>
sage<span class="p">:</span> G<span class="o">.</span>show<span class="p">(</span>aspect_ratio<span class="o">=</span><span class="mi">1</span><span class="p">,</span> axes<span class="o">=</span><span class="bp">False</span><span class="p">)</span>
</pre></div></div><p>
Or this animation :
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> a <span class="o">=</span> T<span class="o">.</span>animate<span class="p">()</span> <span class="c">#45 seconds </span>
sage<span class="p">:</span> a
Animation <span class="k">with</span> <span class="mi">328</span> frames
sage<span class="p">:</span> a<span class="o">.</span>show<span class="p">()</span> <span class="c"># take some time like 2 minutes</span>
</pre></div></div><p>
Now, I am happy with the patch. Needs review!
</p>
<p>
Sébastien
</p>
TicketslabbeFri, 22 Jul 2011 18:17:00 GMT
https://trac.sagemath.org/ticket/11379#comment:29
https://trac.sagemath.org/ticket/11379#comment:29
<p>
The above 328 frames animation is here :
</p>
<p>
<a class="ext-link" href="http://thales.math.uqam.ca/~labbes/Experimentations/florent.gif"><span class="icon"></span>http://thales.math.uqam.ca/~labbes/Experimentations/florent.gif</a>
</p>
<p>
done with the following parameters
</p>
<pre class="wiki">sage: a.show(delay=50, iterations=1)
</pre>
TicketrbeezerMon, 25 Jul 2011 03:42:45 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379_quantamino-total-sl.patch</em>
</li>
</ul>
<p>
Standalone, comprehensive patch
</p>
TicketrbeezerMon, 25 Jul 2011 03:46:55 GMTstatus changed
https://trac.sagemath.org/ticket/11379#comment:30
https://trac.sagemath.org/ticket/11379#comment:30
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I like all the changes (no holes!). And the 2-D pieces look real nice. I think this is ready to go - builds, passes long tests, nice documentation on 4.7.1.alpha4. So positive review.
</p>
<p>
One patch needed a commit message, and since it was easy, I just rolled everything into one big "total" patch. Still has Sebastian's name on it.
</p>
<p>
Nice work on a big project - this will be a great way to demonstrate backtracking (and dancing links).
</p>
<p>
Rob
</p>
TicketjdemeyerMon, 25 Jul 2011 13:18:31 GMTmilestone changed
https://trac.sagemath.org/ticket/11379#comment:31
https://trac.sagemath.org/ticket/11379#comment:31
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.7.1</em> to <em>sage-4.7.2</em>
</li>
</ul>
TicketjdemeyerWed, 17 Aug 2011 20:36:03 GMTstatus changed
https://trac.sagemath.org/ticket/11379#comment:32
https://trac.sagemath.org/ticket/11379#comment:32
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
The commit message of <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11379/trac_11379_corrections-sl.patch" title="Attachment 'trac_11379_corrections-sl.patch' in Ticket #11379">trac_11379_corrections-sl.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11379/trac_11379_corrections-sl.patch" title="Download"></a> should be changed since it contains a reference to a mercurial queue.
</p>
TicketrbeezerWed, 17 Aug 2011 20:51:39 GMTattachment set
https://trac.sagemath.org/ticket/11379
https://trac.sagemath.org/ticket/11379
<ul>
<li><strong>attachment</strong>
set to <em>trac_11379_corrections-sl-v2.patch</em>
</li>
</ul>
<p>
New version with edited commit string
</p>
TicketrbeezerWed, 17 Aug 2011 20:53:01 GMTstatus, description changed
https://trac.sagemath.org/ticket/11379#comment:33
https://trac.sagemath.org/ticket/11379#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11379?action=diff&version=33">diff</a>)
</li>
</ul>
<p>
I consolidated the commit strings ont eh one patch, and had to use a new name for the file, since I do not have the privileges to replace it.
</p>
<p>
Rob
</p>
TicketjdemeyerThu, 18 Aug 2011 22:03:39 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11379#comment:34
https://trac.sagemath.org/ticket/11379#comment:34
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.7.2.alpha2</em>
</li>
</ul>
TicketslabbeFri, 19 Aug 2011 16:06:06 GMT
https://trac.sagemath.org/ticket/11379#comment:35
https://trac.sagemath.org/ticket/11379#comment:35
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11379#comment:33" title="Comment 33">rbeezer</a>:
</p>
<blockquote class="citation">
<p>
I consolidated the commit strings ont eh one patch, and had to use a new name for the file, since I do not have the privileges to replace it.
</p>
</blockquote>
<p>
Thanks Rob for taking care of this. Thanks again for the whole review. I am happy to see this is now merged!
</p>
<p>
Sébastien
</p>
TicketrbeezerFri, 19 Aug 2011 17:18:38 GMT
https://trac.sagemath.org/ticket/11379#comment:36
https://trac.sagemath.org/ticket/11379#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11379#comment:35" title="Comment 35">slabbe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11379#comment:33" title="Comment 33">rbeezer</a>:
Thanks Rob for taking care of this.
</p>
</blockquote>
<p>
No problem. I knew Jeroen was busy merging patches, and I was busy rebasing some of my linear algebra stuff, so I wanted to "strike while the iron was hot."
</p>
<blockquote class="citation">
<p>
Thanks again for the whole review. I am happy to see this is now merged!
</p>
</blockquote>
<p>
My pleasure - it is a nice piece of work. Feel free to cc me on other combinatorial goodness.
</p>
<p>
Best of luck with the upcoming addition to the family!
</p>
<p>
Rob
</p>
TicketfbisseyWed, 07 Sep 2011 23:31:37 GMT
https://trac.sagemath.org/ticket/11379#comment:37
https://trac.sagemath.org/ticket/11379#comment:37
<p>
Just a note from my testing of 4.7.2.alpha2. I have no problem on a vanilla sage even with python 2.7 installed. However in sage-on-gentoo one test is failing
</p>
<pre class="wiki"> .. NOTE::
The DLX solver throws a Segmentation Fault when the
number of rows is zero::
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search() # not tested
BOOM !!!
</pre><p>
sage-on-gentoo goes BOOM at
</p>
<pre class="wiki">sage: x = dlx_solver(rows)
</pre><p>
With a SIGABRT
</p>
<pre class="wiki">sage: x = dlx_solver(rows)
python2.7: sage/combinat/matrices/dancing_links_c.h:217: void dancing_links::setup_columns(): Assertion `nr_columns > 0' failed.
/usr/lib64/libcsage.so(print_backtrace+0x24)[0x7fea73a945f7]
/usr/lib64/libcsage.so(sigdie+0x1d)[0x7fea73a94687]
/usr/lib64/libcsage.so(sage_signal_handler+0x157)[0x7fea73a94822]
/lib64/libpthread.so.0(+0xfee0)[0x7fea79206ee0]
/lib64/libc.so.6(gsignal+0x35)[0x7fea78ea5ee5]
/lib64/libc.so.6(abort+0x186)[0x7fea78ea7896]
/lib64/libc.so.6(__assert_fail+0xf5)[0x7fea78e9e7a5]
/usr/lib64/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x855d)[0x7fea4e73255d]
</pre><p>
while normal sage goes BOOM in the next not tested bit with a SIGSEGV
</p>
<pre class="wiki">sage: x = dlx_solver(rows)
sage: x.search()
/home/work/fbissey/sandbox/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0x31)[0x7fe2bbd11e65]
/home/work/fbissey/sandbox/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0x7fe2bbd11e97]
/home/work/fbissey/sandbox/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handler+0x20e)[0x7fe2bbd11ae4]
/lib64/libpthread.so.0(+0xfee0)[0x7fe2c0fc5ee0]
/home/work/fbissey/sandbox/sage-4.7.2.alpha2/local/lib/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x847d)[0x7fe29b0c547d]
</pre><p>
We go BOOM in sage-on-gentoo for the reason stated in the notes (0 rows).
</p>
TicketslabbeFri, 09 Sep 2011 21:33:39 GMT
https://trac.sagemath.org/ticket/11379#comment:38
https://trac.sagemath.org/ticket/11379#comment:38
<blockquote class="citation">
<p>
sage-on-gentoo goes BOOM at
</p>
<pre class="wiki">sage: x = dlx_solver(rows)
</pre></blockquote>
<p>
Would adding <code> # not tested </code> at the end of that line would be an acceptable fix ?
</p>
<p>
Should we open a ticket for it?
</p>
<p>
Sébastien
</p>
TicketfbisseyFri, 09 Sep 2011 23:06:11 GMT
https://trac.sagemath.org/ticket/11379#comment:39
https://trac.sagemath.org/ticket/11379#comment:39
<p>
I am doing that right now in sage-on-gentoo. I suspect that in a vanilla sage install
</p>
<pre class="wiki"> sage: x = dlx_solver(rows)
</pre><p>
is left unevaluated and you only get a segfault when accessing x. The only thing
that tells me that something else may happen is that I get a SIGABRT instead of a SIGSEGV. I don't think we need to open a new ticket or change this one for that matter. sage-on-gentoo doesn't have official status. I wanted to make a comment in case it prompted in insight. I suspect it may surface in vanilla sage sooner or later but it is difficult to know what is the trigger since I am applying a few tickets on top of 4.7.2.alpha2 plus a few custom hacks here and there.
</p>
TicketjdemeyerMon, 19 Sep 2011 09:00:17 GMT
https://trac.sagemath.org/ticket/11379#comment:40
https://trac.sagemath.org/ticket/11379#comment:40
<p>
<strong>Any</strong> Segmentation Fault, documented or not, is a bug. So I think this really points to a problem with the original patch. See <a class="closed ticket" href="https://trac.sagemath.org/ticket/11814" title="defect: Catch and fix the segmentation fault in dlx_solver (closed: fixed)">#11814</a> for a follow-up.
</p>
Ticket