dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Program doesn't solve it.
Goto page Previous  1, 2
 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Daily Sudoku puzzles
View previous topic :: View next topic  
Author Message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich
PostPosted: Wed Aug 10, 2005 6:06 am    Post subject: Reply with quote
Ok. I think that the difficulty of a game should be measured as the sum of the difficulties of each step. One step is finding a number in a cell and than we get to the next step (except when we found the last number).
Now we reduced the problem to define the difficulty for a step, of a position. Here we will have a set of possibilities out of all that are left. This ones can be of 2 kinds. The first - simple, that can be found after we did the direct Excludes and second - complex, that can be found ONLY when doing the indirect Excludes. Now the difficulty is dependent on the number of indirect excludes we have to do.
The question is: how should I quantify the "indirect" excludes and their numbers and their dependency (meaning that a indirect exclude is a prerequirement of a second indirect exclude, etc).
When you try to get the 11 numbers that can be found with "logic" only, out of the following:

043080250
600000000
000001094
900004070
000608000
010200003
820500000
000000005
034090710

meaning trying to solve the first 11 numbers, you will understand better that I mean. This diffiulty is of course refering to humans and not computer programs.
Any feedback, ideas ?!
Back to top
View user's profile Send private message
Guest
PostPosted: Wed Aug 10, 2005 10:51 am    Post subject: Reply with quote
I do not speak english, sorry
in row 1 and row 9, "6" only in col 6 and col 9
-> in col 6 and col 9, "6" only in row 1 and row9 -> "9" in row 7 col 9
Back to top
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich
PostPosted: Wed Aug 10, 2005 11:17 am    Post subject: Reply with quote
Anonymous wrote:
I do not speak english, sorry
in row 1 and row 9, "6" only in col 6 and col 9
-> in col 6 and col 9, "6" only in row 1 and row9 -> "9" in row 7 col 9


German?
Back to top
View user's profile Send private message
Guest
PostPosted: Wed Aug 10, 2005 12:39 pm    Post subject: Reply with quote
Spanish
Back to top
asteron
Guest
PostPosted: Tue Aug 16, 2005 5:26 pm    Post subject: Reply with quote
I wrote a program in python that hasnt gotten stuck on anything from here yet. I first make a board of squares and then define all the "neighborhoods" that are present on the board (rows columns and boxes). I have four rules.

1. If a box has one possible value assign it that value
2. If a neighborhood has one possible square for a value assign that square the value
3. If all the possible squares of a value in a neighborhood share a different neighborhood remove that value from the other squares of the second neighborhood
4. If all the possible squares for a set of values in the neighborhood equal the number of values remove the other candidate values from those squares. (I call these pigeons)

Squares basically pass messages of events to the nieghborhoods they belong to (when values get assigned or eliminated) and neighborhoods message eachother for rule 3. The solver doesnt stop until there are no more messages pending.

Here's the core if anyone is interested.

Code:
def processMessage(self):
        if len(self.messages) == 0:
            return
        msg = self.messages[0]
        self.messages = self.messages[1:]
        dirty = False
           
        if msg.type == PIGEON:
            for c in self.cells:
                if c in msg.cells:
                    if c.removeButVals(msg.arg):
                        dirty = True
                   
        if msg.type == VAL_SET or msg.type == SHARED:
            affected = []
            remCells = []
            for c in self.cells:
                if c not in msg.cells:
                    if c.remove(msg.arg):
                        dirty = True
                        remCells.append(c)
                        for n in c.nei:
                            if not n == self and not n in affected:
                                affected.append(n)
            for nei in affected:
                message = Message(REMOVED,remCells,msg.arg)
                nei.acceptMessage(message)


        if msg.type == REMOVED:
            match = self.findCellsWithCan(msg.arg)
           
            if len(match) == 1 and len(match[0].can) > 1:
                match[0].setValue(msg.arg)
                dirty = True
            elif len(match) > 1:
                # all shared neighborhoods of cells with the type that was removed
                matchNeiResult = filter(lambda n: reduce(lambda x,m: x and n in m.nei, match, True),match[0].nei)
                for result in matchNeiResult:
                    message = Message(SHARED,match,msg.arg)
                    result.acceptMessage(message)
               
                possiblePigeons = map(lambda x: (x,self.findCellsWithCan(x)), filter(lambda x: x not in self.knowns,match[0].can))
                possiblePigeons = filter(lambda (x,cells): self.contains(match,cells) and len(cells)>1, possiblePigeons)
               
               
                if len(possiblePigeons) == len(match):
                    pigeons = map(lambda (x,c):x,possiblePigeons)
                    pigeonHoles = match
                    message = Message(PIGEON,match,pigeons)
                    result.acceptMessage(message)                 
Back to top
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich
PostPosted: Fri Aug 19, 2005 11:16 am    Post subject: Reply with quote
So, when you try your program on a lot of Sudoku positions, which ones remians "unsolved" ? The answer will tell us about how good your algorithm and it's implementation is.
What is your experience?
Do you want some examples to test it?

see u,
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Daily Sudoku puzzles All times are GMT
Goto page Previous  1, 2
Page 2 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


Powered by phpBB © 2001, 2005 phpBB Group