View previous topic :: View next topic 
Author 
Message 
schwa Guest

Posted: Thu Aug 04, 2005 11:22 pm Post subject: Program doesn't solve it. 


I'm writing a sudokusolving program.
It so far has only TWO rules, though one is pretty broad and general. Pretty much all the easy and medium puzzles, and some hard ones are beaten by my first rule. The hard ones, and most of the very hard ones, are solved by my second rule.
I'm trying to avoid doing ANY guessandcheck: I want it to solve the puzzle by pure logic. Of course, a little recursive procedure will take care of all the guessandcheck you could want.
But on the march 20th puzzle, my solver gets stuck at
Code: 
1 378 3678 9 2 35 34568 3568 348
5 2 4 368 1 7 368 368 9
3689 389 3689 3568 568 4 2 7 1
3679 5 3679 346 469 8 1 36 2
3689 389 3689 1 569 2 47 3568 47
4 1 2 7 56 35 3568 9 38
238 6 358 2458 458 9 378 1 378
278 78 1 28 3 6 9 4 5
389 4 3589 58 7 1 38 2 6

(I hope that format is readable  if not, let me know and I'll repost it in another format).
Any suggestions as to what my poor program's next step ought to be? I don't see any good rules, myself.
Thank you,
Joshua Zucker 

Back to top 


Steve
Joined: 04 Aug 2005 Posts: 3 Location: Leicester

Posted: Sat Aug 06, 2005 8:35 am Post subject: 


The next move is to look at the 5's in R3. The only 5's are in the middle box hence you can elimiate all 5's in the top middle box that are not on R3.
This eliminates the 5 in R1C6 thus leaving it to be a 3.
A similar principle can be applied to the 7's in R4. The must be in the left box thus eliminating the 7's in R5C1C3.
... and again on R8 with the 7's 

Back to top 


schwa
Joined: 04 Aug 2005 Posts: 9

Posted: Mon Aug 08, 2005 11:22 pm Post subject: 


Thanks Steve!
I thought I had coded that rule as my rule 2: I call it the "box rule", that if a row intersects a box, and a certain digit only appears as a possibility in the intersection but nowhere else in the row, then delete that digit as a possibility from the rest of the box (and viceversa, with "box" and "row" switched).
My rule 1 is: If in any given row (or column or box), there is a set of n cells that, among them, have at most n digits possible, then delete those n digits from the possibilities in the rest of the row (or column or box). n = 1 is the obvious statement that if a cell is, say, a 5, delete the 5s from the rest of that row or column. n = 8 is the almostasobvious statement that if a 5 appears in only one place in a row, then that cell must be a 5 (all the other 8 digits would be deleted from that box).
I run rule 1, with n = 1, 8, 2, 7, 3, 6, 4, 5, and then the (apparently buggy!) box rule.
Between those two rules, I've been able to solve everything ... I think. Better debug that box rule!
My goal is to solve every sudoku puzzle without ever having to do lookahead or backtracking, just purely logical rules.
Again, thanks for the help: looks like you helped me find a bug in my code for the box rule.
Joshua Zucker aka schwa 

Back to top 


schwa
Joined: 04 Aug 2005 Posts: 9

Posted: Mon Aug 08, 2005 11:37 pm Post subject: 


Indeed, there was a (in hindsight obvious!) bug in the "box rule".
Now, with the two rules I mentioned in the previous post, there's not a sudoku I've found that can't be solved. In fact, I've only ever had to use the 1, 8, 2, 7, and box rules.
Does anyone have a REALLY HARD sudoku that they think might not succumb to this approach?
Thanks,
Joshua Zucker 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Tue Aug 09, 2005 7:29 am Post subject: 


Hi,
Here is a real hard one:
043080250
600000000
000001094
900004070
000608000
010200003
820500000
000000005
034090710
My program could find only 11 new numbers (only "logic", no try and error).
How good is yours? 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Tue Aug 09, 2005 7:34 am Post subject: 


Here an additional one to compare our programs:
020000000
000600003
074080000
000003002
080040010
600500000
000010780
500009000
000000040
For this one it has found "only" 8 numbers.
We can exchange details like: final position, traces, etc. 

Back to top 


jimn
Joined: 02 Aug 2005 Posts: 1

Posted: Tue Aug 09, 2005 8:25 am Post subject: lookahead 


I have found that the very difficult sudokus cannot be solved determinatively. you must look ahead. Ive seen a couple where it was necessary to make two such decisions to get the solution.
It depends on the limiting rules that the puzzle setter uses. I would suppose it is possible to set a puzzle which does have a solution where no part of the answer may be logically derived. Its an interesting proposition anyway.
JIMN 

Back to top 


Guest

Posted: Tue Aug 09, 2005 8:32 am Post subject: 


So, what is your program produce as output for the 2 above mentioned Sudoku positions? Is it not giving any output? At least how much he could solve  this is what I would expect.
I will start. For the first one, here is up to which it could be solved, without the "look ahead" algorithm. Only with "logic":
Final SuDoku Table
0 4 3 9 8 0 2 5 0
6 0 0 4 2 5 0 0 0
2 0 0 0 0 1 0 9 4
9 0 0 0 0 4 0 7 0
3 0 0 6 0 8 0 0 0
4 1 0 2 0 9 0 0 3
8 2 0 5 0 0 0 0 0
0 0 0 0 4 0 0 0 5
5 3 4 8 9 0 7 1 0 

Back to top 


schwa
Joined: 04 Aug 2005 Posts: 9

Posted: Tue Aug 09, 2005 3:07 pm Post subject: 


For the first one, my program gives
Code: 
17 4 3 9 8 67 2 5 167
6 789 1789 4 2 5 138 38 178
2 578 578 37 36 1 68 9 4
9 568 2568 13 135 4 1568 7 1268
3 47 257 6 157 8 49 24 129
4 1 5678 2 57 9 568 68 3
8 2 17 5 16 367 49 346 69
17 69 69 17 4 23 38 238 5
5 3 4 8 9 26 7 1 26

So it looks like it gets just as far as you expected.
I still think there must be more rules we can establish  maybe they will turn out to be in some sense equivalent to looking ahead, but I want to find a way to program it without backtracking.
If you add just one given bit of information  say that the top left is a 1  then it is solved easily. So it does only take one guess. And if the top left is a 7, then it's inconsistent.
Anyone have any ideas on what to do with the above grid? Any rules that might work for me to program?
Thanks,
Joshua Zucker aka schwa 

Back to top 


schwa
Joined: 04 Aug 2005 Posts: 9

Posted: Tue Aug 09, 2005 3:15 pm Post subject: 


someone_somewhere wrote:  Here an additional one to compare our programs:
020000000
000600003
074080000
000003002
080040010
600500000
000010780
500009000
000000040
For this one it has found "only" 8 numbers.
We can exchange details like: final position, traces, etc. 
For this one, my program used the "n=7" rule a whole bunch of times, more than I've ever seen it used on any other grid. That rule says, effectively, that if there are two numbers (say 5 and 6) that are only possible in two cells in a row (or column or box), then those two numbers can be eliminated from the possibilities in the rest of that row.
But my program still couldn't quite get to the end.
It got stuck at
Code: 
13 2 6 349 35 7 149 59 8
8 9 5 6 2 14 14 7 3
13 7 4 39 8 15 1269 259 169
4 5 7 1 9 3 8 6 2
9 8 3 2 4 6 5 1 7
6 1 2 5 7 8 39 39 4
2 36 9 34 1 45 7 8 56
5 4 8 7 36 9 1236 23 16
7 36 1 8 356 2 369 4 569

Again, any ideas about what to do other than guess/check?
Joshua Zucker
[/code] 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Tue Aug 09, 2005 4:08 pm Post subject: 


I suppose that you have "typed by hand" the following:
17 4 3 9 8 67 2 5 167
6 789 1789 4 2 5 138 38 178
2 578 578 37 36 1 68 9 4
9 568 2568 13 135 4 1568 7 1268
3 47 257 6 157 8 49 24 129
4 1 5678 2 57 9 568 68 3
8 2 17 5 16 367 49 346 69
17 69 69 17 4 23 38 238 5
5 3 4 8 9 26 7 1 26
because you have a typing mistake!
In column 2 row 1 you have "4"
and in column 2 row 5 have "47".
Your program was finding (I hope) "57" instead of "47"!
P.S. my program did the same, with the above mentioned exception. 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Tue Aug 09, 2005 4:20 pm Post subject: 


Hi Joshua,
For the:
13 2 6 349 35 7 149 59 8
8 9 5 6 2 14 14 7 3
13 7 4 39 8 15 1269 259 169
4 5 7 1 9 3 8 6 2
9 8 3 2 4 6 5 1 7
6 1 2 5 7 8 39 39 4
2 36 9 34 1 45 7 8 56
5 4 8 7 36 9 1236 23 16
7 36 1 8 356 2 369 4 569
my program found the same.
So, it looks to me that we are both stucked at the same level and point.
At the moment I have no additional idea for "logical" algorithm.
Probably we need a "look ahead" because the lemon was squized at the limit.
One more test. Is your program solving this one:
0 0 2 0 0 0 1 9 8
0 4 0 0 9 0 0 3 6
3 0 0 0 0 0 0 0 4
0 0 0 0 7 3 0 4 0
0 0 0 1 0 6 0 0 0
0 8 0 2 5 0 0 0 0
8 0 0 0 0 0 0 0 3
9 3 0 0 2 0 0 5 0
1 6 4 0 0 0 9 0 0 

Back to top 


Guest

Posted: Tue Aug 09, 2005 4:41 pm Post subject: 


someone_somewhere wrote:  Hi Joshua,
this one:
0 0 2 0 0 0 1 9 8
0 4 0 0 9 0 0 3 6
3 0 0 0 0 0 0 0 4
0 0 0 0 7 3 0 4 0
0 0 0 1 0 6 0 0 0
0 8 0 2 5 0 0 0 0
8 0 0 0 0 0 0 0 3
9 3 0 0 2 0 0 5 0
1 6 4 0 0 0 9 0 0 
Code: 
(vector
(vector (list 6) (list 7) (list 2) (list 3) (list 4) (list 5) (list 1) (list 9) (list 8))
(vector (list 5) (list 4) (list 8) (list 7) (list 9) (list 1) (list 2) (list 3) (list 6))
(vector (list 3) (list 9) (list 1) (list 8) (list 6) (list 2) (list 5) (list 7) (list 4))
(vector (list 2) (list 1) (list 6) (list 9) (list 7) (list 3) (list 8) (list 4) (list 5))
(vector (list 4) (list 5) (list 9) (list 1) (list 8) (list 6) (list 3) (list 2) (list 7))
(vector (list 7) (list 8) (list 3) (list 2) (list 5) (list 4) (list 6) (list 1) (list 9))
(vector (list 8) (list 2) (list 5) (list 4) (list 1) (list 9) (list 7) (list 6) (list 3))
(vector (list 9) (list 3) (list 7) (list 6) (list 2) (list 8) (list 4) (list 5) (list 1))
(vector (list 1) (list 6) (list 4) (list 5) (list 3) (list 7) (list 9) (list 8) (list 2)))

Yup, it solves it!
And you can see why I type by hand the output: I haven't bothered writing good output formatting for my program (written in PLT Scheme) so the output looks like this if I don't edit it. Someday I shall fix that. Right now I want a better algorithm!
Joshua 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Tue Aug 09, 2005 4:51 pm Post subject: 


Ok Joshua, you are good. You are very good.
One more question: how many line of codes has your program, how much time it takes to execute and how much time it took you to write it?
(you see it is only one question
see u, 

Back to top 


Guest

Posted: Tue Aug 09, 2005 5:04 pm Post subject: 


someone_somewhere wrote:  Ok Joshua, you are good. You are very good.
One more question: how many line of codes has your program, how much time it takes to execute and how much time it took you to write it?
(you see it is only one question
see u, 
Well, my father started working on some of the ideas, we spent some time talking about it. Then it took me an afternoon to write it, and another hour or so to find and fix the bug in the box rule.
Scheme is, in my opinion, a good language for making programs easy and fast to write and debug, but it's not so fast to execute. In fact I haven't even bothered compiling it! It just runs interpreted. On my 700 MHz eMac here, it takes about 6 cpu seconds to solve a very hard one like 20Mar2005 here on this site, 14.5 cpu seconds to solve your extremely hard one from that last post.
As for how many lines of code it has, here's the whole program for your enjoyment.
Code: 
(define XMAX 9)
(define YMAX 9)
(define ALLPOSSIBLE (buildlist 9 (lambda (n) (add1 n))))
(define KTOTRY (list 1 8 2 0 7 3 6 4 5)) ;;order in which to try the rules, probably doesn't really matter. 0 is the box rule.
;list of all the rows/columns/boxes. a row is a list of 9 pairs, representing the 9 coords in that row.
(define LOROWS (append (buildlist 9 (lambda (x) (buildlist 9 (lambda (y) (list x y)))))
(buildlist 9 (lambda (y) (buildlist 9 (lambda (x) (list x y)))))
(buildlist 9 (lambda (box) (buildlist 9 (lambda (cell)
(list (+ (* 3 (quotient box 3)) (quotient cell 3))
(+ (* 3 (remainder box 3)) (remainder cell 3)))))))))
;;if a set of k cells contains, in their union, only k numbers, then no other places in the row can be those k numbers
;;sudokusolve1 is just the k=1 case of this. I think sudokusolve2 is equivalent to the k=8 case, too!
(define (sudokusolvek sudoku k)
(define (sudokusolvekrow sudoku k row)
(foldl (lambda (sokc s) (sudokusolvekset s sokc row)) sudoku (subsets row k)))
(define (sudokusolvekset sudoku sokc row)
(let ((numin (getnums sudoku sokc)))
(cond
[(> (length numin) (length sokc)) sudoku]
[else (let ((restofrow (filter (lambda (c) (not (contains? sokc c))) row)))
(foldl (lambda (val s) (delete s val restofrow)) sudoku numin))])))
(cond
[(= k 0) (sudokuboxrule sudoku)]
[else (foldl (lambda (row s) (sudokusolvekrow s k row)) sudoku LOROWS)]))
(define (sudokuboxrule sudoku)
;;looks at intersections of pairs of rows, if size > 1 then
;;looks to see if a number occurs in row1 only in the intersection, and if so,
;;deletes that number from the remainder of row2.
(define (sudokuboxhelp sudoku lor1 lor2)
(define (sudokuboxhelp2 sudoku row lor) ;;called with only one row from lor1, iterates through lor2 with it
(cond
[(empty? lor) sudoku]
[else (let ((intersection (filter (lambda (c) (contains? row c)) (first lor))))
(cond
[(or (<= (length intersection) 1) (equal? intersection (first lor))) (sudokuboxhelp2 sudoku row (rest lor))]
[else (let ((numin (getnums sudoku intersection))
(restofrow (filter (lambda (c) (not (contains? intersection c))) row)))
(let ((numonly (foldl (lambda (c nums)
(filter (lambda (n) (not (contains? (getspot sudoku (first c) (second c)) n)))
nums))
numin restofrow)))
(cond
[(empty? numonly) (sudokuboxhelp2 sudoku row (rest lor))]
[else (let ((restofrow2 (filter (lambda (c) (not (contains? intersection c))) (first lor))))
(sudokuboxhelp2
(foldl (lambda (n s) (delete s n restofrow2)) sudoku numonly) row (rest lor)))])))]))]))
(foldl (lambda (row s) (sudokuboxhelp2 s row lor2)) sudoku lor1))
(sudokuboxhelp sudoku LOROWS LOROWS))
(define (sudokusolve sudoku)
(define (sudokusolvetry sudoku lok)
(cond
[(empty? lok) (begin (display (sudokucheck sudoku)) (newline)
sudoku)]
[else (let ((status (sudokucheck sudoku)))
(cond
[(equal? status "solved!") sudoku]
[(equal? status "inconsistent!") sudoku]
[else (let ((new (sudokusolvek sudoku (first lok))))
(cond
[(equal? sudoku new) (begin (display (list "rule " (first lok) " failed"))
(sudokusolvetry sudoku (rest lok)))]
[else (begin (display (list "rule " (first lok) " worked")) (newline)
(sudokusolve new))]))]))]))
(sudokusolvetry sudoku KTOTRY))
;;this does the backtracking/guessandcheck if the other rules are not sufficient.
(define (sudokurecurse sudoku)
(define (sudokurecursehelp sudoku x y)
(cond
[(= x XMAX) (sudokurecursehelp sudoku 0 (add1 y))]
[(= y YMAX) sudoku]
[else
(begin
(display (list x y (getspot sudoku x y)))
(newline)
(let ((spot (getspot sudoku x y)))
(cond
[(= (length spot) 1) (sudokurecursehelp sudoku (add1 x) y)]
[else (begin (display (list "trying to set " (list x y) " to " (first spot))) (newline)
(let ((new (sudokusolve (subst sudoku x y (list (first spot))))))
(let ((status (sudokucheck new)))
(cond
[(equal? status "solved!") new]
[(equal? status "inconsistent!") (sudokurecursehelp (subst sudoku x y (rest spot)) 0 0)]
[else (sudokurecursehelp new (add1 x) y)]))))])))]))
(let ((new (sudokusolve sudoku)))
(let ((status (sudokucheck new)))
(cond
[(equal? status "solved!") new]
[(equal? status "inconsistent!") (error 'sudokurecurse "inconsistent grid!")]
[else (sudokurecursehelp new 0 0)]))))
(define (sudokucheck sudoku)
(define (rowok? sudoku row) ;;union of everything in the row must have 1 thru 9 in it, and no impossible cells.
(and
(andmap (lambda (c) (not (empty? (getspot sudoku (first c) (second c))))) row)
(equal? (unique (quicksort (apply append (map (lambda (c) (getspot sudoku (first c) (second c))) row)) <))
ALLPOSSIBLE)))
(cond
[(andmap (lambda (row) (rowok? sudoku row)) LOROWS)
(cond
[(andmap (lambda (row) (andmap (lambda (c) (= 1 (length (getspot sudoku (first c) (second c))))) row)) LOROWS)
"solved!"]
[else "not done yet"])]
[else "inconsistent!"]))
(define (delete sudoku val locells)
(cond
[(empty? locells) sudoku]
[else (let ((x (first (first locells)))
(y (second (first locells))))
(delete (subst sudoku x y (filter (lambda (n) (not (= n val))) (getspot sudoku x y)))
val
(rest locells)))]))
;;boring utility functions from here on.
;;a sudoku is a 9x9 vector of lists of 1 through 9 elements, representing the possibilities for that spot.
;;a grid is a much more convenient vector with 0s representing unknown spots and digits representing known spots. So this utility function lets you type in grids more easily.
(define (grid>sudoku grid)
(buildvector 9 (lambda (y)
(buildvector 9 (lambda (x)
(let ((spot (getspot grid x y)))
(cond
[(or (empty? spot) (= 0 spot)) ALLPOSSIBLE]
[(list? spot) spot]
[else (list spot)])))))))
(define (contains? l item)
(cond
[(empty? l) false]
[(equal? (first l) item) true]
[else (contains? (rest l) item)]))
(define (subst vv x y new)
(let ((YMAX (vectorlength vv))
(XMAX (vectorlength (vectorref vv 0))))
(cond
[(or (>= y YMAX) (>= x XMAX)) (error 'subst "cannot set beyond end of vector")]
[else (buildvector YMAX (lambda (yc)
(cond
[(= y yc) (buildvector XMAX (lambda (xc)
(cond
[(= x xc) new]
[else (vectorref (vectorref vv yc) xc)])))]
[else (vectorref vv yc)])))])))
(define (getspot vv x y)
(vectorref (vectorref vv y) x))
(define (getnums sudoku loc)
(unique (quicksort (apply append (map (lambda (c) (getspot sudoku (first c) (second c))) loc)) <)))
(define (unique l)
(cond
[(empty? l) l]
[(empty? (rest l)) l]
[(equal? (first l) (second l)) (unique (rest l))]
[else (cons (first l) (unique (rest l)))]))
(define (subsets l k)
(cond
[(= k 0) (list empty)]
[(< (length l) k) empty]
[(= (length l) k) (list l)]
[else (append
(map (lambda (al) (cons (first l) al)) (subsets (rest l) (sub1 k)))
(subsets (rest l) k))]))

Joshua Zucker 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Tue Aug 09, 2005 7:10 pm Post subject: 


Hi Joshua,
Thank you. It was a please to meet you.
There is always someone better than me.
I know it from the time I played chess, in the club.
You developed the program quicker, because you used a better language.
From the point of view, of the execution, it does not matter. It could be the same if you compile it.
From the point of view of the algorithm, it looks like we are on the same lavel. Both programs, yours and my, are solving what can be solved without using a "look ahead" technique (I am almost sure).
At least I have tested it on about 200 hardest, very hard and fiendish positions.
I done math at Uni and work now with software.
I can give you an other problem to think about it.
If you are interested.
my email: andrei.stoffel@gmail.com
P.S. I think that we got to the end of the rope with SuDoku. The rest to program a "look ahead" is only a matter of an excercise.
The challange could now be to generate "fiendish" positions.
A open question remains: "how difficult" is a position? If we answer to it, we could get to the next step for generation.
I have an idea about an answer. What's your point of view?
see u,
Andrei Stoffel 

Back to top 


schwa
Joined: 04 Aug 2005 Posts: 9

Posted: Tue Aug 09, 2005 7:34 pm Post subject: 


someone_somewhere wrote: 
Both programs, yours and my, are solving what can be solved without using a "look ahead" technique (I am almost sure).

I have a feeling that there are still more ideas out there of how to analyze these very difficult positions.
Quote: 
P.S. I think that we got to the end of the rope with SuDoku. The rest to program a "look ahead" is only a matter of an excercise.

The program I gave has (sudokusolve ...) which solves using logic only, and (sudokurecurse ...) which does as much as it can using logic, then tries guess/check/backtrack.
Quote: 
The challange could now be to generate "fiendish" positions.

Yes, that would be an interesting project: a program to generate very difficult positions.
Quote: 
A open question remains: "how difficult" is a position? If we answer to it, we could get to the next step for generation.
I have an idea about an answer. What's your point of view?

Oooh, that's a tough one.
How about "average number of possibilities per spot" after doing a first pass of cleaning out the obvious impossibilities (where that digit is already present in the row/column/box)?
Another good one, with my rule set, is how many times it needs to invoke the "tricky" rules (box, n=2, n=7). The n=1 and n=8 rules are sort of "trivial" by comparison.
Then, of course, there's the puzzles that aren't solvable with the current rules at all! I have no really good idea of how to measure their difficulty, except by how much guessing and backtracking is necessary. Your puzzles were all solved by guessing in just the top left spot.
Thanks for the ideas, the tough puzzles, and above all the fun discussion!
I still want to find out how to solve your hardest ones without making that one guess.
Joshua 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Tue Aug 09, 2005 9:00 pm Post subject: 


schwa wrote:  someone_somewhere wrote: 
Both programs, yours and my, are solving what can be solved without using a "look ahead" technique (I am almost sure).

I have a feeling that there are still more ideas out there of how to analyze these very difficult positions.
Tell me when you have got to something more than the feeling.
Quote: 
P.S. I think that we got to the end of the rope with SuDoku. The rest to program a "look ahead" is only a matter of an excercise.

The program I gave has (sudokusolve ...) which solves using logic only, and (sudokurecurse ...) which does as much as it can using logic, then tries guess/check/backtrack.
Yup. That what I meant. I have only the first part.
Quote: 
The challange could now be to generate "fiendish" positions.

Yes, that would be an interesting project: a program to generate very difficult positions.
Quote: 
A open question remains: "how difficult" is a position? If we answer to it, we could get to the next step for generation.
I have an idea about an answer. What's your point of view?

Oooh, that's a tough one.
How about "average number of possibilities per spot" after doing a first pass of cleaning out the obvious impossibilities (where that digit is already present in the row/column/box)?
The cleaning  I call the "exclude" of a number for a cell. Meaning that it can not be there. Than the process of "excluding" has 2 phases:
1. the, let's call them direct excludes. You called them "obvious impossibilities".
2. the, let's call them indirect excludes. I have analysed this kind of excludes and think that I have found them all.
So, trying to solve a position (without a program) you will tend to use (because of the optic) only the first category, and only when you don't find a number, you will have to start thinking about the second category.
What about getting to evaluate a position with a single number, something like the entropy ?!
If you know the game mastermind, you will have to select the question that induces the minimum entropy, or in other words, gets the maximum of information, independent of the oponents response.
Another good one, with my rule set, is how many times it needs to invoke the "tricky" rules (box, n=2, n=7). The n=1 and n=8 rules are sort of "trivial" by comparison.
Here I can't follow you.
Then, of course, there's the puzzles that aren't solvable with the current rules at all! I have no really good idea of how to measure their difficulty, except by how much guessing and backtracking is necessary. Your puzzles were all solved by guessing in just the top left spot.
For the second part, and relative good Sidoku solver, can "see" that they got to the point where there is no more "logical" number to be set, we need a different/similar ?! way to evaluate the difficulty of the position.
Thanks for the ideas, the tough puzzles, and above all the fun discussion!
I still want to find out how to solve your hardest ones without making that one guess.
Notify me, when you got only ONE more number from the stuckposition!
That will be great. All my intuition, feeling and calculations tell me the same: "the end of the rope", for which I do not have a mathematical prove.
But, we are still young.
see u,
Joshua 


Back to top 


schwa
Joined: 04 Aug 2005 Posts: 9

Posted: Tue Aug 09, 2005 9:10 pm Post subject: 


For the difficulty:
Entropy would be the log of the product of the number of possibilities for each square. That would be a fine measure. The question is, when to measure it? Certainly you should do the "obvious" cleaning, but should you use any more difficult rules first?
I think it might be best to just measure after the obvious cleaning. Some of the easy puzzles then are already solved!
Also you ask about my other measures.
The most obvious rules look at only one cell, or one number at a time.
The harder rules look at the intersection of a row and box, or they look at sets of two or three cells in a row, or sets of two or three numbers in a row.
So it might be good to measure the difficulty by the number of times those harder rules have to be used.
Joshua 

Back to top 


Guest

Posted: Wed Aug 10, 2005 2:07 am Post subject: 


Y'all need to get a life!!!!
Interesting stuff!!!!!
M 

Back to top 




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
