From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>
To: Pascal Brisset <pascal.brisset@enac.fr>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Sudoku solver
Date: Tue, 15 Nov 2005 14:22:02 +0100 (NFT) [thread overview]
Message-ID: <Pine.A41.4.44.0511151358430.1597664-100000@ibm1> (raw)
In-Reply-To: <4379DAEF.7060108@recherche.enac.fr>
Bonjour,
> The "optimal algorithm" is not enough; some grids require more (for
> example a "shaving" technique as described by Helmut).
What I understood in Helmut's paper is that most of the Sudoku instances
were backtrack-free when a combination of matching constraints was used
(same with card, cardinality matrix, etc.)
When shaving is allowed, forward checking or just bound consistency closes
almost all the instances without backtracking. That might be a better
advice for "ad hoc" solvers like Frisch's since he seems to be already
doing forward checking.
> where search is not included. So it does not solve all the instances:
It shouldn't be difficult to add a simple search (generate) is it ?
Diego Olivier
next prev parent reply other threads:[~2005-11-15 13:22 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-11-15 4:27 Jon Harrop
2005-11-15 8:55 ` [Caml-list] " Alain Frisch
2005-11-15 9:23 ` Diego Olivier Fernandez Pons
2005-11-15 12:56 ` Pascal Brisset
2005-11-15 13:22 ` Diego Olivier Fernandez Pons [this message]
2005-11-15 13:32 ` Pascal Brisset
2005-11-15 14:41 ` Christophe Raffalli
2005-11-15 19:05 ` Diego Olivier Fernandez Pons
2005-11-15 19:37 ` David Thomas
2005-11-16 6:07 ` Jon Harrop
2005-11-16 7:25 ` Alain Frisch
2005-11-15 20:56 ` Karl Zilles
2005-11-16 8:00 ` Oliver Bandel
2005-11-16 8:15 ` Alain Frisch
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.A41.4.44.0511151358430.1597664-100000@ibm1 \
--to=diego.fernandez_pons@etu.upmc.fr \
--cc=caml-list@inria.fr \
--cc=pascal.brisset@enac.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).