Need some hard examples

Need some hard examples

Does anyone have some hard (long-running) examples? I have a collection but only one seems to take any appreciable time. Also have any of you played with under-constrained puzzles (lots of wide open spaces), and if so have you need to develop any special heuristics to avoid an extensive search in the vast empty spaces? What about dead-end detection (you've closed off a section of the puzzle and it is thus unsolvable until you backtrack, assuming you have a search-tree-like algorithm)? I've attached a 15x15 that is reasonably hard, but still not enough to take a long time.

AttachmentSize
Download hard_time.on.your.hands.txt260 bytes
17 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

Here is my result for this problem.

1 3
RDDRRRULLURRRDDRRUURDRRRDDDRDDDDLLDDRURD
DDDDLUUULDDDLULDLUURRUUUUURRUULLLDDLDDRD
LLUUUURUURRRUULLDLLLDDDDLLDRDDDLLUULLDDD
RRRDRRUURDDDLLLLLULLUULUUURRRRUURRUUULDD
LLDDLLLUUUUURDDDDRUURRULLUUU

This is really more difficult than other problems here.

Here is the result

1 10
RRRRDRRDDRRUUURDDRRRRDLDLDDDLDRRRDLDDDRU
URRRUULURURULULURRRRULLURRRDDDLLDRDRDLLD
RDDRDLLDDRRDDLLLLURULLDLDDDLLDDRRDDDRRDD
LLDLUUULLLLDDDDLLLLLUURRURURULULUUURRUUU
LDDLLDDDDLULLLLDDRRURDRDLLLDDDLULUULDDLL
LURURULLUUUULLLULUURRDDRRRULLUULURULURRR
DLDRRUURULLUULLLULULUUURRDDDRURRDDRURURU
LLLLLURRRRRRRDLDDDRDDRRRULLURRRURDRURDDR
UUULLLLLDLULUUULLU

I solved 2 (maybe because of lucky?) but never 2x2.

1 5
RRDDRRDDDRRDDDDRUUURDDRRDDDRRURRDDRUUURR
ULLLLLULLLURUURRULLURRULLLDDLLDLLUURRULL
LURRRRRRRRRDRDLDRRUUURRRRDRDDRRRRDRUULLL
UURDRRRDDRDLDRRDDDDLUUULLULLDDRRRDDDRRDL
DLLDRDLDLLLULDLUURRRDRUULLUUURRDLDRRUUUL
LLLDDLLUUUULLURRRDDRRUUULLLLLURRULLLDDDD
LUULLDRDLDRRRRRDDDLLDRRRDDDLLLDLLLLLLLUR
ULUUUULDLLDRRDDDDLLLULDLUURRRDRUULLUUUUU
LLUUUULLULLDDRRRDDLLULDDRRRDLDRRURDDLLLL
LDRRRDDLDLLULLLUUUURDDDRUUURRULLULLURRUU
LLURRUURRU

I have not been able to solve it yet either, so perhaps it has no solution.

Using the solution proposed by for 2 above, I guess, a solution for 2x2 is not hard to construct, visually (since the nature of the problem is known). Programmatically, it's a different story...

Nice! How long did it take your program to arrive at the solution?

Quoting john_e_lilley
Nice! How long did it take your program to arrive at the solution?

I used GIMP to come up with this solution... ;)

I picked the output from #5 duplicated it, and connected both halves to produce this output just to show that a result is possible. My program struggles even with the base version of this problem... :(

Looking forward to reading other write-ups once the problem is done.

Nice! You could submit GIMP as your proposed solution, with the condition that at least two judges attempt to solve the puzzle at the same time, thus fullfilling the multithreaded requirement!

I agree, I am really looking forward to reading everyone elses writeups. This has been some of the most fun programming I have ever done :)

Your great, My program has to run more than 10 min to get answer! -_-

Aw, I was hoping someone had this monster program that could solve anything ;-)

33 33

I took about 30 seconds

写字楼里写字间,写字间里程序员 程序人员写程序,又拿程序换酒钱 酒醒只在网上坐,酒醉还来网下眠 酒醉酒醒日复日,网上网下年复年

You solved 2x2 ?
good job !
btw, how many cpu cores did you use?

Quoting mdma
Nice! You could submit GIMP as your proposed solution, with the condition that at least two judges attempt to solve the puzzle at the same time, thus fullfilling the multithreaded requirement!

I have very little confidence in my program. If I can't improve it further, I may have to do exactly that... :)

Core 2 Duo T6570
16 X 334 s
33 X 33 30 s

写字楼里写字间,写字间里程序员 程序人员写程序,又拿程序换酒钱 酒醒只在网上坐,酒醉还来网下眠 酒醉酒醒日复日,网上网下年复年

Ret.txt

My results:

写字楼里写字间,写字间里程序员 程序人员写程序,又拿程序换酒钱 酒醒只在网上坐,酒醉还来网下眠 酒醉酒醒日复日,网上网下年复年

Leave a Comment

Please sign in to add a comment. Not a member? Join today