Infinite Loop Evaluating Sudoku

[Bill Woessner]

I was playing around with using Prolog for solving and generating
Sudoku puzzles.  Sometimes, it gets stuck in an infinte loop.  Here's
the relevant information:

Linux sarastro 2.6.27.19-170.2.35.fc10.x86_64 #1 SMP Mon Feb 23
13:00:23 EST 2009 x86_64 x86_64 x86_64 GNU/Linux
Prolog top-Level (GNU Prolog) 1.3.1
No flags passed to 'configure'
====BEGIN SUDOKU.PL====
sudoku(C11, C12, C13, C14, C15, C16, C17, C18, C19,
        C21, C22, C23, C24, C25, C26, C27, C28, C29,
        C31, C32, C33, C34, C35, C36, C37, C38, C39,
        C41, C42, C43, C44, C45, C46, C47, C48, C49,
        C51, C52, C53, C54, C55, C56, C57, C58, C59,
        C61, C62, C63, C64, C65, C66, C67, C68, C69,
        C71, C72, C73, C74, C75, C76, C77, C78, C79,
        C81, C82, C83, C84, C85, C86, C87, C88, C89,
        C91, C92, C93, C94, C95, C96, C97, C98, C99) :-

        fd_domain([C11, C12, C13, C14, C15, C16, C17, C18, C19,
        C21, C22, C23, C24, C25, C26, C27, C28, C29,
        C31, C32, C33, C34, C35, C36, C37, C38, C39,
        C41, C42, C43, C44, C45, C46, C47, C48, C49,
        C51, C52, C53, C54, C55, C56, C57, C58, C59,
        C61, C62, C63, C64, C65, C66, C67, C68, C69,
        C71, C72, C73, C74, C75, C76, C77, C78, C79,
        C81, C82, C83, C84, C85, C86, C87, C88, C89,
        C91, C92, C93, C94, C95, C96, C97, C98, C99], 1, 9),

        fd_all_different([C11, C12, C13, C14, C15, C16, C17, C18, C19]),
        fd_all_different([C21, C22, C23, C24, C25, C26, C27, C28, C29]),
        fd_all_different([C31, C32, C33, C34, C35, C36, C37, C38, C39]),
        fd_all_different([C41, C42, C43, C44, C45, C46, C47, C48, C49]),
        fd_all_different([C51, C52, C53, C54, C55, C56, C57, C58, C59]),
        fd_all_different([C61, C62, C63, C64, C65, C66, C67, C68, C69]),
        fd_all_different([C71, C72, C73, C74, C75, C76, C77, C78, C79]),
        fd_all_different([C81, C82, C83, C84, C85, C86, C87, C88, C89]),
        fd_all_different([C91, C92, C93, C94, C95, C96, C97, C98, C99]),

        fd_all_different([C11, C21, C31, C41, C51, C61, C71, C81, C91]),
        fd_all_different([C12, C22, C32, C42, C52, C62, C72, C82, C92]),
        fd_all_different([C13, C23, C33, C43, C53, C63, C73, C83, C93]),
        fd_all_different([C14, C24, C34, C44, C54, C64, C74, C84, C94]),
        fd_all_different([C15, C25, C35, C45, C55, C65, C75, C85, C95]),
        fd_all_different([C16, C26, C36, C46, C56, C66, C76, C86, C96]),
        fd_all_different([C17, C27, C37, C47, C57, C67, C77, C87, C97]),
        fd_all_different([C18, C28, C38, C48, C58, C68, C78, C88, C98]),
        fd_all_different([C19, C29, C39, C49, C59, C69, C79, C89, C99]),

        fd_all_different([C11, C12, C13, C21, C22, C23, C31, C32, C33]),
        fd_all_different([C14, C15, C16, C24, C25, C26, C34, C35, C36]),
        fd_all_different([C17, C18, C19, C27, C28, C29, C37, C38, C39]),
        fd_all_different([C41, C42, C43, C51, C52, C53, C61, C62, C63]),
        fd_all_different([C44, C45, C46, C54, C55, C56, C64, C65, C66]),
        fd_all_different([C47, C48, C49, C57, C58, C59, C67, C68, C69]),
        fd_all_different([C71, C72, C73, C81, C82, C83, C91, C92, C93]),
        fd_all_different([C74, C75, C76, C84, C85, C86, C94, C95, C96]),
        fd_all_different([C77, C78, C79, C87, C88, C89, C97, C98, C99]),

        fd_labeling([C11, C12, C13, C14, C15, C16, C17, C18, C19,
        C21, C22, C23, C24, C25, C26, C27, C28, C29,
        C31, C32, C33, C34, C35, C36, C37, C38, C39,
        C41, C42, C43, C44, C45, C46, C47, C48, C49,
        C51, C52, C53, C54, C55, C56, C57, C58, C59,
        C61, C62, C63, C64, C65, C66, C67, C68, C69,
        C71, C72, C73, C74, C75, C76, C77, C78, C79,
        C81, C82, C83, C84, C85, C86, C87, C88, C89,
        C91, C92, C93, C94, C95, C96, C97, C98, C99]).
