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