Colouring the queen graphs

The n×n  queen graph has the squares of n×n chessboard for its vertices and two such vertices are adjacent if, and only if, queens placed on the two squares attack each other. On page 191 of The Unexpected Hanging And Other Mathematical Diversions, Martin Gardner states without a proof that the n×n queen graph is n-colourable whenever n mod 6 is 1 or 5.

The proof is easy: When the chessboard is thought of as the Cartesian square of {0,1,...,n-1}, colour vertex (i,j) by (j-2i) mod n. This construction is illustrated below on n=5 and on n=7.


  0     1     2     3     4  
  3     4     0     1     2  
  1     2     3     4     0  
  4     0     1     2     3  
  2     3     4     0     1  
          
  0     1     2     3     4     5     6  
  5     6     0     1     2     3     4  
  3     4     5     6     0     1     2  
  1     2     3     4     5     6     0  
  6     0     1     2     3     4     5  
  4     5     6     0     1     2     3  
  2     3     4     5     6     0     1  


Verifying that (as long as n mod 6 is 1 or 5) no two vertices of the same colour are adjacent is a routine exercise, but here are the details anyway.

Consider vertices (i,j) and (x,y) of the same colour. By definition,
(*)    2(x-i) is congruent to (y-j) mod n.
If the two vertices are in the same row (x=i), then (*) implies y=j. If the two vertices are in the same column (y=j), then (*) implies x=i since n is odd. If the two vertices are on the same diagonal, then x-i=y-j or x-i=j-y; in the former case, (*) implies (x,y)=(i,j); in the latter case, (*) implies (x,y)=(i,j) since 3 does not divide n.
The same argument (with the "x-i=y-j or x-i=j-y" replaced by x-i is congruent to y-j mod n or x-i is congruent to j-y mod n) shows that the colouring works even for more powerful queens, whose diagonal moves wrap around the chessboard. In this toroidal variation, the condition n mod 6 = 1 or 5 is not only sufficient but also necessary for the existence of an n-colouring: proofs of necessity have been found by The toroidal and three-dimensional variants of the n-queens problem are discussed in Three Dimensional Queens Problems (L.Allison, C.N.Yee, and M.McGaughey); a related bibliography has been maintained by Walter Kosters; we will restrict ourselves to the original theme on the ordinary chessboard with no wrap-arounds.

None of the n×n queen graphs with n = 2,3,4 or 6 is n-colourable: there is no stable set (= set of pairwise nonadjacent vertices) of size two in the 2×2 queen graph; there is no stable set of size three in the 3×3 queen graph; there are precisely two stable sets of size four in the 4×4 queen graph and neither of them includes a corner square of the board; there are precisely four stable sets of size six in the 6×6 queen graph and neither of them includes a corner square of the board.

Thorold Gosset (Messenger of Mathematics, Vol. 44, July 1914, page 48) gave an elegant proof that the 8×8 queen graph is not 8-colourable: Every stable set of size eight in this graph intersects the set of twenty cells marked below by X in at least three points (verifying this claim is greatly facilitated by the catalog of all stable sets of size eight in the 8×8 queen graph), and so at most six such sets can be pairwise disjoint.


             X  X  X  X            
       X                          X      
 X                                      X
 X                                      X
 X                                      X
 X                                      X
       X                          X      
             X  X  X  X            


A variation on Gosset's theme goes as follows: Every stable set of size eight in the 8×8 queen graph intersects the set of twelve cells marked below by Y in at most one point, and so twelve such sets are required to cover every Y.


 Y                                      Y
                                               
             Y              Y            
                   Y  Y                  
                   Y  Y                  
             Y              Y            
                                               
 Y                                      Y


More generally, if numerical weights are assigned to the vertices of the n×n queen graph in such a way that their sum over every stable set of size n is at most 1 and yet the total sum exceeds n, then the graph is not n-colourable.

The 9×9 queen graph is not 9-colourable (a fact established by the code LPCOLOR written by Anuj Mehrotra and Michael A.Trick), but the weighting argument is not strong enough to yield this conclusion: in the 9×9 queen graph, there is a family of 36 stable sets of size nine such that each of the 81 vertices belongs to precisely four stable sets in the family. This family consists of all sets obtained from the five sets shown below by rotating the chessboard and/or flipping it along one of its axes of symmetry.


 Q                                        
                Q                         
                                    Q     
           Q                              
                                         Q
                               Q          
                     Q                    
      Q                                   
                          Q               
 Q                                        
                     Q                    
                                         Q
                          Q               
                Q                         
      Q                                   
                                    Q     
           Q                              
                               Q          


      Q                                   
                     Q                    
                               Q          
                                         Q
           Q                              
                          Q               
                Q                         
 Q                                        
                                    Q     
           Q                              
                          Q               
                                    Q     
                     Q                    
 Q                                        
                                         Q
                               Q          
      Q                                   
                Q                         


      Q                                   
                Q                         
                                         Q
                               Q          
                     Q                    
           Q                              
 Q                                        
                          Q               
                                    Q     


