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   

Canonical sudoku algorithm?
Goto page Previous  1, 2, 3, 4, 5, 6  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
gsf

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

Items
PostPosted: Fri Mar 31, 2006 3:56 am    Post subject: Reply with quote

Lummox JR wrote:
Aye, naturally there are other canonical forms. The main thing to my mind is just to find which ones really work, and how. The new modification to gsf's algorithm makes it the first, to my knowledge, to fully canonize a puzzle.

I tried to be careful to say a canonicalization algorithm
within the context of an algorithm we can talk about the canonical forms

this algorithm canonicalizes the top1465 solution grids at ~3400/sec/Ghz

the other implementation metioned in the player's forum is based on nauty
and works on puzzles; it runs much slower on solution grids
Back to top
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Fri Mar 31, 2006 4:59 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
gsf

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

Items
PostPosted: Fri Mar 31, 2006 7:10 am    Post subject: Reply with quote

Lummox JR wrote:
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.

I once thought that pointer better than indexed array held universally
and "optimized" array indexing => pointer in a <regex.h> boyer moore matcher,
only to find out that the pointer implementation lost by an unexpected
amount (something like 10-20%, it was a few years back)

why?
many architectures have indexing instructions that may play nicely with
level 1 cache for small indexes
some architectures have 8 byte pointers that may be overkill for small chunks of memory, even 4 byte pointers may lose to 1 or 2 byte indexes

also, given char swap[18][9][9], how, short of adding subroutine calls,
do you instruct C to make a pointer p to &swap[b] work as p[i][j]?
Back to top
View user's profile Send private message Visit poster's website
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Mar 31, 2006 4:58 pm    Post subject: Reply with quote

gsf wrote:
also, given char swap[18][9][9], how, short of adding subroutine calls, do you instruct C to make a pointer p to &swap[b] work as p[i][j]?


Code:
typedef   char   C99[9][9];

C99   swap[18], *p;

p = &swap[b];   /* -or-   p = swap + b; */

(*p)[i][j]


should work.
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Fri Mar 31, 2006 7:49 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
gsf

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

Items
PostPosted: Fri Mar 31, 2006 8:38 pm    Post subject: Reply with quote

daj95376 wrote:
gsf wrote:
also, given char swap[18][9][9], how, short of adding subroutine calls, do you instruct C to make a pointer p to &swap[b] work as p[i][j]?

Code:
typedef   char   C99[9][9];
C99   swap[18], *p;
p = &swap[b];   /* -or-   p = swap + b; */
(*p)[i][j]


ha, thanks
an embarrassment and a vindication for one response
I recoded swap[test.box] and swap[best.box] to be pointers
and it slowed down by a factor of ~4 (a little more than the 20% I remembered)
I didn't dig into the pentium assembly to see whats going on
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: Fri Mar 31, 2006 8:46 pm    Post subject: Reply with quote

Lummox JR wrote:
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.

this is where I got into trouble
if p is to be used as p[i][j] the C compiler needs to know the j dimension
you could recode the swap array to be 2 dimensions
but then the row/col permutation logic would have to be reworked

I don't want to discourage pointer recodings for a head to head comparison
(my quick attempt could have been lame -- it did produce the same output though)
but for now I'm sticking with the indexed version
Back to top
View user's profile Send private message Visit poster's website
jedimaster

Joined: 02 Apr 2006
Posts: 1
:

Items
PostPosted: Sun Apr 02, 2006 7:30 am    Post subject: I make puzzle generator & do it like this Reply with quote

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.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sun Apr 02, 2006 12:41 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Wed Apr 05, 2006 6:19 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
gsf

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

Items
PostPosted: Wed Apr 05, 2006 6:37 am    Post subject: Reply with quote

Lummox JR wrote:
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.

it might take longer to compute this canonical form than to solve the puzzle

a feature of keying off the solution is that the canonical puzzles for all puzzles
with the same solution are lexicographically related
one could catalog families of puzzles by canonical solutions with each member
of the family a canonical puzzle represented as an 81 bit mask of the cells
visible from the canonical solution

e.g., the canonical puzzles for all 17's derived from one solution grid
would be images of the canonical solution with 0's in different positions
Back to top
View user's profile Send private message Visit poster's website
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Wed Apr 05, 2006 4:56 pm    Post subject: Reply with quote

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.

Code:
Naked        Singles
      Hidden Singles
Naked/Hidden Pairs
Naked/Hidden Triples
Naked/Hidden Quads
Locked Candidates
...


My hypothetical solver would repeatedly search for all Naked Singles before advancing to Hidden Singles. Once it has advanced to Hidden Singles, it repeatedly searches for them. If none are found, then the search would advance to Naked/Hidden Pairs. If one or more are found, then the search drops back to the first solution technique and continues from there. The solver continues in this fashion until the puzzle is solved.

Now, the key to creating my equivalence classes is that two counters are kept for each solution technique. The first counter counts the number of times a technique was successful during its first invocation. The second counter counts the total number of times a technique was successful while solving the puzzle.

Two puzzles are equivalent if their corresponding counters are equal.

Note: There is one additional step that I would take on every puzzle: zero the first counter for Naked Singles. In my opinion, this makes for more (logically) uniform comparisons.
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Wed Apr 05, 2006 7:31 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Moritz

Joined: 07 Oct 2006
Posts: 23
:
Location: Edinburgh, Scotland

Items
PostPosted: Sat Oct 07, 2006 10:35 am    Post subject: Reply with quote

Hi,

Soultaker wrote:
For clarity; the (naive) algorithm I proposed was: try each of the 3 million or so possible permutations on the solution grid and determine which one results in the lexicographically smallest solution. Apply this same transformation to the original puzzle to bring it into normal form.


That's more or less what I implemented.
But you don't have to calculate all permutations. You can apply them to one number at a time, and as soon as you realise that you don't get the lexicographic minimum, you can abort this transformation and start the next one. Saves 50% execution time.

A good way to do this is to store all 3!^4 transformations in an array and then apply them one-by-one to each number (of course to the x and y coordinate seperately).

Moritz
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: Sat Oct 07, 2006 1:25 pm    Post subject: Reply with quote

Moritz wrote:
Hi,

Soultaker wrote:
For clarity; the (naive) algorithm I proposed was: try each of the 3 million or so possible permutations on the solution grid and determine which one results in the lexicographically smallest solution. Apply this same transformation to the original puzzle to bring it into normal form.


That's more or less what I implemented.

so what is the (estimated) average time-to-solve/time-to-canonicalize
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 Previous  1, 2, 3, 4, 5, 6  Next
Page 4 of 6

 
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