
View previous topic :: View next topic 
Author 
Message 
 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

Posted: Fri Mar 31, 2006 3:56 am Post subject: 


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 


 Lummox JR
 Joined: 07 Sep 2005  Posts: 202  :   Items 

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 differencemaybe not huge, but noticeable. 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

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


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 differencemaybe 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 1020%, 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 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

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


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 


 Lummox JR
 Joined: 07 Sep 2005  Posts: 202  :   Items 

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. 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

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


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 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

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


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 


 jedimaster
 Joined: 02 Apr 2006  Posts: 1  :   Items 

Posted: Sun Apr 02, 2006 7:30 am Post subject: I make puzzle generator & do it like this 


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 


 Ruud Site Admin
 Joined: 17 Sep 2005  Posts: 708  :  Location: Netherlands  Items 

Posted: Sun Apr 02, 2006 12:41 pm Post subject: 


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 


 Lummox JR
 Joined: 07 Sep 2005  Posts: 202  :   Items 

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 81digit number where the nongivens 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 lefttoright, topdown 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 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

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


Lummox JR wrote:  It occurs to me that another nice candidate for canonical puzzle form would be the minimum 81digit number where the nongivens 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 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

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.
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 


 Lummox JR
 Joined: 07 Sep 2005  Posts: 202  :   Items 

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. 

Back to top 


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

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


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 onebyone to each number (of course to the x and y coordinate seperately).
Moritz 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

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


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 timetosolve/timetocanonicalize 

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
