Canonical sudoku algorithm?

Lummox JR · Posted: Fri Mar 31, 2006 4:59 am Post subject:

I have a feeling that some pointer optimizations might speed up your algorithm somewhat. My gut tells me, for instance, that storing swap[b] in a pointer would reduce a lot of calculation time due to so much indexing of the swap array. After all, this only changes 18 times, but it's used many many more times than that. Given how many times test.map and best.map are accessed, a pointer for those couldn't hurt either. With the great number of iterations involved, cutting out unncessary indexing could really make a difference--maybe not huge, but noticeable.

gsf · Posted: Fri Mar 31, 2006 7:10 am Post subject:

daj95376 · Posted: Fri Mar 31, 2006 4:58 pm Post subject:

Lummox JR · Posted: Fri Mar 31, 2006 7:49 pm Post subject:

char **p=&swap[b] should work quite well enough, I would think. Good point about the indexing routines, though I still suspect that given the number of iterations it might be worth trying.

gsf · Posted: Fri Mar 31, 2006 8:38 pm Post subject:

gsf · Posted: Fri Mar 31, 2006 8:46 pm Post subject:

jedimaster

First find a solution.
Second generate a full sudoku grid ,what I mean full is that it is a sudoku but without an empty cell.
Third randomly remove a cell's number,and use the solution to solve the puzzle ,if this puzzle can be solved just keep that number be removed,if this puzzle can not be solve don't remove that number.

I wrote a program by c++ language and generate a hard puzzle in about 2 seconds.

Ruud · Site Admin

Hi jedimaster,

welcome to the forum.

Should you have read this thread, you would have known that it is about creating a canonical version of a sudoku, not just a sudoku.

To start a new thread, click "new topic". To reply to an existing thread, open the thread and click "new reply"

Ruud.

Lummox JR · Posted: Wed Apr 05, 2006 6:19 am Post subject:

It occurs to me that another nice candidate for canonical puzzle form would be the minimum 81-digit number where the non-givens are marked as 0. An advantage of this form is that you can find the top row from just a few choices that have the minimum number of clues. A major disadvantage is that it's harder to compute the permutations from there; you'd pretty much have to run this as a backtracking algorithm marking down which columns and rows and bands have been locked in place. If there's any digit missing from the givens, this form would always make that a 9.

I was thinking though that an exact cover solver like dancing links could work nicely for this. All you'd need would be some basic constraints, and an ordering system that told the solver which to check first:

- Transposition (1 constraint)
- Row band A in position B (9 constraints)
- Column band A in position B (9 constraints)
- Row A in band position C (27 constraints)
- Column A in band position B (27 constraints)

Numbering would be such that the first digit in left-to-right, top-down order is 1, then 2, then 3, etc. At each stage of the solver, it would have to determine if the available choices rule out anything as good as the current best form.

gsf · Posted: Wed Apr 05, 2006 6:37 am Post subject:

daj95376 · Posted: Wed Apr 05, 2006 4:56 pm Post subject:

Please forgive me, but I'd like to go off on a tangent and propose a different way to define equivalence classes on puzzles. Since my recollection of college mathematics is colder that a cemetery headstone, bear with me even if my equivalence classes aren't technically correct.

First off, let me state that I consider two puzzles to be equivalent if I can solve them by employing the same solution techniques in the same order.

My equivalence classes are based on a hypothetical solver that systematically solves puzzles by exhaustively trying each solution technique before advancing or restarting from the beginning. Consider the following partial list of techniques.

Lummox JR · Posted: Wed Apr 05, 2006 7:31 pm Post subject:

I don't think defining equivalence based on solve techniques would work very well, although it could provide some insight into what makes some puzzles harder than others. To do it absolutely the best way, though, I think you'd want to also count separately the times you returned to other techniques, e.g. a6b1a2c1a4b2c1... where a, b, c are different techniques.

The problem there, though, is that there's no objective definition of which techniques are harder than others. Depending on the technique set and order, different comparisons could yield different results. It might be that some puzzle families favor the uniqueness tests, for instance, whereas a test that does not include them or puts them after other techniques might never catch that.

Moritz · Posted: Sat Oct 07, 2006 10:35 am Post subject:

Hi,

gsf · Posted: Sat Oct 07, 2006 1:25 pm Post subject: