帮助kakuro的回溯 [英] help in kakuro's backtrack
本文介绍了帮助kakuro的回溯的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
一段时间以来，我一直在为kakuro编码这种回溯算法，现在我需要您的帮助，因为我碰到了石墙...
plz帮助我在回溯功能中发现逻辑错误 ...我认为它与递归调用有关，因为我尝试调试它，但是我做不到很多...
提前发送tnx
p.s.它是为3(行)* 3(列)编写的，因此更易于解决...
ps.s.也许我应该加上redak = row，stupac = column，duljine = lenghts.
i have been codeing this backtracking algorithm for kakuro for some time and now i need your help cause i had hitten a stone wall...
plz help me find logical error in the backtrack function...i presume it has something to do with recursive call cause i have tried to debug it but i couldnt do much...
tnx in advance
p.s. it is written for 3(rows)*3(columns) just so its easier to get around it...
p.s.s. maybe i should add that redak=row, stupac=column, duljine=lenghts.
<pre lang="xml">#include<stdlib.h>
#include<iostream>
#include<utility>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <string>
using namespace std;
pair<int,int> findplace ( pair<string,int> x[4][4] )
{
int i,j;
pair<int,int> t;
t.first=-1;
t.second=-1;
for (i=1;i<4;i++)
{
for(j=1;j<4;j++)
{
if (x[i][j].second==0)
{
t.first=i;
t.second=j;
return(t);
}
}
}
}
void duljine (pair <string,int> tmp[4][4],pair < pair<string,int>,int > temp[4][4])
{
int i,j,k;
for (i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if (tmp[i][j].first=="stupac")
{
int br=0;
for (k=1;k<4;k++)
{
if(tmp[i][j].first!=tmp[k][j].first)
br=br+1;
else
break;
}
temp[i][j].first=tmp[i][j];
temp[i][j].second=br;
}
if (tmp[i][j].first=="redak")
{
int br=0;
for (k=1;k<4;k++)
{
if(tmp[i][j].first!=tmp[i][k].first)
{
br=br+1;
}
else
break;
}
temp[i][j].first=tmp[i][j];
temp[i][j].second=br;
}
}
}
}
int check1(pair<string,int> x[4][4], int a, pair<int,int> t)
{
int j,k;
set<int> b;
set<int>::iterator si;
for (j=1;j<4;j++)
{
if(x[t.first][j].second!=0)
b.insert(x[t.first][j].second);
}
if(b.count(a)==1)
return(0);
else
return(1);
}
int check2(pair<string,int> x[4][4], int a, pair<int,int> t)
{
int i;
set<int> c;
set<int>::iterator si;
for (i=1;i<4;i++)
{
if(x[i][t.second].second!=0)
c.insert(x[i][t.second].second);
}
if(c.count(a)==1)
return(0);
else
return(1);
}
int check3 (pair <pair <string,int>, int> y[4][4], int a, pair<int,int> t)
{
if(y[t.first][0].first.second-a>=0)
return(1);
else
return(0);
}
int check4 (pair <pair <string,int>, int> y[4][4], int a, pair<int,int> t)
{
if(y[0][t.second].first.second-a>=0)
return(1);
else
return(0);
}
int check5 (int i,set<int> t)
{
if(t.count(i)==1)
return(1);
else
return(0);
}
bool backtrack (pair <string,int> x[4][4], pair <pair <string,int>, int> y[4][4])
{
int i,j,k,l;
pair<int,int> t,w;
for(i=1;i<=9;i++)
{
t=findplace(x);
if(t.first==-1 && t.second==-1)
return(true);
if( check1(x,i,t)==1 && check2(x,i,t)==1)
{
if(y[t.first][0].second>1 && y[0][t.second].second>1)
{
if(y[t.first][0].first.second-i>0 && y[0][t.second].first.second-i>0)
{
x[t.first][t.second].second=i;
y[t.first][0].first.second=y[t.first][0].first.second-i;
y[t.first][0].second=y[t.first][0].second-1;
y[0][t.second].first.second=y[0][t.second].first.second-i;
y[0][t.second].second=y[0][t.second].second-1;
if(backtrack(x,y)==true)
return(true);
}
else
{
return(false);
}
}
if(y[t.first][0].second==1 && y[0][t.second].second>1)
{
if(y[t.first][0].first.second-i==0 && y[0][t.second].first.second-i>0)
{
x[t.first][t.second].second=i;
y[t.first][0].first.second=y[t.first][0].first.second-i;
y[t.first][0].second=y[t.first][0].second-1;
y[0][t.second].first.second=y[0][t.second].first.second-i;
y[0][t.second].second=y[0][t.second].second-1;
if(backtrack(x,y)==true)
return(true);
}
else
{
return(false);
}
}
if(y[t.first][0].second>1 && y[0][t.second].second==1)
{
if(y[t.first][0].first.second-i>0 && y[0][t.second].first.second-i==0)
{
x[t.first][t.second].second=i;
y[t.first][0].first.second=y[t.first][0].first.second-i;
y[t.first][0].second=y[t.first][0].second-1;
y[0][t.second].first.second=y[0][t.second].first.second-i;
y[0][t.second].second=y[0][t.second].second-1;
if(backtrack(x,y)==true)
return(true);
}
else
{
return(false);
}
}
if(y[t.first][0].second==1 && y[0][t.second].second==1)
{
if(y[t.first][0].first.second-i==0 && y[0][t.second].first.second-i==0)
{
x[t.first][t.second].second=i;
y[t.first][0].first.second=y[t.first][0].first.second-i;
y[t.first][0].second=y[t.first][0].second-1;
y[0][t.second].first.second=y[0][t.second].first.second-i;
y[0][t.second].second=y[0][t.second].second-1;
if(backtrack(x,y)==true)
return(true);
}
else
{
return(false);
}
}
}
else
{
return(false);
}
}
return(false);
}
int main (void)
{
int i,j;
pair<int,int> z;
pair <string,int> x[4][4];
x[0][0].first="rupa";
x[0][0].second=100;
x[0][1].first="stupac";
x[0][1].second=11;
x[0][2].first="stupac";
x[0][2].second=9;
x[0][3].first="stupac";
x[0][3].second=12;
x[1][0].first="redak";
x[1][0].second=11;
x[2][0].first="redak";
x[2][0].second=9;
x[3][0].first="redak";
x[3][0].second=12;
for(i=1;i<4;i++)
{for(j=1;j<4;j++)
{
x[i][j].first="prazno";
x[i][j].second=0;
}
}
pair <pair <string,int>, int> y[4][4];
stack< pair<string,int> > tmp;
duljine(x,y);
if(backtrack(x,y)==true)
cout << "evo" << endl;
else
cout << "o boze dragi" << endl;
for(i=1;i<4;i++)
{
for(j=1;j<4;j++)
{
cout<< x[i][j].second << " ";
}
cout << endl;
}
return(0);
}
推荐答案
cmon ppl这么难，没人能回答吗? O.o
如果您有任何疑问，请下午告诉我... tnx
cmon ppl is this so tough so noone can answer? O.o
pm me if u have some doubts...tnx
这篇关于帮助kakuro的回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
