New levels: 1107 to 1206
New levels: 1107 to 1206
since Tron has reached 1106, i've added 100 more juicy levels for the world's solving delight! they use tails' generator, and go up to 2000x2000. if and after Tron beats those, i may call it quits and say that's the max. we'll see...
Most levels generated by tails' generator are structurally easy. 1132 seems to be tough, though. I know exactly were to start, but even after using two weeks of CPU time the best partial solution misses 101481 cells (The board is 1260x1260 cells large). No other level so far needed anywhere close this much time to solve. I have some ideas to improve my solver, but I need to invest some more time to tackle this.
A few details about my solver: It is 4,500 lines of C, about 1,000 are debug code (output of board statistics, printing the board with annotations, writing logs of calculations, consistency checks). The basic idea is to determine and remove infeasible moves, e.g. "the field at y,x will not be entered from the left side". To solve all the levels, I had to implement methods to reduce the percentage of fields, for which the solver cannot determine, which two sides are used, to about 0.3%. These methods include local patterns, recursive patterns and bounded brute force. Only after application of these pre-calculations I employ a simple recursive brute force search. Solving level 1206 (2000x2000) took 37 minutes.