Hello,
while experimenting with some random partial Latin squares I have come
across some squares for which the is_completable() Call seems to loop
indefinitely - i.e. I had to kill sage to abort it (it was not
responding to Ctrl+c) after running for several minutes ... I even once
let it run for some hours with no result.
The machine is an Intel i5 with 2.4 GHz so it should not really be an
issue of speed I hope. (usually these instances are solved within 1 second)
One example is the following 16 x 16 partial Latin square:
---- snip ----
L = [[-1, -1, -1, 6, -1, 0, -1, -1, 9, -1, -1, 8, 11, -1, 4, -1],
[-1, 8, 4, -1, 15, 10, 0, -1, 2, -1, 6, -1, -1, -1, 3, -1],
[-1, -1, 8, -1, -1, 14, 3, 6, -1, -1, 4, 10, 5, 9, 15, -1],
[-1, -1, -1, -1, 13, -1, 8, 11, 15, -1, 7, -1, -1, -1, -1, 2],
[11, -1, 6, -1, 10, 5, -1, 8, -1, -1, 3, -1, 4, -1, -1, 7],
[-1, -1, -1, 11, 14, 8, -1, -1, 5, 7, 10, -1, 2, -1, -1, -1],
[15, -1, 10, -1, -1, -1, 4, -1, -1, -1, -1, 11, -1, 3, -1, -1],
[-1, -1, -1, -1, -1, -1, -1, 5, -1, 2, 12, 0, 7, 10, 11, 14],
[-1, 2, 3, -1, -1, 13, -1, 12, -1, 1, 14, 15, 0, -1, 8, 9],
[ 3, 5, -1, 4, 11, 12, 10, 1, 0, 14, -1, 13, 9, -1, -1, 6],
[ 7, -1, -1, -1, 9, -1, -1, -1, 10, -1, -1, -1, -1, -1, 0, 5],
[ 9, 10, -1, -1, 2, -1, -1, -1, 14, -1, 0, -1, -1, 5, -1, 4],
[-1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12],
[14, 4, 12, 15, -1, -1, -1, 2, -1, -1, -1, -1, 13, -1, -1, -1],
[-1, -1, -1, -1, 6, -1, -1, 9, -1, 0, 8, 4, 14, -1, 10, -1],
[-1, 0, 13, 8, -1, 3, -1, 14, 11, 10, -1, 2, 15, -1, 1, -1]]
L.is_completable() # <-- this seems to run forever....
---- snip ----
I am curious if anybody else can confirm this problem.
If it really is a bug in the solver (i.e. dancing links implementation)
it might not be so easy to track it down ... I stumbled upon it while
generating many random partial Latin squares (it has not yet happened
for squares smaller than 15x15)
Kind regards,
Maximilian
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
