Prośba o pomoc w rozwiązywaniu problemów z układem C++ Eight queens

Question

Napisałem funkcję w kodzie C++ dla eight queens problem. Program ma wydrukować wszystkie 92 możliwych rozwiązań. Mogę tylko pobiegać do 40. Nie wiem, gdzie jest problem. Spróbuj debugować, ale wciąż utknąłem.

#include "stdafx.h" 
#include <cmath> 
#include <iostream> 
using namespace std; 

bool ok(int board[8][8]){ 
    for(int c = 7; c > 0; c--){ 
     int r = 0; 
     while(board[r][c] != 1){ 
      r++; 
     } // while loop 

     for(int i = 1; i <= c; i++){ 
      if(board[r][c-i] == 1) 
       return false; 
      else if (board[r-i][c-i] == 1) 
       return false; 
      else if (board[r+i][c-i] == 1) 
       return false; 
     } // for loop 

    } // for loop 
     return true; 
} // ok 

void print(int board[8][8], int count){ 
    cout << count << endl; 
    for(int i = 0; i < 8; i++){ 
     for(int j = 0; j < 8; j++){ 
      cout << board[i][j]; 
     } // for loop 
     cout << endl; 

    } // for loop 

    cout << endl; 
} // print board 

int main(){ 

    int board[8][8]={0}; 
    int count = 0; 
    for(int i0 = 0; i0 < 8; i0++) 
     for(int i1=0; i1 < 8; i1++) 
      for(int i2 = 0; i2 < 8; i2++) 
     for(int i3 = 0; i3 < 8; i3++) 
      for(int i4 = 0; i4 < 8; i4++) 
      for(int i5 = 0; i5 < 8; i5++) 
       for(int i6 = 0; i6 < 8; i6++) 
       for(int i7 = 0; i7 < 8; i7++){ 
       board[i0][0]=1; 
          board[i1][1]=1; 
          board[i2][2]=1; 
          board[i3][3]=1; 
          board[i4][4]=1; 
          board[i5][5]=1; 
          board[i6][6]=1; 
          board[i7][7]=1; 

          if(ok(board))print(board, ++count); 

          board[i0][0]=0; 
          board[i1][1]=0; 
          board[i2][2]=0; 
          board[i3][3]=0;   
          board[i4][4]=0; 
          board[i5][5]=0; 
          board[i6][6]=0; 
          board[i7][7]=0; 

           } 
    return 0; 
} 

Answer 1

Twój problem jest w funkcji ok. Ma trzy błędy, wszystkie związane z granicami macierzy. Pierwszy błąd (co będzie, jeśli coś spowodować otrzymać zbyt wiele rozwiązań), jest tutaj:

for(int c = 7; c > 0; c--){ 

To nigdy nie będzie sprawdzał kolumnę 0. Test powinien być c >= 0.

Pozostałe dwa błędy, które powodują nieprzewidywalne zachowanie, są tutaj:

for(int i = 1; i <= c; i++){ 
     if(board[r][c-i] == 1) 
      return false; 
     else if (board[r-i][c-i] == 1) 
      return false; 
     else if (board[r+i][c-i] == 1) 
      return false; 
    } // for loop 

Może to spowodować, że funkcja ok wrócić dowolną liczbę wyników fałszywie ujemnych. W moim przypadku skompilowanie i uruchomienie programu z tymi dwoma błędami nie przyniosło żadnych rozwiązań. To tylko przypadek, że produkuje dla ciebie 40 rozwiązań.

Problem jest ponownie związany z granicami. Zmienna i przesuwa się od 1 do c, a więc c-i przesuwa się w dół z c-1 do 0, zgodnie z przeznaczeniem.

Jednak nie sprawdzasz, czy r-i i r+i pozostają w granicach macierzy. Rozważmy przypadek, że r = 7 i i = 4. Następnie r+i = 11, który przebiega poza koniec wiersza. Podobnie, jeśli r = 0 i i jest cokolwiek innego niż 0, r-i będzie ujemny i będzie przebiegać poza początkiem wiersza.

Należy dodać dodatkowe kontrole, aby upewnić się, że wartości wiersza używane w testach w tej pętli mieszczą się w zakresie od 0 do 7. Można skorzystać z zachowania zwarciowego operatorów logicznych w C++. to, na przykład:

else if (<test> && board[r-i][c-i] == 1) 

zbada board[r-i][c-i] tylko jeśli <test> jest prawdą.

Wychodzę z dodawania poprawek do tych dwóch pierwszych błędów jako ćwiczenia dla ciebie, ponieważ jest to bardzo prawdopodobne zadanie domowe (a jeśli tak, powinieneś dodać tag [zadanie domowe] do pytania) .