3 ms·
http://www.ulb.ac.be/di/algo/secollet/papers/crs06.pdf http://www.ulb.ac.be/di/algo/secollet/papers/crs06.pdf claims a 6x6 board that requires 93 moves. That c
by Someone 8y ago
http://www.ulb.ac.be/di/algo/secollet/papers/crs06.pdf http://www.ulb.ac.be/di/algo/secollet/papers/crs06.pdf claims a 6x6 board that requires 93 moves.
That could be a matter of counting moves differently (if you move a car two places, is that one or two moves?), but I think that’s unlikely, as it would require about forty such multi-step moves.
So, who’s wrong? You, that paper, or me?
- fogleman 8y agoMentioned this in the Prior Art section and another comment here, but his "moves" are single-square steps. Running my solve utility on his hardest puzzle yields: $ go run cmd/solve/main.go BBBCDEFGGCDEF.AADEHHI....JI.KK.JLLMM {true [A-1 C+2 B+1 E+1 F-1 A-1 I-1 K-2 D+2 B+2 G+2 I-2 A+1 H+1 F+4 A-1 H-1 I+2 B-2 E-1 G-3 C-1 D-2 I-1 H+4 F-1 J-1 K+2 L-2 C+3 I+3 A+2 G+2 F-3 H-2 D+1 B+1 J-3 A-2 H-2 C-2 I-2 K-4 C+1 I+1 M-2 D+2 E+3 A+4] 49 93 49 12266 1494475} 93 steps, but just 49 moves. That puzzle is on line 13 of my database: 49 BBBKLMHCCKLMH.AALMDDJ....IJEE..IFFGG 24132 https://www.michaelfogleman.com/static/rush/rush1000.txt https://www.michaelfogleman.com/static/rush/rush1000.txt
- flashman 8y agoFWIW I think your approach to counting moves is more logical. We're more interested in understanding how many intermediate states a puzzle has between its initial state and solution. Whether you move a piece by one square or three is not particularly interesting.