The New Sudoku Players' Forum

[gsf]

For your crasy grid I regard.
It seems that the problem is in sample sudoku
It must use a bad recursive method(PERHAPS)

it was your crazy grids from a previous post
I said it had many solutions because I feared it might be counting the number of atoms in my cpu chip

if a program goes haywire the top three things to check are
(1) the input
(2) the program
(3) the task

in this case neither the input nor the program is bad
in this case the task is unreasonable with respect to human lifespan
the program will just take a long time to count many solutions

now, knowing this, the programmer may look at the problem differently
if the count is all that's necessary then each solution need not be generated to be counted
(the two programs cited count solutions by solving, but that's ok, they are tasked to solve)
this observation is where isomorphism and permutation groups stepped in and made it possible
to count all completed sudoku grids without generating each and every one

papy, you seem to be hooked on using counting to detect puzzle differences
I gave a hint that looking at candidate grids may be a good place to start
this will work sometimes, but not in all cases
(this means: don't use counting to prove isomorphism)
for these two puzzles (posted by you from gordon's 17's)

Code: Select all

.......81.3.2..............1.8.6..4....7..3..6........5..3..7...9....2......1....
.......81.3.2..............1.8.6..4....9..3..6........5..3..7...7....2......1....


the number of pencilmark grid cells with i candidates (not counting clues), 1<=i<=9 is

Code: Select all

0.2.4.20.21.10.6.1.0
0.2.4.18.21.12.6.1.0


and the number of pencilmark grid cells with candidate i is

Code: Select all

17.32.18.49.49.36.32.31.47
17.32.18.49.49.36.35.31.48


in the second case, if 7 and 9 were interchangeable up to isomorphism,
the 7th and 9th entries above would also have to be interchanged

[Papy]

It seems that I have not well understood or well explaiubn my idea:
I well nte that the grid is a BAD grid and IOT IS aa grid generate my by soft.
Sorry that it make creazy Simple sudoku

For the bug analyse I agree but the problem is Simple Sudoku become creazy: what it means?

The input valid (no bad caracteres and a firt control give a goog clues repartition.

Now this puzzle have multi solutiuon. It seems that it is during this calcul that the soft become creazy. Why ? Because you have many solutions?
I use solvers find on the web and sometimes the time to solve increase: more thanon night (pIV 2GHtz)!

I think that in parrticular case the moidule to generate and controle the multi solution is wrong. But is normal to a software to have bugs.:
A software without bugs does not exist , you have only softaware wihth well hiden bugs!

For me no mater my Boris Sudoku have bugs and you show them. I try to correct them. I thing that there are more bug in Windows that in Simple Sudoku or Boris! That don't means that the M$ programmer azre bad!!!

How the software detremine that a grid have one solution. Is perhaps here that is the problem

Could youplease end me multi solution grid WITH THE NUMBER of solution please

Papy

[Papy]

What do you exactely call pencilsmarks? I don't understand

Code: Select all

0.2.4.20.21.10.6.1.0
0.2.4.18.21.12.6.1.0
 

I Have stop the control of the position clues.
I work on morph and how to detect isomorphisme
I am stopped at the sample that I give Ihey are different but I don't know hox to proove it(with my computer!)
(I dont find the link to load your solver )

Papy

[Papy]

I think that I found why this grid make your solver crazy

The first block have no clues so the software have to make speculartion on 27 cells 9 times. 9^27
if you just inverse the grid all is OK

.................................1.7.12.........16..9.9..8....1..8..4.3...4..68.9
9.86..4...3.4..8..1....8..9.9..61.........21.7.1.................................

I keep the sample: good for testing recursing!!!!

Papy

[gsf]

I think that I found why this grid make your solver crazy

sigh

looking backwards or forwards makes no difference
there will still be the same number of solutions
in this case its too large for a program to generate and count each one
its not due to a bad or inefficient backtracking solver
its due to a problem mismatch
there are some problems that are too large to count every instance
this is one of those problems

but that does not mean we can't count
it just means that we need a different counting tool
for instance, molecular weight in chemistry allows us to get a close estimate
on the number of molecules in a blob of stuff
one person with an electron microscope and very tiny tweezers would need
10^umpteenth lifetimes to do the same estimate

I'm done here
use search on the programmer's and player's forums
the answers to almost all of your questions in this thread are there

[udosuk]

Reversing the clues... What a brilliant idea! I just don't want any more labouring work on my precious little CPU chips wasted on a multiple-solutional sudoku puzzle (aka pseudoku)...

What do you exactely call pencilsmarks? I don't understand

Code: Select all

0.2.4.20.21.10.6.1.0
0.2.4.18.21.12.6.1.0
 

That means, on each puzzle with the initial clues, you can do the most basic elimination - for each given clue the same number cannot appear in the same row/column/box... Now you have a basic idea of how many possible candidates (pencilmarks) appear in each of the 81 cell. In fact I think the 2 lists given aren't right - the first elements should be 17 not 0 (17 given clues). So basically, the first gird has 17 cells with 1 candidate, 2 cells with 2 candidates, 4 cells with 3 candidates, 20 cells with 4 candidates, etc... Checking the sums:

Code: Select all

17+2+4+20+21+10+6+1+0=81
17+2+4+18+21+12+6+1+0=81

So the 2 puzzles must be essentially different, because the first has 20 4-candidate cells and 10 6-candidate cells, while the 2nd has 18 & 12 respecively...

But be careful - even if the 2 puzzles has the same such list, they could still be essentially different.

And gsf has given another method - checking how many cells each candidate appears (e.g. 1 appears in 17 cells, 2 appears in 32 cells, etc)...

[udosuk]

.................................1.7.12.........16..9.9..8....1..8..4.3...4..68.9
9.86..4...3.4..8..1....8..9.9..61.........21.7.1.................................

And to add - why this puzzle couldn't give a unique solution is obvious without the need for a proof - it has a whole empty band (r789). If you have a solution, you could just get 5 more different solutions by exchanging 2 of the 3 bottom rows...

If you have taken the time to read some of the threads quoted here you would not make such a mistake... I like your enthusiasm but it seems you need to spend a bigger effort to research what has been done before you ask others to help you... Another source I want to give you is this wikipedia page:

http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

If you don't want to spend an hour or two studying these information you can't blame others for not wanting to help you - the communication gap is simply too big...

[gsf]

In fact I think the 2 lists given aren't right - the first elements should be 17 not 0 (17 given clues).

ok, one more post here for udosuk
I looked at this too and thought it was a bug
but there are some puzzles where a pencilmark grid will have
one candidate in a non-clue cell and I wanted to differentiate those from the clue cells
that's why I qualified it with (not counting clues)

But be careful - even if the 2 puzzles has the same such list, they could still be essentially different.

this apparently cannot be emphasized enough
I almost didn't post counting arguments because of that

[udosuk]

Yes, I realised it right after I posted the above reply... Some puzzles do have initial naked singles... Especially if symmetry is required...

But it just bugs me to see the list doesn't sum to 81! Perhaps we should do this:

Code: Select all

(17+)0+2+4+20+21+10+6+1+0=81
(17+)0+2+4+18+21+12+6+1+0=81

[Papy]

It's not because I have an other approche of the Sudoiku that your or my approch are bad.
What you call a brute force for example is not a brute force!
The recursive algoi is not a Brurte Force technique.
Or the implementation in the sudoku.

Using a real brute force like in my software alxways finds all solutios.
Reversing the grid is not a dream and make the solver find the first solution more quiclly because clues are at the beginning but of course to compute all te solutions the time is the same.
But the problem is not to compute all the solutions but to say : unique ot multiply solutions. So it's faster to have the clues at the top

My theory , at this time, doesn't permit to create 17 sudokus valid
But do yo knowtaht that on a 17 clues grid you have only 35 repartitions available for the column, the row , the box?

With the 5.4 billions of grid we have only 10000 DISPOSITIONS differents the 25000 other are only value arrangement.
Why 35? Why this ones? Why not the same for the value repartitions.

I just ask for morphs recoize algo. You don'rt have . No matter I look on other sites. If someone have found how to do other people will find!

If you want, a day, I explain you my brute force: but it's not a traditionnal algo
You know, us, the freenchies, like to write our own algo specialy when other peopledon't want to explain us...

Wait...
Papy

[Papy]

Thanks for the link on the Mathematiques of Sudoku
I have consulted wikipedia but this article doesn't existe on the french version. It is a pety informatiuon are numerus!!!

[udosuk]

Have you taken a look at this?

http://fr.wikipedia.org/wiki/Sudoku

Also, this:

http://babelfish.altavista.com/babelfish/trurl_pagecontent?lp=en_fr&url=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMathematics_of_Sudoku

Wait a minute on the above link for the translation process...

[Papy]

I know the french version and the professoir of informatique!
But no mathematical explications!
Sudoku just arrive in France(some moinths) So we have to get all the 'culture'
I still not understand

0.2.4.20.21.10.6.1.0
0.2.4.18.21.12.6.1.0

You say that it is the number of pencils marks .
For a row, a column, a box
In a grid it's the same for row,box, column?
Papy

[udosuk]

For this puzzle:

Code: Select all

.......81.3.2..............1.8.6..4....7..3..6........5..3..7...9....2......1....

If you have the Simple Sudoku program, you could load the puzzle into it and it would generate the following pencilmark grid:

Code: Select all

 *--------------------------------------------------------------------------------*
 | 2479    24567   245679   | 4569    34579   345679   | 4569    8       1        |
 | 4789    3       145679   | 2       45789   1456789  | 4569    5679    45679    |
 | 24789   1245678 1245679  | 145689  345789  13456789 | 4569    235679  2345679  |
 |--------------------------+--------------------------+--------------------------|
 | 1       257     8        | 59      6       2359     | 59      4       2579     |
 | 249     245     2459     | 7       24589   124589   | 3       12569   25689    |
 | 6       2457    234579   | 14589   234589  1234589  | 1589    12579   25789    |
 |--------------------------+--------------------------+--------------------------|
 | 5       12468   1246     | 3       2489    24689    | 7       169     4689     |
 | 3478    9       13467    | 4568    4578    45678    | 2       1356    34568    |
 | 23478   24678   23467    | 45689   1       2456789  | 45689   3569    345689   |
 *--------------------------------------------------------------------------------*

Simple Sudoku has done the most basic automatic eliminations for you.

The #pencilmark list is:

Code: Select all

(17.)0.2.4.20.21.10.6.1.0

In the list you have 10 numbers. The 1st one = the number of initial givens = 17 (r1c89,r2c24,r4c1358,r5c47,r6c1,r7c147,r8c27,r9c5).

The 2nd one = the number of cells with 1 possible candidate/pencilmark = 0 (Since we have no naked single here)

The 3rd one = the number of cells with 2 possible candidates = 2 (r4c4=59, r4c7=59, in this case r4c47 form a naked pair)

The 4th one = the number of cells with 3 possible candidates = 4 (r4c2=257, r5c1=249, r5c2=245, r7c8=169)

...

The 9th one = the number of cells with 8 possible candidates = 1 (r3c6=13456789)

The 10th one = the number of cells with 9 possible candidates = 0

Understand?

[Papy]

Thanks a lot
I undersrtand and I think that it was the idea which my théory need

I have Simple Sudoku it will be useful

Papy.