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.