N 퀸 동적 인 2D 배열을 사용하여 C++ 및 백 트랙킹 사용

Question

나는 백 트랙킹을 사용하여 N 개의 여왕 문제를 해결하려고 노력했습니다. 내가 인터넷에서 발견 한 접근법의 대부분은 벡터를 포함하고있어서 인터넷의 일부 애플릿처럼 솔루션을 시각화하기가 어렵습니다.

필자가 생각해 낸 해결책은 사용 된 동적 2D 배열의 인덱싱과 관련하여 많은 문제를 겪고 있으며 Dev-C++ 디버거를 사용하여 알아낼 수 없습니다. 도움 및/또는 건설적인 비판은 높게 평가됩니다. 미리 감사드립니다. 여기

내가 해낸 솔루션입니다 :

#include<iostream> 
#include<string.h> 
#include<conio.h> 

using namespace std; 

void display(char** b, int len); 
void initialize(char** &b, int k); 
void consider1strow(char ** b, int len); 
void markunsafe(char** board, int rowno, int colno); 
void marksafe(char** board, int rowno, int colno); 
void considerrow(char** board, int rowno); 
void backtrack(char** board, int rowno); 
bool checksafety(char** board, int rowno, int colno); 
void place(char** board, int rowno, int colno); 
void solve(char** board, int len); 


int state[20] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; 
int len; 

void display(char** board, int len) 
{ 
    int i, j; 
    cout << endl << "The current state of the board:" << endl; 
    for (i = 0; i < len; i++) 
    { 
     for (j = 0; j < len; j++) 
     { 
      cout << board[i][j]; 
     } 
     cout << endl; 
    } 
} 

void initialize(char** &b, int k) 
{ 

    int i, j; 

    //create dynamic board 
    b = new char*[k]; 
    for (i = 0; i < k; i++) 
    { 
     b[i] = new char[k]; 
    } 

    //initialize array 
    for (i = 0; i < k; i++) 
    { 
     for (j = 0; j < k; j++) 
     { 
      b[i][j] = '-'; 
     } 
    } 

} 

void consider1strow(char ** board, int len) 
{ 
    int col; 
    cout << "Enter the column to try for the first row!"; 
    cin >> col; 
    board[0][col - 1] = 'Q'; 
    state[0] = col - 1; 
    markunsafe(board, 0, col - 1); 
    display(board, len); 
} 

void markunsafe(char** board, int rowno, int colno) 
{ 
    int i, j; 

    //mark row as unsafe 
    for (i = 0; i < len; i++) 
    { 
     board[rowno][i] = 'x'; 
    } 

    //mark column as unsafe 
    for (i = 0; i < len; i++) 
    { 
     board[i][colno] = 'x'; 
    } 

    //mark unsafe diagonals 
    for (i = 0; i < len; i++) 
    { 
     for (j = 0; j < len; j++) 
     { 
      if ((rowno + colno) == (i + j)) 
      { 
       board[i][j] = 'x'; //check if index gives a problem of +/- 1 
      } 
      if ((rowno - colno) == (i - j)) 
      { 
       board[i][j] = 'x'; //check if index gives a problem of +/- 1 
      } 
     } 
    } 
    board[rowno][colno] = 'Q'; 

} 

void marksafe(char** board, int rowno, int colno) 
{ 
    int i, j; 

    //mark row as safe 
    for (i = 0; i < len; i++) 
    { 
     board[rowno][i] = '-'; 
    } 

    //mark column as unsafe 
    for (i = 0; i < len; i++) 
    { 
     board[i][colno] = '-'; 
    } 

    //mark unsafe diagonals 
    for (i = 0; i < len; i++) 
    { 
     for (j = 0; j < len; j++) 
     { 
      if ((rowno + colno) == (i + j)) 
      { 
       board[i][j] = '-'; //check if index gives a problem of +/- 1 
      } 
      if ((rowno - colno) == (i - j)) 
      { 
       board[i][j] = '-'; //check if index gives a problem of +/- 1 
      } 
     } 
    } 
} 


void considerrow(char** board, int rowno) 
{ 
    bool safe = 0; 
    int i; 

    for (i = 0; i < len; i++) 
    { 
     safe = checksafety(board, rowno, i); 
     if (safe && (i >= state[rowno])) 
     { 
      break; 
     } 
    } 
    if (safe && (i >= state[rowno])) 
    { 
     place(board, rowno, i); 
    } 
    else if (!safe) 
    { 
     backtrack(board, rowno); 
    } 
} 

