Skip to content

Instantly share code, notes, and snippets.

@mrmx

mrmx/Chess-Knight-Moves

Last active October 7, 2016 22:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mrmx/08db9b21c41645a42f28f393629ed2bc to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mrmx/08db9b21c41645a42f28f393629ed2bc to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. mrmx revised this gist Oct 7, 2016. 1 changed file with 0 additions and 8 deletions.
    8 changes: 0 additions & 8 deletions Chess-Knight-Moves
    View file
    Original file line number Diff line number Diff line change
    @@ -62,14 +62,6 @@ public class KnightRider {
    this.y = y;
    }

    public int getX() {
    return x;
    }

    public int getY() {
    return y;
    }

    int dist(int a, int b) {
    return (int) Math.hypot(a - x, b - y);
    }
  2. mrmx revised this gist Oct 7, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Chess-Knight-Moves
    View file
    Original file line number Diff line number Diff line change
    @@ -49,7 +49,7 @@ public class KnightRider {
    return best.get(0);
    }

    static class Knight {
    final static class Knight {

    int x, y;

  3. mrmx revised this gist Oct 7, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Chess-Knight-Moves
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,7 @@ import java.util.List;

    /**
    * Compute the minimum knight movements from (0,0) -> (A,B)

    *
    * @author mrmx
    */
    public class KnightRider {
  4. mrmx created this gist Oct 7, 2016.
    118 changes: 118 additions & 0 deletions Chess-Knight-Moves
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,118 @@
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;

    /**
    * Compute the minimum knight movements from (0,0) -> (A,B)

    * @author mrmx
    */
    public class KnightRider {

    public static void main(String[] args) {
    for (int i = 1; i <= 10; i++) {
    for (int j = 1; j <= 10; j++) {
    System.out.println("##########################################");
    System.out.println("Moves:(" + i + "," + j + "):");
    System.out.println(solution(i, j));
    }
    }
    //System.out.println("Solution:" + solution(4, 5));
    }

    private static int solution(int A, int B) {
    Knight k = new Knight();
    if (k.dist(A, B) >= 100000000d) {
    return -2;
    }
    return move(k, A, B, 0);
    }

    private static int move(Knight k, int A, int B, int moves) {
    if (k.goal(A, B)) {
    return moves;
    }
    if (k.dist(A, B) < 8 && moves > 8) {
    return moves;
    }
    List<Knight> movements = k.getMovements(A, B);
    moves++;
    //System.out.println("Best:" + movements + " moves " + moves);
    List<Integer> best = new LinkedList<>();
    for (Knight path : movements) {
    if (path.goal(A, B)) {
    return moves;
    }
    best.add(move(path, A, B, moves));
    }
    Collections.sort(best);
    return best.get(0);
    }

    static class Knight {

    int x, y;

    public Knight() {
    this(0, 0);
    }

    public Knight(int x, int y) {
    this.x = x;
    this.y = y;
    }

    public int getX() {
    return x;
    }

    public int getY() {
    return y;
    }

    int dist(int a, int b) {
    return (int) Math.hypot(a - x, b - y);
    }

    boolean goal(int a, int b) {
    return x == a && y == b;
    }

    List<Knight> getMovements(int a, int b) {
    List<Knight> movements = getMovements();
    Collections.sort(movements, (Knight o1, Knight o2) -> o1.dist(a, b) - o2.dist(a, b));
    return movements.size() > 3 ? movements.subList(0, 3) : movements.subList(0, 2);
    }

    List<Knight> getMovements() {
    List<Knight> moves = new LinkedList<>();
    moves.add(new Knight(x + 2, y + 1));
    moves.add(new Knight(x + 1, y + 2));
    if (y - 1 >= 0) {
    moves.add(new Knight(x + 2, y - 1));
    if (x - 2 >= 0) {
    moves.add(new Knight(x - 2, y - 1));
    moves.add(new Knight(x - 2, y + 1));
    }
    }
    if (y - 2 >= 0) {
    moves.add(new Knight(x + 1, y - 2));
    if (x - 1 >= 0) {
    moves.add(new Knight(x - 1, y - 2));
    }
    }
    if (x - 1 >= 0) {
    moves.add(new Knight(x - 1, y + 2));
    }

    return moves;
    }

    @Override
    public String toString() {
    return "(" + x + "," + y + ")";
    }

    }

    }