Moscow 5

Assignment 1

This is a KenKen puzzle solver using a brute force algorithm implementing recursive backtracking to solve a KenKen puzzle. The program creates a possible map of solutions and sequencially substitutes possible valid inputs into the solution map accordingly. When a solution is found to be a failure the program exits the recursive loop back to the last stable solution and continues with the solution map.

Source: [KenKen Solver]

We will be optimizing the following functions:

The update_possible method:

// Iterate through solution we have so far, and

//   remove possibilities from possible map

void puzzle::update_possible () {

  for (int i = 1; i <= this->size; ++i) {

    for (int j = 1; j <= this->size; ++j) {

      if (this->solution[i][j] != 0) {

this->possible[make_pair(i, j)].clear();

int taken = this->solution[i][j];

update_possible_row(taken, i);

update_possible_column(taken, j);

      }

    }

  }

}