Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Preferred clue patterns
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
jido

Joined: 15 Aug 2007
Posts: 17
:

Items
PostPosted: Fri Aug 17, 2007 7:33 pm    Post subject: Preferred clue patterns Reply with quote

When chosing a mask for the clues to show, is it better to chose random clues or are there some patterns that sudoku players prefer?

Is there a difference between sudoku beginners, intermediate, advanced in that respect?

Thanks.
Back to top
View user's profile Send private message Visit poster's website
jido

Joined: 15 Aug 2007
Posts: 17
:

Items
PostPosted: Sat Aug 18, 2007 12:32 am    Post subject: Reply with quote

After doing some reading around here, I think I should focus on "unavoidables".

Maybe beginners would like more than two clues per unavoidable, while intermediate or advanced players would want no more. Then use random positions (maybe shooting for aesthetics) for the rest.

What maximum size unavoidable should I be looking at? If I do not want too much processor use, is it enough to look at size up to 9, then count on statistics and hope bigger sets are covered?

I will not go more than size 11. In sudoku checker there are >400 sets of size 12.
Back to top
View user's profile Send private message Visit poster's website
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Sat Aug 18, 2007 2:09 am    Post subject: Reply with quote

At first I thought that you wondered about random spacing versus symmetry.

I now think that neither of us know what your question is.

Elucidate?
Back to top
View user's profile Send private message
jido

Joined: 15 Aug 2007
Posts: 17
:

Items
PostPosted: Sat Aug 18, 2007 9:36 am    Post subject: Reply with quote

Smile

No I was not thinking about random spacing versus symmetry. I was thinking of the patterns in a grid that appeal to sudoku players.

For example, a beginner would like the satisfaction to fill a line or a box fast, or find all the 4's in the grid (that's my level).

An intermediate player would like the challenge to have less clues, forcing him or her to scan all boxes, marking the cells with alternatives...

Finally the advanced player would simply want a grid that is not easily solvable with common techniques.

I think it is possible to generate the two first type of grid automatically by looking at the unavoidables and insert more or less clues in there according to the level.

The third type of grid (advanced) would require a solver and some heuristics, so I would probably not target that group. I can just include a "enter your own" puzzle type, where people can paste boards from other sources.
Back to top
View user's profile Send private message Visit poster's website
jido

Joined: 15 Aug 2007
Posts: 17
:

Items
PostPosted: Sun Aug 19, 2007 3:45 am    Post subject: Reply with quote

Hey, can someone run this grid through checker?

I found only one unavoidable of size <= 6 in it

Code:
145873926832469715769521348627945831413782659598316274981234567356197482274658193

That means that a random grid of about 25 clues may have only one solution, doesn't it?
Back to top
View user's profile Send private message Visit poster's website
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sun Aug 19, 2007 6:26 am    Post subject: Reply with quote

jido wrote:
Hey, can someone run this grid through checker?

From a small run with my puzzle generator, these three puzzles resulted. They each have 33 clues/givens.

Code:
1..8.39..8.2.69..5..952...86..9.......3.8.6.......6..49...345..3..19.4.2..46.8..3
1..87...68...69.1..695.13.....9.5..1....8....5..3.6.....12.456..5.19...22...58..3
1..873..68...6..1..695.13.....9.5..1....8....5..3.6.....12.456..5..9...22..658..3
Back to top
View user's profile Send private message
jido

Joined: 15 Aug 2007
Posts: 17
:

Items
PostPosted: Sun Aug 19, 2007 11:18 am    Post subject: Reply with quote

Yeah, maybe it does require ~30 clues for a random grid. I found that 27 givens starting from a 25 and adding clues until sudokusolver solves it, then clearing the most obvious moves:

Code:
. 4 .|. 7 .|9 . .
. 3 .|. . .|. 1 .
. . 9|. . .|3 . 8
-----+-----+-----
6 . .|9 4 .|. . 1
. . 3|7 . .|6 . .
5 . .|. 1 .|. . 4
-----+-----+-----
9 8 .|. . .|5 . 7
. . .|1 . .|4 . 2
. . .|. 5 8|. . .

And that 24 clues with some more effort:
Code:
. 4 .|. 7 .|9 . .
. 3 .|. . .|. 1 .
7 . 9|. . .|3 . .
-----+-----+-----
6 . .|9 4 .|. . 1
. . 3|. . .|6 . .
5 . .|. 1 .|. . 4
-----+-----+-----
9 . .|. . .|. . 7
. . 6|1 . .|. . 2
. . .|. 5 8|. . .

