If we want to fill the empty squares by the numbers $1$, $2$, $3$, $4$, $5$, $6$ so that all the numbers appear in each row and column, how can we find the number of ways to do that?
$$\begin{array}{|c|c|c|c|c|c|} \hline \;1\strut\;& \;2\; & \;3\; & \;4\; & \;5\; &\;6\;\\\hline 2 \strut& & & & & 5\\\hline 3 \strut& & & & & 4\\\hline 4 \strut& & & & & 3\\\hline 5 \strut& & & & & 2\\\hline 6\strut & 5& 4& 3& 2& 1\\\hline \end{array}$$
On
This problem can be solved for arbitrary board sizes $n \times n$ by a backtracking algorithm. The number of solutions starting at $n=1$ is given by $$1, 1, 0, 2, 0, 16.$$ A Perl implementation of this algorithm follows.
#! /usr/bin/perl -w
#
sub conflict {
my ($n, $b) = @_;
for(my $row = 0; $row < $n; $row++){
my $seen = [(0) x ($n+1)];
for(my $col = 0; $col < $n; $col++){
$seen->[$b->[$row][$col]]++;
}
for(my $s = 1; $s <= $n; $s++){
if($seen->[$s] > 1){
return 1;
}
}
}
for(my $col = 0; $col < $n; $col++){
my $seen = [(0) x ($n+1)];
for(my $row = 0; $row < $n; $row++){
$seen->[$b->[$row][$col]]++;
}
for(my $s = 1; $s <= $n; $s++){
if($seen->[$s] > 1){
return 1;
}
}
}
return 0;
}
sub search {
my ($n, $board, $free, $count) = @_;
if(scalar(@$free) == 0){
$$count++;
for(my $row = 0; $row < $n; $row++){
for(my $col = 0; $col < $n; $col++){
printf " %02d", $board->[$row][$col];
}
printf "\n";
}
printf "\n";
return;
}
for(my $val = 1; $val <= $n; $val++){
my $cell = shift @$free;
my ($cur_row, $cur_col) =
($cell->{row}, $cell->{col});
$board->[$cur_row][$cur_col] = $val;
if(!conflict($n, $board)){
search($n, $board, $free, $count);
}
$board->[$cur_row][$cur_col] = 0;
unshift @$free, $cell;
}
}
MAIN: {
my $n = shift || 4;
if($n<1 || $n !~ /^\d+$/){
print STDERR "integer argument please\n";
exit -1;
}
my $board = [];
for(my $row = 0; $row < $n; $row++){
my $data = []; push @$board, $data;
for(my $col = 0; $col < $n; $col++){
if($row == 0){
push @$data, $col+1;
}
elsif($row == $n-1){
push @$data, $n-$col;
}
elsif($col == 0){
push @$data, $row+1;
}
elsif($col == $n-1){
push @$data, $n-$row;
}
else{
push @$data, 0;
}
}
}
my $free = [];
for(my $row = 1; $row < $n-1; $row++){
for(my $col = 1; $col < $n-1; $col++){
push @$free, {'row' => $row, 'col' => $col};
}
}
my $total = 0;
search($n, $board, $free, \$total);
printf "%d solutions found\n", $total;
exit 0;
}
If it finishes calculating the result for $n = 8$ any time soon I will post that here.
On
The above answer treats a problem that simply has too many free variables. It can be refined, however, and be made to produce number squares that satisfy an amazing number of constraints. We let go of the requirement for the border cells from the original problem, and instead use the following requirements. If $n = a\times b$, with $a>1$ and $b>1$ and $a$ is the integer closest to $\sqrt{n}$, the following must hold on an $n\times n$ board:
That is a series of very strong constraints, yet boards exist that solve them. Here is one for $n=8$ with $2\times 4$ tiles:
01 03 05 06 07 08 04 02 04 02 07 08 05 06 01 03 06 05 03 02 01 04 07 08 07 08 01 04 03 02 06 05 03 04 08 05 06 07 02 01 02 01 06 07 08 05 03 04 05 07 04 03 02 01 08 06 08 06 02 01 04 03 05 07
This one is $n=9$ with $3\times 3$ tiles:
01 04 05 03 06 08 09 07 02 06 02 08 07 04 09 03 01 05 07 09 03 01 02 05 04 08 06 02 05 09 04 01 03 08 06 07 08 07 06 09 05 02 01 03 04 03 01 04 06 08 07 02 05 09 05 03 07 08 09 04 06 02 01 04 08 01 02 07 06 05 09 03 09 06 02 05 03 01 07 04 08
This one is $n=10$ with $2\times 5$ tiles:
01 03 05 06 04 07 08 10 09 02 07 02 09 10 08 03 05 06 01 04 05 08 03 02 09 10 01 04 07 06 06 10 07 04 01 02 03 09 05 08 09 04 01 08 05 06 07 02 03 10 02 06 10 03 07 08 09 05 04 01 04 07 02 05 10 09 06 01 08 03 03 01 08 09 06 04 10 07 02 05 08 09 06 01 02 05 04 03 10 07 10 05 04 07 03 01 02 08 06 09
The trick here is to fill the diagonals before the squares.
#! /usr/bin/perl -w
#
use warnings;
no warnings 'recursion';
sub checkseen {
my ($n, $seen) = @_;
for(my $s = 1; $s <= $n; $s++){
if($seen->[$s] > 1){
return 1;
}
}
return 0;
}
sub conflict {
my ($n, $f1, $f2, $b) = @_;
# rows
for(my $row = 0; $row < $n; $row++){
my $seen = [(0) x ($n+1)];
for(my $col = 0; $col < $n; $col++){
$seen->[$b->[$row][$col]]++;
}
if(checkseen($n, $seen)){
return 1;
}
}
# cols
for(my $col = 0; $col < $n; $col++){
my $seen = [(0) x ($n+1)];
for(my $row = 0; $row < $n; $row++){
$seen->[$b->[$row][$col]]++;
}
if(checkseen($n, $seen)){
return 1;
}
}
# subsquares $f1 by $f2
for(my $e1 = 0; $e1 < $f2; $e1++){
for(my $e2 = 0; $e2 < $f1; $e2++){
my ($base1, $base2) = ($e1*$f1, $e2*$f2);
my $seen = [(0) x ($n+1)];
for(my $row = 0; $row < $f1; $row++){
for(my $col = 0; $col < $f2; $col++){
$seen->[$b->[$base1+$row][$base2+$col]]++;
}
}
if(checkseen($n, $seen)){
return 1;
}
}
}
# subsquares $f2 by $f1
for(my $e1 = 0; $e1 < $f1; $e1++){
for(my $e2 = 0; $e2 < $f2; $e2++){
my ($base1, $base2) = ($e1*$f2, $e2*$f1);
my $seen = [(0) x ($n+1)];
for(my $row = 0; $row < $f2; $row++){
for(my $col = 0; $col < $f1; $col++){
$seen->[$b->[$base1+$row][$base2+$col]]++;
}
}
if(checkseen($n, $seen)){
return 1;
}
}
}
# diagonal 1
my $seen = [(0) x ($n+1)];
for(my $pos = 0; $pos < $n; $pos++){
$seen->[$b->[$pos][$pos]]++;
}
if(checkseen($n, $seen)){
return 1;
}
# diagonal 2
$seen = [(0) x ($n+1)];
for(my $pos = 0; $pos < $n; $pos++){
$seen->[$b->[$pos][$n-1-$pos]]++;
}
if(checkseen($n, $seen)){
return 1;
}
return 0;
}
sub search {
my ($n, $f1, $f2, $board, $free, $count) = @_;
if(scalar(@$free) == 0){
$$count++;
for(my $row = 0; $row < $n; $row++){
for(my $col = 0; $col < $n; $col++){
printf " %02d", $board->[$row][$col];
}
printf "\n";
}
printf "\n";
return;
}
for(my $val = 1; $val <= $n; $val++){
my $cell = shift @$free;
my ($cur_row, $cur_col) =
($cell->{row}, $cell->{col});
$board->[$cur_row][$cur_col] = $val;
if(!conflict($n, $f1, $f2, $board)){
search($n, $f1, $f2, $board, $free, $count);
}
$board->[$cur_row][$cur_col] = 0;
unshift @$free, $cell;
}
}
MAIN: {
my $n = shift || 4;
if($n<1 || $n !~ /^\d+$/){
print STDERR "integer argument please\n";
exit -1;
}
my ($f1, $f2);
$f1 = int(sqrt($n));
while($n%$f1>0){
$f1--;
}
$f2 = $n/$f1;
if($f1==1){
print STDERR "composite number required\n";
exit -2;
}
my $board = [];
for(my $row = 0; $row < $n; $row++){
my $data = []; push @$board, $data;
for(my $col = 0; $col < $n; $col++){
push @$data, 0;
}
}
my $free = [];
for(my $row = 0; $row < $n; $row++){
for(my $col = 0; $col < $n; $col++){
if($row==$col || $row==$n-1-$col){
push @$free, {'row' => $row, 'col' => $col};
}
}
}
for(my $row = 0; $row < $n; $row++){
for(my $col = 0; $col < $n; $col++){
if($row!=$col && $row!=$n-1-$col){
push @$free, {'row' => $row, 'col' => $col};
}
}
}
my $total = 0;
search($n, $f1, $f2, $board, $free, \$total);
printf "%d solutions found, subsquares %d x %d\n",
$total, $f1, $f2;
exit 0;
}
The second row must contain a $3$ and a $4$, neither of which can be in either the third or the fourth column; thus, they must be in the second and fifth columns, in either order, and the missing $1$ and $6$ can then be filled in in either of two ways. That is, there are $2^2=4$ ways to fill in the second row acceptably.
Now proceed to the third row. It must contain a $2$ and a $5$, and they must go in the middle two columns; they can still go there in either order. The missing $1$ and $6$ will then fill the second and fifth columns, and they can appear in either order, so there are $4\cdot2^2=16$ ways to fill the second and third rows acceptably.
In the fourth row the missing $2$ and $5$ must occupy the middle two columns, just as in the third row. Thus, there is only one possible way to place them. The $1$ and $6$ must occupy the second and fifth columns, again just as in the third row, so they must be placed in the order not used in the third row. Thus, the layout of the fourth row is completely determined by the layout of the third row.
Similarly, the layout of the fifth row is completely determined by the layout of the second row, and the total number of acceptable arrangements is just $16$.
The array below shows the possibilities. Numbers separated by a slash are alternatives for that cell. The four red cells are free choices, but once they’ve been chosen everything else is completely determined.
$$\begin{array}{|c|c|c|c|c|c|} \hline 1&2&3&4&5&6\\ \hline 2&\color{red}{3/4}&\color{red}{1/6}&6/1&4/3&5\\ \hline 3&\color{red}{1/6}&\color{red}{2/5}&5/2&6/1&4\\ \hline 4&6/1&5/2&2/5&1/6&3\\ \hline 5&4/3&6/1&1/6&3/4&2\\ \hline 6&5&4&3&2&1\\ \hline \end{array}$$