回溯法解小学数字填数练习（1）

原创

孟君

发布于 2023-08-08 09:04:02

2420

发布于 2023-08-08 09:04:02

文章被收录于专栏：孟君的编程札记

周末，女儿让我辅导她一会数学作业，其中包含一个数字方阵题目，如下图所示；

做这种题目，我们基本的思路如下：

确定一个数占据起始点
- 比如把1放入顶点，作为起始点
确定一个方向（比如）
- 比如选择逆时针或者顺时针，本文实例选择逆时针的方式
选择不同的数进行尝试
- 选择不同的数进行尝试，以保证边上的数值加起来为一个期望的值，如加起来为10，直到找到合适的解为止。

这其实就是回溯法的思路。所以，在辅导她完成作业的同时，顺手写了几个解题的demo程序，记录一下。

题目一、每条线上的三个数和为10

题目1描述：
把1、2、3、4、5、7这六个数填入下图的圆圈里，每条线上的三个数的和都是10。

暴力法

一次随机产生10组结果。

第1次随机产生的结果: [1, 4, 5, 3, 2, 7]
  1  
 4 7 
5 3 2

第2次随机产生的结果: [5, 4, 1, 7, 2, 3]
  5  
 4 3 
1 7 2

第3次随机产生的结果: [1, 4, 5, 3, 2, 7]
  1  
 4 7 
5 3 2

第4次随机产生的结果: [1, 7, 2, 3, 5, 4]
  1  
 7 4 
2 3 5

第5次随机产生的结果: [1, 7, 2, 3, 5, 4]
  1  
 7 4 
2 3 5

第6次随机产生的结果: [1, 7, 2, 3, 5, 4]
  1  
 7 4 
2 3 5

第7次随机产生的结果: [5, 4, 1, 7, 2, 3]
  5  
 4 3 
1 7 2

第8次随机产生的结果: [5, 4, 1, 7, 2, 3]
  5  
 4 3 
1 7 2

第9次随机产生的结果: [1, 4, 5, 3, 2, 7]
  1  
 4 7 
5 3 2

第10次随机产生的结果: [5, 3, 2, 7, 1, 4]
  5  
 3 4 
2 7 1

一共随机[1059]次, 共产生满足条件结果[10]个

回溯法

找到结果 : [1, 4, 5, 3, 2, 7]
  1  
 4 7 
5 3 2

找到结果 : [1, 7, 2, 3, 5, 4]
  1  
 7 4 
2 3 5

找到结果 : [2, 3, 5, 4, 1, 7]
  2  
 3 7 
5 4 1

找到结果 : [2, 7, 1, 4, 5, 3]
  2  
 7 3 
1 4 5

找到结果 : [5, 3, 2, 7, 1, 4]
  5  
 3 4 
2 7 1

找到结果 : [5, 4, 1, 7, 2, 3]
  5  
 4 3 
1 7 2

题目二、每条线上的三个数和为27

题目2描述：
在圆圈里填上不同的数，使每条边上的三个数和都是27。

分析

考虑到小学低年级的内容，我们按照正整数来考虑，一条边上的数字最小1、2、最大为24。所以，找数字的时候在这个范围可以找下。

输出部分结果

找到结果 : [4, 17, 6, 16, 5, 18]
  4  
 17 18 
6 16 5

找到结果 : [4, 17, 6, 18, 3, 20]
  4  
 17 20 
6 18 3

找到结果 : [4, 17, 6, 19, 2, 21]
  4  
 17 21 
6 19 2

找到结果 : [4, 17, 6, 20, 1, 22]
  4  
 17 22 
6 20 1

找到结果 : [4, 18, 5, 1, 21, 2]
  4  
 18 2 
5 1 21

... ... 省略 ...  ... 


找到结果 : [22, 1, 4, 20, 3, 2]
  22  
 1 2 
4 20 3

找到结果 : [22, 1, 4, 21, 2, 3]
  22  
 1 3 
4 21 2

找到结果 : [22, 2, 3, 20, 4, 1]
  22  
 2 1 
3 20 4

