免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 相继自然数既不同行也不同列

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}
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

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

TOP

12072
  1. /*
  2. 相继自然数既不同行也不同列
  3. 1~9九个数字填入3×3的方格中,要求:
  4. 1与2既不同行也不同列且2与3既不同行也不同列且3与4既不同行也不同列且4与5既不同行也不同列
  5. 且5与6既不同行也不同列且6与7既不同行也不同列且7与8既不同行也不同列且8与9既不同行也不同列;
  6. 问:有多少种摆放方案?
  7. */
  8. #include <iostream>


  9. int d[9]={1,2,3,4,5,6,7,8,9};
  10. int cnt;

  11. bool valid(int t)
  12. {
  13.         int r=t/3, c=t%3;
  14.        
  15. //        if(r!=0 && abs(d[t]-d[t-3])==1)
  16. //                return false;
  17. //        if(c!=0 && abs(d[t]-d[t-1])==1)
  18. //                return false;
  19. //        return true;
  20.        
  21. //        return !(r!=0 && abs(d[t]-d[t-3])==1) && !(c!=0 && abs(d[t]-d[t-1])==1);

  22.         return (r==0 || abs(d[t]-d[t-3])!=1) && (c==0 || abs(d[t]-d[t-1])!=1);
  23. }

  24. void backtrack(int t)
  25. {
  26.         if(t==9)
  27.         {
  28.                 ++cnt;
  29.                 return;
  30.         }
  31.         for(int i=t; i<9; ++i)
  32.         {
  33.                 std::swap(d[i],d[t]);
  34.                 if(valid(t))
  35.                         backtrack(t+1);
  36.                 std::swap(d[i],d[t]);
  37.         }
  38. }

  39. int main()
  40. {
  41.         backtrack(0);
  42.         std::cout<<cnt<<std::endl;
  43.         return 0;
  44. }
复制代码
可以很容易地修改到 4^2的数字。问题是阶乘复杂度的,再往上可能就比较吃力了。

TOP

本帖最后由 青青子衿 于 2019-5-11 22:49 编辑

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


emmmm,你想回答的是不是这个问题呀?
[组合] 相继自然数不相邻地填入方格
http://kuing.orzweb.net/viewthread.php?tid=6080

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

TOP

回复 4# 青青子衿

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

TOP

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

只需修改上面的 valid 函数到如下版本
  1. bool valid(int t)
  2. {
  3.         int r=t/3, c=t%3;
  4.        
  5.         for(int i=0; i<r; ++i)
  6.                 if(abs(d[t]-d[3*i+c])==1)
  7.                         return false;
  8.        
  9.         for(int i=0; i<c; ++i)
  10.                 if(abs(d[t]-d[3*r+i])==1)
  11.                         return false;
  12.        
  13.         return true;
  14. }
复制代码

TOP

返回列表 回复 发帖