Collection of sudokus

Everything about Sudoku that doesn't fit in one of the other sections

Re: Collection of sudokus

Postby lerxst » Sun Nov 20, 2011 9:06 pm

eleven wrote:
lerxst wrote:Yes, I thought about this but I'd like different grids (i.e. puzzle with different solution grids). I don't care about minimal or not as it won't impact my "dumb" solver! But I need puzzles with one solution only!

Why shouldn't you get different solution grids ? You have 45000 17 clue puzzles with at least 20000 different sulution grids, where you can start the {-1+2}. Also this operation in most cases will bring you to another grid.
Ah, didn't you understand {-1+2} ? You get the same grid, when you just add a clue of the solution grid, but here you first drop a clue and add 2 different ones (not from the solution grid!) in any 2 empty cells.

If you dont mind, that the puzzles are not minimal, your results will be, eh poor.
In this case ALL puzzles will be very simple on average. As you read, 80% of the 17 clues are singles puzzles and - apart from a few ones -, the others are easy too. If you dont mind redundant clues, this relationship will not change with more clues. It depends on your selection, but probably they will become even easier then.
Now who should be interested, if you can solve 1000 easy puzzles with 30 clues 2% faster than with 17 clues ?


I probably explained myself very badly. I don't mind if a puzzle is minimal or not (though minimal ones are more interesting but minimality has no impact in my case) BUT I want puzzles that lead to one and only one solution grid. Difficulty, in my case, has absolutely no impact.

To make a long story short, I'm solving sudoku puzzles in plain SQL (i.e. not PL/SQL, no loops, no functions, no stored procs, no variables, just plain old SQL and just one SQL statement... For what reason you might ask? Just for the fun of it and to write an article on my blog about SQL optimization. I was just looking for a subject/excuse to present a few concepts and ideas (and to shut up someone who told me this solution wouldn't solve any puzzle in a reasonable time)... I've done it in the past but it was more a proof of concept than anything. The whole thing was wrapped in less than 2 hours.

Now, I'm doing it in a more serious way with measures, explanations and a serious test set to investigate and show a few possibilities. So in my very specific case, the more clues I have, the more index hits I get, the more efficient are the joins, more pruning in done in the index cache, the more index merge chances I get, etc... Solving sudoku puzzles with SQL will never be as quick as a C program but that's not my point nor my intentions!
lerxst
 
Posts: 18
Joined: 13 December 2010
Location: Montréal, Québec, Canada

Re: Collection of sudokus

Postby eleven » Sun Nov 20, 2011 10:05 pm

lerxst wrote:
eleven wrote:
lerxst wrote:But I need puzzles with one solution only!

oops, sorry i misread that.
BUT I want puzzles that lead to one and only one solution grid.

Now what do you mean ? One solution, i.e. the puzzles are unique as usual, or all puzzles have the same solution grid ?
In the first case, what i described above, will give you, what you want. If you dont want them all to be minimal dont use the -e1 option.

If you dont know, how to use gsf's program under windows, try this:
Download it (the downloads are at the bottom of the page) to some directory. Start notepad and copy the line
Code: Select all
sudoku -go"{-1+2}" -f'%v' input17clues.txt > output18clues.txt

there, save as mygenerator.bat in the same directory.
For a test, copy the first line of the 17clues file to input17clues.txt, and click on mygenerator.bat in the explorer. When it is finished, you should find some 100 18 clue puzzles in the output18clues.txt.
eleven
 
Posts: 1536
Joined: 10 February 2008

Re: Collection of sudokus

Postby dobrichev » Sun Nov 20, 2011 10:28 pm

Code: Select all
select grid_text from all_possible_grids where grid_text like '....'


I appreciate your efforts and will be glad if you post a link to your work when ready.

When solving non-minimal puzzles, some of the joins would not add value and this you only add noise to the solving process giving more chances to query optimizer in choosing the execution plan. More possibilities to choose from = more random execution plan = noise.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Collection of sudokus

Postby lerxst » Mon Nov 21, 2011 4:31 am

dobrichev wrote:
Code: Select all
select grid_text from all_possible_grids where grid_text like '....'


I appreciate your efforts and will be glad if you post a link to your work when ready.

When solving non-minimal puzzles, some of the joins would not add value and this you only add noise to the solving process giving more chances to query optimizer in choosing the execution plan. More possibilities to choose from = more random execution plan = noise.

Cheers,
MD


Here's the link to my first attempt at this... Now, I'm getting more serious! No need to generate all possible grids (besides, it would be impossible!) when you can use self-joins in abundance!

http://myfavoriteheadache.wordpress.com/2010/12/15/a-pattern-so-grand-and-complex-part-1/
lerxst
 