====END SUDOKU.PL====
====BEGIN SESSION TRANSCRIPT====
| ?- [sudoku].
compiling /home/bill/sudoku/sudoku.pl for byte code...
/home/bill/sudoku/sudoku.pl compiled, 59 lines read - 26542 bytes written, 27 ms

(4 ms) yes
| ?- sudoku(8, _, 3, _, _, _, _, 2, _,
_, _, _, _, _, 9, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, 4, _, _, 8, _,
_, _, 1, _, _, _, 7, _, _,
_, _, _, _, _, _, _, _, _,
_, _, 8, _, _, 3, _, _, _,
4, _, _, _, _, _, _, _, _,
_, _, _, _, 6, _, 4, _, 5).
====END SESSION TRANSCRIPT====
At this point, I let it run for a good 5 minutes before calling it
quits.  This particular Sudoku doesn't contain any obvious
contradictions.  I'd be willing to bet it doesn't have a unique
solution, either.

--
Bill Woessner

The problem with eating German food is that, an hour later, you're
hungry for power.


_______________________________________________
Bug-prolog mailing list
Bug-prolog@...
http://lists.gnu.org/mailman/listinfo/bug-prolog

[Jasper Taylor]

Your computer is too slow. I re-wrote the query a bit so I could see the
answer...

?- A1=8, A3=3, A8=2, B6=9, D5=4, D8=8, E3=1, E7=7, G3=8, G6=3, H1=4,
I5=6, I7=4,
I9=5,
sudoku(
A1, A2, A3, A4, A5, A6, A7, A8, A9,
B1, B2, B3, B4, B5, B6, B7, B8, B9,
C1, C2, C3, C4, C5, C6, C7, C8, C9,
D1, D2, D3, D4, D5, D6, D7, D8, D9,
E1, E2, E3, E4, E5, E6, E7, E8, E9,
F1, F2, F3, F4, F5, F6, F7, F8, F9,
G1, G2, G3, G4, G5, G6, G7, G8, G9,
H1, H2, H3, H4, H5, H6, H7, H8, H9,
I1, I2, I3, I4, I5, I6, I7, I8, I9).