Similarly, the 10×10 queen graph is not 10-colourable (Michel Vasquez and Günter Stertenbrink, independently of each other, established this fact by computer search), but the weighting argument is not strong enough to yield this conclusion.

Condition  n mod 6 = 1 or 5 , sufficient for n-colourability of the n×n queen graph, is also necessary when n<12. However, this condition is not necessary for all n: counterexamples were found by Michel Vasquez and Günter Stertenbrink, independently of each other. Vasquez's counterexamples with n=12 and n=14 appear in the manuscript New Results on the Queens n2 Graph Coloring Problems, submitted in June 2003 to Journal of Heuristics and published in its Volume 10, Number 4 (July 2004), pp. 407 -- 413; his additional counterexamples have n=15,16,18,20,24,28 and (counterexamples found in January 2004, February 2004, and May 2004, respectively) n=21, n=22, and n=32. Stertenbrink's counterexamples have n=12, n=14, and n=16; they were found in September 2003. Some of these counterexamples are reproduced below; Vasquez's counterexample with n=28 and n=32 appear on his web page.


0 5 9 6 3 8 4 1 10 11 7 2
7 11 4 2 1 6 10 3 0 8 9 5
8 1 10 9 5 2 0 7 11 6 3 4
10 0 3 8 7 11 9 5 4 1 2 6
5 6 11 4 2 1 3 0 8 9 10 7
11 7 0 1 10 4 8 6 3 2 5 9
2 8 6 3 9 5 7 11 1 10 4 0
3 4 5 0 11 10 6 9 2 7 8 1
9 2 1 10 4 7 5 8 6 3 0 11
4 10 7 11 0 3 1 2 9 5 6 8
6 3 2 5 8 9 11 4 7 0 1 10
1 9 8 7 6 0 2 10 5 4 11 3

 
A 12-colouring of the 12×12 queen graph



1 9 11 7 5 13 3 2 12 4 6 10 8 0
7 12 4 8 3 0 11 10 1 2 9 5 13 6
6 3 13 10 1 4 8 9 5 0 11 12 2 7
5 10 1 9 13 2 6 7 3 12 8 0 11 4
4 0 2 6 11 12 9 8 13 10 7 3 1 5
2 8 7 13 0 10 5 4 11 1 12 6 9 3
12 1 5 3 8 11 7 6 10 9 2 4 0 13
0 6 10 12 2 9 4 5 8 3 13 11 7 1
9 11 3 4 6 1 12 13 0 7 5 2 10 8
8 4 12 1 7 3 10 11 2 6 0 13 5 9
11 7 0 2 9 5 13 12 4 8 3 1 6 10
13 2 9 11 4 7 0 1 6 5 10 8 3 12
10 5 8 0 12 6 2 3 7 13 1 9 4 11
3 13 6 5 10 8 1 0 9 11 4 7 12 2

 
A 14-colouring of the 14×14 queen graph


1 10 2 3 8 4 11 12 7 14 13 0 9 6 5
13 3 1 6 2 5 0 10 8 9 12 11 14 7 4
0 7 5 11 1 9 14 2 6 4 3 13 12 10 8
9 12 14 7 6 8 1 4 5 2 11 10 0 3 13
11 6 3 4 9 0 12 13 10 8 14 1 5 2 7
12 14 8 13 3 11 2 5 4 1 6 7 10 0 9
4 2 12 5 10 6 13 7 3 11 0 9 8 14 1
5 11 4 1 7 14 10 0 9 13 8 2 3 12 6
2 13 7 10 0 12 4 8 14 5 9 6 11 1 3
10 0 9 8 5 2 3 6 1 12 4 14 7 13 11
8 1 6 2 13 7 9 14 11 0 10 3 4 5 12
14 4 0 9 12 1 6 3 2 7 5 8 13 11 10
7 9 11 14 4 3 5 1 13 10 2 12 6 8 0
3 8 13 12 11 10 7 9 0 6 1 5 2 4 14
6 5 10 0 14 13 8 11 12 3 7 4 1 9 2

 
A 15-colouring of the 15×15 queen graph


