Creation logic

riddler · Posted: Wed Sep 14, 2005 9:16 pm Post subject: Creation logic

Hello forum !

I am a newbee to this forum so forgive me if i post a "stupid" question or something you have already discussed in depth... Wink

I see a lot of discussions on solve-techniques but almost nothing on the logic behind creating sudoku puzzles.

I guess a method could be :
* start with an empty grid which does not represent the start but the end of the game
* randomly enter some numbers, those are not clues but naked/hidden singles who solve the puzzle as the final step.
* now consider these numbers as the result of say an X-wing
add (false) possibilties to these numbers so that the solver needs to perform an X-wing
right before the end to get back to those same numbers from the previous step
* and so on, basically filling pencilmarks in stead of discarding them

I guess most solvers have also options to generate a grid, and I guess those are generated from scratch using some logic
in stead of pulling them from some kind of set (database or whatever), so where can I find the logic ?

dukuso · Posted: Thu Sep 15, 2005 11:42 am Post subject:

hello riddler,

your method with x-wing etc. is too advanced for me.

I have 2 methods:

1) start with an empty grid
2) fill in a clue at ramdom
3) solve it
4) if there is no sultution remove the last clue
5) if there is more than one solution goto 2

here you might add a 2nd step to remove clues and make a locally minimal sudoku as below.

or 2nd method :

start with a random full grid
generate a random permutation P of the 81 clues
for i=1..81
remove clue P(i)
solve it
if there is more than 1 solution put the clue P(i) in again
next i

2nd method is about 4 times faster

riddler · Posted: Thu Sep 15, 2005 3:23 pm Post subject:

Hello dukuso,

Thanx for your answer.
I guess I didn't clarify the background of my question enough.

I am looking for a logic in stead of a random method.
It could be that I don't fully grasp the consequences of your methods
but it seems to me that they are the inverse of T&E.

I am looking for some logically algorithms to create a grid
perhaps even forcing a solver to use the inverses of those algorithms
(eg. create a grid that needs squirmbag etc.)

With all this focus on solving algorithms I guess I miss some basic understanding of sudoku setting needed to realise that I raise a "stupid" question but I hope there are (or should be ?) equally elegant methods for setting and solving grids.

dukuso · Posted: Thu Sep 15, 2005 3:32 pm Post subject:

do you want to create a sudoku with given difficulty,
=given method required to solve it ?

riddler · Posted: Thu Sep 15, 2005 3:35 pm Post subject:

yes, pff sorry for my english
i need a lot of words to explain what could be said in only a few Wink

My question basically is :
* Can you create a grid using some specific create-algorithms that needs the inverse of those algorithms to solve them
* Are those create-alogithms documented ?
(Eg how to put an X-wing in a grid)
* Are there other methods to ensure you need some specific logic to solve them
* Or is the general consensus : generate a grid with 1 unique solution (with an unknown difficulty level) and rate it afterwards trying to solve it.

Lummox JR · Posted: Fri Sep 16, 2005 3:50 am Post subject:

I've had much the same problem. So far the only answer seems to be to use a fast solver to generate a lot of random grids and sift for the ones you want. If there's any means of guaranteeing a particular technique appears, I'm not aware of it.

dukuso · Posted: Fri Sep 16, 2005 4:47 am Post subject:

start with a full grid selected at random.
Remove clues at random, as long as it still has
a unique solution and can be solved with the required
method.
Check each of the remaining clues : does removing them
give a unique solution ?
If yes, it's the wanted sudoku.
You can try to remove further clues, as long as
there is still a unique solution and no solution
with that technique.

Ruud · Site Admin

This is (currently) my method:

- Start with an empty grid.
- Configure the solver for the appropriate difficulty level.
- Create an array of all position/value combinations (81 x 9 entries)
(loop)
- Pick a random entry from the array and fill it in the grid.
- Use the solver to process the effects of the entry.
- If the puzzle is unsolvable, remove the entry from both the grid and the array.
- As long as there is not a single sollution, remove from the array:

- Loop until the puzzle has been completely solved.

To avoid too many retries, the following optimization is used:

When at least 8 cells in the grid have been filled, sort the array on the number of direct blocks that placing the entry would cause. Then pick a random entry from the top-10 of the array, rather than from the entire array.

When at least 16 cells in the grid have been filled, try all entries from the top-10. Choose the entry that causes the highest number of direct and indirect blocks.

Bo · Posted: Mon Sep 19, 2005 5:07 pm Post subject:

I use the method to start from an empty grid, then add random clues until a unique solution is found (as described earlier in this thread). I have found that the number of retries allowed at each level before returning failure upwards is critical to performance. For peak performance in my case, only 3 retries should be allowed before reporting failure to upper levels forcing them to generate new clues. Thus, it seems as the probability for success rapidly decreases after only a few retries.
A further possibility to increase performance could be to specify different number of allowed retries for different levels. I have not tried this.

Earlier, I relied on a time out to deal with the situation when the program got lost in endless retries. After time out, the program started again with an empty grid.

The new method with the limit on number of retries increased performance about 3 times.

I am quite new to this Forum, hope this is not old stuff.

Regards
Bo

Lummox JR · Posted: Tue Sep 20, 2005 9:37 pm Post subject:

I'm not sure I follow your terminology, Ruud. How do you define "direct block"? And, how do you determine how many the placement of an entry would create?

Ruud · Site Admin

Sorry about the confusion. I've sort of developed my own terminology here.

A direct block is a value that cannot be placed in a particular cell anymore, just following the rules of the game.

Placing a 1 in cell (1,1) in an empty grid would cause a total of 28 direct blocks (values 2-9 for cell (1,1) and 20 peer cells that no longer allow value 1 according to the rules.

Placing a 2 in cell (1,2) next would cause 26 direct blocks, since value 1 was already blocked in (1,2) and value 2 already in (1,1)

For the complete picture, an indirect block is a value that cannot be filled in a cell as a result of a deductive technique. I make the distinction, because my program allows the user to fill a cell with a value that has an indirect block, but not when it has a direct block, since the latter would violate the game rules. An indirect block can be promoted to a direct block when filling a cell afterwards requires a direct block.

There are 81 cells, 9 values, one of them to be filled, so 81x8=648 blocks possible.

Determining how many blocks a placement would cause is simple, because the existing blocks are saved at the cell/value level.

If I apply this technique direct from the start, it would create similar puzzles over and over again, that's why it kicks in at the 9th entry.

For your information: Depending on the configuration of the solver, it creates puzzles with 22-26 clues, which can usually be optimized to 20-24 clues.

The optimizer is a separate feature in my program, which checks whether any of the clues can be removed without invalidating the puzzle.