Five Digit Primes in a 5x5 Grid

Question

|---|---|---|---|---|
| 1 | 1 | 3 | 5 | 1 |
|---|---|---|---|---|
| 3 | 3 | 2 | 0 | 3 |
|---|---|---|---|---|
| 3 | 0 | 3 | 2 | 3 |
|---|---|---|---|---|
| 1 | 4 | 0 | 3 | 3 |
|---|---|---|---|---|
| 3 | 3 | 3 | 1 | 1 |
|---|---|---|---|---| 

(Figure 1)

Figure 1 shows a square. Each row, each column and the two diagonals can be read as a five digit prime number. The rows are read from left to right. The columns are read from top to bottom. Both diagonals are read from left to right. Using the data in the INPUT.TXT file, write a program that constructs such squares.

The prime numbers must have the same digit sum (11 in the example). The digit in the top left-hand corner of the square is pre-determined (1 in the example).

A prime number may be used more than once in the same square.

If there are several solutions, all must be presented. A five digit prime number cannot begin with zeros, ie 00003 is NOT a five digit prime number.

Input Data

11 1

I am attempting to do a question from IOI'94 Competition - Problem 3 - The Primes.

I have built most of the helper functions...

1. Used Sieve of Eratosthenes to generate 5 digit primes (between 9999 & 100000)
2. Built a function to compute the sum of digits (12345 = 1+2+3+4+5 = 15)
3. Built a function to check an array if the sum of digits are the same throughout
4. Built a function to check if a number startsWith a specified digit (startWith(12345,1) return true)

Question: The issue is I don't know how to full the array or use the backtracking capability to keep checking :(. Can anyone help me please? How to I go about filling the 2D array so that it contains values from the prime table and the sum is correct on all angle?

*NB: The Sieve of Eratosthenes method that generates the 5 digit prime, also as the capability of filtering values that starts with X and values sum up to M *

Complete question : http://olympiads.win.tue.nl/ioi/ioi94/contest/day1prb3/problem.html

Prospective order of adding values, just don't know how to do it :(.

 1  2  3  4  5
 6 13 14 12 15
 7 16 11 18 19
 8 10 20 22 23
 9 17 21 24 25

Answer 1

From what you write I assume that you have a list of 5 digit prime numbers already. Filter the list so that it contains only the primes with the right sum of digits.

You'll need a function valid to check for a valid square, given 1 to 5 numbers that go in the columns. (It is clear that the column numbers determine the other rows and diagonals. So, if the 3rd digit of the 1st column is a 7, but there is no prime that starts with 7, we know that we can't use this prime in the first column. Without looking at all the other numbers, this will prune your search tree early.)

You need another function to get sets of all valid prime numbers that have a certain digit at position n (1..5). Perhaps you want to precalculate this and store it in some tree or array.

The major work is done in valid, which must check whether there exist prime numbers for the rows and diagonals with the digits in the positions determined so far by the primes in the columns.

Then the list of solutions is:

[ (c1, c2, c3, c4, c5) | c1 <- primes, valid [c1], 
      c2 <- primes, valid [c1,c2],
      c3 <- primes, valid [c1,c2,c3],
      c4 <- primes, valid [c1,c2,c3,c4],
      c5 <- primes, valid [c1,c2,c3,c4,c5] ]

or, put imperatively:

 for each c1 in primes
    if valid(c1) then foreach c2 in primes
        if valid(c1,c2) then foreach c3 in primes
            if valid(c1,c2,c3) then foreach c4 in primes
                 if valid(c1,c2,c3,c4) then foreach c5 in primes
                      if valid(c1,c2,c3,c4,c5) then print solution

Addendum: Since we need only to look for numbers that begin with a seqeuence of certain digits, the solution can be made more efficient. Consider the case that c1,c2, annd c3 are given and valid() is about to check row 3. It takes the 3rd digit of c1, c2 and c3 and we can interpret these as the leading 3 digits of the number that must appear in row 3. We need only to fill it up with zeroes and can then check if we know a prime number that is greater than this number, but the difference must be lower than 100 (so that the leading digits are preserved). But if we have a sorted array of prime number candidated, this requires not more than a binary search in that array.