0 4 12 8 11 15 2 6 7 3 14 10 9 13 5 1
1 8 11 3 6 12 14 5 4 15 13 7 2 10 9 0
7 5 15 0 8 11 13 2 3 12 10 9 1 14 4 6
9 13 2 14 5 6 1 10 11 0 7 4 15 3 12 8
4 14 6 13 1 10 9 3 2 8 11 0 12 7 15 5
10 3 1 9 12 5 7 15 14 6 4 13 8 0 2 11
15 9 10 7 2 0 4 12 13 5 1 3 6 11 8 14
12 2 5 6 15 1 10 9 8 11 0 14 7 4 3 13
14 0 7 4 13 3 8 11 10 9 2 12 5 6 1 15
13 11 8 5 0 2 6 14 15 7 3 1 4 9 10 12
8 1 3 11 14 7 5 13 12 4 6 15 10 2 0 9
6 12 4 15 3 8 11 1 0 10 9 2 14 5 13 7
11 15 0 12 7 4 3 8 9 2 5 6 13 1 14 10
5 7 13 2 10 9 15 0 1 14 8 11 3 12 6 4
3 10 9 1 4 14 12 7 6 13 15 5 0 8 11 2
2 6 14 10 9 13 0 4 5 1 12 8 11 15 7 3

 
A 16-colouring of the 16×16 queen graph


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
8 4 5 6 1 10 17 3 2 15 14 0 7 16 11 12 13 9
10 13 8 14 0 6 15 12 16 1 5 2 11 17 3 9 4 7
16 7 17 13 8 11 5 14 15 2 3 12 6 9 4 0 10 1
2 8 12 1 7 13 3 0 11 6 17 14 4 10 16 5 9 15
6 14 10 16 15 17 12 13 9 8 4 5 0 2 1 7 3 11
5 16 0 11 9 2 14 10 4 13 7 3 15 8 6 17 1 12
11 2 3 12 17 4 16 9 7 10 8 1 13 0 5 14 15 6
9 17 4 7 3 1 2 5 6 11 12 15 16 14 10 13 0 8
4 11 9 10 12 15 0 1 14 3 16 17 2 5 7 8 6 13
7 3 16 0 13 9 11 2 5 12 15 6 8 4 17 1 14 10
13 9 15 5 10 0 1 6 3 14 11 16 17 7 12 2 8 4
15 5 6 8 14 16 7 17 13 4 0 10 1 3 9 11 12 2
14 0 1 2 5 8 4 11 10 7 6 13 9 12 15 16 17 3
1 12 13 15 11 14 10 8 17 0 9 7 3 6 2 4 5 16
3 15 7 17 6 12 9 4 1 16 13 8 5 11 0 10 2 14
17 6 14 9 2 7 13 16 12 5 1 4 10 15 8 3 11 0
12 10 11 4 16 3 8 15 0 17 2 9 14 1 13 6 7 5

 
An 18-colouring of the 18×18 queen graph


0 4 8 12 11 16 6 19 15 3 2 14 18 7 17 10 13 9 5 1
8 15 0 4 18 12 2 11 6 17 16 7 10 3 13 19 5 1 14 9
4 18 17 8 0 10 3 15 12 7 6 13 14 2 11 1 9 16 19 5
11 0 4 13 14 2 7 8 19 16 17 18 9 6 3 15 12 5 1 10
13 19 14 0 4 9 16 2 10 6 7 11 3 17 8 5 1 15 18 12
14 10 18 17 5 6 13 1 9 2 3 8 0 12 7 4 16 19 11 15
18 3 7 16 10 1 9 12 5 14 15 4 13 8 0 11 17 6 2 19
7 9 13 5 3 15 19 16 1 10 11 0 17 18 14 2 4 12 8 6
19 12 1 11 17 5 8 6 2 15 14 3 7 9 4 16 10 0 13 18
1 7 9 3 15 19 12 5 16 11 10 17 4 13 18 14 2 8 6 0
3 5 11 1 13 17 14 7 18 9 8 19 6 15 16 12 0 10 4 2
17 14 3 9 19 7 10 4 0 13 12 1 5 11 6 18 8 2 15 16
5 11 15 7 1 13 17 18 3 8 9 2 19 16 12 0 6 14 10 4
16 1 5 18 8 3 11 14 7 12 13 6 15 10 2 9 19 4 0 17
12 8 16 19 7 4 15 3 11 0 1 10 2 14 5 6 18 17 9 13
15 17 12 2 6 11 18 0 8 4 5 9 1 19 10 7 3 13 16 14
9 2 6 15 12 0 5 10 17 18 19 16 11 4 1 13 14 7 3 8
6 16 19 10 2 8 1 13 14 5 4 15 12 0 9 3 11 18 17 7
10 13 2 6 16 14 0 9 4 19 18 5 8 1 15 17 7 3 12 11
2 6 10 14 9 18 4 17 13 1 0 12 16 5 19 8 15 11 7 3

 
A 20-colouring of the 20×20 queen graph


