This summer, I'm delighted to share with you my discovery of queen Sudoku, a Sudoku which contains at least one pattern of 9 nonattacking chess queens anywhere in the solution grid (9x9), http://www.muljadi.org/QueenSudoku.htm
If you find any 9-queens patterns in Sudoku, could you please e-mail me the solution grid?
Paul Muljadi
P.S. Like last year's Magic Sudoku, Queen Sudoku can be generalized to nxn solution grid. However, Queen Sudoku requires you to know how the chess queen moves.
Queen Sudoku
21 posts
• Page 1 of 2 • 1, 2
by coloin » Fri Sep 22, 2006 1:02 pm
I have copied an entry from another thread as it wasnt really relevant there!
I acknowlege that it is only of partial relevance here !
According to Red Ed
97.5% of grids have a QS=0
~2.5% have a QS = 1
To extend the analagy - This QS=1 grid will also have a "Rooks score" of at least 1 [RS=1]
I have an inkling that every grid had an RS=1 somewhere in every grid ???
The MC grid has many [9! ?] rook patterns ! [Ony one QS]
Some [of the many minimal] puzzles will have an RS=1 [Each of these "templates " are equivalent ] and some will even have a QS=1
Some puzzles have a partial RS of 8 out of 9 [only 1 type]
Most minimal puzzles have a partial RS of 7 out of 9 [2 types]
Some have 6/9 [?3 types]
Very few have 5/9 [1 type]
There will of course be a variable number of these partial RSs in each minimal puzzle
However most of Gordons 17s that I have looked at have the 7/9 pattern -ie dont have 8/9 or 9/9.
Therefore 7 clues add 10 more.........
Of course this is stil too big a computation....10^15 ways to add 10 more clues at least.
Still there must be many of Gordons 17s which have 12 or 13 clues in common...this is approaching a search.
Possibly a useless observation then....
C
I acknowlege that it is only of partial relevance here !
According to Red Ed
97.5% of grids have a QS=0
~2.5% have a QS = 1
To extend the analagy - This QS=1 grid will also have a "Rooks score" of at least 1 [RS=1]
I have an inkling that every grid had an RS=1 somewhere in every grid ???
The MC grid has many [9! ?] rook patterns ! [Ony one QS]
Some [of the many minimal] puzzles will have an RS=1 [Each of these "templates " are equivalent ] and some will even have a QS=1
Some puzzles have a partial RS of 8 out of 9 [only 1 type]
Most minimal puzzles have a partial RS of 7 out of 9 [2 types]
Some have 6/9 [?3 types]
Very few have 5/9 [1 type]
There will of course be a variable number of these partial RSs in each minimal puzzle
However most of Gordons 17s that I have looked at have the 7/9 pattern -ie dont have 8/9 or 9/9.
Therefore 7 clues add 10 more.........
Of course this is stil too big a computation....10^15 ways to add 10 more clues at least.
Still there must be many of Gordons 17s which have 12 or 13 clues in common...this is approaching a search.
Possibly a useless observation then....
- Code: Select all
It may just be a coincidence but......have you noticed that all puzzles from any grid have from 5 to 9 clues
of the following inverse/disjointed template pattern equivalent ?
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|.6.|
+---+---+---+
|..7|...|...|
|...|..8|...|
|...|...|..9|
+---+---+---+
Most commonly, especially in many of Gfroyles 17s, there are 7 clues of the 9.
e.g a 17
+---+---+---+
|...|...|.12|
|3..|...|.6.|
|...|.4.|...|
+---+---+---+
|9..|...|5..|
|...|..1|.7.|
|.2.|...|...|
+---+---+---+
|...|35.|4..|
|..1|4..|8..|
|.6.|...|...|
+---+---+---+
and a 7 clue "disjointed template" [couldnt find an 8 clue]
+---+---+---+
|...|...|..2|
|...|...|...|
|...|.4.|...|
+---+---+---+
|9..|...|...|
|...|..1|...|
|...|...|...|
+---+---+---+
|...|3..|...|
|...|...|8..|
|.6.|...|...|
+---+---+---+
Did Gordon normalize them to this pattern and add the remaining clues ?
The inverse template [8 out of 9] can be found in in both Oceans 2 hardest puzzles.
All puzzles can be classified as to which maximum of 5,6,7,8 or 9 clue inverse templates they have within !
Here is a grid, any minimal puzzle from which can only have a 5 !
Code:
+---+---+---+
|...|...|782|
|...|...|164|
|...|...|935|
+---+---+---+
|732|984|...|
|684|512|...|
|159|376|...|
+---+---+---+
|965|123|...|
|347|698|...|
|218|745|...|
+---+---+---+
C
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by coloin » Fri Sep 22, 2006 4:35 pm
tarek wrote:Does this score change with isomorphism ???
I can see the QS changing, Qs=1 going to QS=0, assuming that another one doesnt become manefest !
However the RS wont change with isomorphism - they are all "equivalent"
C
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by coloin » Fri Sep 22, 2006 5:44 pm
well if you have 3 empty boxes [eg B159] and a full B234678...... - the maximum partial RS in any puzzle generated from this sub-grid will be 6/9 !
likewise if you have only 8 clue numbers in a puzzle [e.g. no 9 clue] then the most you can have is a partial RS of 8/9.
Starting form a full grid - I think in making a puzzle minimal takes away the clues which would give you a 9/9 RS
I dont know the exact distribution of the partial RS in a series of random puzzles ! It may not even be useful - just an observation that Gfroyles 17s all tend to be RS 7/9
C
likewise if you have only 8 clue numbers in a puzzle [e.g. no 9 clue] then the most you can have is a partial RS of 8/9.
Starting form a full grid - I think in making a puzzle minimal takes away the clues which would give you a 9/9 RS
I dont know the exact distribution of the partial RS in a series of random puzzles ! It may not even be useful - just an observation that Gfroyles 17s all tend to be RS 7/9
C
Last edited by coloin on Fri Sep 22, 2006 2:22 pm, edited 2 times in total.
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by Red Ed » Fri Sep 22, 2006 6:12 pm
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.
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.
- Red Ed
- Posts: 633
- Joined: 06 June 2005
by coloin » Fri Sep 22, 2006 6:33 pm
Red Ed wrote:The canonical grid has QS=7, which is uniquely the best among all grids that I've tested..
Mulling......but shouldnt it be 8 or 9 .....[ at least a factor of 648 ?]
Red Ed wrote: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.
Fair enough
Do you think every grid has RS=1 ? In which case they would be the weakest combination of clues !
C
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by Red Ed » Fri Sep 22, 2006 7:20 pm
QS isn't preserved by (the usual notion of) isomorphism; so, no, it needn't be a multiple of 648 (or a factor).
RS values are typically ~200. The MC grid has RS=2241 which I suspect is the max possible. The smallest possible is <100. I've seen RS=84 which can probably be beaten. But ultimately the question should be ... so what?!
RS values are typically ~200. The MC grid has RS=2241 which I suspect is the max possible. The smallest possible is <100. I've seen RS=84 which can probably be beaten. But ultimately the question should be ... so what?!
- Red Ed
- Posts: 633
- Joined: 06 June 2005
Re: Queen Sudoku
by Condor » Thu Apr 26, 2007 12:02 am
muljadi wrote:This summer, I'm delighted to share with you my discovery of queen Sudoku, a Sudoku which contains at least one pattern of 9 nonattacking chess queens anywhere in the solution grid (9x9), http://www.muljadi.org/QueenSudoku.htm
If you find any 9-queens patterns in Sudoku, could you please e-mail me the solution grid?
Paul Muljadi
Hi Paul
I tried your link but didn't see the QueenSudoku. Is the link still valid.
I posted something about sudokus where as many numbers as possible were not attaching each other here.
Posters at first thought I was just talking about the 2 main diagonals. Just go to the second page for the discussion.
I initially thought there was only 1 Sudoku Queen but udosuk pointed out that some occurances of the 2 of the digits could infact be swapped, making 2 near 'identical twins'.
dukuso also posted that it was not possible to do what I was trying to acheive. See his link for a proof.
Is that what you are looking for.
- Condor
- Posts: 62
- Joined: 19 June 2005
by Condor » Sun Apr 29, 2007 1:01 am
I had a look at your Queen Sudoku. I saw 9 cells highlighted. If queens are placed on those cells, they would not be attaching each other. In column 1 on the highlighted cell was the number 1, likewise in column 2 the highlighted cell contained 2, and so on for all the columns. Given some thought, I don't think that would be very difficult to achieve.
There are 46636 possible templates, of which 144 have this feature. I picked 1 and using Simple Sudoku placed the numbers 1 to 9 in the columns to match the template. Then adding a couple more numbers at random in each box, proceeded to produce a 'puzzle'. Initially the puzzle had 0 solutions, so that meant deleting some numbers and then placing some numbers in other places. When I had a puzzle with 1 solution, solved it to get the following:
*--------------------------*
| 5 8 3 | 7 1 9 | 6 4 2 |
| 2 9 1 | 5 4 6 | 8 7 3 |
| 6 7 4 | 3 2 8 | 1 5 9 |
| -------+-------+------- |
| 8 4 7 | 9 5 2 | 3 1 6 |
| 9 6 2 | 1 3 7 | 4 8 5 |
| 1 3 5 | 6 8 4 | 9 2 7 |
| -------+-------+------- |
| 7 5 9 | 4 6 1 | 2 3 8 |
| 4 2 6 | 8 7 3 | 5 9 1 |
| 3 1 8 | 2 9 5 | 7 6 4 |
*--------------------------*
Then I thought why have 1 to 9 matching the columns, why not the rows or boxes. The grid above can be rotated 90 degrees for rows. This one is boxes. It only takes a few minutes to produce them.
*-------------------------*
| 8 3 5 | 9 2 6 | 1 7 4 |
| 4 6 9 | 8 7 1 | 2 3 5 |
| 1 2 7 | 4 5 3 | 9 8 6 |
| -------+-------+------- |
| 2 9 8 | 5 6 4 | 3 1 7 |
| 7 5 3 | 1 8 9 | 6 4 2 |
| 6 1 4 | 7 3 2 | 5 9 8 |
| -------+-------+------- |
| 3 4 6 | 2 9 8 | 7 5 1 |
| 5 8 2 | 3 1 7 | 4 6 9 |
| 9 7 1 | 6 4 5 | 8 2 3 |
*-------------------------*
There are probably millions of grids that have these features.
Ps. Have a read up on the discussions of templates; it might help you with this.
There are 46636 possible templates, of which 144 have this feature. I picked 1 and using Simple Sudoku placed the numbers 1 to 9 in the columns to match the template. Then adding a couple more numbers at random in each box, proceeded to produce a 'puzzle'. Initially the puzzle had 0 solutions, so that meant deleting some numbers and then placing some numbers in other places. When I had a puzzle with 1 solution, solved it to get the following:
*--------------------------*
| 5 8 3 | 7 1 9 | 6 4 2 |
| 2 9 1 | 5 4 6 | 8 7 3 |
| 6 7 4 | 3 2 8 | 1 5 9 |
| -------+-------+------- |
| 8 4 7 | 9 5 2 | 3 1 6 |
| 9 6 2 | 1 3 7 | 4 8 5 |
| 1 3 5 | 6 8 4 | 9 2 7 |
| -------+-------+------- |
| 7 5 9 | 4 6 1 | 2 3 8 |
| 4 2 6 | 8 7 3 | 5 9 1 |
| 3 1 8 | 2 9 5 | 7 6 4 |
*--------------------------*
Then I thought why have 1 to 9 matching the columns, why not the rows or boxes. The grid above can be rotated 90 degrees for rows. This one is boxes. It only takes a few minutes to produce them.
*-------------------------*
| 8 3 5 | 9 2 6 | 1 7 4 |
| 4 6 9 | 8 7 1 | 2 3 5 |
| 1 2 7 | 4 5 3 | 9 8 6 |
| -------+-------+------- |
| 2 9 8 | 5 6 4 | 3 1 7 |
| 7 5 3 | 1 8 9 | 6 4 2 |
| 6 1 4 | 7 3 2 | 5 9 8 |
| -------+-------+------- |
| 3 4 6 | 2 9 8 | 7 5 1 |
| 5 8 2 | 3 1 7 | 4 6 9 |
| 9 7 1 | 6 4 5 | 8 2 3 |
*-------------------------*
There are probably millions of grids that have these features.
Ps. Have a read up on the discussions of templates; it might help you with this.
- Condor
- Posts: 62
- Joined: 19 June 2005
by Condor » Sun Apr 29, 2007 1:18 am
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.
Red Ed
There are 352 sets for a 9x9 grid when only rows, columns and diagonals are considered as constraints. The sudoku grid has the box constraint as well. There are only 144 templates that meet those 4 constriants.
I made my list by starting with my list of templates and checking to see which also meet the diagonal constraint.
The QS=7 seems to match my results here.
- Condor
- Posts: 62
- Joined: 19 June 2005
21 posts
• Page 1 of 2 • 1, 2
