reset password
Author Message
sdo8
Posts: 54
Posted 20:10 Oct 11, 2019 |

Hi,
 

I am wondering if we are supposed to implement CDS(Central Domain Selection) via tie-breaking when determining the selected variable under first fail. Example: Assuming you have domains as: (col, number of available values), and n = 10, if you have (1,2) and (7,2), would you select 7 as a variable since it is closest to the center(5,6) (column-wise, that is)? Or should we just implement CDS when we have already selected the variable, and sort the values around values closest to the center? I currently have implemented the CDS by possible values (closest to center row-wise).

 

Currently, with n=20, my N-Queens problem finishes with 199305 assignments WITHOUT first fail.

WITH first fail, I'm down to about 117 assignments (almost a 99.9994% decrease). 

However, with CDS AND first fail, I go up to 303.

 

When my n = 200, the amount of assignments with JUST first fail is 1715.

However, with BOTH first fail and CDS, my assignments are at 202.

 

It looks like the first fail and CDS is the most consistent and results in the least amount of assignments for larger numbers.
Is there any case where we would prefer just first-fail over both first fail and CDS?

 

Thanks

rabbott
Posts: 1649
Posted 21:45 Oct 11, 2019 |

As you said, Central Domain Selection is applied primarily to values, not to variables, although using it to break ties sounds like a good idea.

Also, as you note, problems are not simply ordered. Sometimes it takes longer to solve a smaller problem than a longer one. The structure of the problem may be such that some problems are inherently easier than others because of how the queen patterns interact. (I can't explain it, though.)  I think the same thing happens when selecting values. Most of the time, selecting a value in the center is better than one toward the edges, but that isn't guaranteed to work. 

I've even had some problems in which I used a certain amount of randomness to select variables and domains. In many cases, the differences in the results are not trivial -- even though the random choices would seem more or less equivalent.

sdo8
Posts: 54
Posted 10:21 Oct 12, 2019 |

That is very interesting. I can understand how some problems may be inherently easier. Thank you for the response.