CODEWITHSUNDEEP
algorithmrecursioncode-complexity
Rimantas Radžiūnas
Rimantas Radžiūnas

Reputation: 257

Finding complexity of backtracking recursive algorithm

I have this recursive algorithm:

#include <iostream>
#include <cmath>
#include <map>
#include <iterator>
#define N 8
using namespace std;
void putIntoBoard(int a, int b, int board[][N]);
bool isFull(int  board[][N]);
void cleanBoard(int board[][N]);
void bishopSolver(int level, int i, int board[][N]);
void putIntoArray(int a, int b);
void printout();

map<int, int> coordMap;

int main(){
    int board [N][N]= {0};
    int count= 0;
    int level;
    int i;



    bishopSolver(0,0,board);

    return 0;
}

void printout(){

    for (map<int,int>::iterator it = coordMap.begin(); it != coordMap.end(); ++it) {
        int value = it->second;


        int y = value / 8;
        int x = value - y * 8;
        cout<<"("<<x<<";"<<y<<"), ";
        x=x+1;
        if ((x) == 7) x=0;
        cout<<"("<<x<<":"<<y<<"), "<<endl;


    }
}




void putIntoBoard(int a, int b, int board[][N]){


    int i=a,j=b;
    board[i][j]=1;

    while(i>0 && (j<7) )/*Up right*/{
        i--;
        j++;
        board[i][j]=1;
    }
    i=a;
    j=b;
    while(j>0 && i>0) /*Up Left*/{
        i--;
        j--;
        board[i][j]=1;

    }
    i=a;
    j=b;
    while(i<7&& j<7) /*Down right*/{
        i++;
        j++;
        board[i][j]=1;

    }
    i=a;
    j=b;

    while(i<7 && j>0) /*Down left*/{

        i++;
        j--;
        board[i][j]=1;
    }


}
bool isFull(int  board[][N]){

    int x1, y1;

    for (map<int,int>::iterator it = coordMap.begin(); it != coordMap.end(); ++it) {
        int value = it->second;


        int y = value / 8;
        int x = value - y * 8;
        putIntoBoard(x, y, board);
    }

    int i, j;
    int count=0;
        for (i=0; i<=7; i++){

            if (i%2==1) j=1;
        else j=0;

        for (; j<=7; j+=2){
            if (board[i][j]==1) count++;
        }
    }
    if (count==32){
        cleanBoard(board);
        return true;
    }else{
        cleanBoard(board);
        return false;
    }
}
void cleanBoard(int board[][N]){
      for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++) board[i][j]=0;
    }
}

void addToMap(int level, int i) {
    coordMap[level] = i;
}

void removeFromMap(int level) {
    coordMap.erase(level);
}


void bishopSolver(int level, int i, int board[][N]){
    int size = 63 - (6 -  level);
    for (; i < size; i+=2){
        addToMap(level, i);
        if(level == 3 && isFull(board)){

            cout<<"Solved: "<<endl;
            printout();
            return;
        }
        if (level < 3){
            bishopSolver(level + 1, i + 2, board);
        }
        removeFromMap(level);
    }
}

Basically it solves bishop problem to fill chessboard with 8 bishops so that whole chessboard is occupied with 8 bishops moves. In my opinion, this algorithm is n!, but it's not brute force, so I'm wrong. Could anybody provide me a right answer here?

Upvotes: 0

Views: 131

Answers (1)

vib
vib

Reputation: 2274

If N=8 there is no asymptotic complexity.

If N varies the brute force approach would be (wouldn't it ?) to choose N cells among the N^2 available and to check whether placing bishops on them works. This leads to a complexity of N^2 choose N ~ N^{2N}/N! ~ (Ne)^N (times a polynomial term). This is exponentially more than N! ~ (N/e)^N.

I have not read through the details of your algo but I would bet it is actually N!.

Upvotes: 1

Related Questions