A1 = 8
A2 = 1
A3 = 3
A4 = 5
A5 = 7
A6 = 4
A7 = 6
A8 = 2
A9 = 9
B1 = 2
B2 = 4
B3 = 5
B4 = 6
B5 = 1
B6 = 9
B7 = 3
B8 = 7
B9 = 8
C1 = 6
C2 = 7
C3 = 9
C4 = 2
C5 = 3
C6 = 8
C7 = 1
C8 = 5
C9 = 4
D1 = 3
D2 = 2
D3 = 6
D4 = 7
D5 = 4
D6 = 5
D7 = 9
D8 = 8
D9 = 1
E1 = 5
E2 = 8
E3 = 1
E4 = 3
E5 = 9
E6 = 6
E7 = 7
E8 = 4
E9 = 2
F1 = 7
F2 = 9
F3 = 4
F4 = 1
F5 = 8
F6 = 2
F7 = 5
F8 = 6
F9 = 3
G1 = 1
G2 = 6
G3 = 8
G4 = 4
G5 = 5
G6 = 3
G7 = 2
G8 = 9
G9 = 7
H1 = 4
H2 = 5
H3 = 7
H4 = 9
H5 = 2
H6 = 1
H7 = 8
H8 = 3
H9 = 6
I1 = 9
I2 = 3
I3 = 2
I4 = 8
I5 = 6
I6 = 7
I7 = 4
I8 = 1
I9 = 5 ?
There are indeed multiple solutions. My Macbook took about 334000ms
(5-6mins).
    --Jasper

Bill Woessner wrote:

