New Year Primes Challenge

[w.r...@ntlworld.com]

Greetings and happy new year; I thought I would set a little challenge
for you to try for fun and profit. So here is my ....

NEW YEAR PRIMES CHALLENGE

A prime square of size N is a square of digits with the following
properties:

a. Each row and each column is a prime number
b. The two diagonals are prime numbers
c. The numbers in the rows, columns and diagonals when read backwards
are also prime numbers.
d. All the 4N + 4 primes are distinct

There exists just one such square (non-isomorphic i.e. apart from
rotations and reflections) for N = 4

1 1 9 3
9 2 5 7
3 8 5 1
3 3 1 9

Above 4, the number of solutions increases rapidly. For example, there
are 35,953 (non-isomorphic) squares for N = 5 which I compute in 31.5
sec using Bloodshed C++ (2.75 GHz PC with 1.75 Gb). I contend that
this kind of problem cannot be solved (efficiently) in any pure
functional programming language. You may disagree

Challenge: I offer £20.00 for the first pure (assignment free) Qi
program that can generate and count the non-isomorphic solutions for
any value of N. The program should perform within an order of
magnitude of my C++ program for N = 5 (about 5 minutes) modulo the CPU
performance. It is not necessary to print the solutions, or even to
remember them, only to enumerate them.

Deadline Jan 31st 2011.

happy new year to all

Willi

[puzzler]

Thanks for posting this challenge. It's an interesting problem. It
was cross-posted to the Clojure google group, which is how I found
about it.

Unfortunately, your program is flawed, which renders your challenge
moot.

Using a purely functional program written in Clojure, I calculate that
there are 63422 isomorphically unique squares that satisfy the
constraints laid out in your problem for N=5.

I have posted the 63422 prime squares found by my program to:
https://docs.google.com/leaf?id=0B0JrHNwD7hNSZTBmMzg5ZGEtZWZmZC00ZWI3LTk4MWItMjU2MDljMDBjYjNm&hl=en
Several volunteers from the Clojure mailing list have independently
confirmed that each of the prime squares in that file satisfy your
constraints and are isomorphically unique. This does not prove that I
have found all of the prime squares (although I believe I have), but
it demonstrates that there are certainly more than the 35,953
solutions that your program enumerated. You can easily download the
file and verify these prime squares for yourself.

Perhaps you would get the correct answer if you used a functional
programming language instead of C++ :)

My program takes longer to run than yours (it takes about 20 minutes,
although I've made no efforts to profile it and look for speed
optimizations), but it's rather silly to compare my running time
against a program that doesn't work. If you want, I can generate a
wrong answer in 30 seconds too :)

In any case, I hope that I will get the challenge reward for
demonstrating one of the key merits of functional programming -- it's
easier to write a program that is correct! Frankly, even if I wanted
to get a blazingly fast solution by coding it in C++, I'd probably
start first in a functional programming language to make sure I have a
clear and correct program, and only then (if I couldn't get it to run
fast enough for my purposes) would I translate it over to C++. I have
found that this process of writing first in a functional language and
then porting to C++ often results in faster development time (for me,
at least) than writing it directly in C++ and trying to experiment/
test/debug/refactor the design while working in C++.

--Mark

P.S. Let us know how long it takes for you to find the bug(s) and fix
your C++ program. I'd also be curious to know how long you spent on
it to begin with. Unfortunately, I didn't keep track of my time
closely, but I estimate that I spent about 6 hours first trying a
rather complicated solving strategy that didn't work out. Then I
threw out my code and started over, coming up with a better, simpler
strategy in about 4 hours.

[Mark Tarver]

I'm sure Willi will offer you his congratulations when he is better;
he is laid up sick at the moment.

He did post me this morning to the effect that his 35,953 figure was
wrong and too small, but retired to bed
shortly after!

I agree with you about the relative merits of functional and
procedural languages.

Mark

On Jan 1, 10:01 pm, puzzler <mark.engelb...@gmail.com> wrote:
> Thanks for posting this challenge.  It's an interesting problem.  It
> was cross-posted to the Clojure google group, which is how I found
> about it.
>
> Unfortunately, your program is flawed, which renders your challenge
> moot.
>
> Using a purely functional program written in Clojure, I calculate that
> there are 63422 isomorphically unique squares that satisfy the
> constraints laid out in your problem for N=5.
>

> I have posted the 63422 prime squares found by my program to:https://docs.google.com/leaf?id=0B0JrHNwD7hNSZTBmMzg5ZGEtZWZmZC00ZWI3...

[w.r...@ntlworld.com]

Challenge Problem

Sorry for the delay; I was ill and needed a day or so after recovery
to check the solution given here.

Only one solution has been posted. Congratulations to the gentleman*
who wins the £20.00. The number of squares, 63244, he has found, in
about 20 minutes, is correct. The number that was stated in my
formulation of the problem was incorrect. In an attempt to cut out the
generation of isomorphic repetitions, I made a wrong assumption. After
changing a couple of lines in my program, it now produces the correct
number of squares in 56 secs, over 20 times faster than the Clojure
program. It would still be interesting to see if a pure functional
program could more closely approach this performance.

It does not seem possible to solve the problem for N = 6 within a
reasonable time. There are obviously many more solutions, and each
solution takes longer to find, on average. For N = 5, my program
generates the answers at a rate of over 1000/sec. For N = 6, the
program generates less than 900/min.

