设为首页 加入收藏

TOP

使用C++破解九宫格游戏(一)
2013-10-17 09:04:41 】 浏览:8503
Tags:使用 破解 九宫 游戏

  看到论坛上有位大神用C#写了一个破解数独的程序(点击打开链接),不过我对C#也不懂,比较喜欢C++,就用标准C++也写了一个,希望各位喜欢。三纯程序,纯控制台程序,纯各人爱好,纯算法程序,无win API。基本思路与之前那个类似,采用brute force加剪枝,找到第一个符合条件的情况就立即退出不再查找。一般一个合格的数独只有唯一解,如果你的数独多解的话,那也就不叫数独了。

  代码如下:

  #include

  #include

  using namespace std;

  const int MAX_SIZE = 9; // 九宫格

  struct Pos {

  Pos(int x, int y) : row(x), col(y) {};

  int row;

  int col;

  };

  typedef deque qpos;

  qpos Q; // 记录要放置数字的位置

  // 九宫格数组,0表示玩家要放置数字的位置

  int sudoku[MAX_SIZE][MAX_SIZE] = {

  {0, 0, 3, 0, 5, 0, 0, 0, 9},

  {0, 0, 0, 1, 0, 0, 0, 2, 5},

  {0, 8, 0, 0, 3, 7, 0, 0, 0},

  {0, 0, 0, 0, 0, 8, 0, 9, 7},

  {2, 0, 0, 0, 6, 0, 0, 0, 4},

  {9, 4, 0, 0, 0, 0, 8, 0, 1},

  {0, 0, 0, 6, 9, 0, 4, 0, 0},

  {8, 0, 0, 0, 0, 5, 0, 0, 0},

  {6, 0, 0, 0, 1, 0, 9, 0, 0},

  };

  void printSudoku()

  {

  cout << "-------------------------" << endl;

  for (int i = 0; i < MAX_SIZE; i++) {

  for (int j = 0; j

  if (j % 3 == 0) {

  cout << "| ";

  }

  cout << sudoku[i][j] << " ";

  }

  cout << "| ";

  cout << endl;

  if ( (i+1) % 3 == 0 ) {

  cout << "-------------------------" << endl;

  }

  }

  }

  bool check(Pos p, int n)

  {

  int cur_row = p.row;

  int cur_col = p.col;

  // 验证行列是否合格

  for (int i = 0; i < MAX_SIZE; i++) {

  if (n == sudoku[i][cur_col] || n == sudoku[cur_row][i]) {

  return false;

  }

  }

  // 验证九宫格内是无复生数字

  int grid_row = ( cur_row / 3 ) * 3;

  int grid_col = ( cur_col / 3 ) * 3;

  for (int i = 0; i < 3; i++) {

  if (n == sudoku[grid_row][i + grid_col] ||

  n == sudoku[grid_row + i][grid_col]) {

  return false;

  }

  }

  return true;

  }

  bool place(qpos & Q)

  {

  // 递归结束条件为没有要断续放置数字的位置

  if (Q.empty()) {

  printSudoku();

  return true;

  }

  Pos cur(Q.front().row, Q.front().col); // 当前需要放置的位置信息

  Q.pop_front();

  for (int i = 1; i <= 9; i++) { // 从1到9轮流尝试

  if ( check(cur, i) ) {

  sudoku[cur.row][cur.col] = i; // 放置数字i到当前位置

  if ( !place(Q) ) { // 放置下一位置

  // 下一位置放置失败,则在当前位置尝试放置下一个i

  sudoku[cur.row][cur.col] = 0; // 将当前位置值重置

  } else { // 下一位置放置成功

  return true;

  }

  }

  }

  Q.push_front(cur); //当前位置不论怎么放置数字,下一位置都无法放置成功,

  // 重新插入该位置信息,返回上一级放置位置

  return false;

  }

  int main()

  {

  // Q中保存需要放置数字的位置

  for (int i = 0; i < MAX_SIZE; i++) {

  for (int j = 0; j < MAX_SIZE; j++) {

  if (0 == sudoku[i][j]) {

  Q.push_back(Pos(i, j));

  }

  }

  }

  place(Q);

  return 0;

  }

  #include

  #include

  using namespace std;

  const int MAX_SIZE = 9; // 九宫格

  struct Pos {

  Pos(int x, int y) : row(x), col(y) {};

  int row;

  int col;

  };

  typedef deque qpos;

  qpos Q; // 记录要放置数字的位置

   

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++关键字之static 下一篇C++接口与实现分离的2种方法

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目