bug-prolog
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Infinite Loop Evaluating Sudoku


From: Bill Woessner
Subject: Infinite Loop Evaluating Sudoku
Date: Mon, 16 Mar 2009 21:22:36 -0400

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.




reply via email to

[Prev in Thread] Current Thread [Next in Thread]