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 '15 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$ – Thomas Andrews Dec 9 '15 at 14:41
  • $\begingroup$ I'm fairly certain it is 8 for rook and bishop. I'll check again though $\endgroup$ – thorium Dec 9 '15 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$ – Ross Millikan Dec 9 '15 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 '15 at 14:17
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 '15 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.