Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

New book "The Hidden Logic of Sudoku"
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 5:56 am    Post subject: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Wed Jun 13, 2007 7:00 am    Post subject: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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. Smile
Back to top
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 7:15 am    Post subject: Re: Re: New book "The Hidden Logic of Sudoku" Reply with quote

angusj wrote:
As a suggestion, you might want to add your website to your profile. Smile

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
View user's profile Send private message Visit poster's website
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Wed Jun 13, 2007 7:28 am    Post subject: Re: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 7:33 am    Post subject: Re: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 7:37 am    Post subject: Hidden chains defined in "The Hidden Logic of Sudoku&qu Reply with quote

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
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 7:57 am    Post subject: xyt-chains defined in "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 8:03 am    Post subject: Re: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Jun 13, 2007 12:42 pm    Post subject: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 12:58 pm    Post subject: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Jun 13, 2007 1:27 pm    Post subject: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 2:12 pm    Post subject: Re: New book "The Hidden Logic of Sudoku" Reply with quote

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
View user's profile Send private message Visit poster's website
Red Ed

Joined: 04 Nov 2006
Posts: 21
:

Items
PostPosted: Wed Jun 13, 2007 8:53 pm    Post subject: Reply with quote

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
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Thu Jun 14, 2007 4:07 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Thu Jun 14, 2007 6:44 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron