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 1, 2  Next
 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Daily Sudoku puzzles
View previous topic :: View next topic  
Author Message
schwa
Guest





PostPosted: Thu Aug 04, 2005 11:22 pm    Post subject: Program doesn't solve it. Reply with quote

I'm writing a sudoku-solving 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 guess-and-check: I want it to solve the puzzle by pure logic. Of course, a little recursive procedure will take care of all the guess-and-check 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

PostPosted: Sat Aug 06, 2005 8:35 am    Post subject: Reply with quote

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 R5C1-C3.

... and again on R8 with the 7's
Back to top
View user's profile Send private message
schwa



Joined: 04 Aug 2005
Posts: 9

PostPosted: Mon Aug 08, 2005 11:22 pm    Post subject: Reply with quote

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 vice-versa, 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 almost-as-obvious 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
View user's profile Send private message
schwa



Joined: 04 Aug 2005
Posts: 9

PostPosted: Mon Aug 08, 2005 11:37 pm    Post subject: Reply with quote

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



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Tue Aug 09, 2005 7:29 am    Post subject: Reply with quote

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



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Tue Aug 09, 2005 7:34 am    Post subject: Reply with quote

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



Joined: 02 Aug 2005
Posts: 1

PostPosted: Tue Aug 09, 2005 8:25 am    Post subject: lookahead Reply with quote

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






PostPosted: Tue Aug 09, 2005 8:32 am    Post subject: Reply with quote

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

PostPosted: Tue Aug 09, 2005 3:07 pm    Post subject: Reply with quote

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



Joined: 04 Aug 2005
Posts: 9

PostPosted: Tue Aug 09, 2005 3:15 pm    Post subject: Reply with quote

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



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Tue Aug 09, 2005 4:08 pm    Post subject: Reply with quote

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



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Tue Aug 09, 2005 4:20 pm    Post subject: Reply with quote

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






PostPosted: Tue Aug 09, 2005 4:41 pm    Post subject: Reply with quote

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

PostPosted: Tue Aug 09, 2005 4:51 pm    Post subject: Reply with quote

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 Wink
see u,
Back to top
View user's profile Send private message
Guest






PostPosted: Tue Aug 09, 2005 5:04 pm    Post subject: Reply with quote

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 Wink
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 20-Mar-2005 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 ALL-POSSIBLE (build-list 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 (build-list 9 (lambda (x) (build-list 9 (lambda (y) (list x y)))))
                       (build-list 9 (lambda (y) (build-list 9 (lambda (x) (list x y)))))
                       (build-list 9 (lambda (box) (build-list 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
;;sudoku-solve1 is just the k=1 case of this.  I think sudoku-solve2 is equivalent to the k=8 case, too!
(define (sudoku-solvek sudoku k)
  (define (sudoku-solvek-row sudoku k row)
    (foldl (lambda (sokc s) (sudoku-solvek-set s sokc row)) sudoku (subsets row k)))
  (define (sudoku-solvek-set sudoku sokc row)
    (let ((num-in (get-nums sudoku sokc)))
      (cond
        [(> (length num-in) (length sokc)) sudoku]
        [else (let ((rest-of-row (filter (lambda (c) (not (contains? sokc c))) row)))
                (foldl (lambda (val s) (delete s val rest-of-row)) sudoku num-in))])))
  (cond
    [(= k 0) (sudoku-box-rule sudoku)]
    [else (foldl (lambda (row s) (sudoku-solvek-row s k row)) sudoku LOROWS)]))
 

(define (sudoku-box-rule 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 (sudoku-box-help sudoku lor1 lor2)
    (define (sudoku-box-help2 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))) (sudoku-box-help2 sudoku row (rest lor))]
                  [else (let ((num-in (get-nums sudoku intersection))
                              (rest-of-row (filter (lambda (c) (not (contains? intersection c))) row)))
                          (let ((num-only (foldl (lambda (c nums)
                                                   (filter (lambda (n) (not (contains? (get-spot sudoku (first c) (second c)) n)))
                                                           nums))
                                                 num-in rest-of-row)))
                            (cond
                              [(empty? num-only) (sudoku-box-help2 sudoku row (rest lor))]
                              [else (let ((rest-of-row2 (filter (lambda (c) (not (contains? intersection c))) (first lor))))
                                      (sudoku-box-help2
                                       (foldl (lambda (n s) (delete s n rest-of-row2)) sudoku num-only) row (rest lor)))])))]))]))
    (foldl (lambda (row s) (sudoku-box-help2 s row lor2)) sudoku lor1))
  (sudoku-box-help sudoku LOROWS LOROWS))


