Re: Infinite Loop Evaluating Sudoku

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.