dimanche 22 novembre 2020

C++ nonogram solver out of range

I want to write a C++ program that solves a given nonogram recursively using backtracking. The nonogram is just a grid defined with using grid = vector<vector>; in which '#' represents a marked cell. I defined two function that check if the current row and column is correct, given that there's the current position is marked. These unctions should tell me whether I am allowed to mark a cell at each step, and the idea is to try out every possible combinations. Then I also have a function check_solution that checks if the final result is correct.

using hints = vector<int>;

//given that the cell (row,col) is marked, check if current row is valid
bool row_valid(const grid& nonogram, vector<hints> row_hints,unsigned int row, unsigned int col){
unsigned int num=0, count=0;

 for(int i=0; i<=col; i++){
   if (nonogram.at(row).at(i)=='#'){
      while(i<=col&&nonogram.at(row).at(i)=='#'){
        count+=1;
        i+=1; //since (row,col) is marked, the while loop stops with i=col+1;
      } 

      if (num>=row_hints.size()) return false;
      else if (i!=col+1&&count!=row_hints.at(row).at(num)) return false;
      else if(i==col+1&&count<=row_hints.at(row).at(num)){
        //check if there's enough place left for the rest of the marked cells
        int sum=row_hints.at(row).at(num)-count; 
        for(unsigned int l=num+1; l<row_hints[row].size();l++){
          sum=sum+row_hints.at(row).at(l)+1;
        }
        if (sum<nonogram[0].size()) return true;
      }
      num+=1;
   }
 }
 return false;
}


The col_valid function is almost the same.

The constraints row_hints and col_hints are matrices of the form vector<vector>, for example row_hints.at(i).at(j) refers to the i-th row and the length of the j-th run (a run is a consecutive sequence of marked boxes).

When tested separately on small nonograms, these functions seem to work well, but when I call them inside my recursive function solve, I get out of range, or no solution found when there is a solution.

bool solve_from(grid& nonogram,
                const std::vector<vector<unsigned int>>& row_hints,
                const std::vector<vector<unsigned int>>& col_hints,
                int row, int col) {
  int n=get_rows(nonogram);
  int m=get_cols(nonogram);

if(row==n-1&&col==m-1){
  nonogram.at(row).at(col)='#';
  if(check_solution(nonogram, row_hints, col_hints)) return true;
  else{
    nonogram.at(row).at(col)='.'; return check_solution(nonogram, row_hints, col_hints);
  }
} 

else{
    for (int i=row; i<n; i++){
      for (int j=col; j<m; j++){
          nonogram.at(i).at(j)='#';
          if (row_valid(nonogram,row_hints,i,j)&&col_valid(nonogram,col_hints,i,j)){
            if (j<m-1&&solve_from(nonogram, row_hints,col_hints,i,j+1)) return true;
            else if (j==m-1&&i<n-1&&solve_from(nonogram, row_hints,col_hints,i+1,0)) return true;
         
         } nonogram.at(i).at(j)='.';
      }
    }
} 

  return false;
}


The idea is then to apply the solve_from function with solve_from(nonogram, row_hints, col_hints, 0, 0). But the code doesn't work, I get out of range, it says something like

vector::M_range_check: __n (which is 1) this->size() (which is 1)

multiple times. The only times when it actually returns a nonogram, it is wrong. Someone please help me? It's a class assignment.

Aucun commentaire:

Enregistrer un commentaire