[2015-11-04] Challenge #239 [Intermediate] A Zero-Sum Game of Threes : dailyprogrammer

[2015-11-04] Challenge #239 [Intermediate] A Zero-Sum Game of Threes : dailyprogrammer
Let's pursue Monday's Game of Threes further!
To make it more fun (and make it a 1-player instead of a 0-player game), let's change the rules a bit: You can now add any of [-2, -1, 1, 2] to reach a multiple of 3. This gives you two options at each step, instead of the original single option.
With this modified rule, find a Threes sequence to get to 1, with this extra condition: The sum of all the numbers that were added must equal 0. If there is no possible correct solution, print Impossible.

public static boolean solve(long num, long total)
{
    if (num < 1)
    {
        return false;
    }

    if (num == 1)
    {
        return (total == 0) ? true : false;
    }

    int mod = (int) (num % 3);
    switch (mod)
    {
        case 0:
            if (solve(num / 3, total))
            {
                output = (num + " 0 \n") + output;
                return true;
            }
            break;
        case 1:
            if (solve((num + 2) / 3, total + 2))
            {
                output = (num + " 2\n") + output;
                return true;
            }
            else if (solve((num - 1) / 3, total - 1))
            {
                output = (num + " -1\n") + output;
                return true;
            }
            break;
        case 2:
            if (solve((num + 1) / 3, total + 1))
            {
                output = (num + " 1\n") + output;
                return true;
            }
            else if (solve((num - 2) / 3, total))
            {
                output = (num + " -2\n") + output;
                return true;
            }
            break;
    }
    return false;
}
Python:
def solve(n, diff_sum=0):
    if n <= 1:
        if n == 1 and diff_sum == 0:
            yield (1,)
    else:
        r = n % 3
        if r == 0:
            variants = solve(n//3, diff_sum)
        else:
            d1, d2 = -r, 3-r
            variants = chain(solve((n+d1)//3, diff_sum+d1),
                             solve((n+d2)//3, diff_sum+d2))

        for solution in variants:
            yield (n,) + solution

def show(N):
    have_solution = False
    for solution in solve(N):
        have_solution = True
        for n, n_next in zip(solution, solution[1:]):
            print(n, n_next*3-n)
        print(1)
        print("-"*20)

    if not have_solution:
        print("Impossible")
Read full article from [2015-11-04] Challenge #239 [Intermediate] A Zero-Sum Game of Threes : dailyprogrammer