## Queen Sudoku

Everything about Sudoku that doesn't fit in one of the other sections

### Queen Sudoku

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?

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.

Posts: 4
Joined: 15 July 2005

(deleted: see later)
Last edited by Red Ed on Fri Sep 22, 2006 2:09 pm, edited 1 time in total.
Red Ed

Posts: 633
Joined: 06 June 2005

Is there a grid where QS=0?

So, at the moment your best QS is 4... How many grids out of the 5 million did you find? Could you list them out please?
udosuk

Posts: 2698
Joined: 17 July 2005

(deleted: see later)
Last edited by Red Ed on Fri Sep 22, 2006 2:09 pm, edited 1 time in total.
Red Ed

Posts: 633
Joined: 06 June 2005

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

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: 1864
Joined: 05 May 2005

Does this score change with isomorphism ???

tarek

tarek

Posts: 3416
Joined: 05 January 2006

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: 1864
Joined: 05 May 2005

I can understand that that the RS should stay constant, however it seems that I may be missing the point here because I thought thought that RS should always be 9 or always it is not a sudoku

tarek

Posts: 3416
Joined: 05 January 2006

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
Last edited by coloin on Fri Sep 22, 2006 2:22 pm, edited 2 times in total.
coloin

Posts: 1864
Joined: 05 May 2005

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

Posts: 633
Joined: 06 June 2005

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: 1864
Joined: 05 May 2005

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?!
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Queen Sudoku

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?

Hi Paul

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

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.

Condor

Posts: 62
Joined: 19 June 2005

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

Next