//
// © 2005-2007 Cazfi
//

#include "sdks.h"

#include <stdlib.h>
#include <iostream>

bool explain      = false; // Explain solution
bool intermediate = false; // Display intermediate solutions
bool quiet        = false; // Disable default messages

#define PARAM_EXPLAIN_L  "--explain"
#define PARAM_EXPLAIN_S  "-e"
#define PARAM_HELP_L     "--help"
#define PARAM_HELP_S     "-h"
#define PARAM_QUIET_L    "--quiet"
#define PARAM_QUIET_S    "-q"
#define PARAM_INTERMED_L "--intermediate"
#define PARAM_INTERMED_S "-i"
#define PARAM_SIZE_L     "--size"
#define PARAM_SIZE_S     "-s"

int main(int argc, char *argv[])
{
  sudoku *si;
  int i;
  int base = 3;

  for (i = 1; i < argc; i++) {
    if (!strncmp(argv[i], PARAM_EXPLAIN_L, strlen(PARAM_EXPLAIN_L)) ||
        !strncmp(argv[i], PARAM_EXPLAIN_S, strlen(PARAM_EXPLAIN_S))) {
      explain = true;
    } else if (!strncmp(argv[i], PARAM_HELP_L, strlen(PARAM_HELP_L)) ||
               !strncmp(argv[i], PARAM_HELP_S, strlen(PARAM_HELP_S))) {
      std::cout << "Usage: " << argv[0];
      std::cout << " [" PARAM_SIZE_L     "|" PARAM_SIZE_S     " <value>]";
      std::cout << " [" PARAM_EXPLAIN_L  "|" PARAM_EXPLAIN_S  "]";
      std::cout << " [" PARAM_QUIET_L    "|" PARAM_QUIET_S    "]";
      std::cout << " [" PARAM_INTERMED_L "|" PARAM_INTERMED_S "]";
      std::cout << " [" PARAM_HELP_L     "|" PARAM_HELP_S     "]";
      std::cout << "\n\n";
      std::cout << "Enter sudoku line by line.\n";
      std::cout << "9 characters each line, 9 lines.\n";
      std::cout << "Mark unknown by '?', known by numerical value.\n";
      std::cout << "\nExample:\n";
      std::cout << "3???2?698\n";
      std::cout << "?62?9???4\n";
      std::cout << "4???1??5?\n";
      std::cout << "????82??1\n";
      std::cout << "??6?7?3??\n";
      std::cout << "7??36????\n";
      std::cout << "?4??5???2\n";
      std::cout << "9???3?54?\n";
      std::cout << "185?4???7" << std::endl;

      return EXIT_SUCCESS;
    } else if (!strncmp(argv[i], PARAM_QUIET_L, strlen(PARAM_QUIET_L)) ||
               !strncmp(argv[i], PARAM_QUIET_S, strlen(PARAM_QUIET_S))) {
      quiet = true;
    } else if (!strncmp(argv[i], PARAM_INTERMED_L, strlen(PARAM_INTERMED_L)) ||
               !strncmp(argv[i], PARAM_INTERMED_S, strlen(PARAM_INTERMED_S))) {
      intermediate = true;
    } else if (!strncmp(argv[i], PARAM_SIZE_L, strlen(PARAM_SIZE_L)) ||
               !strncmp(argv[i], PARAM_SIZE_S, strlen(PARAM_SIZE_S))) {
      if (argc <= i + 1) {
        std::cerr << "Value for parameter \"" << argv[i] << "\" missing!" << std::endl;
        return EXIT_FAILURE;
      }
      base = atoi(argv[i+1]);

      if (base < MIN_BASE || base > MAX_BASE) {
        std::cerr << "Illegal value " << base << " for \"" << argv[i] << "\".\n";
        std::cerr << "Minimum is " << MIN_BASE << " and maximum " << MAX_BASE << ".";
        std::cerr << std::endl;
        return EXIT_FAILURE;
      }

      i++; // Do not handle value as independent parameter
    } else {
      std::cerr << "Unknown parameter \"" << argv[i] << "\"!" << std::endl;
      return EXIT_FAILURE;
    }
  }

  if (!quiet) {
    std::cout << "sdks " SDKS_VERSION "\n";
    std::cout << "Try '" << argv[0] << " --help' for usage info.\n";
    std::cout << "Waiting input" << std::endl;
  }

  si = new sudoku(base);

  if(! si->read()) {
    return EXIT_FAILURE;
  }
  std::cout << "Starting situation:" << std::endl;
  si->print();
  si->solve();
  if (si->check_legality()) {
    // Legal solution
    std::cout << "Result:" << std::endl;
    si->print();
  } else {
    std::cout << "Got illegal result" << std::endl;
    if (intermediate) {
      si->print();
    }
  }

  delete si;

  return EXIT_SUCCESS;
}


