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 制約は、2 つの変数間のバイナリ制約です。数独には、3 つの異なるバイナリ制約タイプがあります。数独の特定のノード (正方形) n について: (1) n の行のすべてのノードが n と同じ値であってはなりません。(2) n の列のすべてのノードが n と同じ値であってはなりません。(3) n と同じ正方形内のすべてのノードが n と同じ値であってはなりません。

これらの制約を R2 制約として定式化する必要があります。疑似コードとまったく同じようにする必要はありません。これは、アルゴリズムの概要にすぎません。数独の考え方は、ノードのドメインを割り当てたり変更したりするときに、関係のあるノードのドメインとの一貫性を強制する必要があるということです (同じ行、列、正方形にあるノードのドメインを減らします)。 . お役に立てば幸いです。

于 2013-10-22T01:11:31.703 に答える