// Sample backtracking program.  The user is prompted for an (x, y) position
// and the program uses backtracking to find all possible paths to that
// location using moves of N, NE, and E.
//
// Please note that the use of a String parameter in this program is NOT an
// example to emulate for the programming assignment.  This can be highly
// inefficient for a large backtracking problem that includes significant
// exploration.

import java.util.*;

public class GoNorthEast {
    public static void main(String[] args) {
        giveIntro();
        Scanner console = new Scanner(System.in);
        System.out.print("Target x and y location? ");
        int x = console.nextInt();
        int y = console.nextInt();
        System.out.println();
        solve(x, y);
    }

    /// post: explains program to the user
    public static void giveIntro() {
        System.out.println("This program finds all paths from (0, 0) to");
        System.out.println("a given location making moves of N, NE, or E.");
        System.out.println();
    }

    // pre: path represents a series of moves form (0, 0), to (currX, currY)
    // post: prints all solutions for moving from (currX, currY) to (x, y)
    public static void explore(int currX, int currY, int x, int y,
                               String path) {
        if (currX == x && currY == y) {
            System.out.println(path);
        } else if (currX <= x && currY <= y) {
            explore(currX, currY + 1, x, y, path + " N");
            explore(currX + 1, currY + 1, x, y, path + " NE");
            explore(currX + 1, currY, x, y, path + " E");
        }
    }

    // post: Finds and prints all solutions for traveling from (0, 0) to (x, y)
    public static void solve(int x, int y) {
        System.out.println("solutions:");
        explore(0, 0, x, y, "moves:");
    }
}