in reply to Better algorithm for Number Place Puzzle

I think in your description you made one typo:

For example, if N=5, the puzzle has 25 columns, ...

.. I think should have said "if sqrt(N)=5".

To approach this, first off I don't see any reason to choose random numbers: for a 36x36 square, there are at most 36 numbers to consider, so it seems strange to pick 10,000 random numbers rather than just try each of the 36 in turn.

Second, the numbers have no intrinsic meaning, they are just labels - you could colour the squares using 36 different colours, and you'd still be solving the same problem. That implies in particular that given any solution you could swap, say, all the 1s and 2s around and have a new solution - it is just a different way of labelling the 36 colours using numbers. Given that, you might as well choose a fixed labelling by pre-filling the first row with the numbers in order.

Third, there is a very easy way to construct a magic NxN square for any odd N, and I suspect a small tweak to that construction would also allow you to construct a solution for this problem for odd N. I've blanked it out below in case you don't want to know.

Create a mask consisting of knight's moves, then shift and repeat. Eg for a 7x7 grid the mask would look like:

  x......                     1234567
  ..x....                     6712345
  ....x..                     4567123
  ......x  giving the square  2345671
  .x.....                     7123456
  ...x...                     5671234
  .....x.                     3456712

[download]

Fourth, you may be able to get substantial speedups by dealing with bit vectors rather than arrays; however, I'd suggest posting your code here for more specific advice.

Hugo

Replies are listed 'Best First'.
Re: Re: Better algorithm for Number Place Puzzle
by davidj (Priest) on May 23, 2004 at 22:30 UTC
    hv,

    First, You are correct. I did make a typo which you successfully caught. Thank you.

    Second, I don't know how magic squares would help. The constraints are totally different. That is, I don't see how meeting the constraints of a magic square puzzle would successfully meet the constraints of the number place puzzle.

    Third, you are right. It would be easy to generate a single solution by simply shifting the numbers on each row, and then using matrix rules to generate other solutions, but that would take the fun out of it :)

    Finally, my concern at this point is not speed. Rather, it is the effectiveness of an algorithm to generate solutions of any size.

    davidj
[reply]

      I don't know how magic squares would help. The constraints are totally different.

      If you take a standard (N x N) magic square, consisting of the numbers from 1 .. N^2, and then reduce each number module N, you will in some (all?) cases get a square consisting of the numbers 1 .. N such that each number appears exactly once in each row and column.

      The nature of your squares is identical to this case, except for the additional constraint that the N interior squares must each contain each number once. So solutions to this problem are a subset of the (n^2 x n^2) magic squares.

      For this sort of problem I'm more used to either a) showing that there is a solution (any solution) by finding one; or b) finding all solutions. In your case you seem to be aiming at a quite different goal, in which randomness plays a necessary part, but I'm not at all clear what your precise goal is.

      Finally, my concern at this point is not speed. Rather, it is the effectiveness of an algorithm to generate solutions of any size.

      Hmm, so when failing to find a solution in 500,000 random attempts you're concerned not with how long that took but with how many attempts it took? But given that you're selecting the numbers at random, I'm not sure how you'd reduce that except by weighting the numbers towards the ones more likely to give a solution, and I can't offhand see any way to do that without knowing in advance what solutions are possible.

      Sorry, I've realised that I really have no idea what you're asking for.

      Hugo

[reply]
      Mmm. Seems like you think you have an easy solution, but you don't want to use it. What makes you think this problem has more than one solution?
      A massive flamewar beneath your chosen depth has not been shown here
[reply]
        There is any easy solution: on a 36x36, let the top row be the numbers 1-36, the second row be 2-36,1, the third row be 3-36,1,2, and so on. But that's not the point of the exercise. The point is to find a way to build some intelligence into a program that will randomly generate solutions of any size.

        The problem does have more than one solution. Swapping any two rows or columns of one solution will generate another solution. This can be done repeatedly in any number of combinations to generate thousands of solutions. But again that is not the point of the exercise.

        davidj
[reply]

In Section Seekers of Perl Wisdom