void solve_log(cell *pcell, const char *msg)
{
  if(explain) {
    std::cout << "(" << pcell->get_x() << "," << pcell->get_y() << "):";
    std::cout << msg << std::endl;
  }
}


sudoku::sudoku()
{
  sudoku(3);
}


sudoku::sudoku(int base)
{
  int i, j;

  base_size = base;
  dimension = base*base;
  unsolved = dimension*dimension;
  cells = new cell**[dimension];

  for (i = 0; i < dimension; i++) {
    cells[i] = new cell*[dimension];
    for (j = 0; j < dimension; j++) {
      cells[i][j] = new cell(base);
    }
  }
}


sudoku::~sudoku()
{
  int i, j;

  for (i = 0; i < dimension ; i++) {
    for (j = 0; j < dimension; j++) {
      delete cells[i][j];
    }
    delete cells[i];
  }

  delete cells;
}


void sudoku::print()
{
  int ry, rx, y, x, ri, i;

  for(ry = 0; ry < base_size; ry++) {
    for (ri = 0; ri < base_size; ri++) {
      std::cout << "+";
      for (i = 0; i < base_size; i++) {
        std::cout << "-";
      }
    }
    std::cout << "+\n";
    for(y = 0; y < base_size; y++) {
      for(rx = 0; rx < base_size; rx++) {
        std::cout << "|";
        for(x = 0; x < base_size; x++) {
          get_row_cell(ry*base_size+y, rx*base_size+x)->print();
        }
      }
      std::cout << "|\n";
    }
  }
  for (ri = 0; ri < base_size; ri++) {
    std::cout << "+";
    for (i = 0; i < base_size; i++) {
      std::cout << "-";
    }
  }
  std::cout << "+\n";
}


void sudoku::print_possibilities()
{
  int ry, rx, y, x, i, j, vy, vx;
  int count = 0;
  cell *pcell;

  // Print header
  std::cout << " ";
  for (rx = 0; rx < base_size; rx++) {
    std::cout << "  ";
    for (i = 0; i < base_size; i++) {
      for (j = 0; j < (base_size / 2); j++) {
        std::cout << " ";
      }
      std::cout << int_to_char(count++);
      for (j++; j < base_size; j++) {
        std::cout << " ";
      }
      std::cout << " "; // Space between cells
    }
  }

  std::cout << "\n";
  count = 0; // Y-coordinate now on

  for (ry = 0; ry < base_size; ry++) {
    print_possibility_ruler();
    for (y = 0; y < base_size; y++) {
      print_possibility_verticals();
      for (vy = 0; vy < base_size; vy++) {
        if (vy == base_size / 2) {
          // Line starts with Y-coordinate
          std::cout << int_to_char(count++) << " ";
        } else {
          std::cout << "  ";
        }

        for (rx = 0; rx < base_size; rx++) {
          std::cout << "| ";
          for (x = 0; x < base_size; x++) {
            pcell = get_row_cell(ry*base_size+y, rx*base_size+x);
            if (pcell->solved()) {
              if (vy == base_size / 2) {
                for (i = 0; i < base_size / 2; i++) {
                  std::cout << "*";
                }
                std::cout << int_to_char(pcell->solved());
                i++;
                for (;i < base_size; i++) {
                  std::cout << "*";
                }
              } else {
                for (i = 0; i < base_size; i++) {
                  std::cout << "-";
                }
              }
            } else {
              for (vx = 0; vx < base_size; vx++) {
                if (pcell->is_possible(vy*base_size+vx+1)) {
                  std::cout << int_to_char(vy*base_size+vx+1);
                } else {
                  std::cout << "-";
                }
              }
            }
            std::cout << " "; // Space between cells
          }
        }
        std::cout << "|\n";
      }
    }
    print_possibility_verticals();
  }
  print_possibility_ruler();
}


void sudoku::print_possibility_ruler()
{
  int ri, i;

  std::cout << "  +";
  for (ri = 0; ri < base_size; ri++) {
    std::cout << "-";
    for (i = 0; i < base_size*(base_size+1); i++) {
      // Each cell needs base_size characters + space between cells
      std::cout << "-";
    }
    std::cout << "+";
  }
  std::cout << "\n";
}


void sudoku::print_possibility_verticals()
{
  int ri, i;

  std::cout << "  |";
  for (ri = 0; ri < base_size; ri++) {
    std::cout << " ";
    for (i = 0; i < base_size*(base_size+1); i++) {
      // Each cell needs base_size characters + space between cells
      std::cout << " ";
    }
    std::cout << "|";
  }
  std::cout << "\n";
}


bool sudoku::check_legality()
{
  int row, col, reg, linear, i;
  bool legal = true;
  int result;
  char logmsg[50];
  cell *pcell, *ccell;

  // Rows
  for (row = 0; row < dimension; row++) {
    for (col = 0; col < dimension; col++) {
      pcell = get_cell(CT_ROW, row, col);
      result = pcell->solved();
      if (result) {
        for (i = col + 1; i < dimension; i++) {
          ccell = get_cell(CT_ROW, row, i);
          if (ccell->solved() == result) {
            // Two cells in same row has same result
            sprintf(logmsg, "Row has %d also in (%d, %d)", result, i, row);
            solve_log(pcell, logmsg);

            legal = false;
          }
        }
      }
    }
  }

  // Columns
  for (col = 0; col < dimension; col++) {
    for (row = 0; row < dimension; row++) {
      pcell = get_cell(CT_COL, col, row);
      result = pcell->solved();
      if (result) {
        for (i = row + 1; i < dimension; i++) {
          ccell = get_cell(CT_COL, col, i);
          if (ccell->solved() == result) {
            // Two cells in same column has same result
            sprintf(logmsg, "Column has %d also in (%d, %d)", result, col, i);
            solve_log(pcell, logmsg);

            legal = false;
          }
        }
      }
    }
  }

  // Regions
  for (reg = 0; reg < dimension; reg++) {
    for (linear = 0; linear < dimension; linear++) {
      pcell = get_cell(CT_REG, reg, linear);
      result = pcell->solved();
      if (result) {
        for (i = linear + 1; i < dimension; i++) {
          ccell = get_cell(CT_REG, reg, i);
          if (ccell->solved() == result) {
            // Two cells in same region has same result
            sprintf(logmsg, "Region has %d also in (%d, %d)", result,
                    linear_to_x(reg, i), linear_to_y(reg, i));
            solve_log(pcell, logmsg);

            legal = false;
          }
        }
      }
    }
  }

  return legal;
}


bool sudoku::read()
{
  int i, j;
  char line[500];

  for(i = 0; i < dimension; i++) {
    std::cin >> line;

    for (j = 0; j < dimension; j++) {
      int value;

      if (line[j] == '\0') {
        std::cerr << "Line " << i + 1 << " too short!" << std::endl;
        return false;
      }
      value = char_to_int(line[j]);
      
      if (line[j] != '?' && (value < 1 || value > base_size*base_size)) {
        std::cerr << "Illegal character '" << line[j] << "' in line ";
        std::cerr << i + 1 << "." << std::endl;
        return false;
      }
    }
    if (line[dimension] != '\0') {
      std::cerr << "Line " << i + 1 << " too long!" << std::endl;
      return false;
    }

    for(j = 0; j < dimension; j++) {
      get_row_cell(i, j)->setxy(j, i);
      if(line[j] != '?') {
        get_row_cell(i, j)->set_result(line[j] - '0', "Preset value");
        unsolved--;
      }
    }
  }
  return true;
}


bool sudoku::solve()
{
  int i;
  bool advanced = true;
  bool first_round = true;

  while (advanced && unsolved) {
    while(advanced && unsolved) {

      // Lets loop simple (fast) tests as long as they help
      while(advanced && unsolved) {
        advanced = false;

        if (!first_round && intermediate) {
          print_possibilities();
        }
        first_round = false;

        for(i = 0; i < dimension; i++) {
          advanced |= solve_base(CT_ROW, i);
        }
        for(i = 0; i < dimension; i++) {
          advanced |= solve_base(CT_COL, i);
        }
        for(i = 0; i < dimension; i++) {
          advanced |= solve_base(CT_REG, i);
        }
      }
      if(unsolved) { // We need more complex solving techniques
        if (intermediate) {
          std::cout << "Slow" << std::endl;
        }
        for(i = 0; i < dimension; i++) {
          advanced |= solve_region_slow(i);
        }
        for(i = 0; i < dimension; i++) {
          advanced |= solve_slow_rowcol(CT_ROW, i);
        }
        
        for(i = 0; i < dimension; i++) {
          advanced |= solve_slow_rowcol(CT_COL, i);
        }
      }
    }
    if (unsolved) { // We need pairing checks!
      if (intermediate) {
        std::cout << "Pairing" << std::endl;
      }
      for (i = 0; i < dimension; i++) {
        advanced |= solve_pairing(CT_ROW, i);
      }
      for (i = 0; i < dimension; i++) {
        advanced |= solve_pairing(CT_COL, i);
      }
      for (i = 0; i < dimension; i++) {
        advanced |= solve_pairing(CT_REG, i);
      }
    }
  }

  if(unsolved) {
    std::cout << "Unsolvable " << unsolved << std::endl;
    if (intermediate) {
      print_possibilities();
    }
    return false;
  }
  return true;
}


bool sudoku::solve_base(construct_type construct, int cnum)
{
  int i, j;
  int solved = 0;
  bool advanced = false;
  char msg_already[50];
  char msg_only[50];

  sprintf(msg_already, "Value already in %s", construct_name(construct));
  sprintf(msg_only, "Only place for value in %s", construct_name(construct));

  for(i = 0; i < dimension; i++) {
    int cleanup = get_cell(construct, cnum, i)->solved();
    if(cleanup) {
      for(j = 0; j < dimension; j++) {
        if(i != j) {
          remove_result rr =
            get_cell(construct, cnum, j)->remove_possibility(cleanup,
                                                             msg_already);
          if(rr != RR_KNOWN) {
            advanced = true;
            if(rr == RR_SOLVED) {
              unsolved--;
            }
          }
        }
      }
    }
  }
  for(i = 1; i <= dimension; i++) {
    int place = -1;
    for(j = 0; j < dimension; j++) {
      if(get_cell(construct, cnum, j)->is_possible(i)) {
        if(place == -1) {
          place = j;
        } else {
          place = -2;
        }
      }
    }
    if(place >= 0) {
      if(get_cell(construct, cnum, place)->set_result(i, msg_only)) {
        advanced = true;
        unsolved--;
      }
    }
  }
  return advanced;
}


bool sudoku::solve_slow_rowcol(construct_type construct, int cnum)
{
  int i, j;
  int reg;
  bool advanced = false;

  assert(construct != CT_REG);

  for(i = 1; i <= dimension; i++) { // Each possible cell value
    int only_region = -1;

    // Whether value for this row/col can be in region
    for (reg = 0; reg < base_size; reg++) {
      bool result;
      int abs_reg = get_reg(construct, cnum, reg);

      for (j = 0; j < base_size; j++) {
        if (construct == CT_ROW) {
          result = get_row_cell(cnum, region_origo_x(abs_reg) + j); 
        } else {
          assert(construct == CT_COL);
          result = get_col_cell(cnum, region_origo_y(abs_reg) + j);
        }
        if (result) {
          if (only_region != -1 && only_region != abs_reg) {
            // Already had region, so there is several of them
            only_region = -2;
            break;
          } else {
            only_region = abs_reg;
          }
        }
      }
      if (only_region == -2) {
        break;
      }
    }

    if (only_region >= 0) {
      // Value for this row/col must be in region only_region
      char logmsg[50];

      sprintf(logmsg, "At %s %d, value can be only at this region (%d)",
              construct_name(construct), cnum, only_region);

      for (j = 0; j < dimension; j++) {
        if ((construct == CT_ROW && cnum != linear_to_y(only_region, j)) ||
            (construct == CT_COL && cnum != linear_to_x(only_region, j))) {
          // Linear coordinate j is not in this row/col
          remove_result rr = get_reg_cell(only_region, j)->remove_possibility(i, logmsg);
          if(rr != RR_KNOWN) {
            advanced = true;
            if(rr == RR_SOLVED) {
              unsolved--;
            }
          }
        }
      }
    }

  }
  return advanced;
}


bool sudoku::solve_region_slow(int region)
{
  int i, j;
  int row, col; // Relative to region
  bool advanced = false;

  for(i = 1; i <= dimension; i++) { // Each possible cell value
    int only_row = -1;
    int only_col = -1;

    // Whether value for this region can be in row/column
    for (row = 0; row < base_size; row++) {
      for (col = 0; col < base_size; col++) {
        bool result;
        result = get_regxy_cell(region, col, row)->is_possible(i);
        if (result) {
          if (only_row != -1 && only_row != row) {
            // Already had row, so there is several of them.
            only_row = -2;
          } else {
            only_row = row;
          }
          if (only_col != -1 && only_col != col) {
            // Already had col, so there is several of them.
            only_col = -2;
          } else {
            only_col = col;
          }
        }
      }
    }

    if (only_row >= 0) {
      // Value for this region must be in row only_row

      char rowmsg[50];
      sprintf(rowmsg, "At region %d, value can be only at this row (%d)",
              region, only_row);

      for (j = 0; j < dimension; j++) {
        if (!region_x(region, j)) {
          // X-coordinate j is in another region
          remove_result rr = get_row_cell(region_origo_y(region) + only_row, j)->
            remove_possibility(i, rowmsg);
          if(rr != RR_KNOWN) {
            advanced = true;
            if(rr == RR_SOLVED) {
              unsolved--;
            }
          }
        }
      }
    }

    if (only_col >= 0) {
      // Value for this region must be in col only_col

      char colmsg[50];
      sprintf(colmsg, "At region %d, value can be only at this column (%d)",
              region, only_col);

      for (j = 0; j < dimension; j++) {
        if (!region_y(region, j)) {
          // Y-coordinate j is in another region
          remove_result rr = get_col_cell(region_origo_x(region) + only_col, j)->
            remove_possibility(i, colmsg);
          if(rr != RR_KNOWN) {
            advanced = true;
            if(rr == RR_SOLVED) {
              unsolved--;
            }
          }
        }
      }
    }

  }
  return advanced;
}


