人工智能的编程示例 爱因斯坦推理题

1.在一条街上，有5座房子，喷了5种颜色。

2.每个房里住着不同国籍的人。

3.每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物。

其中：

(1)、英国人住在红色的房子里；
(2)、瑞典人养狗作为宠物；
(3)、丹麦人喝茶；
(4)、绿房子紧挨着白房子，在白房子的左边；
(5)、绿房子的主人喝咖啡；
(6)、抽Pall Mall牌香烟的人养鸟；
(7)、黄色房子里的人抽Dunhill牌香烟；
(8)、住在中间那个房子里的人喝牛奶；
(9)、挪威人住在第一个房子里面；
(10)、抽Blends牌香烟的人和养猫的人相邻；
(11)、养马的人和抽Dunhill牌香烟的人相邻；
(12)、抽BlueMaster牌香烟的人和啤酒；
(13)、德国人抽Prince牌香烟；
(14)、挪威人和住在蓝房子的人相邻；
(15)、抽Blends牌香烟的人和喝矿泉水的人相邻。
问题是：谁养鱼?

符号化表示如下：
英国人   p1
瑞典人   p2
丹麦人   p3
挪威人   p4
德国人   p5

红房      h1
绿房      h2
白房      h3
黄房      h4
蓝房      h5

房子的位置从左到右为 1,2,3,4,5

茶          d1
咖啡       d2
牛奶       d3
啤酒       d4
矿泉水    d5

Pall Mall   y1
Dunhill     y2   
Blends      y3
BlueMaster   y4
Prince           y5

狗                  a1
鸟                  a2
猫                  a3
马                  a4
鱼                  a5  

十五句汉语的逻辑的表示式如下
p1=h1
p2 =a1
p3 =d1
w(h2)+1=w(h3)
h2=d2
y1=a2
h4=y2
w(h?)=3=d3
w(h?)=1=p4
|w(y3)- w(a3)|=1
|w(y2)-w(a4)|=1
y4=d4
y5=p5
|w(p4)-w(h5)|=1
|w(y3)-w(d5)|=1

从如下的顺序开始推理
w(p4)=1
w(h5)=2

w(h2)=4
w(h3)=5
w(h1)=3
w(h4)=1

人工推理的过程如下图所示：

推理结束时，25个对象各自对应一个从1到5的数字，人的类别，房子的类别，饮料的类别，烟的类别以及宠物的类别，本类别内的数字不能重复，这是题面上的硬约束。

以上图为编码根据，就可以程序化地实现推理了。数据结构是一个二维的数组。大小是25*5。每一次的推理都是根据约束条件，

划去不可能的数字。约束条件的表示，经过两次的转换，才能进入程序化的推理过程，例如 英国人住红房子，这句话，计算机硬件无法直接处理。第一次转换为 p1与h1关联。 第二次再转换为0与5关联。翻译成计算机程序能懂的语言就是二维数组的第0项与第5项的内容完全一致。

根据上述的15个逻辑关系表达式以及人工推理的列表，编写了如下的Javascript程序，实现了数理逻辑上的人工推理到程序化推理的转化

function test()
{
var result=0;
result=initArray([25],function(a){return range([5]);});

result=set_value_by_group(result,12,3);  // set d3=3;
result=copy_constraint(result,[[10,2],[11,6],[13,18]]);

result=set_value_by_group(result,3,1);  // set p4=1;
result=copy_constraint(result,[[0,5],[1,20],[2,10],[4,19]]);

result=set_abs_contraint_by_group(result,[[3,9]]);
//result=set_value_by_group(result,9,2);  // set h5=2;
result=copy_constraint(result,[[5,0],[6,11],[8,16]]);

result=set_value_by_group(result,7,5);
result=copy_constraint(result,[[5,0],[6,11],[8,16]]);

result=set_value_by_group(result,6,4);
result=copy_constraint(result,[[5,0],[6,11],[8,16]]);

 result=set_abs_contraint_by_group(result,[[14,17],[16,23]]);
 
 result=copy_constraint(result,[[10,2],[11,6],[13,18],[0,5],[1,20],
 [2,10],[4,19],[5,0],[6,11],[8,16],[18,13],[20,1],[19,4],[16,8],[15,21],[21,15]]);
 
 result=check_unique(result);
 
 result=set_abs_contraint_by_group(result,[[14,17]]);
 
  result=copy_constraint(result,[[10,2],[11,6],[13,18],[0,5],[1,20],
 [2,10],[4,19],[5,0],[6,11],[8,16],[18,13],[20,1],[19,4],[16,8],[15,21],[21,15]]);
 
 result=set_abs_contraint_by_group(result,[[17,22]]);
 
 result=copy_constraint(result,[[10,2],[11,6],[13,18],[0,5],[1,20],
 [2,10],[4,19],[5,0],[6,11],[8,16],[18,13],[20,1],[19,4],[16,8],[15,21],[21,15]]);
 
document.getElementById("txt3").innerText=list(result,function(a){return a;});    //list(arr,functionname)
}