(define (sudoku-solve sudoku)
  (define (sudoku-solve-try sudoku lok)
    (cond
      [(empty? lok) (begin (display (sudoku-check sudoku)) (newline)
                           sudoku)]
      [else (let ((status (sudoku-check sudoku)))
              (cond
                [(equal? status "solved!") sudoku]
                [(equal? status "inconsistent!") sudoku]
                [else (let ((new (sudoku-solvek sudoku (first lok))))
                        (cond
                          [(equal? sudoku new) (begin (display (list "rule " (first lok) " failed"))
                                                      (sudoku-solve-try sudoku (rest lok)))]
                          [else (begin (display (list "rule " (first lok) " worked")) (newline)
                                       (sudoku-solve new))]))]))]))
  (sudoku-solve-try sudoku KTOTRY))



;;this does the backtracking/guess-and-check if the other rules are not sufficient.
(define (sudoku-recurse sudoku)
  (define (sudoku-recurse-help  sudoku x y)
    (cond
      [(= x XMAX) (sudoku-recurse-help sudoku 0 (add1 y))]
      [(= y YMAX) sudoku]
      [else
       (begin
      (display (list x y (get-spot sudoku x y)))
      (newline)
      (let ((spot (get-spot sudoku x y)))
         (cond
           [(= (length spot) 1) (sudoku-recurse-help sudoku (add1 x) y)]
           [else (begin (display (list "trying to set " (list x y) " to " (first spot))) (newline)
                        (let ((new (sudoku-solve (subst sudoku x y (list (first spot))))))
                          (let ((status (sudoku-check new)))
                            (cond
                              [(equal? status "solved!") new]
                              [(equal? status "inconsistent!") (sudoku-recurse-help (subst sudoku x y (rest spot)) 0 0)]
                              [else (sudoku-recurse-help new (add1 x) y)]))))])))]))
 
  (let ((new (sudoku-solve sudoku)))
    (let ((status (sudoku-check new)))
      (cond
        [(equal? status "solved!") new]
        [(equal? status "inconsistent!") (error 'sudoku-recurse "inconsistent grid!")]
        [else (sudoku-recurse-help new 0 0)]))))



(define (sudoku-check sudoku)
  (define (row-ok? 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? (get-spot sudoku (first c) (second c))))) row)
     (equal? (unique (quicksort (apply append (map (lambda (c) (get-spot sudoku (first c) (second c))) row)) <))
             ALL-POSSIBLE)))
  (cond
    [(andmap (lambda (row) (row-ok? sudoku row)) LOROWS)
     (cond
       [(andmap (lambda (row) (andmap (lambda (c) (= 1 (length (get-spot 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))) (get-spot 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)
  (build-vector 9 (lambda (y)
                  (build-vector 9 (lambda (x)
                                  (let ((spot (get-spot grid x y)))
                                     (cond
                                       [(or (empty? spot) (= 0 spot)) ALL-POSSIBLE]
                                       [(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 (vector-length vv))
        (XMAX (vector-length (vector-ref vv 0))))
    (cond
      [(or (>= y YMAX) (>= x XMAX)) (error 'subst "cannot set beyond end of vector")]
      [else (build-vector YMAX (lambda (yc)
                                 (cond
                                   [(= y yc) (build-vector XMAX (lambda (xc)
                                                                  (cond
                                                                    [(= x xc) new]
                                                                    [else (vector-ref (vector-ref vv yc) xc)])))]
                                   [else (vector-ref vv yc)])))])))

(define (get-spot vv x y)
  (vector-ref (vector-ref vv y) x))

(define (get-nums sudoku loc)
  (unique (quicksort (apply append (map (lambda (c) (get-spot 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

PostPosted: Tue Aug 09, 2005 7:10 pm    Post subject: Reply with quote

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



Joined: 04 Aug 2005
Posts: 9

PostPosted: Tue Aug 09, 2005 7:34 pm    Post subject: Reply with quote

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 (sudoku-solve ...) which solves using logic only, and (sudoku-recurse ...) 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
View user's profile Send private message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Tue Aug 09, 2005 9:00 pm    Post subject: Reply with quote

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 (sudoku-solve ...) which solves using logic only, and (sudoku-recurse ...) 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 stuck-position!
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
View user's profile Send private message
schwa



Joined: 04 Aug 2005
Posts: 9

PostPosted: Tue Aug 09, 2005 9:10 pm    Post subject: Reply with quote

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






PostPosted: Wed Aug 10, 2005 2:07 am    Post subject: Reply with quote

Y'all need to get a life!!!! Very Happy Very Happy Very Happy Very Happy

Interesting stuff!!!!!

M
Back to top
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Daily Sudoku puzzles 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


Powered by phpBB © 2001, 2005 phpBB Group