Posts: 18
Joined: 13 December 2010
Location: Montréal, Québec, Canada

Re: Collection of sudokus

Postby dobrichev » Mon Nov 21, 2011 10:07 am

It is interesting.

You can try some of the hardest puzzles to see whether they are solvable in reasonable time.
My expectation is that they will lead to large intermediate results, flooding the available memory. But this is based only on my intuition and they could fit in memory as well.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Collection of sudokus

Postby lerxst » Mon Nov 21, 2011 2:51 pm

dobrichev wrote:It is interesting.

You can try some of the hardest puzzles to see whether they are solvable in reasonable time.
My expectation is that they will lead to large intermediate results, flooding the available memory. But this is based only on my intuition and they could fit in memory as well.

Cheers,
MD


Ain't that bad... I tried a few 17-clues and there's a way to solve them very very very quickly! But you'll have to wait for my article to know how! I'm still in the process of writing the article and I am still generating sudoku grids to measure the correlation between number of givens versus solving time for my "way of solving". I'll study the impact of every optimization "trick" on solving time along the way. It's not rocket science really, it's just a matter of knowing a few tips & tricks and "thinking out of the box" to allow you to use a database for something it was not designed for in the first place. I'm a lot more impressed by what you guys are doing here than by what I am playing with!
lerxst
 
Posts: 18
Joined: 13 December 2010
Location: Montréal, Québec, Canada

Re: Collection of sudokus

Postby m_b_metcalf » Mon Nov 21, 2011 11:39 pm

lerxst wrote:
dobrichev wrote:You can try some of the hardest puzzles to see whether they are solvable in reasonable time.

Ain't that bad... I tried a few 17-clues and there's a way to solve them very very very quickly!

Well, this we all know: 17-clue puzzles, as has been pointed out twice, are easy. The hard ones typically have 22 - 26 clues and there are very many examples in the Patterns Game -- look for ED ratings above 10.0, this, for example:

Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 7 . 2 . . . 
 . . . . 5 . . . .
 . . . . . 6 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5



Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Collection of sudokus

Postby lerxst » Tue Nov 22, 2011 5:55 am

m_b_metcalf wrote:
lerxst wrote:
dobrichev wrote:You can try some of the hardest puzzles to see whether they are solvable in reasonable time.

Ain't that bad... I tried a few 17-clues and there's a way to solve them very very very quickly!

Well, this we all know: 17-clue puzzles, as has been pointed out twice, are easy. The hard ones typically have 22 - 26 clues and there are very many examples in the Patterns Game -- look for ED ratings above 10.0, this, for example:

Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 7 . 2 . . . 
 . . . . 5 . . . .
 . . . . . 6 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5



Regards,

Mike Metcalf


You probably missed my previous post in this thread but as I was explaining, in my specific case, 17-givens are usually the hardest to solve because they don't have enough clues to help the plan optimizer much...
lerxst
 
Posts: 18
Joined: 13 December 2010
Location: Montréal, Québec, Canada

Re: Collection of sudokus

Postby m_b_metcalf » Tue Nov 22, 2011 6:31 am

lerxst wrote:You probably missed my previous post in this thread but as I was explaining, in my specific case, 17-givens are usually the hardest to solve because they don't have enough clues to help the plan optimizer much...

Well, maybe we could agree to use a common definition of 'hard'. Usually, here, it's as defined by Sudoku Explainer.

Your method reminds me of one I tried years ago and that I abandoned very quickly, namely to go down row by row with a set of nine digits randomly ordered, shuffling those digits along the row to conform to the givens and to the sudoku contraints. This rapidly leads to a deadlock and a restart, so it took seconds to solve a puzzle.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Collection of sudokus

Postby lerxst » Tue Nov 22, 2011 6:48 am

m_b_metcalf wrote:
lerxst wrote:You probably missed my previous post in this thread but as I was explaining, in my specific case, 17-givens are usually the hardest to solve because they don't have enough clues to help the plan optimizer much...

Well, maybe we could agree to use a common definition of 'hard'. Usually, here, it's as defined by Sudoku Explainer.

Your method reminds me of one I tried years ago and that I abandoned very quickly, namely to go down row by row with a set of nine digits randomly ordered, shuffling those digits along the row to conform to the givens and to the sudoku contraints. This rapidly leads to a deadlock and a restart, so it took seconds to solve a puzzle.

Regards,

Mike Metcalf


Okay! Sorry for the confusion, that's why I added "in my case". As I explained previously, my method ain't rocket science and I'm not pretending it is : it's simply using 2 things a RDBMS does efficiently and quickly : joining and comparisons!

