java - 数独与 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;
}

每个节点都保存我的数独表中一个元素的坐标。但是我用什么来限制 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 约束。您不需要完全按照伪代码的方式进行操作，这只是算法的概要。数独的想法是，当您进行分配或更改节点的域时，您必须强制与其相关节点的域保持一致(减少同一行、列和正方形中的域) .希望对您有所帮助。