edit: typo in first grid
Back to top
View user's profile Send private message Visit poster's website
JPF

Joined: 05 Dec 2005
Posts: 29
:
Location: Paris

Items
PostPosted: Sun Aug 19, 2007 5:05 pm    Post subject: Reply with quote

Hi jido,
Your puzzles are nice but not minimal.
You can remove some givens and still have valid puzzles.
Here are some examples :

Puzzle 1
remove 4 givens :
Code:

 . 4 . | . 7 . | . . .
 . . . | . . . | . 1 .
 . . . | . . . | 3 . 8
-------+-------+-------
 6 . . | 9 4 . | . . 1
 . . 3 | 7 . . | 6 . .
 5 . . | . 1 . | . . .
-------+-------+-------
 9 8 . | . . . | 5 . 7
 . . . | 1 . . | 4 . 2
 . . . | . 5 8 | . . .


Puzzle 2
remove 1 given :
Code:

 . 4 . | . 7 . | 9 . .
 . . . | . . . | . 1 .
 7 . 9 | . . . | 3 . .
-------+-------+-------
 6 . . | 9 4 . | . . 1
 . . 3 | . . . | 6 . .
 5 . . | . 1 . | . . 4
-------+-------+-------
 9 . . | . . . | . . 7
 . . 6 | 1 . . | . . 2
 . . . | . 5 8 | . . .


Now, still with the same grid, here are some more subgrids :

24 clues, minimal, symmetric
Code:

 . 4 . | . 7 . | . . .
 . . 2 | . . . | . . 5
 . 6 . | . . 1 | 3 . 8
-------+-------+-------
 6 . . | . . 5 | . . 1
 . . 3 | . . . | 6 . .
 5 . . | 3 . . | . . 4
-------+-------+-------
 9 . 1 | 2 . . | . 6 .
 3 . . | . . . | 4 . .
 . . . | . 5 . | . 9 .


21 clues, minimal
Code:

 . . . | 8 7 . | . . 6
 . . . | . . . | . . .
 . . . | . . . | 3 4 .
-------+-------+-------
 . 2 . | . . . | . . .
 . 1 . | 7 8 . | . . .
 5 9 . | . 1 . | 2 . .
-------+-------+-------
 . 8 . | . . 4 | 5 . .
 3 . 6 | . . . | . . .
 . . 4 | . . . | 1 9 .


JPF
Back to top
View user's profile Send private message
jido

Joined: 15 Aug 2007
Posts: 17
:

Items
PostPosted: Sun Aug 19, 2007 6:02 pm    Post subject: Reply with quote

Thanks!
Did you make the puzzles by hand, by program or find from a database?

I think I may have missed something important... Is this a size 4 unavoidable set?
Code:
1 . .|2 . .
. . .|. . .
. . .|. . .
-----+-----
2 . .|1 . .
Back to top
View user's profile Send private message Visit poster's website
JPF

Joined: 05 Dec 2005
Posts: 29
:
Location: Paris

Items
PostPosted: Tue Aug 21, 2007 9:57 pm    Post subject: Reply with quote

Well, my computer is becoming my right hand Smile

What kind of database could I use to find puzzles having a given solution ?

To answer your initial question, look at the techniques used by a solver.
If you don't have your own solver, see here.

JPF
Back to top
View user's profile Send private message
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Wed Aug 22, 2007 9:02 am    Post subject: Reply with quote

jido wrote:
I think I may have missed something important... Is this a size 4 unavoidable set?
Code:
1 . .|2 . .
. . .|. . .
. . .|. . .
-----+-----
2 . .|1 . .


No, it isn't. You cannot exchange the 1s & 2s since there are in different blocks/boxes/nonets.

Here are two size 4 unavoidable sets:
Code:
1 . 2|. . .
. . .|. . .
. . .|. . .
-----+-----
2 . 1|. . .



1 . .|2 . .
. . .|. . .
2 . .|1 . .
-----+-----
. . .|. . .


The unavoidable sets principle is quite simple. When you remove the digits forming an unavoidable set from the solved puzzle, it leads to several solutions. Therefore, at least one of these digits must be given.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Aug 22, 2007 4:12 pm    Post subject: Reply with quote

JPF wrote:

