dailysudoku.com

[schwa]

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

[Steve]

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

[schwa]

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" xx).

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

[schwa]

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

[someone_somewhere]

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?

[someone_somewhere]

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.

[jimn]

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

[Guest]

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

[schwa]

For the first one, my program gives

[schwa]

[someone_somewhere]

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.

[someone_somewhere]

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

[Guest]

[someone_somewhere]

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,

[Guest]

[someone_somewhere]

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

[schwa]

[someone_somewhere]

[schwa]

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

[Guest]

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

Interesting stuff!!!!!

M