| View previous topic :: View next topic |
| Author |
Message |
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
 Posted: Wed Jun 13, 2007 5:56 am Post subject: New book "The Hidden Logic of Sudoku" |
 |
|
This is to announce to this forum that I have just published a new book "The Hidden Logic of Sudoku", which may be of interest to some of you.
Contrary to many mathematical approaches to Sudoku (based on graph colouring, …), my approach is based on candidates elimination and on resolution rules of types similar to those discussed in these forums.
All details can be found on my Web page (that the robot does not allow me to display here because this is my first post, but that you can easily find from the name of the book).
Let me just mention a few examples of mathematical results proved:
- three meta-theorems on symmetry, which allow me to introduce auxiliary representations and new rules based on them,
- precise logical relationships between Naked Subsets, Hidden Subsets and "Fishy patterns",
- any sudoku resolution rule that is block-free (i.e. does not mention blocks) is already valid for Latin Squares (intuitively obvious but not so obvious to prove),
- a few subsumption results (rule A reduces to rules B, C, …),
- lots of independence results (rule A does not reduce to …),
- a confluence theorem (applying rules in any order cannot prevent one from reaching a solution),
- new simple graphical representations for chains, which are proved to be equivalent to well defined logical formulæ,
- a precise evaluation of the efficiency of each rule (all my rules have been implemented in a solver and 56000 puzzles have been solved).
Of course, I'd be very very interested by the opinion of expert players (which I am not) on all this. |
|
| Back to top |
|
 |
| angusj
Site Admin
 | | Joined: 18 Jun 2005 | | Posts: 406 | | : | |