> I was playing around with using Prolog for solving and generating
> Sudoku puzzles.  Sometimes, it gets stuck in an infinte loop.  Here's
> the relevant information:
>
> Linux sarastro 2.6.27.19-170.2.35.fc10.x86_64 #1 SMP Mon Feb 23
> 13:00:23 EST 2009 x86_64 x86_64 x86_64 GNU/Linux
> Prolog top-Level (GNU Prolog) 1.3.1
> No flags passed to 'configure'
> ====BEGIN SUDOKU.PL====
> sudoku(C11, C12, C13, C14, C15, C16, C17, C18, C19,
>         C21, C22, C23, C24, C25, C26, C27, C28, C29,
>         C31, C32, C33, C34, C35, C36, C37, C38, C39,
>         C41, C42, C43, C44, C45, C46, C47, C48, C49,
>         C51, C52, C53, C54, C55, C56, C57, C58, C59,
>         C61, C62, C63, C64, C65, C66, C67, C68, C69,
>         C71, C72, C73, C74, C75, C76, C77, C78, C79,
>         C81, C82, C83, C84, C85, C86, C87, C88, C89,
>         C91, C92, C93, C94, C95, C96, C97, C98, C99) :-
>
>         fd_domain([C11, C12, C13, C14, C15, C16, C17, C18, C19,
>         C21, C22, C23, C24, C25, C26, C27, C28, C29,
>         C31, C32, C33, C34, C35, C36, C37, C38, C39,
>         C41, C42, C43, C44, C45, C46, C47, C48, C49,
>         C51, C52, C53, C54, C55, C56, C57, C58, C59,
>         C61, C62, C63, C64, C65, C66, C67, C68, C69,
>         C71, C72, C73, C74, C75, C76, C77, C78, C79,
>         C81, C82, C83, C84, C85, C86, C87, C88, C89,
>         C91, C92, C93, C94, C95, C96, C97, C98, C99], 1, 9),
>
>         fd_all_different([C11, C12, C13, C14, C15, C16, C17, C18, C19]),
>         fd_all_different([C21, C22, C23, C24, C25, C26, C27, C28, C29]),
>         fd_all_different([C31, C32, C33, C34, C35, C36, C37, C38, C39]),
>         fd_all_different([C41, C42, C43, C44, C45, C46, C47, C48, C49]),
>         fd_all_different([C51, C52, C53, C54, C55, C56, C57, C58, C59]),
>         fd_all_different([C61, C62, C63, C64, C65, C66, C67, C68, C69]),
>         fd_all_different([C71, C72, C73, C74, C75, C76, C77, C78, C79]),
>         fd_all_different([C81, C82, C83, C84, C85, C86, C87, C88, C89]),
>         fd_all_different([C91, C92, C93, C94, C95, C96, C97, C98, C99]),
>
>         fd_all_different([C11, C21, C31, C41, C51, C61, C71, C81, C91]),
>         fd_all_different([C12, C22, C32, C42, C52, C62, C72, C82, C92]),
>         fd_all_different([C13, C23, C33, C43, C53, C63, C73, C83, C93]),
>         fd_all_different([C14, C24, C34, C44, C54, C64, C74, C84, C94]),
>         fd_all_different([C15, C25, C35, C45, C55, C65, C75, C85, C95]),
>         fd_all_different([C16, C26, C36, C46, C56, C66, C76, C86, C96]),
>         fd_all_different([C17, C27, C37, C47, C57, C67, C77, C87, C97]),
>         fd_all_different([C18, C28, C38, C48, C58, C68, C78, C88, C98]),
>         fd_all_different([C19, C29, C39, C49, C59, C69, C79, C89, C99]),
>
>         fd_all_different([C11, C12, C13, C21, C22, C23, C31, C32, C33]),
>         fd_all_different([C14, C15, C16, C24, C25, C26, C34, C35, C36]),
>         fd_all_different([C17, C18, C19, C27, C28, C29, C37, C38, C39]),
>         fd_all_different([C41, C42, C43, C51, C52, C53, C61, C62, C63]),
>         fd_all_different([C44, C45, C46, C54, C55, C56, C64, C65, C66]),
>         fd_all_different([C47, C48, C49, C57, C58, C59, C67, C68, C69]),
>         fd_all_different([C71, C72, C73, C81, C82, C83, C91, C92, C93]),
>         fd_all_different([C74, C75, C76, C84, C85, C86, C94, C95, C96]),
>         fd_all_different([C77, C78, C79, C87, C88, C89, C97, C98, C99]),
>
>         fd_labeling([C11, C12, C13, C14, C15, C16, C17, C18, C19,
>         C21, C22, C23, C24, C25, C26, C27, C28, C29,
>         C31, C32, C33, C34, C35, C36, C37, C38, C39,
>         C41, C42, C43, C44, C45, C46, C47, C48, C49,
>         C51, C52, C53, C54, C55, C56, C57, C58, C59,
>         C61, C62, C63, C64, C65, C66, C67, C68, C69,
>         C71, C72, C73, C74, C75, C76, C77, C78, C79,
>         C81, C82, C83, C84, C85, C86, C87, C88, C89,
>         C91, C92, C93, C94, C95, C96, C97, C98, C99]).
> ====END SUDOKU.PL====
> ====BEGIN SESSION TRANSCRIPT====
> | ?- [sudoku].
> compiling /home/bill/sudoku/sudoku.pl for byte code...
> /home/bill/sudoku/sudoku.pl compiled, 59 lines read - 26542 bytes written, 27 ms
>
> (4 ms) yes
> | ?- sudoku(8, _, 3, _, _, _, _, 2, _,
> _, _, _, _, _, 9, _, _, _,
> _, _, _, _, _, _, _, _, _,
> _, _, _, _, 4, _, _, 8, _,
> _, _, 1, _, _, _, 7, _, _,
> _, _, _, _, _, _, _, _, _,
> _, _, 8, _, _, 3, _, _, _,
> 4, _, _, _, _, _, _, _, _,
> _, _, _, _, 6, _, 4, _, 5).
> ====END SESSION TRANSCRIPT====
> At this point, I let it run for a good 5 minutes before calling it
> quits.  This particular Sudoku doesn't contain any obvious
> contradictions.  I'd be willing to bet it doesn't have a unique
> solution, either.
>
>  

_______________________________________________
Bug-prolog mailing list
Bug-prolog@...
http://lists.gnu.org/mailman/listinfo/bug-prolog

[Salvador Abreu]

> Your computer is too slow. I re-wrote the query a bit so I could see  
> the answer...

if you use fd_labelingff instead of fd_labeling you'll converge on a  
solution *much* faster (like in 1ms for the first solution on a  
macbook pro...)

