1

我正在尝试在 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;
}

每个节点都保存我的数独表中元素的坐标。但是我对 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;
  }

在当前状态下，我在应用后得到的修改域是不正确的。我的实施有缺陷吗？我会很感激一些提示，让我朝着正确的方向前进，因为这个问题给我带来了很大的麻烦。

4

1 回答 1

2

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

您需要将这些约束制定为您的 R2 约束。您不需要完全像伪代码那样做，这只是算法的大纲。数独的想法是，当您进行分配或更改节点的域时，您必须强制与其有关系的节点的域保持一致（减少同一行、列和正方形中的域） . 希望对您有所帮助。

于 2013-10-22T01:11:31.703 回答