3 7 11 15 13 14 8 12 1 19 5 9 4 20 16 17 0 10 6 18 2
19 12 3 7 16 5 1 10 9 4 0 18 14 17 13 8 11 2 20 15 6
7 20 19 9 3 8 17 13 0 5 16 1 15 11 12 4 14 6 18 2 10
11 3 7 18 10 12 5 1 20 9 4 0 16 13 15 19 2 17 8 6 14
1 8 15 3 7 11 20 4 14 0 13 10 5 18 17 16 6 9 2 19 12
18 9 5 16 17 2 6 0 3 7 8 20 19 12 14 1 10 15 11 4 13
17 14 13 12 18 15 10 8 2 6 19 3 7 1 9 5 20 4 16 0 11
20 18 8 14 19 13 2 6 4 10 1 16 17 5 11 3 7 0 12 9 15
5 15 12 17 6 16 4 18 11 14 9 19 10 7 1 2 13 20 3 8 0
10 19 2 1 11 20 0 17 16 15 12 14 13 9 5 6 3 8 4 7 18
6 1 17 5 14 9 16 2 10 13 20 15 8 0 18 11 12 7 19 3 4
16 5 6 10 1 4 7 11 15 12 14 13 18 19 2 20 9 3 0 17 8
2 10 1 20 15 0 3 5 8 17 11 12 9 16 6 18 4 19 14 13 7
13 11 14 2 5 1 9 7 19 18 3 8 6 4 0 15 17 12 10 16 20
9 2 18 6 20 7 11 3 5 1 17 4 0 10 8 13 16 14 15 12 19
15 6 9 13 8 3 12 14 17 20 10 5 1 2 4 0 19 18 7 11 16
14 17 0 11 4 18 19 16 7 8 15 2 12 6 20 9 5 1 13 10 3
12 4 10 19 0 17 13 15 18 2 6 11 20 3 7 14 8 16 5 1 9
8 0 16 4 12 6 14 9 13 3 18 7 2 15 19 10 1 11 17 20 5
4 13 20 0 9 10 15 19 12 16 2 6 11 8 3 7 18 5 1 14 17
0 16 4 8 2 19 18 20 6 11 7 17 3 14 10 12 15 13 9 5 1

 
A 21-colouring of the 21×21 queen graph


0 2 4 6 8 10 12 14 16 18 20 21 19 17 15 13 11 9 7 5 3 1
4 6 8 2 1 21 17 10 12 15 19 18 14 13 11 16 20 0 3 9 7 5
2 0 10 4 6 8 19 13 14 20 17 16 21 15 12 18 9 7 5 11 1 3
17 4 2 8 0 14 11 6 18 13 21 20 12 19 7 10 15 1 9 3 5 16
6 15 0 16 2 20 8 4 10 12 18 19 13 11 5 9 21 3 17 1 14 7
12 11 19 17 21 9 15 0 7 2 4 5 3 6 1 14 8 20 16 18 10 13
14 20 18 0 13 7 5 11 3 16 9 8 17 2 10 4 6 12 1 19 21 15
10 13 16 7 5 3 20 19 9 1 14 15 0 8 18 21 2 4 6 17 12 11
9 7 3 13 20 18 1 17 15 5 11 10 4 14 16 0 19 21 12 2 6 8
19 5 11 1 9 16 14 21 6 3 13 12 2 7 20 15 17 8 0 10 4 18
1 9 14 3 7 5 10 12 20 19 16 17 18 21 13 11 4 6 2 15 8 0
3 12 5 11 18 17 21 1 8 7 15 14 6 9 0 20 16 19 10 4 13 2
7 1 9 10 3 15 4 18 17 21 12 13 20 16 19 5 14 2 11 8 0 6
15 8 7 20 4 13 16 2 19 0 10 11 1 18 3 17 12 5 21 6 9 14
5 3 6 19 16 12 0 20 11 14 8 9 15 10 21 1 13 17 18 7 2 4
21 14 1 12 17 19 6 8 4 10 3 2 11 5 9 7 18 16 13 0 15 20
18 17 21 14 11 0 13 7 2 8 5 4 9 3 6 12 1 10 15 20 16 19
16 19 20 15 10 2 9 5 13 6 1 0 7 12 4 8 3 11 14 21 18 17
8 21 13 5 19 11 3 15 0 17 7 6 16 1 14 2 10 18 4 12 20 9
11 18 12 9 15 6 2 16 21 4 0 1 5 20 17 3 7 14 8 13 19 10
20 16 15 18 12 4 7 9 1 11 2 3 10 0 8 6 5 13 19 14 17 21
13 10 17 21 14 1 18 3 5 9 6 7 8 4 2 19 0 15 20 16 11 12

 
A 22-colouring of the 22×22 queen graph



