使用AC3的数独

Question

我正在尝试用java实现数独问题。目前，我已经成功地实现了回溯的天真实现，它似乎起作用了，但我需要的是使用AC3算法。我已经在几个资源上看到了它的伪代码：http://en.wikipedia.org/wiki/AC-3_algorithm (一个例子)，我想知道会有什么限制。

function arc-reduce (x, y)
 bool change = false
 for each vx in D(x)
     find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)
     if there is no such vy {
         D(x) := D(x) - vx
         change := true
     }
 return change

更具体地说，我将X，Y作为2个节点发送：

class Node{
 int i,j;
}

每个节点保存我的sudoku表中元素的坐标。但是，我应该使用什么作为R2约束呢？

我目前的尝试：

  Map m; //contains a map with structure <i,j,List> where i and j are the coordinates in the sudoku table, and List is the initial Domain of that spot on the table;  

  public boolean arc-reduce(Node x, Node y){ 
  ArrayList l1 = m.get(x.i,x.j);
  ArrayList l2 = m.get(y.i,y.j);

  char one,two;
  boolean found=false, change=false;

  for(int a=0;a<l1.size();a++){
     one = l1.get(a);
     found = false;            

     for(int b=0;b<l2.size();b++){
     two = l2.get(b);

         if(one==two && x.i==y.i) //same char same line
             found=true;
         if(one==two && x.j==y.j) //same char same column
             found=true;

     }
     if(found==false){
     l1.remove(i);
     change=true;
     }

  }
  return change;
  }

在它的当前状态下，我在应用这个之后得到的修改过的域名是不正确的。我的实现中有缺陷吗？我非常感谢一些提示，让我走上正确的方向，因为这个问题给我带来了很大的麻烦。

Answer 1

R2约束是两个变量之间的二元约束。在数独中，有3种不同的二进制约束类型。对于数独的给定节点(平方) n：(1) n的行中的每个节点不得具有与n相同的值。(2) n列中的每个节点不得具有与n相同的值。(3)与n相同的正方形中的每个节点不得具有与n相同的值。

您需要将这些约束制定为您的R2约束。你不需要完全按照伪代码来做，这只是算法的一个提纲。数独的想法是，当你分配或改变一个节点的域时，你必须强制与它有关系的节点的域保持一致(减少那些在同一行、列和正方形中的域)。希望这对你有帮助。