void backtrack(char** board, int rowno) 
{ 
    marksafe(board, rowno - 2, state[rowno - 2]); 
    considerrow(board, rowno); 
} 

bool checksafety(char** board, int rowno, int colno) 
{ 
    if (rowno == 0) 
    { 
     return 1; 
    } 
    else if (board[rowno][colno] == 'x') 
    { 
     return 0; 
    } 
    else if (board[rowno][colno] == '-') 
    { 
     return 1; 
    } 
} 


void place(char** board, int rowno, int colno) 
{ 
    board[rowno][colno] = 'Q'; 
    state[rowno] = colno; 
    markunsafe(board, rowno, colno); 
} 

void solve(char** board, int len) 
{ 
    int i = 0; 
    if (i == len) 
    { 
     display(board, len); 
    } 
    else 
    { 
     consider1strow(board, len); 
     for (i = 1; i < len; i++) 
     { 
      considerrow(board, i); 
     } 
    } 
} 

int main() 
{ 
    char** board; 
    cout << "Enter the size of the board!"; 
    cin >> len; 
    initialize(board, len); 
    solve(board, len); 
    getch(); 
} 

Answer 1

그것은 초기 구성 후 실행,하지만 당신은 그것을 인쇄 아닙니다. (해결 안쪽)이 변경이 대한

for(i=1;i<len;i++) 
{considerrow(board,i);} 

을 : 그 외에

for(i=1; i<len; i++) { 
     considerrow(board,i); 
     display(board,len); 
} 

을, 당신이 되돌아을 수행하는 방법에 문제가있는 것입니다. 사용할 수있는 옵션이 없으면 이전 행에서 여왕을 제거하고 (확인) 공격하는 모든 셀을 안전하다고 표시합니다 (ok가 아닙니다). 문제는 이들 세포 중 일부가 다른 여왕의 공격을받을 수 있으므로 안전하다고 표시 할 수 없다는 것입니다. 게다가, 당신은 그 행에 다른 여왕을 배치하지 않습니다.

먼저 다음과 같이 재귀 적으로 만듭니다. considerrow은 다음 행으로 자신을 호출하고 성공하면 참 (1), 실패하면 참 (0)을 반환합니다. 다음 행에 실패하면 현재 행에서 다음 여왕을 사용할 수 있고 성공할 때까지 또는 거짓을 반환 할 때까지 considerrow을 다시 호출 할 수 있습니다.

특정 행에 다른 여왕을 고려하려면 다음 두 가지를 할 수 있습니다. 다음 행에 considerrow으로 전달할 보드 복사본을 만듭니다 (따라서 '이전'복사본으로 다른 여왕을 시도하십시오)), 모든 셀을 안전한 것으로 표시 한 다음 기존의 모든 여왕을 검사하여 셀을 안전하지 않은 것으로 표시하십시오.

편집 :

는 재귀 만들려면, 우리는 다음 값으로 considerrow 전화 자체를 만들려고하고 있습니다. 첫 번째 행을 호출해야한다 해결

void backtrack(char** board, int rowno) { 
    //Clear the current row 
    marksafe(board,rowno,state[rowno]); 
    //Check that every cell attacked by another queen is marked unsafe 
    for(int i=0; i<rowno; i++) markunsafe(board,i,state[i]); 
} 

그 일 :

bool considerrow(char** board,int rowno) { 
    //Print the board 
    display(board,len); 
    bool safe=0; 
    int i; 

    for(i=0; i<len; i++) { 
     safe=checksafety(board,rowno,i); 
     if(safe) { 
      place(board,rowno,i); 
      //Is this the last row? If so, we suceeded 
      if (rowno==len-1) return 1; 
      //Call itself with next row, check if suceeded 
      if (considerrow(board,rowno+1)) 
       return 1; 
      else //Failed, try a different row 
       backtrack(board,rowno); 
     } 
    } 
    return 0; //If we got here, then we ran out of colums. Return failure 
} 

역 추적 기능이 같은 현재 행을 되돌릴 수정할 수

void solve(char** board,int len) { 
    considerrow(board,0); 
    display(board,len); 
}