puzzle sample from NP-completeness proof

puzzle sample from NP-completeness proof

I entered this puzzle sample form here:http://www2.stetson.edu/~efriedma/papers/pearl/pearl.htmlI think it is entered correctly, and it is very challenging due to size and locally-underconstrained nature. Care to give it a try?

AdjuntoTamaño
Descargar npcomplete.txt3.13 KB
publicaciones de 7 / 0 nuevos
Último envío
Para obtener más información sobre las optimizaciones del compilador, consulte el aviso sobre la optimización.

Thank you
Here is my result.

1 5

RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUU

RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUU

RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUU

RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRDRR

RDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRR

RDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRR

RDLLLDRRRDLLLDRRRDLLLDRRRDLLLDDDLUUULDDD

LUUULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDD

LUUULURRULUURRRUUULLLURRRULLLURRRUUURDDD

RUUURDDDRUUURDDDRRRDLLLDRRRDLLLDRRRDLLLD

DDLUUULDDDLUUULDDDLDRRRRRRRRRUUUUUUUUUUL

LUUUULLULURRRRRULLLLLLDDDLUUULDDDLUUULDD

DLUUULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDD

DLUUULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDD

DLUUULDDDLUUULDDDLUUULLLURRRULLLURRRULLL

URRRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUUR

DDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUUR

DDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUUR

DDDRUUURDDDRRRDLLLDRRRDLLLDRRRRUUUUULLLU

RRRUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL

LLLLDDDDDDDDDDRRDDRDLLLDDDDDDDDDDRRRDDDR

RRRRRRRRRRUUULDDLLLLLUUULDDDLUUULDDDLUUU

LLLURRRULLLURRRULLLURRRUUURDDDRUUURDDDRU

UURDDDRRRDLLLDRRRDLLLDRRRRUUUUUUURURRRRR

RRRRDRURDRDDDDDDDLLLLURRRULLLURRRULLLUUU

LDDDLUUULDDDLUUULDDDLLLDRRRDLLLDRRRDLLLD

RRRDDDRUUURDDDRUUURRRDRRURDDDLLDRDLDDDLU

UULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDDLU

UULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDDLU

UULDDDLUUULDDDLUUULLLURRRULLLURRRULLLURR

RULLLURRRULLLURRRULLLURRRULLLURRRULLLURR

RULLLURRRULLLURRRULLLURRRULLLURRRULLLURR

RULLLURRRURUUU

Maybe we can develop a puzzle generator to generate more puzzles like this one.

Nice! My solver could not reach a solution in reasonable time on a 4-core. Can you tell me how long this took and on what kind of computer?

I improved my solver today, and the current result is
1 5
RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUU
RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUU
RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRUUU
RDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDRDRR
RDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRR
RDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRRRDLLLDRR
RDLLLDRRRDLLLDRRRDLLLDRRRDLLLDDDLUUULDDD
LUUULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDD
LUUULUUUURDRRRRUURDDDRUUURDDDRUUURRRULLL
URRRULLLURRRULLLUUULDDDLUUULDDDLUUULDDDL
LLDRRRDLLLDRRRDLLLLUUUUULURRRRULURRRRRRR
URDRRURULLLLLURRRRRULLLLLLDDDLUUULDDDLUU
ULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDDLUU
ULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDDLUU
ULDDDLUUULDDDLUUULDDDLUUULLLURRRULLLURRR
ULLLURRRUUURDDDRUUURDDDRUUURDDDRUUURDDDR
UUURDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDR
UUURDDDRUUURDDDRUUURDDDRUUURDDDRUUURDDDR
UUURDDDRUUURDDDRRRDLLLDRRRDLLLDRRRRUUUUU
LLLURRRULLLULLLLLLLLLLLLLLLLLLLLLLLLLLLL
LLLLLDDDLLLDDDDDDDRDRURDDLLLDDDRUURRRRRR
RRRDRRURDRRDDLULLLLDRRRDDDDDLLLLURRRULLL
URRRULLLUUULDDDLUUULDDDLUUULDDDLLLDRRRDL
LLDRRRDLLLDRRRDDDRUUURDDDRUUURDDRRRRRRDR
RDRRRRRUUUULDDDLUUULDDDLUUULLLURRRULLLUR
RRULLLURRRUUURDDDRUUURDDDRUUURDDDRRRDLLL
DRRRDLLLDDRDDDDRRDLDDDLUUULDDDLUUULDDDLU
UULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDDLU
UULDDDLUUULDDDLUUULDDDLUUULDDDLUUULDDDLU
UULLLURRRULLLURRRULLLURRRULLLURRRULLLURR
RULLLURRRULLLURRRULLLURRRULLLURRRULLLURR
RULLLURRRULLLURRRULLLURRRULLLURRRURUUU

It is reached in only several seconds on a 4-core PC. Maybe we used very different ideas. The very wide and nearly empty puzzle is most time consuming for my solver (although easy to human).

Yes my solver is probably very different than anyone else, because I wanted to develop some different ideas. It uses a "constraint processor" over the possible line shapes, combined with a recursive solution seeker. The constraintprocessor sometimes solves boards without any search at all, however it makes for a much slower search recursion than simple move-explorer. I hope we get to see all writeup papers when the contest is finished.

I used heuristic and random function.
My solver cannot solve this problem now :-(
The old version can solve it, but it is only because of lucky......

I can solve this one.....again......... finally......

Deje un comentario

Por favor inicie sesión para agregar un comentario. ¿No es socio? Únase ya