How to reduce a puzzle to its minimum clues

Programs which generate, solve, and analyze Sudoku puzzles

How to reduce a puzzle to its minimum clues

Postby snowbear » Sat Nov 26, 2005 3:32 pm

[A]
Anyone knows any method/program etc on how to reduce a puzzle to the minimum number of clues and yet still gives it the same single unique and valid solution?

[B]
How can we determine the minimum number of clues for a puzzle to be valid and has one unique solution?


Thanks!
snowbear
 
Posts: 20
Joined: 27 October 2005

Postby evert » Sun Nov 27, 2005 12:03 am

This post is more or less about the same issue.
evert
 
Posts: 186
Joined: 26 August 2005

Postby dukuso » Sun Nov 27, 2005 6:14 am

you can use this program:
http://magictour.free.fr/suex9-.exe
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby snowbear » Sun Nov 27, 2005 11:57 am

{dukuso}:

Syntax for the program is: -

program file [seed]

[A]
What is the format and extension for the file?

[B]
Can we create a file with clues and let it reduce it to the minimum number of clues and still have the same solution?

Thanks
snowbear
 
Posts: 20
Joined: 27 October 2005

Postby dukuso » Sun Nov 27, 2005 12:04 pm

snowbear wrote:{dukuso}:

Syntax for the program is: -

program file [seed]

[A]
What is the format and extension for the file?



format: 81 symbols, numbers for clues, 0 or . for holes
extension:whatever you want

[B]
Can we create a file with clues and let it reduce it to the minimum number of clues and still have the same solution?

Thanks



sure. Note that there are lots of different ways and minimal
sudokus to perform the task
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby snowbear » Sun Nov 27, 2005 1:57 pm

{dukuso}:

Thanks a lot! Finally got it work. It's a great program! It's fun to check out the sudoku that it generates.

[A]

"sure. Note that there are lots of different ways and minimal
sudokus to perform the task"


(i)
What you meant is that there are many more other minimal soduko that can also be generated other than the first set we get, right?

If we can wait around, is there any way to

(ii)
tell the program that we want to reduce the puzzle to one with say 16 clues?

(iii)
ask the program to indicate the total number of minimal unique and valid puzzle it can reduce to? And may show the generated puzzle if we want to?

[B]
Besides this program, is there any other program that does sth similiar?

Thanks a lot!
snowbear
 
Posts: 20
Joined: 27 October 2005

Postby dukuso » Sun Nov 27, 2005 2:16 pm

> (i)
> What you meant is that there are many more other minimal
> soduko that can also be generated other than the first set we
> get, right?

yes

> If we can wait around, is there any way to
>
> (ii)
> tell the program that we want to reduce the puzzle to one with
> say 16 clues?

I could change it so to generate lots of random puzzles
and then pri nt the statistics

> (iii)
> ask the program to indicate the total number of minimal unique
> and valid puzzle it can reduce to? And may show the generated
> puzzle if we want to?

the program would have to rub rheough all permutations
of the clues, so this is too slow, except for sparse grids
with only few possibilities to delete clues.
We could mark the clues which can be removed and then backtrack through
all permutations of these. I haven't yet done this

> [B]
> Besides this program, is there any other program that does sth
> similiar?

probably. It's very similar to a sudoku-generator
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby snowbear » Sun Nov 27, 2005 2:39 pm

"
> If we can wait around, is there any way to
>
> (ii)
> tell the program that we want to reduce the puzzle to one with
> say 16 clues?

I could change it so to generate lots of random puzzles
and then pri nt the statistics
"

Could you help to add this feature when you are free:
For a given puzzle, say with 17-40 givens (reject 41 or more givens for the moment),

-have the program reduced it to a minimal puzzle with a number indicated by user (say 16; if not indicated, you can assign a default or sth that the present version is using)
-indicate if it is not possible to reduce it to eg 16 givens; the program will only look for the what the user indicate and nothing else.
-if say a 16 givens is possible, for each set the grid is output as in present program (the human readable version). Duplication will be checked by the user manually for the moment.

Thanks
snowbear
 
Posts: 20
Joined: 27 October 2005

Postby snowbear » Sun Nov 27, 2005 4:44 pm

{dukuso}:

I was going thru the postings again and realise that we may be talking about similiar things but I am referring to a smaller scale.

The better subject should be:
How to reduce the number of givens in a puzzle to its minimum clues and yet give the same unique solution as the starting puzzle

The reference is to reduce the existing givens to a min, not the full grid. This should make it easier to program.

My apology
snowbear
 
Posts: 20
Joined: 27 October 2005

Postby dukuso » Sun Nov 27, 2005 4:49 pm

here is a program which prints a sub-sudoku with minimum number
of clues and same solution to a given sudoku with <33 clues.
If the given sudoku has more clues then it takes too long.

http://magictour.free.fr/suex9--.exe

you can send email to sterten{at}aol.com , when you have some more special wishes.When it's easy to add them, I'll try.
dukuso
 
Posts: 479
Joined: 25 June 2005


Return to Software