2004/11/23

9個の?」の解法探索アルゴリズムのメモ。
以下の1〜6を1ターンとして、(1,1),(2,1)および(2,2)〜(9,8)までを走査する。

  1. ある方向に1進む。以下を満たす進路しか残っていなければ、次のターンに。

    • 枠外へは進めない

    • すでにラインがある場所へは進めない

    • 同じ場所から前に一度進んだことがある方向には進めない


  2. その場所から、1. で進んだ方向と90度異なるいずれかの方向に進む。以下を満たす進路しか残っていなければ、その反対方向に進む。それでも進路がなかったら、次のターンに。

    • 枠外へは進めない

    • すでにラインがある場所へは進めない

    • 同じ場所から前に一度進んだことがある方向には進めない


  3. その場所から、2. で進んだ方向と同じ方向に進む。以下を満たす進路しか残っていなければ、2. に戻る。

    • 枠外へは進めない

    • すでにラインがある場所へは進めない


  4. その場所から、1. で進んだ方向と逆の方向に進む。以下を満たす進路しか残っていなければ、2. に戻る。

    • 枠外へは進めない

    • すでにラインがある場所へは進めない


  5. その場所から、2. で進んだ方向と同じ方向に進む。以下を満たす進路しか残っていなければ、2. に戻る。

    • 枠外へは進めない

    • すでにラインがある場所へは進めない


  6. その場所から、2. で進んだ方向と同じ方向に2つ進む。以下を満たす進路しか残っていなければ、2. に戻る。

    • 枠外へは進めない

    • すでにラインがある場所へは進めない。ただし、1つ先が埋まっていても、2つ先が空いていれば進める


No comments :