recursion - Finding complexity of backtracking recursive algorithm -


i have 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(){      (map<int,int>::iterator = coordmap.begin(); != 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;      (map<int,int>::iterator = coordmap.begin(); != 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;         (i=0; i<=7; i++){              if (i%2==1) j=1;         else j=0;          (; 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]){       (int i=0; i<n; i++)     {         (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);     (; < size; i+=2){         addtomap(level, i);         if(level == 3 && isfull(board)){              cout<<"solved: "<<endl;             printout();             return;         }         if (level < 3){             bishopsolver(level + 1, + 2, board);         }         removefrommap(level);     } }

basically solves bishop problem fill chessboard 8 bishops whole chessboard occupied 8 bishops moves. in opinion, algorithm n!, it's not brute force, i'm wrong. provide me right answer here?

if n=8 there no asymptotic complexity.

if n varies brute force approach (wouldn't ?) choose n cells among n^2 available , check whether placing bishops on them works. leads complexity of n^2 choose n ~ n^{2n}/n! ~ (ne)^n (times polynomial term). exponentially more n! ~ (n/e)^n.

i have not read through details of algo bet n!.


Comments

Post a Comment

Popular posts from this blog

php - failed to open stream: HTTP request failed! HTTP/1.0 400 Bad Request -

this code i'm using find latitude , longitude of place: function coords($address){ echo $url="http://maps.googleapis.com/maps/api/geocode/json?address=".$address; $json = file_get_contents(urlencode($url)); $data = json_decode($json, true); print_r($data['results'][0]['geometry']['location']['lat']); print_r($data['results'][0]['geometry']['location']['lng']); } however returns warning: failed open stream: http request failed! http/1.0 400 bad request if use above code in simple procedure works fine not in function. note: have tried curl_init()... method produced same result? instead of encoding whole url encode address part. following code work fine $add='jamshoro phase 2'; $url="http://maps.googleapis.com/maps/api/geocode/json?address=".urlencode($add); $json = file_get_contents($url); $data = json_decode($json, true); print_r($data['r
Read more

java - How to filter a backspace keyboard input -

i have code gives message when key number pressed: txtvalueofclause.addeventfilter(keyevent.key_typed, new eventhandler<keyevent>() { @override public void handle(keyevent t) { char ar[] = t.getcharacter().tochararray(); char ch = ar[t.getcharacter().tochararray().length - 1]; if (!(ch >= '0' && ch <= '9')) { system.out.println("the char entered not number"); t.consume(); } } }); now if press on wrong button , press backspace remove it, error message. how can add backspace input if statement? i have found answer: txtvalueofclause.addeventfilter(keyevent.key_typed, new eventhandler<keyevent>() { @override public void handle(keyevent t) { char ar[] = t.getcharacter().tochararray(); char ch = ar[t.getcharacter().tochar
Read more

java - Show Soft Keyboard when EditText Appears -

i have code in android app, alert dialog , keyboard, , when dialog shown want keyboard appear. not , not sure why? here code: final alertdialog.builder alert = new alertdialog.builder(this); alert.settitle("title"); alert.setmessage("message"); final edittext input = new edittext(this); input.setinputtype(inputtype.type_class_number); alert.setview(input); input.setonfocuschangelistener(new view.onfocuschangelistener() { @override public void onfocuschange(view v, boolean hasfocus) { if (hasfocus) { log.i(tag, "in focus"); inputmethodmanager inputmethodmanager = (inputmethodmanager) getsystemservice(context.input_method_service); inputmethodmanager.showsoftinput(input, inputmethodmanager.show_implicit); } } }); but keyboard not appear though edit text in focus, , tell appear why, doesn't come up? thanks in advance.
Read more