2
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Dec 9, 2015 at 14:41
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 9, 2015 at 14:41
  • $\begingroup$ I'm fairly certain it is 8 for rook and bishop. I'll check again though $\endgroup$
    – thorium
    Dec 9, 2015 at 14:43
  • $\begingroup$ @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$ $\endgroup$ Dec 9, 2015 at 14:50
  • 1
    $\begingroup$ 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$. $\endgroup$
    – hardmath
    Dec 11, 2015 at 14:17

1 Answer 1

4
$\begingroup$

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;
}
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Dec 12, 2015 at 2:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .