数独 - 软件工程实践 2017 第二次作业

/root
  /BIN                   // 可执行文件目录
    sudoku.exe           // 可执行文件
  /src                   // 源文件目录
    stdafx.h             //  Visual Studio 自带头文件
    stdafx.cpp           //  Visual Studio 自带头文件
    targetver.h          //  Visual Studio 自带头文件
    sudokuMaker.h        // 数独生成类声明
    sudokuMaker.cpp      // 数独生成类实现
    fileController.h     // 文件控制类声明
    fileController.cpp   // 文件控制类实现
    usageValidator.h     // 使用规范类声明
    usageValidator.cpp   // 使用规范类实现
    Sudoku.cpp           // 主程序入口
  README.md              // 说明

class sudokuMaker {
  public:
    bool generateAndPrint(const int &sudokuQuantity);  // 循环生成数独并且打印到文件

  private:
    int blank;  // 数独棋盘待填格数，新的待填数独棋盘模板初始化后有 72 格待填
    int hint;  // 数独棋盘提示格数
    int fullBoard[9][9];  // 完整数独棋盘
    fileController fc;  // 文件控制器，用来输出到文件
    void newTemplate();  // 产生新的待填数独棋盘模板
    bool dfs();  // 深度优先搜索填写数独棋盘
    int validNumbersQuantity(const int &row, const int &col, int (&mark)[10]);
        // 某一格可填写数字数量计算
};

class fileController {
  public:
    bool open(const string &outputPath);  // 打开文件以输出
    void write(int (&fullBoard)[9][9]);  // 写入
    void close();  // 关闭文件

  private:
    ofstream outFile;
};

class usageValidator {
  public:
    int check(int argc, char **argv);  // 检查输入

  private:
    int checkStringAndConvertToInteger(const string &str); // 检查字符串并转换成整数
};

bool sudokuMaker::generateAndPrint(const int &sudokuQuantity) {
  if (fc.open(".\\sudoku.txt")) {
    for (int i = 1; i <= sudokuQuantity; i++) {
      while (true) {
        newTemplate();  // 随机生成模板，除了第一行第一个，把其他八个数字随机填入数独棋盘
        if (dfs()) {  // 深度优先搜索
          fc.write(fullBoard);  // 若成功则输出到文件
          break;
        }
        // 失败则重新循环
      }
    }
    fc.close();
    return true;
  }
  return false;
}

bool sudokuMaker::dfs() {
  if (blank == 0) {
    return true;  // 填写完毕，无空格
  }

  int minQuantity = 10;  // 当前可填写数字最少的数量
  int mini = 0, minj = 0;  // 当前 可填写数字数量最少 的格子位置

  int mark[10] = {0};  // 标记已填写和未填写的数字

  // 寻找可填写数字数量最少的格子
  for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
      if (fullBoard[i][j] != 0) {
        continue;
      }

      int count = validNumbersQuantity(i, j, mark);  // 计算可填写数字数量
      if (count == 0) {
        return false;
      }
      if (count < minQuantity) {
        minQuantity = count;
        mini = i;
        minj = j;
      }
    }
  }

  // 优先填写 可填写数字数量最少 的格子
  validNumbersQuantity(mini, minj, mark);
  for (int i = 1; i <= 9; i++) {
    if (mark[i] == 0) {
      fullBoard[mini][minj] = i;
      blank--;
      dfs();
      if (blank == 0) {
        return true;
      }
      fullBoard[mini][minj] =  0; // 回溯
      blank++;
    }
  }
  return true;
}

int sudokuMaker::validNumbersQuantity(const int &row, const int &col, int (&mark)[10]) {
  for (int i = 0; i < 10; i++) {
    mark[i] = 0;
  }
  for (int i = 0; i < 9; i++) {  // 某一格所在的行和列已填写数字记录
    mark[fullBoard[i][col]] = 1;
    mark[fullBoard[row][i]] = 1;
  }
  int baseRow = row / 3 * 3;
  int baseCol = col / 3 * 3;
  for (int i = 0; i < 3; i++) {  // 某一格所在的九宫格已填写数字记录
    for (int j = 0; j < 3; j++) {
      mark[fullBoard[baseRow + i][baseCol + j]] = 1;
    }
  }
  int count = 0;
  for (int i = 1; i <= 9; i++) {  // 可填写数字计算
    if (mark[i] == 0) {
      count++;
    }
  }
  return count;
}

int usageValidator::checkStringAndConvertToInteger(const string &str) {
  size_t sizeOfString = str.size();
  for (size_t i = 0; i < sizeOfString; i++) {
    int temp = int(str[i]);
    if (temp >= 48 && temp <= 57) {
      continue;
    }
    else {
      return 0;  // 字符串中某个字符不是数字则返回 0，即失败
    }
  }
  int convertedInteger = stoi(str);  // 字符串转换为整数
  if (convertedInteger <= 0 || convertedInteger > 1000000) {
    return 0;  // 不在 0 到 1000000 则返回失败
  }
  return convertedInteger;
}