search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

Add Quantumino solver to sage/games #11379

Closed seblabbe closed 13 years ago

seblabbe commented 13 years ago

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

Apply:

  1. attachment: trac_11379_quantamino-sl.patch
  2. attachment: trac_11379_corrections-sl-v2.patch
  3. attachment: trac_11379_color_issue-sl.patch
  4. attachment: trac_11379-reviewer-docs.patch
  5. attachment: trac_11379_hole_bug-sl.patch
  6. attachment: trac_11379_2d_boundary-sl.patch

Component: misc

Keywords: sd31

Author: Sébastien Labbé

Reviewer: Rob Beezer

Merged: sage-4.7.2.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/11379

seblabbe commented 13 years ago
comment:35

Replying to @rbeezer:

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.

Thanks Rob for taking care of this. Thanks again for the whole review. I am happy to see this is now merged!

Sébastien

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago
comment:36

Replying to @seblabbe:

Replying to @rbeezer: Thanks Rob for taking care of this.

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

Thanks again for the whole review. I am happy to see this is now merged!

My pleasure - it is a nice piece of work. Feel free to cc me on other combinatorial goodness.

Best of luck with the upcoming addition to the family!

Rob

kiwifb commented 13 years ago
comment:37

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

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

sage-on-gentoo goes BOOM at

sage: x = dlx_solver(rows)

With a SIGABRT 

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]

while normal sage goes BOOM in the next not tested bit with a SIGSEGV

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]

We go BOOM in sage-on-gentoo for the reason stated in the notes (0 rows).

seblabbe commented 13 years ago
comment:38

sage-on-gentoo goes BOOM at

sage: x = dlx_solver(rows)

Would adding # not tested at the end of that line would be an acceptable fix ?

Should we open a ticket for it?

Sébastien

kiwifb commented 13 years ago
comment:39

I am doing that right now in sage-on-gentoo. I suspect that in a vanilla sage install

 sage: x = dlx_solver(rows)

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.

jdemeyer commented 13 years ago
comment:40

Any Segmentation Fault, documented or not, is a bug. So I think this really points to a problem with the original patch. See #11814 for a follow-up.