Problem 244

[dnovatchev]

The definition of the problem includes the following phraze:

"Now, starting from configuration (S), find all shortest ways to reach configuration (T)."

It is not clear what exactly is meant by "all shortest ways". I have found at least two possible interpretations:


1. From all solutions select only those, whose length is N, where N is the minimum of the lengths of all solutions.

2. Use all different solution paths, such that each intermediate position on the path is visited exactly once (eliminate paths containing loops)

Using definition 1. above I have implemented a solution, [snip], but its checksum is not the expected answer.

Could someone, please, provide the exact correct interpretation of the quoted phraze?

Thanks,

Dimitre

[dnovatchev]

I have solved the problem -- it was elsewhere: I was check-summing the reverse of the solution.

[LarryC]

I love singular form.

[quilan]

Well, you've already finished the problem so you know the solution, but if that sort of wording comes up in the future the intent was, I'm sure, the first; all the checksums of solutions of length N (where N is the minimum length).

[harryh]

A few words were snipped from the first post, so as not to spoil the problem for others.

[elr]

i kinda got stuck here,i have found a solution which appear to be minimal with path length of 47(or 46)

however whats make the situation wierd is that if i eliminate cycles and already seen boards i find only
one solution,and if i wont there are just too many solutions and the problem cant be solved in 1 minute

[quilan]

i kinda got stuck here,i have found a solution which appear to be minimal with path length of 47(or 46)

however whats make the situation wierd is that if i eliminate cycles and already seen boards i find only
one solution,and if i wont there are just too many solutions and the problem cant be solved in 1 minute

Well, if you think of it, a cycle of more than one node can NEVER provide the minimal path.

Ex:

A -> [B -> C -> D -> B] -> E
will always be longer than
A -> B -> E

So yeah, pro-tip: don't allow cycles.

[elr]

well what i tried so far is :
my algorithm is iterative deep first search (that increase deep per iteration,so i am sure what i got is the minimal
path)

1)if i disallow cycles + disallow exploring states that already been seen and does not lead to a solution i find only 1
solution

2)if i allow to explore states that already seen but they not a cycle the algorithm can run for hours without completing
(its find many solutions,but it doesnt stop (tested for 7 hours))

if i go with way 1 i get one solution only which is not the answer ,if i go with way 2 there is no way i finish it in 1 minute

[daniel.is.fischer]

I would recommend a breadth-first search for finding shortest paths.

[elr]

BFS would find the shortest path for sure however its would require alot of memory
while as far as i know depth limited search where the limit increase per failed iteration
(so called iterative deeping search) would perform the same as BFS however its would
require much less memory (since no OPEN/CLOSE lists are managed)

[daniel.is.fischer]

BFS would find the shortest path for sure however it would require a lot of memory

Not here. There aren't many states.

while as far as i know depth limited search where the limit increase per failed iteration
(so called iterative deeping search) would perform the same as BFS

I think the performance would be significantly worse. If your IDDFS fails for limit n, you have to re-trace all those paths for limit n+1 and so on.
Since we don't have a tree here but a graph with cycles, that could (and I think here it would) be a lot of repeated work, you can reach many states by several paths of (approximately) the same length (e.g. LU and UL; UU, LURU, LUUR, and ULUR), the children of such states would be visited multiple times in each iteration.