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   

Has anyone tried solving these puzzles using templates?
Goto page Previous  1, 2, 3
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Jun 29, 2006 11:39 pm    Post subject: Reply with quote

daj95376 wrote:
Would you please expand on the particulars of the comparisons performed and how overlapping combinations are filtered

Each template (digit configuration) is stored in 3 32-bit integers.
27 bits in each integer are used for 3 rows of data.

The class that implements the template has several bitwise methods, which use the 3 integers simulaneously.

Methods include:

Indexed Biton and Bitoff
Bitwise Or
Bitwise And
Bitwise Xor
Bitwise Complement
(non)Zero test

An overlap is tested with Bitwise And + Nonzero test
Filtering is best performed by maintaining a double linked list, removing nodes from the list as required. An array can be used to rebuild the list.

Ruud
Back to top
View user's profile Send private message Visit poster's website
PeteTy

Joined: 10 Jun 2006
Posts: 2
:

Items
PostPosted: Thu Nov 02, 2006 7:15 pm    Post subject: POM Reply with quote

POM

these pattern overlays got me wondering

is this similar to the old problem of putting 8 non attacking queens on a chessboard?
or it would be a 9x9 chessboard with nine queens?
the 8x8 has 12 solutions
the 9x9 has 46 .
after rotations and reflections are omitted

with sudoku grids able to be rotated column for column and cute for chute or tower for tower in addition.... this seems to end up being way less than thousands

when you eliminate the diagonal move and place a rook in a nonet with sudoku grids able to be rotated column for column and tower for tower
isnt this a lot less?

I tend to be wrong a lot in sudoku forums but ill write a bfbi program real quick and find out.
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Fri Nov 03, 2006 8:24 pm    Post subject: Reply with quote

I also thought the non attacking rook patterns [RS] were more relevant to sudoku puzzles/grids ....................
This
Code:
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|.6.|
+---+---+---+
|..7|...|...|
|...|..8|...|
|...|...|..9|
+---+---+---+


The many ways to represent this are essentially "equivalent"

9! for relabelling
6^8 for row/ comumn/ box/ shuffling.....but some are counted twice !

Is there one in every grid ?

a relevant post was here Queen sudoku

I have no idea how Red Ed came up with these figures....but he is probably right..

Red Ed wrote:
Oops, sorry, I messed up earlier. There are actually 352 sets of nine non-attacking queens on a 9x9 grid, not 144 as originally claimed. The canonical grid has QS=7, which is uniquely the best among all grids that I've tested.

I don't think that QS or RS (which, by analogy with QS, should be a score out of 9! = 362880) is a very natural or useful score, though, since neither pays any attention to the box constraint of sudoku.


The non-attacking queens template is not usually preserved by swapping box/row/colums.

Can you take it furthur ?

In particular the question I asked
coloin wrote:
Do you think every grid has RS equal to or greater than 1 ? In which case they would be the weakest combination of clues !


Red Ed seemed to think that the average grid had a RS of around 200, [min found was 84], which probably answers the question.......

May not be relevant to anything........

C
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2, 3
Page 3 of 3

 
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