Author: Stan Eisenstat
Subject: Re: [Cs223] Multiple Solutions
Date: Friday, 17 Apr 2020, 07:57:04

    > Message Posted By: Unknown
    ...
    > When I run
    >
    > ./Nine20 2 5 100 123456789- -123456789
    >
    > I get a solution that uses 32 steps. However, the staff solution prints a
    > different 32-step solution. This is definitely possible in general
    > considering there can be more than one way to move from one pos to another
    > using the same number of steps.
    >
    > Technically, both are correct given the specs right? I think it might be
    > an issue of not chaining equal keys in order of testing for equality with
    > GOAL during the "for each reachable position" step... but then again,
    > aren't there potential variations in the order in which we might test the
    > list of reachable positions?

As I posted earlier:

  Date: 14 Apr 2020 19:26:35 -0400 (Tue)
  Subject: Re: [Cs223] Path from initial to goal is unique?
   
      > Message Posted By: Unknown
      >
      > Is it possible for there to be multiple shortest paths from initial to
      > goal?  (different intermediate steps, but same # of steps taken to get
      > there) I'm assuming so, since the order in which the new positions are
      > processed depends on the order in which they're computed.
   
  Yes, for all but the simplest instances there will be
  multiple shortest paths, each with the same number of
  moves.  That is why most of the tests use "wc -l" to
  count the number of moves rather than display them.  The
  alternative is a "verify" program that checks that a
  sequence of moves is valid.
   
--Stan-