3
$\begingroup$

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}$$

(original image)

$\endgroup$
  • 2
    $\begingroup$ I would start by looking at possible ways you can add the 2's you need. Then see how that effects the placement of the 5's, proceed to the 3's and 4's, and finally put the 1's and 6's in. $\endgroup$ – Shard Jan 19 '13 at 18:19
  • $\begingroup$ There was nothing wrong with the original image, but I've put in a MathJax version of the table so that people who are less familiar with formatting here can more easily make their answers look nice. If you look at the revision history, you can copy and paste the code to use it in your answer. $\endgroup$ – Zev Chonoles Jan 19 '13 at 18:37
6
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The answer for $n=8$ is $1069056$ solutions. $\endgroup$ – Marko Riedel Jan 20 '13 at 3:46
0
$\begingroup$

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:

  • every row contains all values from $1$ to $n$
  • every column contains all values from $1$ to $n$
  • every tile when we tile the board using tiles that are $a\times b$ contains all values from $1$ to $n$
  • every tile when we tile the board using tiles that are $b\times a$ contains all values from $1$ to $n$
  • every diagonal contains all values from $1$ to $n$.

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.