> test 80 has 11881161 solutions! Your algorithm generate all of them in just 3 seconds!?

I was wrong. The algorithm (backtracking) generates all the (15741649, "all the" contains a large amount of convention, because of branch and bounding) solutions for test80 in ~72 seconds. First solution found in 3.223853s for standard random seed and 0.563442s for search in lexicographical order. But my heuristics finds solution for test80 in 0.000041s and it goes before the backtracking, so test80 is not the problem at all.

test67 (first solution): 0.290 (lexicographical order)
test67 (complete enumeration, 1 solution): 0.373 (lexicographical order)
test70 (first solution): 0.179 (lexicographical order)
test70 (complete enumeration, 2 solutions): 0.187 (lexicographical order)

Number of solutions for each separate line for test80 (lines sorted):
109
115
209
3981
4442
10091
38691
0 // this one is not even calculated, because not needed

Hardware: Intel Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz (3.90GHz Trubo Boost per single core, vs 2.40GHz (same arch) on OJ system). Specially bought for this problem).

BTW test5 is a tough nut to crack for the algorithm.

Edited by author 26.10.2020 22:38

 > solve it by changing the heuristic parameter (every 3-5 works)

Your heuristics is highly effective, if I understand correctly. Is it true, that you can select a parameter ("seed") for the heuristics by just 3-5 tries? For each hard test case. Then you write `for (int seed : {seed_test70, seed_test67, seed_test80, seed_test69, seed_test77, seed_test79}) heuristics(seed);` and even for test79 (e.g., here "last" one) all iterations run in less then 1 second? I.e. less then a small number of milliseconds per every seed value, you collect?

Edited by author 26.10.2020 23:46

Edited by author 26.10.2020 23:45

nothing like this, my solution is common for all test and direct randomization is minimal. Actually I have kind of deterministic one (stuck on test#67 and can't pass #82 too, but not critical) and ideas for improving it, but don't have motivation and time to do this.
I'm not going to share an idea or give hints.

Спасибо и на этом.

Do you use one algorithm or you mix them ?

Edited by author 29.10.2020 11:56

I use two algorithms. Heuristics and branch and bounded brute force. They called in the next order: 1 try of heuristics (I think 90% of tests are covered by this first one) (it take about 1-2ms), then highly clipped b&b brute force (I think it get about a couple of hundreds of milliseconds in worst case - on test 77 or 79 it fails and made complete (unsuccessful) enumeration through all clipped DoD), then infinite number of tries of the same heuristics (it get about first tens or mb one hundred of milliseconds average, but for some good seed (in fact I enumerate first 20 of them - two was good enough) it get mb less than ten milliseconds or so).

A vast majority of test are covered by heuristics. It works well on those tests, that have big actual number of unique solutions. For these brute force produces too big number of solutions, that results in MLE. Heuristics is simple and have regular structure. Actually it can find solutions for any test, but for some of them (test67) the probability per try is too low to reliable fit in 1 seconds of time limit.
On the contrary brute force is highly effective on those tests, which have one or two unique solutions (or maybe thousands -- don't even know, because I have only test67 and test70, which have such a property). Branch and bounding works highly effective on these.

The only "cheating" to get solution for me was to find right seed for test79 (I don't know its structure and I want to collect it maybe). Don't even know how rare it -- I find it from the first try. Another cheating -- is to optimize. I made holes in DoD of brute force. So enumeration was reduced a lot for minor number of tests. Optimization is not valuable at all from algorithmic point of view. It is a bullshit full of magic numbers.

My backtracking algorithm runs in 4.0 sec on Java and 8.0 sec on C++ for test 78, 0.178 sec on Java and
0.165 sec on C++ for test 67.

I can conclude, that your backtracking algorithm is (exactly) as optimal as mine. I bet you use something like `std::vector<std::bitset<99>>` to store solutions per every row and something like `std::unordered_map<std::bitset<9>, std::unordered_set<std::bitset<99>>>` for branch and bounding, isn't it?

Yes, you are right, but I use my bit set implementation. I have found another constraint but I don't know for now how to implement optimal!

What is the constraint? Is it a secret for now?

It's no secret, but it won't be fair to post it here

OK, I think I'll come up with one too. Knowing that there is something besides `std::unordered_map<std::bitset<9>, std::unordered_set<std::bitset<99>>>` is enough.

Edited by author 29.10.2020 18:39

 > I use my bit set implementation

Do you use _bit_scan_forward/_bit_scan_reverse when recover solution? Can it be an improvement over std::bitset?

Yes, It can, but I don't think it will improve more than 0.1 second!

Edited by author 31.10.2020 12:56

It is not critic recovering and saving solution!

Anyways it is interesting to implement next-bit-set-iterator.

Do you use parallel programing ?

No. Because it have no sense. User time of all the threads are summed up.

Edited by author 20.11.2020 22:00