Divisibility Puzzle

Yesterday a friend of mine gave me this puzzle to solve :

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number should satisfy the following requirements:

The number should be divisible by 9.

If the right-most digit is removed, the remaining number should be divisible by 8.

If the two right-most digits are removed, the remaining number should be divisible by 7.

If the three right-most digits are removed, the remaining number should be divisible by 6.

…

If the eight right-most digits are removed, the remaining number should be divisible by 1.

We sure can solve this using crazy mathematics, but I have a clever idea, let the computer solve it for us.

How about writing code to solve this .. FUN \m/

When you break down this problem , its basically which permutation of 123456789 satisfy the above conditions.

So All we have to do is loop through all the permutations and for every permutation check if it satisfies the above conditions.

I know its not ideal to go through all the n! permutations and find the number. But it WORKS and it gave me solution in seconds.

You can read about this puzzle here (Mathematical Approach):

http://math.ucsd.edu/~wgarner/personal/puzzles/div_puzzle_sol.htm
Here is my code :

    private void Permute(String str)
        {
            int length = str.Length;
            bool[] used = new bool[length];
            StringBuilder output = new StringBuilder();
            char[] input = str.ToCharArray();

            DoPermute(input, output, used, length, 0);
        }

        private void DoPermute(char[] input, StringBuilder output, bool[] used, int length, int level)
        {
            if (level == length)
            {
                if (CheckIfCorrect(output.ToString()))
                {
                    //Found the number
                }
                return;
            }

            for (int i = 0; i < length; ++i)
            {
                if (used[i]) continue;

                output.Append(input[i]);
                used[i] = true;
                DoPermute(input, output, used, length, level + 1);
                used[i] = false;
                output.Length = output.Length - 1;
            }
        }

        private bool CheckIfCorrect(String number)
        {
            int deletedDigits = 0;
            int divisor = 9;

            while (deletedDigits <= 7)
            {
                if (!IsDivisible(number.Substring(0, number.Length - deletedDigits++), divisor--))
                    return false;
            }

            return true; // Yes this is the number \m/
        }

        private bool IsDivisible(string number, int divisor)
        {
            return Convert.ToInt64(number) % divisor == 0;
        }

private void Permute(String str)

{

int length = str.Length;

bool[] used = new bool[length];

StringBuilder output = new StringBuilder();

char[] input = str.ToCharArray();

DoPermute(input, output, used, length, 0);

}

private void DoPermute(char[] input, StringBuilder output, bool[] used, int length, int level)

{

if (level == length)

{

if (CheckIfCorrect(output.ToString()))

{

//Found the number

}

return;

}

for (int i = 0; i < length; ++i)

{

if (used[i]) continue;

output.Append(input[i]);

used[i] = true;

DoPermute(input, output, used, length, level + 1);

used[i] = false;

output.Length = output.Length - 1;

}

private bool CheckIfCorrect(String number)

{

int deletedDigits = 0;

int divisor = 9;

while (deletedDigits <= 7)

{

if (!IsDivisible(number.Substring(0, number.Length - deletedDigits++), divisor--))

return false;

}

return true; // Yes this is the number \m/

}

private bool IsDivisible(string number, int divisor)

{

return Convert.ToInt64(number) % divisor == 0;

}

Recent Posts

Algotutor