Backtracking: 8 Епископов, чтобы занять всю доску

Question

Я застрял в написании этого алгоритма обратного отслеживания. Проблема: 8 епископов должны покрыть всю шахматную доску. Все, что нужно сделать, это разместить 4 епископа на белых шахматных площадках, проверить, занимает ли он 32 пространства. Если это так, переместите 4 новых епископа влево, чтобы они стояли на черных пространствах, и проблема решена. Если это не так - используйте обратный путь для размещения епископов где-то в другом месте. Проблема в том, что я просто не могу написать обратный путь - мне кажется слишком сложным.

Вот что я сделал:

void findBishops(){ 
    for (int i=0; i<N; i++){ //get row 
     int j; 
     if (i%2==1) j=1; //2n+1 row has second white space, so we skip the first black space 
     else j=0; 
     for (; j<N; j+=2){ //get column 
      //put into array those bishop coordinates and repeat 3 more times to get all 4 bishops. 
      isFull(board, array); //give coordinates and check if all white spaces are occupied 
      //if not - backtrack 
      } 
    } 
} 

bool isFull(int board[][N], array[]){ 
    putIntoBoard(board, array[0], array[1]); 
    putIntoBoard(board, array[2], array[3]); 
    putIntoBoard(board, array[4], array[5]); 
    putIntoBoard(board, array[6], array[7]); 

    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){ 
     clean(board); 
     return true; 
    }else{ 
     clean(board); 
     return false; 
    } 
} 

void putIntoBoard(int board[][N], int a, int b){ //fills diagonal white spaces on board with 1's 
    int i=a,j=b; 
    board[i][j]=1; 

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

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

    } 
    i=a; 
    j=b; 

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

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


} 

Вот main function:

#include <iostream> 
#define N 8 
using namespace std; 
void print(int board[][N]); 
void putIntoBoard(int a, int b, int board[][N]); 
bool isFull(int board[][N], array[]); 
void clean(int board[][N]); 

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

    findBishops(); 

    cout<<"Counted possibilites: "<<count<<endl; 
    return 0; 
} 

Это просто прототип, если у вас есть что-то лучше, пожалуйста, поделитесь, я с удовольствием принимают все отзывы ,

EDIT: Я забыл включить мой другой АЛГОРИТМ использовал несколько дней назад, но это не имеет никакой рекурсии, ни откатов, вот оно:

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



    for (int i=0; i<N; i++) 
    { 
     int j; 
     if (i%2==1) j=1; 
     else j=0; 
     for (; j<N; j+=2) 
     { 
      for(int k=0; k<N; k++) 
      { 
       int n; 
       if (k%2==1) n=1; 
       else n=0; 
       for (; n<N; n+=2) 
       { 

        for (int l=0; l<N; l++) 
        { 
         int o; 
         if (l%2==1) o=1; 
         else o=0; 
         for (; o<N; o+=2) 
         { 

          for(int m=0; m<N; m++) 
          { 
           int p; 
           if (m%2==1) p=1; 
           else p=0; 
           for (; p<N; p+=2) 
           { 

            if (isFull(board,i,j,k,n,l,o,m,p)) 
            { 
             count++; 
             cout<<"Board filled up with white spaces on: ("<<i<<","<<j<<"), "<<"("<<k<<","<<n<<"), "<<"("<<l<<","<<o<<"), "<<"("<<m<<","<<p<<"), "<<endl; 
            } 

           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
    cout<<"Counted possibilities: "<<count<<endl; 

    return 0; 
} 

Answer 1

Для перемещения 4 епископов на черные поля, просто зеркало относительно вертикальной центральной оси. Или горизонтальный - результат будет таким же. Они отправятся на черные поля, и они будут угрожать всем черным полям (если они угрожают всем белым полям перед зеркальным отображением).