--
Salvador Abreu       --  http://www.di.uevora.pt/~spa/
Departamento de Informatica
Universidade de Evora - PORTUGAL




_______________________________________________
Bug-prolog mailing list
Bug-prolog@...
http://lists.gnu.org/mailman/listinfo/bug-prolog

[Daniel Diaz-3]

Your program is too slow. You can speed up it using a heuristics. Try
for instance

fd_labelingff

or (if you want the number of backtracks)

fd_labeling([...], [variable_method(ff), backtracks(B)]),

Daniel

Bill Woessner a écrit :

> I was playing around with using Prolog for solving and generating
> Sudoku puzzles.  Sometimes, it gets stuck in an infinte loop.  Here's
> the relevant information:
>
> Linux sarastro 2.6.27.19-170.2.35.fc10.x86_64 #1 SMP Mon Feb 23
> 13:00:23 EST 2009 x86_64 x86_64 x86_64 GNU/Linux
> Prolog top-Level (GNU Prolog) 1.3.1
> No flags passed to 'configure'
> ====BEGIN SUDOKU.PL====
> sudoku(C11, C12, C13, C14, C15, C16, C17, C18, C19,
>         C21, C22, C23, C24, C25, C26, C27, C28, C29,
>         C31, C32, C33, C34, C35, C36, C37, C38, C39,
>         C41, C42, C43, C44, C45, C46, C47, C48, C49,
>         C51, C52, C53, C54, C55, C56, C57, C58, C59,
>         C61, C62, C63, C64, C65, C66, C67, C68, C69,
>         C71, C72, C73, C74, C75, C76, C77, C78, C79,
>         C81, C82, C83, C84, C85, C86, C87, C88, C89,
>         C91, C92, C93, C94, C95, C96, C97, C98, C99) :-
>
>         fd_domain([C11, C12, C13, C14, C15, C16, C17, C18, C19,
>         C21, C22, C23, C24, C25, C26, C27, C28, C29,
>         C31, C32, C33, C34, C35, C36, C37, C38, C39,
>         C41, C42, C43, C44, C45, C46, C47, C48, C49,
>         C51, C52, C53, C54, C55, C56, C57, C58, C59,
>         C61, C62, C63, C64, C65, C66, C67, C68, C69,
>         C71, C72, C73, C74, C75, C76, C77, C78, C79,
>         C81, C82, C83, C84, C85, C86, C87, C88, C89,
>         C91, C92, C93, C94, C95, C96, C97, C98, C99], 1, 9),
>
>         fd_all_different([C11, C12, C13, C14, C15, C16, C17, C18, C19]),
>         fd_all_different([C21, C22, C23, C24, C25, C26, C27, C28, C29]),
>         fd_all_different([C31, C32, C33, C34, C35, C36, C37, C38, C39]),
>         fd_all_different([C41, C42, C43, C44, C45, C46, C47, C48, C49]),
>         fd_all_different([C51, C52, C53, C54, C55, C56, C57, C58, C59]),
>         fd_all_different([C61, C62, C63, C64, C65, C66, C67, C68, C69]),
>         fd_all_different([C71, C72, C73, C74, C75, C76, C77, C78, C79]),
>         fd_all_different([C81, C82, C83, C84, C85, C86, C87, C88, C89]),
>         fd_all_different([C91, C92, C93, C94, C95, C96, C97, C98, C99]),
>
>         fd_all_different([C11, C21, C31, C41, C51, C61, C71, C81, C91]),
>         fd_all_different([C12, C22, C32, C42, C52, C62, C72, C82, C92]),
>         fd_all_different([C13, C23, C33, C43, C53, C63, C73, C83, C93]),
>         fd_all_different([C14, C24, C34, C44, C54, C64, C74, C84, C94]),
>         fd_all_different([C15, C25, C35, C45, C55, C65, C75, C85, C95]),
>         fd_all_different([C16, C26, C36, C46, C56, C66, C76, C86, C96]),
>         fd_all_different([C17, C27, C37, C47, C57, C67, C77, C87, C97]),
>         fd_all_different([C18, C28, C38, C48, C58, C68, C78, C88, C98]),
>         fd_all_different([C19, C29, C39, C49, C59, C69, C79, C89, C99]),
>
>         fd_all_different([C11, C12, C13, C21, C22, C23, C31, C32, C33]),
>         fd_all_different([C14, C15, C16, C24, C25, C26, C34, C35, C36]),
>         fd_all_different([C17, C18, C19, C27, C28, C29, C37, C38, C39]),
>         fd_all_different([C41, C42, C43, C51, C52, C53, C61, C62, C63]),
>         fd_all_different([C44, C45, C46, C54, C55, C56, C64, C65, C66]),
>         fd_all_different([C47, C48, C49, C57, C58, C59, C67, C68, C69]),
>         fd_all_different([C71, C72, C73, C81, C82, C83, C91, C92, C93]),
>         fd_all_different([C74, C75, C76, C84, C85, C86, C94, C95, C96]),
>         fd_all_different([C77, C78, C79, C87, C88, C89, C97, C98, C99]),
>
>         fd_labeling([C11, C12, C13, C14, C15, C16, C17, C18, C19,
>         C21, C22, C23, C24, C25, C26, C27, C28, C29,
>         C31, C32, C33, C34, C35, C36, C37, C38, C39,
>         C41, C42, C43, C44, C45, C46, C47, C48, C49,
>         C51, C52, C53, C54, C55, C56, C57, C58, C59,
>         C61, C62, C63, C64, C65, C66, C67, C68, C69,
>         C71, C72, C73, C74, C75, C76, C77, C78, C79,
>         C81, C82, C83, C84, C85, C86, C87, C88, C89,
>         C91, C92, C93, C94, C95, C96, C97, C98, C99]).
> ====END SUDOKU.PL====
> ====BEGIN SESSION TRANSCRIPT====
> | ?- [sudoku].
> compiling /home/bill/sudoku/sudoku.pl for byte code...
> /home/bill/sudoku/sudoku.pl compiled, 59 lines read - 26542 bytes written, 27 ms
>
> (4 ms) yes
> | ?- sudoku(8, _, 3, _, _, _, _, 2, _,
> _, _, _, _, _, 9, _, _, _,
> _, _, _, _, _, _, _, _, _,
> _, _, _, _, 4, _, _, 8, _,
> _, _, 1, _, _, _, 7, _, _,
> _, _, _, _, _, _, _, _, _,
> _, _, 8, _, _, 3, _, _, _,
> 4, _, _, _, _, _, _, _, _,
> _, _, _, _, 6, _, 4, _, 5).
> ====END SESSION TRANSCRIPT====
> At this point, I let it run for a good 5 minutes before calling it
> quits.  This particular Sudoku doesn't contain any obvious
> contradictions.  I'd be willing to bet it doesn't have a unique
> solution, either.
>
>  

--
Ce message a ete verifie par MailScanner
pour des virus ou des polluriels et rien de
suspect n'a ete trouve.



_______________________________________________
Bug-prolog mailing list
Bug-prolog@...
http://lists.gnu.org/mailman/listinfo/bug-prolog

[Bill Woessner]

This is fantastic.  Thank you all so much for the feedback.  I'm
obviously a complete newbie at Prolog (OK, I studied it for a week or
2 in college... 10 years ago).  I'm grateful for all your help.

Sincerely,
Bill Woessner

--
Bill Woessner

The problem with eating German food is that, an hour later, you're
hungry for power.


_______________________________________________
Bug-prolog mailing list
Bug-prolog@...
http://lists.gnu.org/mailman/listinfo/bug-prolog