Items |
|
| Posted: Wed Jun 13, 2007 7:00 am Post subject: Re: New book "The Hidden Logic of Sudoku" |
|
|
| berthier wrote: | | All details can be found on my Web page (that the robot does not allow me to display here because this is my first post, but that you can easily find from the name of the book). |
Yes, found with a google search: http://www-lor.int-evry.fr/~berthier/HLS/index.html
As a suggestion, you might want to add your website to your profile.  |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Wed Jun 13, 2007 7:15 am Post subject: Re: Re: New book "The Hidden Logic of Sudoku" |
|
|
| angusj wrote: | | As a suggestion, you might want to add your website to your profile. |
I may be missing something, but it seems that I can't do that. In the "registration information" page, there is no field for that. Or is it the "location" field? Or should I have 5 posts before it appears? |
|
| Back to top |
|
|
| angusj
Site Admin
| | Joined: 18 Jun 2005 | | Posts: 406 | | : | |
Items |
|
| Posted: Wed Jun 13, 2007 7:28 am Post subject: Re: Re: New book "The Hidden Logic of Sudoku" |
|
|
| berthier wrote: | | I may be missing something, but it seems that I can't do that. In the "registration information" page, there is no field for that. Or is it the "location" field? Or should I have 5 posts before it appears? |
The "Website" field should be directly above the "Location" field in the "Profile Information" section. Perhaps it is hidden until you've made your 5 posts - which we all agree is a nuisance but is outside our control. (Nevertheless, it does definitely cut down on spam.) |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Wed Jun 13, 2007 7:33 am Post subject: Re: Re: New book "The Hidden Logic of Sudoku" |
|
|
| angusj wrote: |
The "Website" field should be directly above the "Location" field in the "Profile Information" section. Perhaps it is hidden until you've made your 5 posts - which we all agree is a nuisance but is outside our control. (Nevertheless, it does definitely cut down on spam.) |
Well, I understand that some type of restriction is necessary. So let me try to have 5 posts that will bring some content. |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Wed Jun 13, 2007 7:37 am Post subject: Hidden chains defined in "The Hidden Logic of Sudoku&qu |
|
|
As an example of patterns I introduce are "hidden chains". These are like usual chains, but in row-number and column-number spaces.
This concept applies to different kinds of chains c-chains (colouring, or whatever you call them), xy-chains, …
I show the unifying power of such chains. |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Wed Jun 13, 2007 7:57 am Post subject: xyt-chains defined in "The Hidden Logic of Sudoku" |
|
|
This post has been completed and transfered to the "Solving sudoku forum"
Last edited by berthier on Fri Jun 15, 2007 2:03 pm; edited 1 time in total |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Wed Jun 13, 2007 8:03 am Post subject: Re: Re: New book "The Hidden Logic of Sudoku" |
|
|
| angusj wrote: |
The "Website" field should be directly above the "Location" field in the "Profile Information" section. Perhaps it is hidden until you've made your 5 posts |
After I had 5 posts, this field did appear in the registration page. Thanks. |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Jun 13, 2007 12:42 pm Post subject: Re: New book "The Hidden Logic of Sudoku" |
|
|
| berthier wrote: | This is to announce to this forum that I have just published a new book "The Hidden Logic of Sudoku", which may be of interest to some of you.
|
I looked over the companion online data for your book
I expected the "Sudogen17 puzzle base" to be a collection of 17 clue puzzles but it isn't -- what does the 17 stand for?
some of the data/code had solution times, what is the time unit for e.g. 2.35?
is your solver written in prolog? |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Wed Jun 13, 2007 12:58 pm Post subject: Re: New book "The Hidden Logic of Sudoku" |
|
|
| gsf wrote: | | berthier wrote: | This is to announce to this forum that I have just published a new book "The Hidden Logic of Sudoku", which may be of interest to some of you.
|
I looked over the companion online data for your book
I expected the "Sudogen17 puzzle base" to be a collection of 17 clue puzzles but it isn't -- what does the 17 stand for?
some of the data/code had solution times, what is the time unit for e.g. 2.35?
is your solver written in prolog? |
Sudogen0 and Sudogen17 are two bases of 10,000 randomly generated puzzles. Here "17" and "0" merely indicate the seed of the random number generator used to generate this puzzles "database". It has no other meaning.
I also use a database of (36,628) 17-clue puzzles, the famous Gordon Royle base.
Solution times (in seconds) indicated after some resolution paths are the resolution times using the CLIPS inference engine. They are not very meaningful, because all the computations have not been done on the same machine. I forgot to eliminate them before putting this online. Maybe I'll do it.
My Sudorules solver is not written in Prolog. It is based on forward chaining and is written in the syntax of JESS or CLIPS (one may use whichever engine he prefers). |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Jun 13, 2007 1:27 pm Post subject: Re: New book "The Hidden Logic of Sudoku" |
|
|
| berthier wrote: |
My Sudorules solver is not written in Prolog. It is based on forward chaining and is written in the syntax of JESS or CLIPS (one may use whichever engine he prefers). |
aha
does the jess/clips solver take advantage of the "learning" aspects of the rete matching algorithm?
i.e., does it get better as it processes a batch of puzzles?
or, after a bunch of puzzles are processed, can you look at the resulting rete network and
infer new constraint rules (different from the initial set of rules)? |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Wed Jun 13, 2007 2:12 pm Post subject: Re: New book "The Hidden Logic of Sudoku" |
|
|
| gsf wrote: | does the jess/clips solver take advantage of the "learning" aspects of the rete matching algorithm?
i.e., does it get better as it processes a batch of puzzles?
or, after a bunch of puzzles are processed, can you look at the resulting rete network and
infer new constraint rules (different from the initial set of rules)? |
My purpose was not the automatic discovery of new rules, but the proper logical formulation and implementation of known rules, together with the definition (and implementation) of all their super-symmetric counterparts.
The Rete algorithm itself does not provide any possibility of learning (i.e. adding automatically new rules). Inspecting the Rete network for extracting rules from it would be a really difficult task.
Some extensions of the Rete algorithm can learn, such as Soar. Soar is a great idea, but it is terribly slow (at least the version I used years ago).
If automatic learning of new rules was the topic of interest, another approach would be starting from the constraints defining the problem and using a tool based on constraints. But I have no example of any new rule that would have been produced that way.
Given all the rules already known, automatic learning of (really) new rules seems very difficult. It may therefore be a very good learning example in AI. |
|
| Back to top |
|
|
| Red Ed
| | Joined: 04 Nov 2006 | | Posts: 21 | | : | |
Items |
|
| Posted: Wed Jun 13, 2007 8:53 pm Post subject: |
|
|
| gsf, how does your solver's rating work out on Denis' list of puzzles classified by levels? (I should post the same q. to the Players' Forum, I guess, since they've got an endless thirst for running SE, suexrat etc. on puzzles) |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Jun 14, 2007 4:07 am Post subject: |
|
|
| Red Ed wrote: | | gsf, how does your solver's rating work out on Denis' list of puzzles classified by levels? (I should post the same q. to the Players' Forum, I guess, since they've got an endless thirst for running SE, suexrat etc. on puzzles) |
only 3/19351 cause my solver to guess
here they are with berthier's level, SE rating and rating time:
| Code: |
07 8.3 5.00s 900020000000706200087100300000002000001500700590060000008000000140000050000849030
09 7.2 4.00s 400382000000050800900007000000008050002005740050090020240003080009270000006000400
10 8.5 2.00s 100060800008003001000020005060007000034800000002900703000400098000000000609070000
|
the q1 rating ranges from 5 through 620
so its not a bastion of hard puzzles
but that's ok -- its orgainzed by the non-guessing techniques of berthier's solver
on a whim I ran these through with your (RedEd's) BRnet constraints (-q+b) and the first two
required guessing, but the last one solved with BRnets but not (my) XYK constraints
so we have an example where BRnet covers something missed by XYK -- will have to study that later
level 01 are consistently FNB (naked/hidden singles + box-line(locked candidates))
level 02 also have THW (naked/hidden tuples + x-wing/swordfish/jellyfish)
level 03 has some crossover with 02 + XYK (x-cycle + y-cycle + knots (contradiction chains))
but 03-10 seem to be a hodgepodge of XYK
so I'd like to know the details of why one view (mine) of levels 03-10 seems to be random
while another (berthier's) is stratified into 8 layers |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Thu Jun 14, 2007 6:44 am Post subject: |
|
|
| Red Ed wrote: | | gsf, how does your solver's rating work out on Denis' list of puzzles classified by levels? (I should post the same q. to the Players' Forum, I guess, since they've got an endless thirst for running SE, suexrat etc. on puzzles) |
If this can help, I have just put a post in the Solving Techniques Forum, where I describe how my levels are defined. |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
