Breadth first search: Knight cover

Question

I'm trying to follow the USACO training course on algorithms (http://ace.delos.com/usacogate) - and I am currently at a page that describes DFS, BFS etc. I do understand these concepts, but the sample problem they've given for BFS - knight cover - has me puzzled. Here's the problem statement:

Place as few knights as possible on an n x n chess board so that every square is attacked. A knight is not considered to attack the square on which it sits.

This is BFS, the page says, since it tries to see if there's a solution with n knights before trying n+1 knights - which is pretty clear.

However, I don't understand how to formulate the solution from this alone. Can someone help me with the pseudocode for this?

Thanks much in advance!

Answer 1

It is BFS, but you don't search the chessboard; search the space of placements:

Initial state: no knight is placed

Valid move: place a knight on any unoccupied tile

Goal state: all tiles are either occupied or attacked

basic algorithm (BFS of the state space):

• push the initial state to the BFS queue.
• while there is something in the queue:
  • remove one state from the queue.
  • for every unoccupied tile:
    • create a copy of the current state.
    • add one knight to that tile.
    • if the new state doesn't exist in the queue:
      • if the new state is a goal state, finish.
      • else add it to the queue.

Note that I'm assuming that all paths to a state are of the same length. This is true when looking for a set of placements this way, but it is not true in general. In cases where this is not true, you should store the set of all visited nodes to avoid revisiting already explored states.

---

You may require the knights be added left-to-right, top-to-bottom. Then you don't need to check for duplicates in the queue. Additionally, you may discard a state early if you know that an unattacked tile cannot be attacked without violating the insertion order.

If you don't do this and leave the duplicate check as well, the algorithm will still produce correct results, but it will do so much slower. 40 000 times slower, approximately (8!=40 320 is the number of duplicates of an 8-knight state).

---

If you want a faster algorithm, look into A*. Here, one possible heuristic is:

• count the number of unattacked and unoccupied tiles
• divide the count by nine, rounding up (a knight cannot attack more than eight new tiles or occupy more than one)
• the distance (number of knights needed to be added) is no more than this number.

A better heuristic would note the fact that a knight can only attack tiles of the same color, and occupy a tile of the opposite color. This may improve the previous heuristic slightly (but still potentially help a lot).

A better heuristic should be able to exploit the fact that a knight can cover free spots in no more than a 5x5 square. A heuristic should compute fast, but this may help when there are few spots to cover.

---

Technical details:

You may represent each state as a 64-bit bit-mask. While this requires some bitwise manipulation, it really helps memory, and equality checking of 64-bit numbers is fast. If you can't have a 64-bit number, use two 32-bit numbers - these should be available.

Circular array queue is efficient, and it's not that hard to expand its capacity. If you have to implement your own queue, pick this one.

Answer 2

Here is an implementation in C++.

It just uses the basic brute force, so it is only good only till n = 5.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool isFinal(vector<vector<bool> >& board, int n)
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(!board[i][j])
                return false;
        }
    }
    return true;
}

void printBoard(vector<pair<int,int> > vec, int n)
{
    vector<string> printIt(n);
    for(int i = 0; i < n; ++i)
    {
        string s = "";
        for(int j = 0; j < n; ++j)
        {
            s += ".";
        }
        printIt[i] = s;
    }

    int m = vec.size();

    for(int i = 0; i < m; ++i)
    {
        printIt[vec[i].first][vec[i].second] = 'x';
    }

    for(int i = 0; i < n; ++i)
    {
        cout << printIt[i] << endl;
    }
    cout << endl;
}

void updateBoard(vector<vector<bool> >& board, int i, int j, int n)
{
    board[i][j] = true;

    if(i-2 >= 0 && j+1 < n)
        board[i-2][j+1] = true;

    if(i-1 >= 0 && j+2 < n)
        board[i-1][j+2] = true;

    if(i+1 < n && j+2 < n)
        board[i+1][j+2] = true;

    if(i+2 < n && j+1 < n)
        board[i+2][j+1] = true;

    if(i-2 >= 0 && j-1 >= 0)
        board[i-2][j-1] = true;

    if(i-1 >= 0 && j-2 >= 0)
        board[i-1][j-2] = true;

    if(i+1 < n && j-2 >= 0)
        board[i+1][j-2] = true;

    if(i+2 < n && j-1 >= 0)
        board[i+2][j-1] = true;
}

bool isThere(vector<pair<int,int> >& vec, vector<vector<pair<int,int> > >& setOfBoards, int len)
{
    for(int i = 0; i < len; ++i)
    {
        if(setOfBoards[i] == vec)
            return true;
    }
    return false;
}

int main()
{
    int n;
    cin >> n;

    vector<vector<pair<int,int> > > setOfBoards;
    int len = 0;

    vector<vector<bool> > startingBoard(n);
    for(int i = 0; i < n; ++i)
    {
        vector<bool> vec(n,0);
        startingBoard[i] = vec;
    }

    vector<pair<int,int> > startingVec;

    vector<vector<vector<vector<bool> > > > q1;

    vector<vector<vector<pair<int,int> > > > q2;

    vector<vector<vector<bool> > > sLayer1;

    vector<vector<pair<int,int> > > sLayer2;

    sLayer1.push_back(startingBoard);

    sLayer2.push_back(startingVec);

    q1.push_back(sLayer1);

    q2.push_back(sLayer2);

    int k = 0;

    bool flag = false;

    int count = 0;

    while(!flag && !q1[k].empty())
    {
        int m = q1[k].size();

        vector<vector<vector<bool> > > layer1;

        vector<vector<pair<int,int> > > layer2;

        q1.push_back(layer1);

        q2.push_back(layer2);

        for(int l = 0; l < m; ++l)
        {
            vector<vector<bool> > board = q1[k][l];

            vector<pair<int,int> > vec = q2[k][l];

            if(isFinal(board, n))
            {
                while(l < m)
                {
                    board = q1[k][l];
                    vec = q2[k][l];

                    if(isFinal(board, n))
                    {
                        printBoard(vec, n);

                        ++count;
                    }

                    ++l;
                }

                flag = true;
                break;
            }

            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    if(!board[i][j])
                    {
                        pair<int,int> p;
                        p.first = i;
                        p.second = j;

                        vector<vector<bool> > newBoard = board;

                        vector<pair<int,int> > newVec = vec;

                        newVec.push_back(p);

                        updateBoard(newBoard, i, j, n);

                        sort(newVec.begin(), newVec.end());

                        if(!isThere(newVec, setOfBoards, len))
                        {
                            q1[k+1].push_back(newBoard);
                            q2[k+1].push_back(newVec);

                            setOfBoards.push_back(newVec);
                            ++len;
                        }
                    }
                }
            }
        }

        ++k;
    }

    cout << count << endl;
}