Here is another related challenge: can you find *a* ‘prime square’ for
N = 6, 7, ... I have found squares up to N = 9, and am now working on
N = 10, which requires a slightly different approach, as the prime
numbers are larger and also cannot all be stored in memory.

Willi Riha

*Will the winner get in touch with me re payment!

On Jan 1, 10:01 pm, puzzler <mark.engelb...@gmail.com> wrote:

> Thanks for posting this challenge.  It's an interesting problem.  It
> was cross-posted to the Clojure google group, which is how I found
> about it.
>
> Unfortunately, your program is flawed, which renders your challenge
> moot.
>
> Using a purely functional program written in Clojure, I calculate that
> there are 63422 isomorphically unique squares that satisfy the
> constraints laid out in your problem for N=5.
>

> I have posted the 63422 prime squares found by my program to:https://docs.google.com/leaf?id=0B0JrHNwD7hNSZTBmMzg5ZGEtZWZmZC00ZWI3...

[puzzler]

On Jan 7, 12:49 pm, "w.r...@ntlworld.com" <w.r...@ntlworld.com> wrote:
> *Will the winner get in touch with me re payment!

I sent you an email off-list. Let me know if you didn't receive it.

Playing around with the JVM settings, I was able to get a speedup of
my Clojure code without doing any further modifications. I'm getting
around 14 minutes on a 2Ghz machine; given that my machine is slower
than yours, that's roughly in the ballpark of 10x slower than your C++
version, which is about what I expect from Clojure.

I don't have time to work on this problem more, but here's a summary
of how I approached it. Maybe someone will be motivated to run with
this in Qi. I'll use the 5-digit problem as an example.

Build a set of all the 5-digit primes where reversing the digits gives
a different prime number. These are the relevant primes for building
the prime square.

Also, consider the 5-digit primes which are less than their reverse.
I'll call these "halfPrimes" because this set is half the size of all
the primes under consideration (we've kept one prime from each pair).
halfPrimes will turn out to be important for ensuring that the grids
are unique with respect to isomorphism.

Build some sort of table/hashmap where you can easily look up
questions like:
Give me a set of all the prime numbers where the third digit is a 5.
Give me a set of all the prime numbers where the first digit is a 1.
etc.

A solving state is a collection of lines that need to be solved.
For each line, I track:
1. The cells of the prime square that it spans.
2. A "pattern" that tells you what digits are known so far for this
line, for example, 1**89.
3. A set of all primes that fit the pattern so far.

#1 doesn't change, but #2 and #3 change as the solving progresses
(they begin with a blank pattern and all the primes are
possibilities).

We only need to consider one direction for each line, so for a 5x5
grid, there are 12 lines we need to solve.

Also, you need a table where you can easily lookup for a given cell,
which lines go through that cell and at what position they intersect
that cell.

So for example, if the grid cells are labeled:
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
then cell 11 is part of the line [10,11,12,13,14] at its second
position and part of the line [1,6,11,16,21] at its third position.

Armed with all this pre-compiled data, the solving strategy is
relatively straightforward.

To achieve isomorphically unique grids, we begin by picking two primes
from the halfPrimes set and assign them to the two diagonal lines.
We'll now do a depth-first to find all the grids that match those two
starter lines. If we do this for every combination of two primes from
the halfPrimes set, we're guaranteed to get all the possible prime
squares, exactly once. For odd sizes (such as 5x5), we only need
worry about the combinations of two primes whose middle digit matches.

When you "assign a prime" to a line, you need to remove that prime and
its reverse from the set of possibilities under consideration in all
the other lines. Then, for each digit in the prime, you need to add
it to the "pattern" of all the intersecting lines, and restrict the
set of primes accordingly.

So, for example, if you assign the prime 90019 to the line
[1,6,11,16,21], then you need to add 9 to the pattern for line
[0,1,2,3,4] (so the pattern will now look like *9*** if this is the
first digit to be assigned to that line), and then we intersect its
set of possible primes with the set of all primes that have a 9 as the
second digit.

Using this strategy, just do a depth-first search, always branching by
taking cases on the line with the fewest possible primes.

By using purely functional, non-destructive representations for all
these things, the depth-first, backtracking search is a piece of cake.

I've intentionally avoided getting too specific about the exact
representations I chose, mainly because I want to avoid influencing
others to follow too precisely in my path. It seems clear that
choosing different representations for the lines, the grid, the tables
of information, etc. will have a significant impact on speed. I think
I made reasonable choices, but someone starting from scratch may well
find a faster representation than I. I also speculate that the best
representional choice will be language-dependent. I briefly tried
porting my Clojure solution to Haskell, thinking that as a statically-
typed language, Haskell would be faster. But it actually turned out
to be waaaaaay slower, possibly because the representation I used just
isn't as efficient in Haskell. Clojure's sets and persistent vectors
are quite fast and I made heavy use of them.

I think if I were writing this in an imperative language, I would use
essentially the same strategy, and would similarly use immutable sets
to track the set of possible primes for each line. The "assign a
prime" step is the trickiest step to do efficiently in a functional
language, so I'd probably make use of arrays in my representation of
patterns and lines to hopefully get a bit of a speed boost. Then, it
would be necessary to copy the arrays at each step of the search. Of
course, most functional languages allow some sort of "back door" to do
some mutable trickery behind the scenes for efficiency (for example,
using mutable arrays as an intermediate step to efficiently build some
sort of externally immutable representation). So it's possible to
have your cake and eat it too, but I refrained from using such
features of Clojure to adhere to the spirit of the challenge.

Is there a fundamentally different, better strategy that is only
viable in an imperative language?