Queen Sudoku

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

Queen Sudoku

Postby muljadi » Thu Sep 21, 2006 1:52 am

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.
muljadi
 
Posts: 4
Joined: 15 July 2005

Postby Red Ed » Thu Sep 21, 2006 6:17 am

(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

Postby udosuk » Thu Sep 21, 2006 12:05 pm

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

Postby Red Ed » Thu Sep 21, 2006 5:56 pm

(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

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

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

Postby tarek » Fri Sep 22, 2006 2:19 pm

Does this score change with isomorphism ???

tarek
User avatar
tarek
 
Posts: 2650
Joined: 05 January 2006

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

Postby tarek » Fri Sep 22, 2006 4:55 pm

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:(:!:
User avatar
tarek
 
Posts: 2650
Joined: 05 January 2006

Postby 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
Last edited by coloin on Fri Sep 22, 2006 2:22 pm, edited 2 times in total.
coloin
 
Posts: 1709
Joined: 05 May 2005

Postby 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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

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

Postby 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?!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Queen Sudoku

Postby 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

Postby 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.
Condor
 
Posts: 62
Joined: 19 June 2005

Postby 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

Next

Return to General