View Forum Topic

Forums
CS4660
Too optimistic about the solver

Author	Message
rabbott Posts: 1649	Posted 21:28 Oct 12, 2019 \| When I ran all the columns through the propagator, it produced no additional results. So all we learned from the propagator, at least with respect to the problem variables, is that S must be 9. Running the solver from right to left, with the Variables ordered as 'DEYNRO' a solution is found after 2058 assignments. If we add a starting assignment of S = 9 a solution is found in 1027 assignments, about half as many. So even though the propagator didn't solve the problem, it cut down the number of assignments by a factor of 2. Furthermore, if we run the solver with the variables in the traditional order (SENDMORY) with propagation of all_different, nearly 250,000 assignments are required to find a solution. If we run exactly the same situation except starting with S = 9, only 17,000 assignments are required to find a solution. So again, that single additional fact (S = 9) cut down the number of assignments by more than 90%.
rabbott Posts: 1649	Posted 22:18 Oct 12, 2019 \| Correction. In the message above, I forgot that the propagator also solved for O, which it found to be 0. A search from right to left, with S=9 and O=0 requires fewer than 500 assignments to find a solution. The same search with the traditional variable ordering (SENDMORY) requires fewer than 2,000 assignments. So even though the propagator found values for only S and O, that vastly reduced the search space.

Author

Message

rabbott

Posts: 1649

Posted 21:28 Oct 12, 2019 |

When I ran all the columns through the propagator, it produced no additional results. So all we learned from the propagator, at least with respect to the problem variables, is that S must be 9.

Running the solver from right to left, with the Variables ordered as 'DEYNRO' a solution is found after 2058 assignments. If we add a starting assignment of S = 9 a solution is found in 1027 assignments, about half as many. So even though the propagator didn't solve the problem, it cut down the number of assignments by a factor of 2.

Furthermore, if we run the solver with the variables in the traditional order (SENDMORY) with propagation of all_different, nearly 250,000 assignments are required to find a solution. If we run exactly the same situation except starting with S = 9, only 17,000 assignments are required to find a solution. So again, that single additional fact (S = 9) cut down the number of assignments by more than 90%.

rabbott

Posts: 1649

Posted 22:18 Oct 12, 2019 |

Correction. In the message above, I forgot that the propagator also solved for O, which it found to be 0. A search from right to left, with S=9 and O=0 requires fewer than 500 assignments to find a solution. The same search with the traditional variable ordering (SENDMORY) requires fewer than 2,000 assignments. So even though the propagator found values for only S and O, that vastly reduced the search space.