请选择 进入手机版 | 继续访问电脑版
查看: 511|回复: 0

[云计算] c++递归解数独,初学者适合

688

主题

688

帖子

2083

积分

猿er

Rank: 1

积分
2083
发表于 2016-8-14 17:58:24
<无详细内容>
  1. #include<iostream>
  2. using namespace std;
  3. void init();
  4. void function(int m);
  5. int canplace(int row,int col,int c);
  6. void outputresult();
  7. int a[9][9], maxm = 0;
  8. int main()
  9. {
  10. init();
  11. function(0);
  12. return 0;
  13. }
  14. void init()
  15. {
  16. int i, j;
  17. for(i = 0; i < 9; i++)
  18. {
  19. for(j = 0; j < 9; j++)
  20. {
  21. cin >> a[i][j];
  22. }
  23. }
  24. }
  25. void function(int m)
  26. {
  27. int i, j, row, col;
  28. if (m >= 81)
  29. {
  30. outputresult();
  31. }
  32. else
  33. {
  34. row = m / 9;
  35. col = m % 9;
  36. if(a[row][col] != 0)
  37. {
  38. function(m+1);
  39. }
  40. for(i = 1; i <= 9; i++)
  41. {
  42. if(canplace(row,col,i) == 1)
  43. {
  44. a[row][col] = i;
  45. function(m + 1);
  46. a[row][col] = 0;
  47. }
  48. }
  49. }
  50. }
  51. int canplace(int row,int col,int c)
  52. {
  53. int i, j;
  54. int flag = 1;
  55. for(i = 0; i < 9; i++ )
  56. {
  57. if(a[row][i] == c || a[i][col] == c)
  58. {
  59. flag = 0;
  60. break;
  61. }
  62. }
  63. if(flag != 0)
  64. {
  65. for(i = (row / 3) * 3; i < (row / 3) * 3 + 3; i++)
  66. {
  67. for(j = (col / 3) * 3; j < (col / 3) * 3 + 3; j++)
  68. {
  69. if(a[i][j] == c)
  70. {
  71. flag = 0;
  72. break;
  73. }
  74. }
  75. if(flag == 0)
  76. {
  77. break;
  78. }
  79. }
  80. }
  81. return flag;
  82. }
  83. void outputresult()
  84. {
  85. int i, j;
  86. for(i = 0; i < 9; i++)
  87. {
  88. if(i % 3 == 0)
  89. {
  90. cout << endl;
  91. }
  92. for(j = 0; j < 9; j++)
  93. {
  94. if(j % 3 == 0)
  95. {
  96. cout << " ";
  97. }
  98. cout << a[i][j] << " ";
  99. }
  100. cout << endl;
  101. }
  102. cout << endl;
  103. }
复制代码


回复

使用道具 举报