12072- /*
- 相继自然数既不同行也不同列
- 1~9九个数字填入3×3的方格中,要求:
- 1与2既不同行也不同列且2与3既不同行也不同列且3与4既不同行也不同列且4与5既不同行也不同列
- 且5与6既不同行也不同列且6与7既不同行也不同列且7与8既不同行也不同列且8与9既不同行也不同列;
- 问:有多少种摆放方案?
- */
- #include <iostream>
- int d[9]={1,2,3,4,5,6,7,8,9};
- int cnt;
- bool valid(int t)
- {
- int r=t/3, c=t%3;
-
- // if(r!=0 && abs(d[t]-d[t-3])==1)
- // return false;
- // if(c!=0 && abs(d[t]-d[t-1])==1)
- // return false;
- // return true;
-
- // return !(r!=0 && abs(d[t]-d[t-3])==1) && !(c!=0 && abs(d[t]-d[t-1])==1);
- return (r==0 || abs(d[t]-d[t-3])!=1) && (c==0 || abs(d[t]-d[t-1])!=1);
- }
- void backtrack(int t)
- {
- if(t==9)
- {
- ++cnt;
- return;
- }
- for(int i=t; i<9; ++i)
- {
- std::swap(d[i],d[t]);
- if(valid(t))
- backtrack(t+1);
- std::swap(d[i],d[t]);
- }
- }
- int main()
- {
- backtrack(0);
- std::cout<<cnt<<std::endl;
- return 0;
- }
复制代码 可以很容易地修改到 4^2的数字。问题是阶乘复杂度的,再往上可能就比较吃力了。 |