// set_add_by_range([1,2,5],1,[1,5])  ---->[2,3]
function set_add_by_range(set1,value,range_value_arr)
{var result=[];
   for(var i=0;i<set1.length;i++)
   {
       var target_value=set1[i]+value;
       if(target_value>=range_value_arr[0]&&target_value<=range_value_arr[1])
          {result.push(target_value);}
   }
   return result;
}

//|result-x_arr|=1
function set_abs_contraint(result,x_arr)
{
var r1=set_add_by_range(x_arr,1,[1,5]);
var r2=set_add_by_range(x_arr,-1,[1,5]);
var r3=set_union(r1,r2);
//var r4=[2,3,4,5];
result=set_inter(r3,result,function(a,b){if (a==b)return 1;else return 0;});
return result;
}

function set_abs_contraint_by_group(result,arr)
{
  for(var i=0;i<arr.length;i++)
   {
            var old_length=result[arr[i][1]].length;
            result[arr[i][1]]=set_abs_contraint(result[arr[i][1]],result[arr[i][0]]);
           if(old_length>1&&result[arr[i][1]].length==1)
             {
            result=set_value_by_group(result,arr[i][1],result[arr[i][1]][0]);
             }
   }
   return result;
}

// d3=3 set_value_by_group(result,12,3)
function set_value_by_group(result,index,value)
{
 
   var  index_bottom=index%5;
   var  index_high=(index-index_bottom)/5;
   var index_value=set_diff(range([5]),[index_bottom+1]);
   for(var i=0;i<index_value.length;i++)
   {
      var target_index=index_high*5+index_value[i]-1;
      var old_length=result[target_index].length;
      result[target_index]=set_diff(result[target_index],[value]);
      if(result[target_index].length==1&&old_length==2)
        {
            result=set_value_by_group(result,target_index,result[target_index][0]);
        }
   }
    result[index]=[value];
   return result;
}

function check_unique(result)
{
   for(var i=0;i<25;i++)
   {
      result=set_unique_value(result,i);
   }
   return result;
}
//2,5  4  3  2,5  1,2,5   （全集-d1U d2Ud3Ud4）/\d5
function set_unique_value(result,index)
{
   var  index_bottom=index%5;
   var  index_high=(index-index_bottom)/5;
   var index_value=set_diff(range([5]),[index_bottom+1]);
   var  union_arr=[];
   for(var i=0;i<index_value.length;i++)
   {
      var target_index=index_high*5+index_value[i]-1;    
      union_arr=set_union(result[target_index],union_arr);
   }
     if(union_arr.length==4)
       {
          var value=set_diff(range([5]),union_arr);
          result[index]=value;
       }
   return result;
}

// result=copy_constraint(result,[[10,2],[11,6],[14,18]])
function copy_constraint(result,arr)
{
   for(var i=0;i<arr.length;i++)
   {
   var old_length=result[arr[i][1]].length;
   result[arr[i][1]]=set_inter(result[arr[i][1]],result[arr[i][0]],function(a,b){if (a==b)return 1;else return 0;});
      if(result[arr[i][1]].length==1&&old_length>1)
        {
           result=set_value_by_group(result,arr[i][1],result[arr[i][1]][0]);
        }
   }
   return result;
}