找到结果 : [22, 2, 3, 23, 1, 4]
  22  
 2 4 
3 23 1

找到结果 : [22, 3, 2, 21, 4, 1]
  22  
 3 1 
2 21 4

找到结果 : [22, 3, 2, 24, 1, 4]
  22  
 3 4 
2 24 1

找到结果 : [22, 4, 1, 23, 3, 2]
  22  
 4 2 
1 23 3

找到结果 : [22, 4, 1, 24, 2, 3]
  22  
 4 3 
1 24 2

题目三、每条线上的四个数和为20

题目3描述：
把1、2、3、4、5、6、7、8、9这九个数填入下图的圆圈里，每条线上的三个数的和都是20。

输出结果：

找到结果 : [1, 3, 7, 9, 2, 4, 5, 6, 8]
   1   
  3 8  
 7   6 
9 2 4 5

找到结果 : [1, 3, 7, 9, 2, 4, 5, 8, 6]
   1   
  3 6  
 7   8 
9 2 4 5

找到结果 : [1, 3, 7, 9, 4, 2, 5, 6, 8]
   1   
  3 8  
 7   6 
9 4 2 5

找到结果 : [1, 3, 7, 9, 4, 2, 5, 8, 6]
   1   
  3 6  
 7   8 
9 4 2 5

找到结果 : [1, 6, 8, 5, 2, 4, 9, 3, 7]
   1   
  6 7  
 8   3 
5 2 4 9

找到结果 : [1, 6, 8, 5, 2, 4, 9, 7, 3]
   1   
  6 3  
 8   7 
5 2 4 9

... ... 省略 ... ... 

找到结果 : [9, 4, 2, 5, 8, 6, 1, 3, 7]
   9   
  4 7  
 2   3 
5 8 6 1

找到结果 : [9, 4, 2, 5, 8, 6, 1, 7, 3]
   9   
  4 3  
 2   7 
5 8 6 1

找到结果 : [9, 7, 3, 1, 6, 8, 5, 2, 4]
   9   
  7 4  
 3   2 
1 6 8 5

找到结果 : [9, 7, 3, 1, 6, 8, 5, 4, 2]
   9   
  7 2  
 3   4 
1 6 8 5

找到结果 : [9, 7, 3, 1, 8, 6, 5, 2, 4]
   9   
  7 4  
 3   2 
1 8 6 5

找到结果 : [9, 7, 3, 1, 8, 6, 5, 4, 2]
   9   
  7 2  
 3   4 
1 8 6 5

四、小结

在女儿通过自己努力解答完题目后，给她讲解了“选择”、“轴对称”，“交换”的思想，其也理解了答案不止一种。另外，也让她尝试题目一，如果边上的3个数和为12的尝试，其也做出来了，还算不错。

边上3个点和为12的一些打印结果

第1次随机产生的结果: [3, 2, 7, 1, 4, 5]
  3  
 2 5 
7 1 4

第2次随机产生的结果: [4, 5, 3, 2, 7, 1]
  4  
 5 1 
3 2 7

第3次随机产生的结果: [4, 1, 7, 2, 3, 5]
  4  
 1 5 
7 2 3

第4次随机产生的结果: [4, 1, 7, 2, 3, 5]
  4  
 1 5 
7 2 3

第5次随机产生的结果: [3, 5, 4, 1, 7, 2]
  3  
 5 2 
4 1 7

第6次随机产生的结果: [4, 1, 7, 2, 3, 5]
  4  
 1 5 
7 2 3

第7次随机产生的结果: [3, 5, 4, 1, 7, 2]
  3  
 5 2 
4 1 7

第8次随机产生的结果: [3, 2, 7, 1, 4, 5]
  3  
 2 5 
7 1 4

第9次随机产生的结果: [7, 1, 4, 5, 3, 2]
  7  
 1 2 
4 5 3

第10次随机产生的结果: [7, 1, 4, 5, 3, 2]
  7  
 1 2 
4 5 3

程序练习真的可以无处不在，算法还有很多改进空间，这里就不继续跟进了。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java