相继自然数既不同行也不同列

青青子衿

1～9九个数字填入3×3的方格中，要求：
1与2既不同行也不同列且2与3既不同行也不同列且3与4既不同行也不同列且4与5既不同行也不同列
且5与6既不同行也不同列且6与7既不同行也不同列且7与8既不同行也不同列且8与9既不同行也不同列；
问：有多少种摆放方案？
一个例子：
\begin{array}{|r|r|r|r|}   
\hline 2 & 8 & 4\\   
\hline 9 & 3 & 6\\   
\hline 7 & 5 & 1\\
\hline \end{array}

realnumber

我猜你不想要编程解决，条件很多
仅仅是“1与2既不同行也不同列且2与3既不同行也不同列且3与4既不同行也不同列”就不容易

业余的业余

12072

2. /*
3. 相继自然数既不同行也不同列
4. 1～9九个数字填入3×3的方格中，要求：
5. 1与2既不同行也不同列且2与3既不同行也不同列且3与4既不同行也不同列且4与5既不同行也不同列
6. 且5与6既不同行也不同列且6与7既不同行也不同列且7与8既不同行也不同列且8与9既不同行也不同列；
7. 问：有多少种摆放方案？
8. */
9. #include <iostream>
12. int d[9]={1,2,3,4,5,6,7,8,9};
13. int cnt;
15. bool valid(int t)
16. {
17.         int r=t/3, c=t%3;
18.        
19. //        if(r!=0 && abs(d[t]-d[t-3])==1)
20. //                return false;
21. //        if(c!=0 && abs(d[t]-d[t-1])==1)
22. //                return false;
23. //        return true;
24.        
25. //        return !(r!=0 && abs(d[t]-d[t-3])==1) && !(c!=0 && abs(d[t]-d[t-1])==1);
27.         return (r==0 || abs(d[t]-d[t-3])!=1) && (c==0 || abs(d[t]-d[t-1])!=1);
28. }
30. void backtrack(int t)
31. {
32.         if(t==9)
33.         {
34.                 ++cnt;
35.                 return;
36.         }
37.         for(int i=t; i<9; ++i)
38.         {
39.                 std::swap(d[i],d[t]);
40.                 if(valid(t))
41.                         backtrack(t+1);
42.                 std::swap(d[i],d[t]);
43.         }
44. }
46. int main()
47. {
48.         backtrack(0);
49.         std::cout<<cnt<<std::endl;
50.         return 0;
51. }

Copy the Code

可以很容易地修改到 4^2的数字。问题是阶乘复杂度的，再往上可能就比较吃力了。

青青子衿

回复 3# 业余的业余

12072
可以很容易地修改到 4^2的数字。问题是阶乘复杂度的，再往上可能就比较吃力了。 ...
业余的业余 发表于 2019-5-11 22:12

emmmm,你想回答的是不是这个问题呀？
[组合] 相继自然数不相邻地填入方格
forum.php?mod=viewthread&tid=6080

这个的结果应该有问题吧！“不同行且不同列”比“不相邻”的要求更高，为什么数目还是一样的呢？

业余的业余

回复 4# 青青子衿

真的是不相邻做的，我改一下。

业余的业余

1512， 如果考虑旋转、镜面对称，是1512/8=189

只需修改上面的 valid 函数到如下版本

2. bool valid(int t)
3. {
4.         int r=t/3, c=t%3;
5.        
6.         for(int i=0; i<r; ++i)
7.                 if(abs(d[t]-d[3*i+c])==1)
8.                         return false;
9.        
10.         for(int i=0; i<c; ++i)
11.                 if(abs(d[t]-d[3*r+i])==1)
12.                         return false;
13.        
14.         return true;
15. }

Copy the Code