0 4 8 12 16 20 19 23 14 3 7 10 11 6 2 15 22 18 21 17 13 9 5 1
8 11 0 4 15 12 6 3 20 19 23 17 16 22 18 21 2 7 13 14 5 1 10 9
4 19 12 8 0 7 2 16 11 14 22 21 20 23 15 10 17 3 6 1 9 13 18 5
22 0 4 18 12 21 8 17 7 15 11 3 2 10 14 6 16 9 20 13 19 5 1 23
14 23 20 0 4 18 16 13 3 8 10 7 6 11 9 2 12 17 19 5 1 21 22 15
18 8 17 15 23 6 21 10 0 4 13 2 3 12 5 1 11 20 7 22 14 16 9 19
15 13 16 19 10 9 20 2 6 22 0 4 5 1 23 7 3 21 8 11 18 17 12 14
11 7 15 22 20 2 13 9 17 5 1 18 19 0 4 16 8 12 3 21 23 14 6 10
17 22 21 3 5 10 1 6 13 9 19 14 15 18 8 12 7 0 11 4 2 20 23 16
21 18 1 23 9 13 5 14 16 2 6 11 10 7 3 17 15 4 12 8 22 0 19 20
3 12 9 5 19 1 11 7 23 21 16 15 14 17 20 22 6 10 0 18 4 8 13 2
5 1 7 11 3 17 12 20 8 18 14 22 23 15 19 9 21 13 16 2 10 6 0 4
7 3 5 9 1 19 14 22 10 16 12 20 21 13 17 11 23 15 18 0 8 4 2 6
1 14 11 7 17 3 9 5 21 23 18 13 12 19 22 20 4 8 2 16 6 10 15 0
23 16 3 21 11 15 7 12 18 0 4 9 8 5 1 19 13 6 14 10 20 2 17 22
19 20 23 1 7 8 3 4 15 11 17 12 13 16 10 14 5 2 9 6 0 22 21 18
9 5 13 20 22 0 15 11 19 7 3 16 17 2 6 18 10 14 1 23 21 12 4 8
13 15 18 17 8 11 22 0 4 20 2 6 7 3 21 5 1 23 10 9 16 19 14 12
16 10 19 13 21 4 23 8 2 6 15 0 1 14 7 3 9 22 5 20 12 18 11 17
12 21 22 2 6 16 18 15 1 10 8 5 4 9 11 0 14 19 17 7 3 23 20 13
20 2 6 16 14 23 10 19 5 13 9 1 0 8 12 4 18 11 22 15 17 7 3 21
6 17 14 10 2 5 0 18 9 12 20 23 22 21 13 8 19 1 4 3 11 15 16 7
10 9 2 6 13 14 4 1 22 17 21 19 18 20 16 23 0 5 15 12 7 3 8 11
2 6 10 14 18 22 17 21 12 1 5 8 9 4 0 13 20 16 23 19 15 11 7 3

 
A 24-colouring of the 24×24 queen graph


In July 2005, Vasquez found a 26-colouring of the 26×26 queen graph.


Problem 1. Is the 27×27 queen graph 27-colourable?


In some cases an r-colouring of the r×r queen graph and an s-colouring of the s×s queen graph can be composed to yield an rs-colouring of the rs×rs queen graph. The idea appears in B. Abramson and M. M. Yung, Construction through decomposition: a divide-and-conquer algorithm for the N-queens problem, Fall Joint Computer Conference Nov 1986, pp. 620-628: The rs×rs chessboard may be thought of as an s×s board of compound squares, each of which is an r×r chessboard in its own right; given a colouring f of the r×r queen graph by colours 0,1,...,r-1 and given a colouring g of the s×s queen graph by colours 0,1,...,s-1, we assign to each square u of the rs×rs chessboard the integer h(u) defined by

h(u) = rg(w) + f(v),
where w is the compound square that contains u and where v specifies the location of u within the r×r chessboard w. This construction, with r=5, s=12, and with f,g as defined on this page, is illustrated on a separate page; in this particular case (as pointed out by Günter Stertenbrink), it happens to produce a 60-colouring of the 60×60 queen graph.


Problem 2. True or false? For all sufficiently large n, the n×n queen graph is n-colourable.



Back to Vašek Chvátal's home page