IBM Ponder This, April 2019

IBM Ponder This is awesome.

For 20 years they have been posting a math/coding/esoteric challenge once a month, and when you nail the answer, you get your name posted on a web site. Wow, name posted on a web site!!! 😊

IBM Ponder This this month (April 2019) is the following:

“Find nine different prime numbers that can be placed in a 3x3 square in such a way that the average of every row, column, and diagonal is also a prime number.”

Here are the steps that I took to solving this problem, and I’ll explain each one of them:

1. Sieve
2. Cache
3. Backtrack
4. Prune
5. Trial-N-Error

Sieve: first apply the sieve of Eratosthenes to produce as many primes as you want, in N^2 time and N space

Cache: cache the primes, you don't want to be performing the same test over and over again

Backtrack: backtracking is a technique commonly used in Algorithms to perform a depth-first-search in order to find a solution

Prune: you need to prune the backtracking by cutting short the search space as soon as you don't find a possible path. I use a helper class "PrimeLine" to keep track of the calculation for each line and as such prune the search space whenever I hit a line that is not a potential candidate for the solution

Trial-N-Error: Even with the above, we're talking about a potentially large search space, in the order of N^9, where N is the max number of primes. Assume that N = 10^4, this is a massive search area: 10^36, or 2^288. Big number (to give you an idea, the number of atoms in the universe is about 2^640). Hence at this point you need to think about some trial and error approaches. When I ran the code for the first time, it did not work since I was going from the smaller primes to the larger ones. I decided to conjecture that the solution would start with bigger primes first. So the backtrack goes in descending order from the large primes to the small ones. It worked.

Code is below, cheers, ACC.

using System;

using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Numerics;

namespace IBMPonderThisApril2019
{
 class Program
 {
  public static int[] primesCache = null;
  public static Hashtable primesCacheHT = new Hashtable();
  static void Main(string[] args)
  {
   //Prime the cache
   PrimesSieve();
   Console.WriteLine("Number of Primes: {0}", primesCache.Length);

   PrimeLine[] rows = new PrimeLine[3];
   for (int i = 0; i < rows.Length; i++)
   {
    rows[i] = new PrimeLine();
   }
   PrimeLine[] cols = new PrimeLine[3];
   for (int i = 0; i < cols.Length; i++)
   {
    cols[i] = new PrimeLine();
   }
   PrimeLine diag1 = new PrimeLine();
   PrimeLine diag2 = new PrimeLine();

   int numberOfSolutions = 0;
   int MAXSOLUTIONS = 100;
   Process(0, primesCache.Length - 1, new int[9], rows, cols, diag1, diag2, ref numberOfSolutions, MAXSOLUTIONS);
  }

  public static void PrimesSieve()
  {
   int MAXSIEVE = 10000;
   bool[] sieve = new bool[MAXSIEVE];

   sieve[0] = sieve[1] = true;
   for (long i = 2; i < MAXSIEVE; i++)
   {
    for (long j = i; i * j < MAXSIEVE; j++)
    {
     sieve[i * j] = true;
    }
   }

   int countCache = 0;
   for (int i = 0; i < MAXSIEVE; i++)
   {
    if (!sieve[i])
    {
     countCache++;
     primesCacheHT.Add(i, true);
    }
   }

   primesCache = new int[countCache];
   int index = 0;
   for (int i = 0; i < MAXSIEVE; i++)
   {
    if (!sieve[i])
    {
     primesCache[index++] = i;
    }
   }
  }

  public static bool Process(int index,
           int primesCacheIndex,
           int[] primes,
           PrimeLine[] rows,
           PrimeLine[] cols,
           PrimeLine diag1,
           PrimeLine diag2,
           ref int numberOfSolutions,
           int maxSolutions)
  {
   if (index >= primes.Length)
   {
    numberOfSolutions++;

    Console.WriteLine("Solution {0}:", numberOfSolutions);
    for (int i = 0; i < primes.Length; i++)
    {
     Console.Write("{0} ", primes[i]);
     if ((i + 1) % 3 == 0)
     {
      Console.WriteLine();
     }
    }
    Console.WriteLine();

    return numberOfSolutions >= maxSolutions;
   }

   int r = index / 3;
   int c = index % 3;

   for (int candidateIndex = primesCacheIndex; candidateIndex >= 0; candidateIndex--)
   {
    int candidate = primesCache[candidateIndex];

    //Rows
    rows[r].Add(candidate);
    if (rows[r].count == 3 && !rows[r].IsAvgPrime())
    {
     rows[r].Remove(candidate);
     continue;
    }
    //Cols
    cols[c].Add(candidate);
    if (cols[c].count == 3 && !cols[c].IsAvgPrime())
    {
     //Remember to remove the row
     rows[r].Remove(candidate);

     cols[c].Remove(candidate);
     continue;
    }
    //Diag 1
    if (r - c == 0)
    {
     diag1.Add(candidate);
     if (diag1.count == 3 && !diag1.IsAvgPrime())
     {
      //Remember to remove the row and col
      rows[r].Remove(candidate);
      cols[c].Remove(candidate);

      diag1.Remove(candidate);
      continue;
     }
    }
    //Diag 2
    if (r + c == 2)
    {
     diag2.Add(candidate);
     if (diag2.count == 3 && !diag2.IsAvgPrime())
     {
      //Remember to remove the row, col and diag1
      rows[r].Remove(candidate);
      cols[c].Remove(candidate);
      if (r - c == 0)
      {
       diag1.Remove(candidate);
      }

      diag2.Remove(candidate);
      continue;
     }
    }

    primes[index] = candidate;
    if (Process(index + 1, candidateIndex - 1, primes, rows, cols, diag1, diag2, ref numberOfSolutions, maxSolutions)) return true;

    //Cleanup
    rows[r].Remove(candidate);
    cols[c].Remove(candidate);
    if (r - c == 0)
    {
     diag1.Remove(candidate);
    }
    if (r + c == 2)
    {
     diag2.Remove(candidate);
    }
   }

   return false;
  }
 }

 class PrimeLine
 {
  public long[] numbers = new long[3];
  public long sum = 0;
  public int count = 0;

  public void Add(long value)
  {
   if (count < 3)
   {
    numbers[count] = value;
    count++;
    sum += value;
   }
  }

  public void Remove(long value)
  {
   sum -= value;
   count--;
  }

  public bool IsAvgPrime()
  {
   if (sum % 3 == 0 && Program.primesCacheHT.ContainsKey((int)(sum / 3)))
   {
    return true;
   }
   return false;
  }
 }
}