2x2, 2x3, 2x4, 2x5, 3x4 etc

rallveird · Posted: Thu Aug 04, 2005 9:58 pm Post subject: 2x2, 2x3, 2x4, 2x5, 3x4 etc

I'm now publishing a lot of different sizes on the puzzles. I will add more in a while.

The smaller sizes are good to test solving methods. All puzzles are indexed according to which method you need to use to solve them, as all puzzles on my site.

If anyone want a spesific size, let me know and I'll make some.

http://www.menneske.no/sudoku/

dukuso · Posted: Fri Aug 05, 2005 10:38 am Post subject: Re: 2x2, 2x3, 2x4, 2x5, 3x4 etc

rallveird · Posted: Fri Aug 05, 2005 12:34 pm Post subject:

To generate a very difficult on 5x5 or bigger takes time, much longer than creating one solvable by "logic".

To create the initial solution (I reduce my puzzles) a normal 3x3 takes 81-90 iterations, that's almost no iterations at all when you remove the 81 you anyway need.

But when you start on 4x4 and 5x5 it's another story. A 4x4 can use over 100000 iterations, and a 5x5 can use millions.

My program can make 9x9x9 and 16x16x16 (or actually any size in 3D) but it's surprisingly many iterations just to make the initial grid. I counted over 200 million iterations to make my first 9x9x9 solution. Reducing it is fast if I stick to "logical" strategies, but think about the amount of time used if not. When I have time I will adjust my web frontend so it can show 3D puzzles.

When it comes to finding a hard 3x3 (9x9) puzzle you would probably find one when I've indexed my database with my new strategies. I've implemented Nishio, Forcing Impossible and Forcing Chain - so the ones not able to be solved by them should be really mean.

dukuso · Posted: Fri Aug 05, 2005 12:58 pm Post subject:

as I understand, you start with a full grid and then remove clues.
You always check, whether the puzzle can be solved by simple
logic or advanced rules and that makes your rating.
And you stop removing cells, as soon as your solver
with the implemented rules can't solve it.
It could still be possible to remove clues from your hardest puzzles,
but then that would require "too advanced" techniques.
right ?

I'm wondering whether it could be possible to generate hard puzzles
quickly without having to solve them, which is slow.
You could just remove a certain fraction of clues randomly
and that would make very hard puzzles for large grids,
but how to ensure that they have only one solution ?

rallveird · Posted: Fri Aug 05, 2005 1:38 pm Post subject:

It's not possible to remove more clues from my optimal sudokus. They're as stripped down as possible. Removing 1 more clue will invalide the sudoku, giving more than 1 solution. The same is true for the symmetrical, but only looking at symmetrical removal. You can still be able to remove some clues to make it optimal instead of symmetrical.

I don't think there exists a way to check for legal grids without checking it for solution. I use different techniques to speed up the generating process, but to be sure in the end you have to iterate through the possibilities (after solving it by logical strategies first).

But on the other side, why do you need to generate the hard ones fast? They're only interesting to experts who want a real challange, and when you get past 3x3 sizes it's not "possible" for a human to solve them. My program use about 10 seconds to find a X-Wing hard puzzle in 3x3. That's fast enough I think.

dukuso · Posted: Fri Aug 05, 2005 4:37 pm Post subject:

>It's not possible to remove more clues from my optimal
>sudokus. They're as stripped down as possible. Removing 1 more
>clue will invalide the sudoku, giving more than 1 solution.
>The same is true for the symmetrical, but only looking at
>symmetrical removal. You can still be able to remove some
>clues to make it optimal instead of symmetrical.

I see. I had just estimated roughly, that a sudoku of that size
should have fewer clues. Maybe I was wrong.
I found now, that a random latin-square completion of
critical size would have n^1.55*1.7 holes, for sudokus
it should be more because of the additional constraint.
That would be 30,131,375 clues for latin squares and
maybe 10-20% (?)less for sudokus.

>I don't think there exists a way to check for legal grids
>without checking it for solution. I use different techniques
>to speed up the generating process, but to be sure in the end
>you have to iterate through the possibilities (after solving
>it by logical strategies first).

we just had an example in another forum, where we put one
clue into 18 disjoint "unavoidable" sets.
Clearly none of these can be removed which can be proved
without solving the puzzle. Nut you still have to solve it
to ensure that there is only one solution.

>But on the other side, why do you need to generate the hard
>ones fast? They're only interesting to experts who want a real
>challange, and when you get past 3x3 sizes it's not "possible"
>for a human to solve them. My program use about 10 seconds to
>find a X-Wing hard puzzle in 3x3. That's fast enough I think.

there is obviously some interest for the hardest puzzles.
Not only by people who want to solve it but also for
theoretical mathematical reasons.
Or just out of curiosity.
Or people give it to friends to tease them:
"hey, you're so good with sudokus, so let's see
whether you can solve THIS " ...

dukuso · Posted: Fri Aug 12, 2005 10:50 pm Post subject:

rallveird · Posted: Sat Aug 13, 2005 5:48 pm Post subject:

I will make optimal versions soon.