DLXアルゴリズム及び応用(一)DLXテンプレート+解数独
11317 ワード
DLXアルゴリズム
原理:ネットが多すぎて、私は書きません.の
用途:正確なオーバーライドの問題を解決する
以下のコードは厳密にアルゴリズムに従って書かれているが,実際にはこのようなデータドメインのないチェーンテーブルに対しては配列でシミュレーションすることができる(DLXアルゴリズムおよび応用(二)Matlab解数独を参照).
コードの中ですべてvectorを使って、もっと通用します~
後半では数独を解く例を示し、数独を正確にカバーする問題にどのように変換するかの文章もネット上で検索された...私は書きません.の
2014-2-15修正:変換方法を書いておきましょう
問題を正確に上書きする行列の表示:
このような行列が与えられ、
例えば2,4,6行目
では、数独問題を324列の正確な上書き問題に変換します.
数独には4つの制限条件があり、それぞれ81列に変換されます.
最初の格子から81番目の格子まで、01行列を徐々に構築しましょう.
3行5列目など、数値が与えられた格子については7
では、23106205259列が1で、その他は0で、それぞれを表します.
数字が指定されていない場合、この格子は9つの可能性があり、9行を挿入します.以下は1です.
最大81*9行の01行列の中で、1組の正確なカバー(81行)を探して、1つの数独を解くことができます
コードは次のとおりです.
例:
最後の数独は伝説のフィンランドの数学者が設計した最も難しい数独で、更新回数から見ると、確かに難しい.
アルゴリズム全体の時間は数独を01マトリクスに変換し、チェーンテーブルを構築するのに浪費され、本当のDLXはまだ短い!
(DLXアルゴリズムでカラムを上書きする操作を1回更新と呼ぶ)
原理:ネットが多すぎて、私は書きません.の
用途:正確なオーバーライドの問題を解決する
以下のコードは厳密にアルゴリズムに従って書かれているが,実際にはこのようなデータドメインのないチェーンテーブルに対しては配列でシミュレーションすることができる(DLXアルゴリズムおよび応用(二)Matlab解数独を参照).
コードの中ですべてvectorを使って、もっと通用します~
後半では数独を解く例を示し、数独を正確にカバーする問題にどのように変換するかの文章もネット上で検索された...私は書きません.の
2014-2-15修正:変換方法を書いておきましょう
問題を正確に上書きする行列の表示:
このような行列が与えられ、
1 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 1 0 1
0 0 1 0 1 1 0
0 1 1 0 0 1 1
0 1 0 0 0 0 1例えば2,4,6行目
では、数独問題を324列の正確な上書き問題に変換します.
数独には4つの制限条件があり、それぞれ81列に変換されます.
---1 81 ， 9*9=81 。 ， 01 01 1
1~9
---81+1 81*2 ， 9 ， ， 1
1~9
---81*2+1 81*3 ， 9
1~9
---81*3+1 81*4 ， 9 最初の格子から81番目の格子まで、01行列を徐々に構築しましょう.
3行5列目など、数値が与えられた格子については7
では、23106205259列が1で、その他は0で、それぞれを表します.
23 = （3-1）*9 + 5 3 5
106= 81 + （3-1）*9 + 7 3 7
205= 81*2 + （5-1）*9 + 7 5 7
259= 81*3 + （2-1）*9 + 7 2 7
数字が指定されていない場合、この格子は9つの可能性があり、9行を挿入します.以下は1です.
：23,100,199,253
：23,101,200,254
........
：23,108,207,261最大81*9行の01行列の中で、1組の正確なカバー(81行)を探して、1つの数独を解くことができます
コードは次のとおりです.
#include
#include
#include
#include
#include
using namespace std;
struct Node{
Node *up, *down, *left, *right, *colRoot, *rowRoot;//
int Num;// ,
int Size;// ,
Node(int i = -1 ): Num(i),Size(0) {};//
};
class DLX{
public:
DLX(vector > &matrix, int m, int n);
~DLX() { delete Head;};//
void init();
void link(vector > &matrix);
void cover(Node *cRoot);
void recover(Node *cRoot);
bool Search(int k = 0);
vector getResult() const { return result;}
int getUpdates() const { return _updates;}
private:
Node *Head;
vector result;//
int _row, _col, _updates;// ,
};
DLX::DLX(vector > &matrix, int m, int n)
:_row(m),_col(n),_updates(0)
{
Head = new Node;
Head->up = Head;
Head->down = Head;
Head->right = Head;
Head->left = Head;
init();
link(matrix);
}
void DLX::init()
{
Node *newNode;
for (int ix = 0; ix < _col; ++ix)// ,
{
newNode = new Node;
newNode->up = newNode;
newNode->down = newNode;
newNode->right = Head->right;
newNode->left = Head;
newNode->right->left = newNode;
Head->right = newNode;
}
for (int ix = 0; ix < _row; ++ix)// ,
{
newNode = new Node(_row-ix);// _row-ix
newNode->down = Head->down;
newNode->up = Head;
newNode->down->up = newNode;
Head->down = newNode;
}
}
void DLX::link(vector > &matrix)
{
Node *current_row, *current_col, *newNode, *current;// , , ,
current_row = Head;
for (int row = 0; row < _row; ++row)
{
current_row = current_row->down;
current_col = Head;
for (int col = 0; col < _col; ++col)
{
current_col = current_col->right;
if (matrix[row][col] == 0)// 0
continue;
newNode = new Node;
newNode->colRoot = current_col;
newNode->rowRoot = current_row;//
newNode->down = current_col;
newNode->up = current_col->up;
newNode->up->down = newNode;
current_col->up = newNode;//
if (current_row->Size == 0)//
{
current_row->right = newNode;
newNode->left = newNode;
newNode->right = newNode;
current_row->Size++;
}
current = current_row->right;// ( )
newNode->left = current->left;
newNode->right = current;
newNode->left->right = newNode;
current->left = newNode;//
current_col->Size++;
}
}
}
void DLX::cover(Node *cRoot)//
{
++_updates;
cRoot->left->right = cRoot->right;
cRoot->right->left = cRoot->left;//
Node *i, *j;
i = cRoot->down;
while (i != cRoot)
{
j = i->right;
while (j != i)
{
j->down->up = j->up;
j->up->down = j->down;
j->colRoot->Size--;
j = j->right;
}
i = i->down;
}
}
void DLX::recover(Node *cRoot)// !!
{
Node *i, *j;
i = cRoot->up;
while (i != cRoot)
{
j = i->left;
while (j != i)
{
j->colRoot->Size++;
j->down->up = j;
j->up->down = j;
j = j->left;
}
i = i->up;
}
cRoot->right->left = cRoot;
cRoot->left->right = cRoot;
}
bool DLX::Search(int k)
{
if (Head->right == Head)// ,
return true;
Node *cRoot, *c;
int minSize = INT_MAX;
for(c = Head->right; c != Head; c = c->right)//
{
if (c->Size < minSize)
{
minSize = c->Size;
cRoot = c;
if (minSize == 1)
break;
if (minSize == 0)// ,
return false;
}
}
cover(cRoot);
Node *current_row,*current;
for (current_row = cRoot->down; current_row != cRoot; current_row = current_row->down)
{
result.push_back(current_row->rowRoot->Num);// result
for (current = current_row->right; current != current_row; current = current->right)
{
cover(current->colRoot);
}
if (Search(k+1))
return true;
for (current = current_row->left; current != current_row; current = current->left)
recover(current->colRoot);
result.pop_back();// , result
}
recover(cRoot);
return false;
}
vector > sudoku2matrix(string &problem)// 01
{
vector > matrix;
for (int ix = 0; ix < 81; ++ix)
{
int val = problem[ix] - '0';
vector current_row(324,0);
if (val != 0)
{
current_row[ix] = 1;
current_row[81 + ix/9*9 + val -1] = 1;
current_row[162 + ix%9*9 +val -1] = 1;
current_row[243 + (ix/9/3*3+ix%9/3)*9 +val -1] = 1;
matrix.push_back(current_row);
continue;
}
for (int jx = 0; jx < 9; ++jx)
{
vector current_row2(324,0);
current_row2[ix] = 1;
current_row2[81 + ix/9*9 + jx] = 1;
current_row2[162 + ix%9*9 +jx] = 1;
current_row2[243 + (ix/9/3*3+ix%9/3)*9 +jx] = 1;
matrix.push_back(current_row2);
}
}
return matrix;
}
vector matrix2sudoku(vector > &matrix, vector result)// 01
{
vector solution(81);
for (int ix = 0; ix < 81; ++ix)
{
vector current = matrix[result[ix]-1];
int pos = 0, val = 0;
for (int jx = 0; jx < 81; ++jx)
{
if (current[jx] == 1)
break;
++pos;
}
for (int kx = 81; kx < 162; ++kx)
{
if (current[kx] == 1)
break;
++val;
}
solution[pos] = val%9 + 1;
}
return solution;
}
void solve_sudoku(string &problem, ostream &os = cout)
{
clock_t start_1 = clock();
vector > matrix = sudoku2matrix(problem);
clock_t end_1 = clock();
float time_1=(float)(end_1-start_1)/CLOCKS_PER_SEC;
clock_t start_2 = clock();
DLX sudoku(matrix,matrix.size(),324);
clock_t end_2 = clock();
float time_2=(float)(end_2-start_2)/CLOCKS_PER_SEC;
clock_t start_3 = clock();
if (!sudoku.Search())
{
os << " !
";
return;
}
clock_t end_3 = clock();
float time_3=(float)(end_3-start_3)/CLOCKS_PER_SEC;
clock_t start_4 = clock();
vector solution = matrix2sudoku(matrix, sudoku.getResult());
clock_t end_4 = clock();
float time_4=(float)(end_4-start_4)/CLOCKS_PER_SEC;
for (int ix = 0; ix < 81; ++ix)
os << solution[ix] << ((ix+1)%9 ? '\0' : '
');
os << " 01 : " << time_1 << "s
"
<< " : " << time_2 << "s
"
<< "Dancing : " << time_3 << "s
"
<< "Dancing : " << sudoku.getUpdates() << "
"
<< " : " << time_4 << "s
" << endl;
}
int main()
{
string problem;
ofstream outfile("solution.txt");
ifstream infile("problem.txt");
while (infile >> problem)
{
outfile << problem << endl;
if (problem.size() != 81)
{
outfile << "
";
continue;
}
solve_sudoku(problem, outfile);
}
}
例:
problem.txt ：
027380010010006735000000029305692080000000000060174503640000000951800070080065340
000000520080400000030009000501000600200700000000300000600010000000000704000000030
800000000003600000070090200050007000000045700000100030001000068008500010090000400
solution.txt
027380010010006735000000029305692080000000000060174503640000000951800070080065340
5 2 7 3 8 9 4 1 6
8 1 9 4 2 6 7 3 5
4 3 6 7 5 1 8 2 9
3 7 5 6 9 2 1 8 4
1 9 4 5 3 8 2 6 7
2 6 8 1 7 4 5 9 3
6 4 3 2 1 7 9 5 8
9 5 1 8 4 3 6 7 2
7 8 2 9 6 5 3 4 1
01 : 0.002s
: 0.002s
Dancing : 0s
Dancing : 324
: 0s
000000520080400000030009000501000600200700000000300000600010000000000704000000030
4 1 6 8 3 7 5 2 9
9 8 2 4 6 5 3 7 1
7 3 5 1 2 9 4 6 8
5 7 1 2 9 8 6 4 3
2 9 3 7 4 6 1 8 5
8 6 4 3 5 1 2 9 7
6 4 7 9 1 3 8 5 2
3 5 9 6 8 2 7 1 4
1 2 8 5 7 4 9 3 6
01 : 0.002s
: 0.002s
Dancing : 0s
Dancing : 419
: 0s
800000000003600000070090200050007000000045700000100030001000068008500010090000400
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
01 : 0.002s
: 0.002s
Dancing : 0.001s
Dancing : 8321
: 0s
最後の数独は伝説のフィンランドの数学者が設計した最も難しい数独で、更新回数から見ると、確かに難しい.
アルゴリズム全体の時間は数独を01マトリクスに変換し、チェーンテーブルを構築するのに浪費され、本当のDLXはまだ短い!
(DLXアルゴリズムでカラムを上書きする操作を1回更新と呼ぶ)