一道企业的面试题目，大家讨论一下吧

问，往一个4×4的大方格中填入数字1，2，3，4，要求每个每行每列都是自然数1-4的排列且相邻方格的数字不能相同，问，共有多少填法?
  比如 1   2   3   4

       2   1   4   3

       3   4   1   2

       4   3   2   1  就满足条件

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

不好意思，题目搞错了，原题目是：  4×4的格子
共分成2×2对称的4个区域
每个区域内包含abcd4个字母
整个区域内的每一行列都包含这四个字母
就是2×2的正方形
一共可以有多少种可能？
就是比如  1 2 3 4

           3 4 1 2

           2 1 4 3

           4 3 2 1
我的答案是：96，方法如下，不知道对错。我是这样想的，自上到下，自左到右，这四个小正方形分别命名为A B C D,   A中，abcd 可以自由排列，共有24种方法；B中，对于A中每一种排序，第一行，只能放入两个字母，（除去A中已有的两个）有2种排序，B中第二行是有2种方法（你会发现，这两个字母和A中弟一行两个字母一样），C中；对于A中每一种程序，第一列只能放入两个字母，有2种方法（同B中第一行类似）；C中第二列，只能放入两个字母，有2种排列（同B中第二行类似）；D中每一次对于A，B，C只能有一个排序。所以，答案=24*2*2*2*2=96。
不好意思，是384，我真的……，晕了，不好意思，大家见笑了，算错了，对不起对不起，
我的答案是：384，方法如下，不知道对错。我是这样想的，自上到下，自左到右，这四个小正方形分别命名为A B C D,   A中，abcd 可以自由排列，共有24种方法；B中，对于A中每一种排序，第一行，只能放入两个字母，（除去A中已有的两个）有2种排序，B中第二行是有2种方法（你会发现，这两个字母和A中弟一行两个字母一样），C中；对于A中每一种程序，第一列只能放入两个字母，有2种方法（同B中第一行类似）；C中第二列，只能放入两个字母，有2种排列（同B中第二行类似）；D中每一次对于A，B，C只能有一个排序。所以，答案=24*2*2*2*2=384。
原来的排列数是p4*p4*p4*p4=24*24*24*24不可能会有96那么少的
第一行24种没有问题，如果固定第一列234不变考虑后面的变化，1234下对应2xxx一共三种变化413，341，143，然后固定第二行，因为上面已经有固定两行，很明显，第三行的3个未定数字只有一种变化，最后行也是只有一种。最后，算上第一列头的变换组合应该是24*3*6=422种
前面多算了，对于xhh的解不甚理解
xxh0534() 说的，有个小问题。我们首先重新把这个4*4的方格的每个位置命名：
a1  a2  b1  b2          a区    b区
a3  a4  b3  b4
c1  c2  d1  d2          c区    d区
c3  c4  d3  d4
OK。然后，根据xxh0534()的做法，b区和c区的排列是互相无关的。其实不是。必须指出，b1、b3和c1、c2不能正好凑成1、2、3、4。也就是说，当a区和b区确定后（此时的方案个数是24*2*2），c区的数据必须根据b区的已经确定的数据来填，即去除上述不可能的排列方案后，新的c区的排列数是2*2-1，所以，最终结果是：24*2*2*(2*2-1)=288。这是我做出的最大值了。当然，也有可能数值会更小。
我觉得是24*(4*(4-1)) = 288种
A区24种，B区4，C区本来也有4种，但有1种情况不行，D区只有一种情况
算错了，同意tonyformu的288，有谁能写出程序吗？参考下
确实是288种,我写了一段代码,就是写得太烂了,但是可以打出来,大家看一看有没有更好的方法
public class Test { /**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
int[] num1=new int[4];
int[] num2=new int[4];
int[] num3=new int[4];
int[] num4=new int[4];
int[] num5=new int[4];
int[] num6=new int[4];
int[] num7=new int[4];
int[] num8=new int[4];
int[] num9=new int[4];
int[] num10=new int[4];
int[] num11=new int[4];
int[] num12=new int[4];
int[] num13=new int[4];
int[] num14=new int[4];
int[] num15=new int[4];
int[] num16=new int[4];
int x=0;
for(int a=0;a<4;a++){
num1[a]=a;
for(int b=0;b<4;b++){
num2[b]=b;
for(int c=0;c<4;c++){
num3[c]=c;
for(int d=0;d<4;d++){
num4[d]=d;
for(int e=0;e<4;e++){
num5[e]=e;
for(int f=0;f<4;f++){
num6[f]=f;
for(int g=0;g<4;g++){
num7[g]=g;
for(int h=0;h<4;h++){
num8[h]=h;
for(int i=0;i<4;i++){
num9[i]=i;
for(int j=0;j<4;j++){
num10[j]=j;
for(int k=0;k<4;k++){
num11[k]=k;
for(int l=0;l<4;l++){
num12[l]=l;
for(int m=0;m<4;m++){
num13[m]=m;
for(int n=0;n<4;n++){
num14[n]=n;
for(int o=0;o<4;o++){
num15[o]=o;
for(int p=0;p<4;p++){
num16[p]=p;
if(num1[a]!=num2[b] && num1[a]!=num3[c] && num1[a]!=num4[d] && num1[a]!=num5[e] && num1[a]!=num9[i] && num1[a]!=num13[m] && num1[a]!=num6[f]
    && num2[b]!=num3[c] && num2[b]!=num4[d] && num2[b]!=num6[f] && num2[b]!=num10[j] && num2[b]!=num14[n] && num2[b]!=num5[e]
    && num3[c]!=num4[d] && num3[c]!=num7[g] && num3[c]!=num8[h] && num3[c]!=num11[k] && num3[c]!=num15[o]
    && num4[d]!=num7[g] && num4[d]!=num8[h] && num4[d]!=num12[l] && num4[d]!=num16[p]
&& num5[e]!=num6[f] && num5[e]!=num7[g] && num5[e]!=num8[h] && num5[e]!=num9[i] && num5[e]!=num13[m]
    && num6[f]!=num7[g] && num6[f]!=num8[h] && num6[f]!=num10[j] && num6[f]!=num14[n]
&& num7[g]!=num8[h] && num7[g]!=num11[k] && num7[g]!=num15[o]
&& num8[h]!=num12[l] && num8[h]!=num16[p]
&& num9[i]!=num10[j] && num9[i]!=num11[k] && num9[i]!=num12[l] && num9[i]!=num13[m] && num9[i]!=num14[n]
&& num10[j]!=num11[k] && num10[j]!=num12[l] && num10[j]!=num13[m] && num10[j]!=num14[n]
&& num11[k]!=num12[l] && num11[k]!=num15[o] && num11[k]!=num16[p]
&& num12[l]!=num15[o] && num12[l]!=num16[p]
&& num13[m]!=num14[n] && num13[m]!=num15[o] && num13[m]!=num16[p]
&& num14[n]!=num15[o] && num14[n]!=num16[p] && num15[o]!=num16[p]){
x++;
System.out.println(num1[a]+"\t"+num2[b]+"\t"+num3[c]+"\t"+num4[d]);
System.out.println(num5[e]+"\t"+num6[f]+"\t"+num7[g]+"\t"+num8[h]);
System.out.println(num9[i]+"\t"+num10[j]+"\t"+num11[k]+"\t"+num12[l]);
System.out.println(num13[m]+"\t"+num14[n]+"\t"+num15[o]+"\t"+num16[p]);
System.out.println("");
System.out.println(x);
System.out.println("");

}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}}
答案是288种
#include <iostream.h>
int a[6][6]={0};
int num=0;
int check(int i,int j,int k){
  int l,m,pi,pj;
  //1. Check the line
  for (l=1;l<=4;l++)
if ( (l!=j) && (a[i][l]!=0) && (a[i][l]==k) )
  return(0);
  //2. Check the column
  for (l=1;l<=4;l++)
if ( (l!=i) && (a[l][j]!=0) && (a[l][j]==k) )
  return(0);
  //3. Check the 2x2 matrix
  //3.1 Firstly we will have to check the parent_i(pi) and parent_j(pj)
  if (i<=2) pi=1;
  else if (i<=4) pi=3;
// else pi=7;
  if (j<=2) pj=1;
  else if (j<=4) pj=3;
  //else pj=7;
  //3.2 Now we can check it
  for (l=0;l<=1;l++)
   for (m=0;m<=1;m++){
if ( ((pi+l)!=i) && ((pj+m)!=j) )
   if ( ( a[pi+l][pj+m]!=0 ) && ( a[pi+l][pj+m]==k ) )
return(0);
   }
  return(1);
}output(){
  int i,j;
  cout<<"One solution is:"<<endl;
  for (i=1;i<=4;i++)
  {
for (j=1;j<=4;j++)
  cout<<a[i][j]<<" ";
cout<<endl;
  }
}backtrack(int i,int j,int k){
  int l;
  if (check(i,j,k)==1)
{
a[i][j]=k; //Fill in the okay solution
//Generate next i,j
do{
    if (j<4) j++;
    else { i++; j=1; }
  } while (a[i][j]!=0); //End of Generate next i,j
if (i<5)
{
    for (l=1;l<=4;l++)
backtrack(i,j,l);
  }
else
{ num++;}
// output();
a[i][j]=0; /*When fails and goes upperwards, the value must be cleared*/
  }
}
main(){
  int i;
  for (i=1;i<=4;i++)
  { backtrack(1,1,1);
  }
  cout<<num;
}
上面的算法我是改造9宫问题的算法：）
不好意思上面main函数中掉用的是backtrack(1,1,i)
ps：算法是我改的，不是原创，不要搞个人崇拜哦。。
to   xxh0534() ( 一级(初级))
本来你的答案是和我的一样的，可是为什么你分析完后要算错呢？？真理就这样给埋没咯，呵呵，还好一改正过来了，哈哈
感觉还是384，上面2行可以确定了24*4种，在xiaoxiao0714() 演示的c区中可以做出4种来的，没有发现有重复的，所以还是觉得是24*4*4=384种