#!/usr/bin/perl

use strict;
use warnings;
no warnings qw /syntax/;

my $N  = 6;
my $SN = $N * $N;

my @chars = (0 .. 9, 'A' .. 'Z', 'a' .. 'z', '/', '+');

my $mask;

foreach my $x (0 .. $N - 1) {
    foreach my $y (0 .. $N - 1) {
        $mask -> [$x] [$y] = $x * $N + $y;
    }
}

my $grid;
foreach my $X (0 .. $N - 1) {
    foreach my $Y (0 .. $N - 1) {
        my $sx = $X * $N;
        my $sy = $Y * $N;
        foreach my $x ($sx .. $sx + $N - 1) {
            foreach my $y ($sy .. $sy + $N - 1) {
                $grid -> [$x] [$y] = $mask -> [($x + $Y) % $N] [($y + 
+$X) % $N];
            }
        }
    }
}

#
# Check correctness.
#

# Rows and columns.
foreach my $x (0 .. $SN - 1) {
    my %hx;
    my %hy;
    foreach my $y (0 .. $SN - 1) {
        $hx {$grid -> [$x] [$y]} = 1;
        $hy {$grid -> [$y] [$x]} = 1;
    }
    die unless $SN == keys %hx && $SN == keys %hy;
}
    
# Grids.
foreach my $x (0 .. $N - 1) {
    foreach my $y (0 .. $N - 1) {
        my %hg;
        foreach my $xx (0 .. $N - 1) {
            foreach my $yy (0 .. $N - 1) {
                $hg {$grid -> [$x * $N + $xx] [$y * $N + $yy]} = 1;
            }
        }
        die unless $SN == keys %hg;
    }
}
             
# Print results (assume $N <= 8).
foreach my $x (0 .. @$grid - 1) {
    foreach my $y (0 .. @{$grid -> [$x]} - 1) {
        print $chars [$grid -> [$x] [$y]];
    }
    print "\n";
}

__END__
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
6789ABCDEFGHIJKLMNOPQRSTUVWXYZ012345
CDEFGHIJKLMNOPQRSTUVWXYZ0123456789AB
IJKLMNOPQRSTUVWXYZ0123456789ABCDEFGH
OPQRSTUVWXYZ0123456789ABCDEFGHIJKLMN
UVWXYZ0123456789ABCDEFGHIJKLMNOPQRST
123450789AB6DEFGHCJKLMNIPQRSTOVWXYZU
789AB6DEFGHCJKLMNIPQRSTOVWXYZU123450
DEFGHCJKLMNIPQRSTOVWXYZU123450789AB6
JKLMNIPQRSTOVWXYZU123450789AB6DEFGHC
PQRSTOVWXYZU123450789AB6DEFGHCJKLMNI
VWXYZU123450789AB6DEFGHCJKLMNIPQRSTO
23450189AB67EFGHCDKLMNIJQRSTOPWXYZUV
89AB67EFGHCDKLMNIJQRSTOPWXYZUV234501
EFGHCDKLMNIJQRSTOPWXYZUV23450189AB67
KLMNIJQRSTOPWXYZUV23450189AB67EFGHCD
QRSTOPWXYZUV23450189AB67EFGHCDKLMNIJ
WXYZUV23450189AB67EFGHCDKLMNIJQRSTOP
3450129AB678FGHCDELMNIJKRSTOPQXYZUVW
9AB678FGHCDELMNIJKRSTOPQXYZUVW345012
FGHCDELMNIJKRSTOPQXYZUVW3450129AB678
LMNIJKRSTOPQXYZUVW3450129AB678FGHCDE
RSTOPQXYZUVW3450129AB678FGHCDELMNIJK
XYZUVW3450129AB678FGHCDELMNIJKRSTOPQ
450123AB6789GHCDEFMNIJKLSTOPQRYZUVWX
AB6789GHCDEFMNIJKLSTOPQRYZUVWX450123
GHCDEFMNIJKLSTOPQRYZUVWX450123AB6789
MNIJKLSTOPQRYZUVWX450123AB6789GHCDEF
STOPQRYZUVWX450123AB6789GHCDEFMNIJKL
YZUVWX450123AB6789GHCDEFMNIJKLSTOPQR
501234B6789AHCDEFGNIJKLMTOPQRSZUVWXY
B6789AHCDEFGNIJKLMTOPQRSZUVWXY501234
HCDEFGNIJKLMTOPQRSZUVWXY501234B6789A
NIJKLMTOPQRSZUVWXY501234B6789AHCDEFG
TOPQRSZUVWXY501234B6789AHCDEFGNIJKLM
ZUVWXY501234B6789AHCDEFGNIJKLMTOPQRS
[download]

Abigail

There's even a much simpler algorithm:

my $N    = 6;
my @nums = (0 .. $N * $N - 1);

my $grid;

foreach my $x (0 .. $N - 1) {
    foreach my $y (0 .. $N - 1) {
        push @$grid => [@nums];
        push @nums  => splice @nums => 0, $N;
    }
    foreach my $y (0 .. $N - 1) {
        splice @nums => $y * $N, $N =>
               @nums [($y * $N + 1) .. (($y + 1) * $N - 1), $y * $N]
    }
}
[download]

Abigail

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.

  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

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

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

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

This can be extended to create a random solution, just randomize the initial block. (This is similar to Abigail-II's solution). Here @start is a N by N matrix whose entries are a random permutation of {1, .., N^2}.

my $n     = shift || 3;

my @start = do {
    use List::Util 'shuffle';
    my @perm = shuffle 1 .. $n*$n;

    map {
         my $row = $_;
         [ map { $perm[$row * $n + $_] } 0 .. $n-1 ]
    } 0 .. $n-1;
};

my @solution;

for my $x ( 0 .. $n*$n - 1 ) {
    for my $y ( 0 .. $n*$n - 1 ) {

        my $block_x = int ($x / $n);
        my $block_y = int ($y / $n);

        $solution[$x][$y] =
            $start[ ($block_x + $y) % $n ][ ($block_y + $x) % $n ];
    }
}

print join "" => map { "@$_\n" } @solution;
[download]

blokhead