# Chromatic number of Queen move chessboard graph

On a regular chess board, let every square represent a vertex. Then, two vertices are connected iff a queen can travel from one square to another in one move (directly).

I'm trying to calculate the chromatic number of this graph. I know it is 2, 4, 8, 8 for knight, king, bishop and rook respectively. I have proven (not rigorously) that the chromatic number for the queen is greater than 8.

PS: Not a HW problem.

• The mention of "Queen tour" in the title is a little confusing, but maybe it is made up by the clarity of the body of your Question. I would start with coloring a smallish board, say $3\times 3$. Note that the chromatic number of an $8\times 8$ board must be at least that of a smaller board. – hardmath Dec 9 '15 at 14:41
• The chromatic number is greater than $8$ for the queen (or rook, or bishop) because the graph has a subgraph isomorphic to $K_8$, the complete graph on $8$ nodes. All eight nodes on row must be different colors. Same for a column. Same for the diagonals. – Thomas Andrews Dec 9 '15 at 14:41
• I'm fairly certain it is 8 for rook and bishop. I'll check again though – thorium Dec 9 '15 at 14:43
• @Thomas Andrews: that shows the number is at least $8$. For the rook it is $8$. You can color each square with the sum of the coordinates $\bmod 8$ – Ross Millikan Dec 9 '15 at 14:50
• The existence of an $11\times 11$ pandiagonal latin square shows that the chromatic number of queen moves on an $8\times 8$ board is at most $11$. – hardmath Dec 11 '15 at 14:17

I wrote a C++ program to brute-force this problem. I have copied it below. There are no $8$-color solutions, but here is a $9$-color one: $$\begin{array}{cccccccc} 7&8&4&9&6&2&1&5\\ 2&1&7&5&3&4&9&6\\ 5&6&2&1&8&7&3&4\\ 4&3&5&6&2&9&8&1\\ 8&7&9&3&4&5&6&2\\ 9&5&6&8&1&3&4&7\\ 3&4&1&2&7&8&5&9\\ 1&2&3&4&5&6&7&8 \end{array}$$ Here is the program. It took half an hour for it to find a solution on my computer. If you set n = 10 it can find a $10$-color solution rather quickly, however:

#include <array>
#include <iostream>

//typedef for the type I use to represent a board with colors on it.
//Changing the dimensions of the board is not recommended as there
//are several other places in the program that assumes it's just 8x8.
typedef std::array<std::array<int, 8>, 8> lulz;

//Forward declarations
bool puzzle(int);
lulz solve(lulz, int);
bool check(lulz, int, int, int);

int main(int argc, char* arg[])
{
int n = 8;

//Test for each integer >=8 whether there is a queen-safe coloring
while (!puzzle(n++));

return 0;
}

bool puzzle(int n)
{
std::cout << "Testing for " << n << " colors." << std::endl;
//I use zeroes to signify squares not yet colored, except for the square with
//coordinates [0][0], where 0 is used as a flag for "no solution found"
lulz board;

//Filling the board with zeroes, except for the first row,
//which must have eight distinct colors anyway.
for (int i = 0; i < 8; i++)
{
board[i][0] = i+1;

for (int j = 1; j < 8; j++)
board[i][j] = 0;
}

//Recursive solution call
board = solve(board, n);

//Printing out the first solution found if any and returning true
if (board[0][0] != 0)
{
//The coordinates of the board follows as closely as possible the standard chess
//square coordinates, with [0][0] representing a1 and [3][5] representing d6.
for (int j = 0; j < 8; j++)
{
for (int i = 0; i < 8; i++)
{
std::cout << board[i][7-j] << " ";
if (board[i][7 - j] < 10) std::cout << " ";
}
std::cout << std::endl;
}

return true;
}

//Returning false if no solutions found
return false;
}

//The recursive solver
lulz solve(lulz b, int n)
{
int x = 0, y = 1;

//Find the first uncolored square on the board
while (b[x][y] != 0)
{
x++;
if (x == 8)
{
x = 0;
y++;
}
}

//This test can be uncommented to print the progress continuously.
//As written it's best suited for n = 9 in my opinion, and a great help to see that
//the program is actually moving forwards. It prints out the first two "free" rows,
//since the first row is just 12345678 anyways.
/*
if (x == 0 && y == 3)
{
std::cout << "Progress: First two free lines equal to " << b[0][2] << b[1][2] << b[2][2] << b[3][2] << b[4][2] << b[5][2] << b[6][2] << b[7][2] << std::endl;
std::cout << "                                        " << b[0][1] << b[1][1] << b[2][1] << b[3][1] << b[4][1] << b[5][1] << b[6][1] << b[7][1] << std::endl << std::endl;
}
*/
//Dummy board
lulz c;

//Loop over all colors
for (int i = 1; i <= n; i++)
{
//If the color i is allowed in square [x][y], fill it in and call next recursion level down
if (check(b, x, y, i))
{
b[x][y] = i;

//Base case, full solution found
if (y == 7 && x == 7) return b;

c = solve(b, n);

//If the recursive call found a solution, return that solution
if (c[0][0] != 0) return c;
}
}

//If the board is unsolvable (the return statement in the loop never triggered), set flag and return
b[0][0] = 0;

return b;
}

bool check(lulz b, int x, int y, int i)
{
//Check earlier squares in row y
for (int k = 1; k <= x; k++)
{
if (b[x-k][y] == i) return false;
}

//Check earlier squares in column x
for (int k = 1; k <= y; k++)
{
if (b[x][y-k] == i) return false;
}

//Check earlier squares in the down-left diagonal
for (int k = 1; k <= std::min(x, y); k++)
{
if (b[x-k][y-k] == i) return false;
}

//Check earlier squares in the down-right diagonal
for (int k = 0; k <= std::min(7-x, y); k++)
{
if (b[x+k][y-k] == i) return false;
}

return true;
}

• This agrees with the literature. Bell and Stevens, A survey of known results and research areas for n-queens, cite a 1976 book "on mathematics and chess" by E. Ya. Gik, Matematika na shakhmatnoi doske (Russian), for the result that the $8\times 8$ chessboard can be colored with nine colors (so that queens on any common color do not attack one another). The coloring of an $n\times n$ "chessboard" was posed by V.V. Menon as Math. Monthly problem E1782 in 1965, with a partial solution given the next year by M. Goldberg. – hardmath Dec 12 '15 at 2:11