What kind of database could I use to find puzzles having a given solution ?

you can use my solver 2007-08-22 to generate puzzles that all have the same solution grid
put the solution grid in s.dat and:
Code:
sudoku -gp -Yg.dat -j0 -n10 -m -sg -e 'm==1&&uniq()'

this will generate 10 different minimal symmetric puzzles, all with the same solution as s.dat
if symmetric minimal are ok then change the -e expression to 'uniq()'
if you are only interested in the smallest #clues then change the -e expression to 'm==1&&min(C)&&uniq()'
for the solution grid
Code:
145873926832469715769521348627945831413782659598316274981234567356197482274658193

these popped out after a few min
Code:

.4...3..6.32..9...7.....3.86.7.......1.7.2.5.......2.49.1.....7...1..48.2..6...9. #    10 FN C26.m/S2.p
...8.3.....24.97..7.......8..........13...65.59.....74....3....35.....82..46.81.. #  1316 FNBTWXY C25.m/S2.v
.4.87....8.2........9..1...6...4.8.....7.2..95...1...4......56.3.......2.7.6.8.9. #    57 FNBT C24.m/S2.a
1.5.7.....3.....1.7..52....6...........7..6.9..8.1.2..9..2....7.......8...4..81.3 #    11 FN C23.m/S2.a

its still running (didn't reach 10 puzzles yet)
results will vary based on the initial pseudo random number generator seed, which is generated if not specified on the command line

[edit: still running, two more:]
Code:

.4...3..68....9......5..3....7.4.......7..65.59....2....1.34..7....9....2.....1.. #    14 FN C22.m/S2.d
....73.....2..97...6....3......4...14..78.6..59........81.3............2...6...9. #    18 FN C21.m/S2.d
Back to top
View user's profile Send private message Visit poster's website
JPF

Joined: 05 Dec 2005
Posts: 29
:
Location: Paris

Items
PostPosted: Thu Aug 23, 2007 7:12 am    Post subject: Reply with quote

Thanks gsf.

Your program is obviously not a database Smile

gsf wrote:
you can use my solver 2007-08-22 to generate puzzles that all have the same solution grid
put the solution grid in s.dat and:
Code:
sudoku -gp -Yg.dat -j0 -n10 -m -sg -e 'm==1&&uniq()'

this will generate 10 different minimal symmetric puzzles, all with the same solution as s.dat

What is Yg.dat ?
and where is s.dat in your command line ?

Thanks in advance.

JPF
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Thu Aug 23, 2007 6:15 pm    Post subject: Reply with quote

JPF wrote:
Thanks gsf.

Your program is obviously not a database Smile

I didn't quite understand the question What kind of database could I use to find puzzles having a given solution ?
I should have asked for clarification
the reason for my not understanding:
to use a database you need a data source, and I don't think there is a large collection of puzzles all having the same solution

the command line had a typo
the option is -Y and the file name is s.dat
s.dat contains the solution grid --- the solution that you want all generated puzzle to have
here is the correct command line
Code:
sudoku -gp -Ys.dat -j0 -n10 -m -sg -e 'm==1&&uniq()'
Back to top
View user's profile Send private message Visit poster's website
jido

Joined: 15 Aug 2007
Posts: 17
:

Items
PostPosted: Mon Aug 27, 2007 3:10 pm    Post subject: Reply with quote

This is exciting...

gsf, what is the meaning of the line starting with # after each result? For example:
Code:
#  1316 FNBTWXY C25.m/S2.v

(I assume bigger numbers are better?)

I now finished a first version of the Javascript that generates the grid. There are three big problems:
- It is slo--o-ow
- I cannot tell in advance the number of unavoidables I end up with (I look only for size 4 and size 6 unavoidable sets) so the number of clues required varies
- The grid is not minimal

This is an example of output:
Code:
2 . 3|. 7 .|. 4 .
. 7 4|8 . 1|6 . 3
. . .|3 4 6|. 7 2
-----+-----+-----
4 . 7|1 . .|3 2 6
. . .|. . 7|. . .
1 . .|4 . 3|. . .
-----+-----+-----
7 4 .|. 1 8|2 3 .
3 2 1|9 . 4|8 . 7
6 . .|7 . .|. 1 .


I chose this one because sodukusolver reports there is only one solution, using one guess. I can also see that it is not minimal (the 7 in the bottom left corner is not needed)
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku 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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron