1. The 1st method i guess would have heavy space requirement,(I'm really trying to improve this method so the i would work for n>15).
2. Undoing the queens isn't the problem, but undoing the changes in the domains of unvisited variables is what is proving to be a tough job
P.S. : I have included my code here , Go through it IF you are interested :)
Thank you once again
On 12/5/05, Dhyanesh <
[EMAIL PROTECTED]> wrote:
A simple way is to store the state in a temporary object before modifying it and doing the recursive call again.
Other way is since you know which queen you just place before the recursive call. Just undo that queen. All other further queens will also be undone when their recursive calls end. I think this is a better way.
-Dhyanesh
On 12/5/05, Rave Hanker <[EMAIL PROTECTED] > wrote:Hello everone,
I'm trying to solve n-queens problem by a new approach(actually , it's quite old) called Contraint Programming, It is basically backtracking combined with notions of local consistancy. My basic algo is this
bool findsol(ChessBoard *ptboard, int row)
{// Basic Backtracking procedure
static int times=1;
if(ptboard->propogate()==false)
return false;
for(int col=0; col<n; col++)
{
if(ptboard->place(row,col))
if(row==n-1)
{
ptboard->dispboard();
cout<<endl<<"Soln No. "<<times++<<".\n";
return true;
}
else if(findsol(ptboard,row+1))
return true;
else
undomoves();
}
return false;
}
Basically i have variables that keep track of the domain each var(queens pos in n rows) can take now the propogate procedure restricts the domain of each unassigned var. according to the values the assigned variables have taken.
My trouble is with writing the undo procedure that requires i put the domains back to the same state it was before the propogate() procedure of this call was invoked. Anyone has any idea on i could write this?
--
Well," said Owl, "the customary procedure in such cases is as follows."
"What does Crustimoney Proseedcake mean?" said Pooh. "For I am a Bear of Very Little Brain, and long words Bother me."
"It means the Thing to Do."
"As long as it means that, I don't mind," said Pooh humbly.
--
Well," said Owl, "the customary procedure in such cases is as follows."
"What does Crustimoney Proseedcake mean?" said Pooh. "For I am a Bear of Very Little Brain, and long words Bother me."
"It means the Thing to Do."
"As long as it means that, I don't mind," said Pooh humbly.