bool sudoku::solve_pairing(construct_type construct, int cnum)
{
  bool advanced = false;
  int start;                         // Cell we search pairings for
  int i, j, pos, num, positions;
  bool possibilities[dimension + 1]; // Values in perfect pairing
  bool pairings[dimension];          // Whether cell in given index is part of pairing
  cell *pcell;
  char logmsg[50];

  sprintf(logmsg, "Pairing in %s", construct_name(construct));

  for (start = 0; start < dimension; start++) {
    pcell = get_cell(construct, cnum, start);
    if (!pcell->solved()) {
      // There can be pairing only with unsolved cells

      // Empty pairings array
      for (i = 0; i < dimension; i++) {
        pairings[i] = false;
      }
      pairings[start] = true;

      num = 0;
      positions = 1;

      // Fill possibilities array with values from start cell
      for (pos = 1; pos <= dimension; pos++ ) {
        if (pcell->is_possible(pos)) {
          possibilities[pos] = true;
          num++;
        } else {
          possibilities[pos] = false;
        }
      }

      // Iterate over rest of the construct
      // No need to check for earlier indexes (if cell B pairs with cell A) since
      // we have already checked other way around (if cell A pairs with cell B)
      for (i = start + 1; i < dimension; i++) {
        cell *ccell = get_cell(construct, cnum, i); // Start cell is compared to this
        bool same_pos = true;

        for (pos = 1; pos <= dimension; pos++) {
          if (possibilities[pos] != ccell->is_possible(pos)) {
            same_pos = false;                       // Possibilites differ
            break;
          }
        }
        if (same_pos) {
          // This cell pairs with start cell
          positions++;
          pairings[i] = true;
          if (num == positions) {
            // There is strict pairing
            // These possibilities are required to fill pairings cells, remove them
            // from other cells.
            for (j = 0; j < dimension; j++) {
              ccell = get_cell(construct, cnum, j);
              if (!pairings[j] && !ccell->solved()) {
                // Cell is not part of pairing and not solved
                for (pos = 1; pos <= dimension; pos++) {
                  if (possibilities[pos]) {
                    // This possibility is part of pairing, remove from this cell
                    remove_result rr;

                    rr = ccell->remove_possibility(pos, logmsg);
                    if (rr != RR_KNOWN) {
                      advanced = true;
                      if(rr == RR_SOLVED) {
                        unsolved--;
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }

  return advanced;
}


cell *sudoku::get_cell(construct_type construct, int cnum, int index)
{
  switch(construct) {
   case CT_ROW:
     return get_row_cell(cnum, index);
   case CT_COL:
     return get_col_cell(cnum, index);
   case CT_REG:
     return get_reg_cell(cnum, index);
  }

  return 0;
}


int sudoku::get_reg(construct_type construct, int cnum, int index)
{
  switch(construct) {
   case CT_ROW:
     return (cnum / base_size) * base_size + index;
   case CT_COL:
     return index * base_size + (cnum / base_size);
   case CT_REG:
     std::cerr << "Internal error! get_reg() for CT_REG!" << std::endl;
     break;
  }

  return -1;
}


cell *sudoku::get_row_cell(int row, int index)
{
  return cells[row][index];
}


cell *sudoku::get_col_cell(int col, int index)
{
  return cells[index][col];
}


cell *sudoku::get_reg_cell(int reg, int index)
{
  return cells[linear_to_y(reg, index)][linear_to_x(reg, index)];
}


cell *sudoku::get_regxy_cell(int reg, int x, int y)
{
  return cells[region_origo_y(reg) + y][region_origo_x(reg) + x];
}


int sudoku::region_origo_x(int region)
{
  return (region % base_size) * base_size;
}


int sudoku::region_origo_y(int region)
{
  return (region / base_size) * base_size;
}


int sudoku::linear_to_x(int region, int linear)
{
  return (region % base_size) * base_size + linear % base_size;
}


int sudoku::linear_to_y(int region, int linear)
{
  return (region / base_size) * base_size + linear / base_size;
}


bool sudoku::region_x(int region, int x)
{
  return x >= region_origo_x(region) &&
    x < (region_origo_x(region) + base_size);
}


bool sudoku::region_y(int region, int y)
{
  return y >= region_origo_y(region) &&
    y < (region_origo_y(region) + base_size);
}


const char *sudoku::construct_name(construct_type construct)
{
  switch(construct) {
   case CT_ROW:
     return "row";
   case CT_COL:
     return "col";
   case CT_REG:
     return "reg";
  }

  return 0;
}


int sudoku::char_to_int(char c)
{
  if (c >= '1' && c <= '9') {
    return c - '0';
  }
  if (c >= 'a' && c <= 'n') {
    return c + 10 - 'a';
  }
  if (c >= 'A' && c <= 'N') {
    return c + 10 - 'A';
  }
  if (c == '0') {
    // High end character
    return base_size*base_size;
  }

  return -1;
}


char sudoku::int_to_char(int n)
{
  if (n < 10) {
    return '0' + n;
  }

  if (base_size > 3 && n == base_size*base_size) {
    // Hex sudoku (and other big sudokus) has '0' as high end character
    return '0';
  }

  if (n < 25) {
    return 'A' + n - 10;
  }

  return '?';
}


cell::cell()
{
  cell(3);
}


cell::cell(int base)
{
  int i;

  result = 0;
  possibility_count = base*base;
  base_size = base;
  possibilities = new bool[base*base + 1];

  for(i = 1 ; i <= base*base; i++) {
    possibilities[i] = true;
  }
}


cell::~cell()
{
  delete [] possibilities;
}


void cell::print()
{
  if(result) {
    std::cout << result;
  } else {
    std::cout << "?" ;
  }
}


bool cell::set_result(int result_in, const char *reason)
{
  int i;
  char logmsg[100];

  if(result) {
    return false;
  }

  sprintf(logmsg, "Solved: %d (%s)", result_in, reason);
  solve_log(this, logmsg);

  result = result_in;
  possibility_count = 1;

  for(i = 0; i <= base_size*base_size; i++) {
    if(i != result) {
      possibilities[i] = false;
    }
  }

  return true;
}


int cell::solved()
{
  return result;
}


bool cell::is_possible(int result_in)
{
  return possibilities[result_in];
}


remove_result cell::remove_possibility(int removed, const char *reason)
{
  int i;
  char logmsg[100];

  if(!possibilities[removed]) {
    return RR_KNOWN;
  }

  sprintf(logmsg, "Possibility %d removed (%s)", removed, reason);
  solve_log(this, logmsg);

  possibility_count--;
  possibilities[removed] = false;

  // Solved
  if(possibility_count == 1) {
    // Just iterate until only possibility found
    for(i = 1; ! possibilities[i]; i++) ;
    set_result(i, "Only possibility left");
    return RR_SOLVED;
  }
  return RR_ADVANCE;
}


void cell::setxy(int x_in, int y_in)
{
  x = x_in;
  y = y_in;
}


int cell::get_x()
{
  return x;
}


int cell::get_y()
{
  return y;
}