Geek asks and answers

First Place Search: Knight

I am trying to follow the USACO algorithms training course ( http://ace.delos.com/usacogate ) - and now I am on a page describing DFS, BFS, etc. I understand these concepts, but the problem with the pattern that they gave to BFS - the jousting cover - is puzzling to me. Here is a description of the problem:

Place as few knights as possible on the nxn chessboard to attack each square. A knight is not considered an attack on the square on which he is sitting.

This is the BFS, this page says, as it tries to see if there is a solution with the nknights before trying the knights n+1- this is pretty clear.

However, I do not understand how to formulate a solution only from this. Can someone help me with pseudo code for this?

Many thanks!

+5
source share
2 answers

This is a BFS, but you are not looking for a chessboard; placement search:

Initial state: the knight is not placed

Actual move: place the knight on any unoccupied tile

Target Status: All tiles are busy or attacked.

basic algorithm (BFS state space):

  • push the initial state to the BFS queue.
  • while there is something in the queue:
    • remove one state from the queue.
    • for each unoccupied tile:
      • create a copy of the current state.
      • add one knight to this plate.
      • if the new state does not exist in the queue:
        • If the new state is a goal state, complete.
        • else add it to the queue.

, , . , . , , , .

, . . , , , , .

, - , . 40 000 , (8!= 40 320 - 8-).

, *. :

  • , ( )
  • ( , ) , .

, . ( ).

, , 5 × 5. , , .

:

64- . , , 64- . 64- , 32- - .

, . , .

+7

++.

, 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;
}
+1

More articles:


All Articles