besides, on another topic, where can I find an explanation of those ratings ? I googled pearl, diamond & a few other terms I was seeing in some forums here but I've not been able to find a definition (as well as examples) of this lingo. Any link you can suggest ?

Thank you!
lerxst
 
Posts: 18
Joined: 13 December 2010
Location: Montréal, Québec, Canada

Re: Collection of sudokus

Postby m_b_metcalf » Tue Nov 22, 2011 7:29 am

lerxst wrote:besides, on another topic, where can I find an explanation of those ratings ? I googled pearl, diamond & a few other terms I was seeing in some forums here but I've not been able to find a definition (as well as examples) of this lingo. Any link you can suggest ?

I forget where they were initially defined, and by whom, but this link should help. There are tens of thousands of examples in the Patterns Games results thread.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Collection of sudokus

Postby eleven » Tue Nov 22, 2011 9:04 am

lerxst wrote:You probably missed my previous post in this thread but as I was explaining, in my specific case, 17-givens are usually the hardest to solve because they don't have enough clues to help the plan optimizer much...

Now you made me curious. This would be the first solving algorithm i am aware of, which handles hard puzzles easier than singles puzzles. So would you try these 10 ones please and compare it with 10 17 clues ?
Code: Select all
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.
98.7.....6.....87...7.....5.4..3.5....65...9......2..1..86...5.....1.3.......4..2
12..3....4....1.2...52..1..5..4..2......6..7......3..8.5....9....9.7..3......8..6
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....
.2.4...8.....8...68....71..2..5...9..95.......4..3.........1..7..28...4.....6.3..
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7
..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.
1.......9..67...2..8....4......75.3...5..2....6.3......9....8..6...4...1..25...6.
1....6.8....7..1........5.6..9.4.....7.2...3.8....76..3....1..5.4.9.......2.7....
.2...67..4...8......93........9..57..1...7..2......61.3...4..6...8.......6...5.2.
eleven
 
Posts: 1536
Joined: 10 February 2008

Re: Collection of sudokus

Postby m_b_metcalf » Tue Nov 22, 2011 9:50 am

eleven wrote:Now you made me curious. This would be the first solving algorithm i am aware of, which handles hard puzzles easier than singles puzzles.

Out of curiosity, I just dug out my old program, described above, and ran it on a 17-clue puzzle, something I never did before abandoning it. It took 5 minutes!

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: Collection of sudokus

Postby eleven » Tue Nov 22, 2011 12:09 pm

eleven wrote:
lerxst wrote:You probably missed my previous post in this thread but as I was explaining, in my specific case, 17-givens are usually the hardest to solve because they don't have enough clues to help the plan optimizer much...

Now you made me curious. This would be the first solving algorithm i am aware of, which handles hard puzzles easier than singles puzzles. So would you try these 10 ones please and compare it with 10 17 clues ?
Code: Select all
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.
98.7.....6.....87...7.....5.4..3.5....65...9......2..1..86...5.....1.3.......4..2
12..3....4....1.2...52..1..5..4..2......6..7......3..8.5....9....9.7..3......8..6
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....
.2.4...8.....8...68....71..2..5...9..95.......4..3.........1..7..28...4.....6.3..
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7
..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.
1.......9..67...2..8....4......75.3...5..2....6.3......9....8..6...4...1..25...6.
1....6.8....7..1........5.6..9.4.....7.2...3.8....76..3....1..5.4.9.......2.7....
.2...67..4...8......93........9..57..1...7..2......61.3...4..6...8.......6...5.2.

[Added:] Here is one more puzzle, which turned out to be hard for sdk_fan's method, which i think has some similarities to yours.
Code: Select all
..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..
eleven
 
Posts: 1536
Joined: 10 February 2008

Re: Collection of sudokus

Postby lerxst » Tue Nov 22, 2011 1:46 pm

@eleven
@m_b_metcalf

As soon as I'm done generating random Sudokus (I'm generating a batch of 10000000 random ones with QQwing), I'll post the results of 17-givens versus the ones you submitted me... I'll keep you posted as soon as possible!

If that's of any help, the "hardest" ones for my database query are puzzles with empty rows and/or empty columns. So if you have a puzzle with a few empty rows AND a few empty columns, that would be terrific. To be precise, columns and rows with less that 2 clues force the optimizer to do a partial match in the index...

For instance, the following grid clearly shows the weaknesses of my solution because of the empty rows AND the empty columns. The more empty rows and empty columns, the harder the database has to work (yes, even with 42 clues!)

000000000034825690059364180097182560000000000081476230025641970076538420000000000

Do you guys have such puzzles in your databases ?!? I'd be interested by those if you have some!
lerxst
 
Posts: 18
Joined: 13 December 2010
Location: Montréal, Québec, Canada

PreviousNext

Return to General