Opened 10 years ago

Last modified 10 years ago

#11379 closed enhancement

Add Quantumino solver to sage/games — at Version 17

Reported by: slabbe Owned by: slabbe
Priority: major Milestone: sage-4.7.2
Component: misc Keywords: sd31
Cc: Merged in:
Authors: Reviewers: Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by slabbe)

Some code to solve the Quantumino Puzzle (see also this video on youtube).

For the human:

Apply:

  1. trac_11379_quantamino-sl.patch
  2. trac_11379_corrections-sl.patch

For the patchbot:

Apply trac_11379_quantamino-sl.patch trac_11379_corrections-sl.patch

Change History (21)

comment:1 Changed 10 years ago by rbeezer

I saw this demo'ed at Sage Days 30. It's really nice. I'll give the patch as look once it appears.

comment:2 Changed 10 years ago by slabbe

Just added the patch.

The file takes 80 seconds to test... so I still need to add some "long" doctest warnings...

Sébastien

Changed 10 years ago by slabbe

comment:3 Changed 10 years ago by slabbe

  • Status changed from new to needs_review

comment:4 Changed 10 years ago by slabbe

Takes now 17 seconds to test on my machine (35s with long test).

Changed 10 years ago by rbeezer

comment:5 follow-up: Changed 10 years ago by rbeezer

  • Status changed from needs_review to needs_work

Hi Sebastien,

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.

  • One doctest failure. I'm on 64-bit Linux - could 32-bit/64-bit be the cause?
    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
    **********************************************************************
    
  • Why does block number 8 (yellow) have a hole in the middle? See discussion below about size.
  • Documentation looks good. I would have liked to see a bit more detail at the module level for a quickstart - more like for the QuantuminoSolver class-level documentation. Specifically:
    • Make it clearer that you will see the puzzle pieces in 3D with the show_pentaminos() command.
    • 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 _repr_ was not as informative as my curiosity.
    • Maybe a real quick overview of the classes: the pentamino and polyomino classes, the solution class, and the solver class.
  • I thought an interact would be fun. Checkboxes for the excluded piece, plus the ability to "explode" the solution via a slider. I'm not suggesting you write an interact, but a size argument as input to show3d() (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 size argument to pass from the solution show3d() down to each piece. But my patch is just a suggestion - it is not ready to use.
  • 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:
    • "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.
    • It is not clear what sub does without looking at the code. A one-line summary and an input list would be enough, I think.
  • 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.
  • 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. :-)

Minor editing

  • "needs to creates" should be "create"
  • "where each pieces is used exactly once" should be "piece"
  • # Class QuantuminoSolultion (misspelled in comment)
  • 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.
  • #bug trac #11272 - can this go away?
  • #return G (twice) - can these go away?

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.

Rob

comment:6 Changed 10 years ago by rbeezer

One more comment I forgot:

ss=quantumino_solver.get_solution(7, box=(3,3,9))

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?

comment:7 in reply to: ↑ 5 ; follow-up: Changed 10 years ago by slabbe

Hi Rob,

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 :

  • I thought an interact would be fun. Checkboxes for the excluded piece, plus the ability to "explode" the solution via a slider. I'm not suggesting you write an interact, but a size argument as input to show3d() (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 size argument to pass from the solution show3d() down to each piece. But my patch is just a suggestion - it is not ready to use.

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.

Sébastien

comment:8 Changed 10 years ago by slabbe

  • Description modified (diff)

comment:9 in reply to: ↑ 7 Changed 10 years ago by slabbe

  • Status changed from needs_work to needs_review

I don't understand what is meant by ""explode" the solution".

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.

I think I was able to answer all of your comments. Needs review!

Sébastien

Changed 10 years ago by slabbe

Applies over the correction patch.

comment:10 follow-up: Changed 10 years ago by rbeezer

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.

Would Franco let you bring the real physical puzzle to Seattle for SD 31?

Rob

comment:11 in reply to: ↑ 10 Changed 10 years ago by slabbe

Would Franco let you bring the real physical puzzle to Seattle for SD 31?

Sure! I'll ask. And will try not to forget it!

Sébastien

comment:12 Changed 10 years ago by mariah

  • Component changed from PLEASE CHANGE to misc

comment:13 follow-up: Changed 10 years ago by slabbe

  • Status changed from needs_review to needs_work

I have been working on it again yesterday. I will update the patches again quite soon. Do not review until then.

Sebastien

comment:14 in reply to: ↑ 13 Changed 10 years ago by rbeezer

  • Description modified (diff)
  • Keywords sd31 added
  • Reviewers set to Rob Beezer

Replying to slabbe:

I have been working on it again yesterday. I will update the patches again quite soon. Do not review until then.

Thanks - ready whenever you are (I think!).

comment:15 Changed 10 years ago by slabbe

Great. So I will upload the patches later tonight! I still have some cleaning to make.

Changed 10 years ago by slabbe

Applies over my first patch

comment:16 Changed 10 years ago by slabbe

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Summary changed from Add Quantamino solver to sage/games to Add Quantumino solver to sage/games

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).

So, compared to what has already been reviewed, I did a bunch of improvements: I created a new file sage/combinat/tiling.py and moved the polyomino class into it. Also, I created a new class called TilingSolver which solves the general problem of Tiling a box by polyomino. This class replaces the old function general_puzzle_solver which I might misspell. The TilingSolver 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 Polyomino and TilingSolver 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.

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?

Question: Should I use Pentomino like Donald Knuth does or Pentamino like the game Quantumino calls the pieces? Which is best?

Good night!

comment:17 Changed 10 years ago by slabbe

  • Description modified (diff)
Note: See TracTickets for help on using tickets.