MATH
Login Or Sign up

Number of sudokus with no consecutive arithmetic progression of length 3 in any row or column.

261 Views Asked by At

How many such Sudokus are there? Any reference to papers, books, articles or any insight into the problem will be greatly appreciated.

I've tried several search engines, scholarly and not, with no results. Maybe there is a terminology for them I am unaware of.

EDIT1 Title updated. No AP for any row or column.

EDIT2 Title updated. Consecutive AP.

combinatorics number-theory algorithms arithmetic arithmetic-combinatorics
Original Q&A
2

There are 2 best solutions below

4
On BEST ANSWER

The following C program produces 165K different solutions during a one minute run. This is a literal translation of the Perl code and some C style issues probably remain as I am not an expert C coder. Compiled with GCC 4.8.3.

#include <stdio.h>

typedef struct {
  int row, col;
} slot;

typedef slot region[9];

typedef struct {
  region regions[27];
  region *incidence[9][9][3];
} boardinf;

typedef int boardvals[9][9];

void search(boardvals *bvptr, boardinf *binfptr,  int sofar)
{
  int row, col;

  if(sofar == 9*9){
    for(row=0; row<9; row++){
      for(col=0; col<9; col++){
        if(col>0) printf(" ");
        printf("%d", (*bvptr)[row][col]);
      }
      printf("\n");
    }
    printf("\n");

    return;
  }

  col = sofar % 9; row = (sofar-col) / 9;

  int val;
  for(val = 1; val <= 9; val++){
    (*bvptr)[row][col] = val;

    int admit = 1, regx;
    for(regx=0; regx<3; regx++){
      region *reg = binfptr->incidence[row][col][regx];

      int sx;
      for(sx=0; sx<9; sx++){
        slot *s = (*reg)+sx;

        if(s->row != row || s->col != col){
          if((*bvptr)[s->row][s->col] == val){
            admit = 0;
            break;
          }
        }
      }

      if(!admit) break;
    }

    if(row>=2){
      int ap[3] = {
        (*bvptr)[row-2][col],
        (*bvptr)[row-1][col],
        (*bvptr)[row][col] };

      if(ap[2]-ap[1] == ap[1]-ap[0]){
        admit = 0;
      }
    }

    if(col>=2){
      int ap[3] = {
        (*bvptr)[row][col-2],
        (*bvptr)[row][col-1],
        (*bvptr)[row][col] };

      if(ap[2]-ap[1] == ap[1]-ap[0]){
        admit = 0;
      }
    }

    if(admit) search(bvptr, binfptr, sofar+1);

    (*bvptr)[row][col] = -1;
  }
}


int main(int argc, char **argv)
{
  boardinf binf;
  int row, col, regx = 0;

  for(row=0; row<9; row++){
    for(col=0; col<9; col++){
      binf.regions[regx][col].row = row;
      binf.regions[regx][col].col = col;

      binf.incidence[row][col][0] = binf.regions+regx;
    }

    regx++;
  }

  for(col=0; col<9; col++){
    for(row=0; row<9; row++){
      binf.regions[regx][row].row = row;
      binf.regions[regx][row].col = col;

      binf.incidence[row][col][1] = binf.regions+regx;
    }

    regx++;
  }

  int x, y;
  for(y=0; y<3; y++){
    for(x=0; x<3; x++){
      int idx = 0;

      for(row=0; row<3; row++){
        for(col=0; col<3; col++){
          binf.regions[regx][idx].row = 3*y+row;
          binf.regions[regx][idx].col = 3*x+col;

          binf.incidence[3*y+row][3*x+col][2] =
            binf.regions+regx;

          idx++;
        }
      }

      regx++;
    }
  }

  boardvals bv;
  for(row=0; row<9; row++){
    for(col=0; col<9; col++){
      bv[row][col] = -1;
    }
  }

  search(&bv, &binf, 0);
}

Here are some of solutions that it computed.

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 7 9 8 3 6 4 5
6 9 3 5 4 1 2 8 7
5 4 8 2 6 7 9 3 1
7 8 2 6 9 5 4 1 3
4 6 1 7 3 8 5 9 2
9 3 5 4 1 2 7 6 8

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 7 9 8 3 6 4 5
6 9 3 5 4 1 2 8 7
5 4 8 2 6 7 9 3 1
7 8 5 6 9 2 4 1 3
4 6 1 7 3 8 5 9 2
9 3 2 4 1 5 7 6 8

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 7 9 8 3 6 4 5
6 9 3 5 4 1 2 8 7
5 4 8 2 6 7 9 3 1
9 6 2 7 3 5 4 1 8
4 3 5 6 1 8 7 9 2
7 8 1 4 9 2 5 6 3

The following three solutions are notable for swapping activity having reached the fourth row.

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 4 3 6 8 5 9 1 7
7 8 1 4 9 3 5 6 2
9 6 5 7 1 2 4 3 8
6 3 2 5 4 8 7 9 1
4 9 7 2 3 1 6 8 5
5 1 8 9 6 7 2 4 3

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 4 3 6 8 5 9 1 7
7 8 1 4 9 3 5 6 2
9 6 5 7 1 2 4 3 8
6 3 7 5 4 8 2 9 1
4 1 2 9 3 7 6 8 5
5 9 8 2 6 1 7 4 3

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 4 3 6 8 5 9 1 7
7 8 1 4 9 3 5 6 2
9 6 5 7 1 2 4 3 8
6 3 8 5 4 7 2 9 1
4 9 7 2 3 1 6 8 5
5 1 2 9 6 8 7 4 3
5
On

By way of approaching this problem from a computational perspective here follows a program that will produce these sudokus in the hope that the reader can profit from the algorithmics that are used and perhaps invent a more compact/efficient algorithm. What is used here is backtracking in its most basic form. We sweep the board row by row, placing compatible values that do not contradict any of the constraints (rows/columns/boxes). On the machine where this was tested solutions are produced almost instantly. For more details on the method I recommend the upvoted work by MJD at this MSE link. Here are the first few sudokus with no arithmetic progression of length three:

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 6 5 9 1 7 2 8 3
7 9 8 2 6 3 4 1 5
5 3 2 6 9 1 7 4 8
6 8 7 5 4 2 9 3 1
9 4 1 7 3 8 5 6 2

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 6 5 9 1 7 2 8 3
7 9 8 2 6 3 4 1 5
5 3 2 6 9 1 7 4 8
9 4 1 7 3 8 5 6 2
6 8 7 5 4 2 9 3 1

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 6 5 9 1 7 2 8 3
7 9 8 2 6 3 4 1 5
6 8 7 5 4 2 9 3 1
9 4 1 7 3 8 5 6 2
5 3 2 6 9 1 7 4 8

Some additional solutions are

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
7 4 2 6 1 8 9 3 5
6 3 5 9 4 2 7 1 8
9 8 1 5 3 7 4 6 2

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
9 4 1 5 3 2 7 6 8
7 3 5 6 4 8 9 1 2
6 8 2 9 1 7 4 3 5

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
9 8 1 5 3 7 4 6 2
6 3 5 9 4 2 7 1 8
7 4 2 6 1 8 9 3 5

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 6 9 7
4 9 7 2 6 1 5 8 3
5 6 8 7 9 3 2 4 1
9 8 1 5 3 7 4 6 2
6 4 5 9 1 2 7 3 8
7 3 2 6 4 8 9 1 5

The Perl code for this was as follows:

#! /usr/bin/perl -w
#

sub search {
    my ($board, $regions, $sofar) = @_;

    if($sofar == 9*9){
        for(my $row = 0; $row < 9; $row++){
            for(my $col = 0; $col < 9; $col++){
                print " " if $col > 0;
                print $board->[$row][$col];
            }
            print "\n";
        }
        print "\n";

        return;
    }

    my $col = $sofar % 9; my $row = ($sofar-$col) / 9;

    for(my $val = 1; $val <= 9; $val++){
        $board->[$row][$col] = $val;

        my $admit = 1;
        foreach my $region (@$regions){
            my %seen; my $empty = 0;

            foreach my $slot (@$region){
                my $ent = $board->[$slot->[0]][$slot->[1]];

                if($ent == -1){
                    $empty++;
                }
                else{
                    $seen{$ent} = 1;
                }
            }

            if(scalar(keys(%seen))+$empty != 9){
                $admit = undef;
                last;
            }
        }

        if($row>=2){
            my @ap = (
                $board->[$row-2][$col],
                $board->[$row-1][$col],
                $board->[$row][$col]);
            if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
                $admit = undef;
            }
        }

        if($col>=2){
            my @ap = (
                $board->[$row][$col-2],
                $board->[$row][$col-1],
                $board->[$row][$col]);
            if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
                $admit = undef;
            }
        }


        search($board, $regions, $sofar+1) 
            if defined($admit);

        $board->[$row][$col] = -1;
    }
}

 MAIN: {
     my $regions = [];

     for(my $line = 0; $line < 9; $line++){
         my $region = [ 
             map {
                 [$line, $_]
             } (0..8) ];
         push @$regions, $region;

         $region = [ 
             map {
                 [$_, $line]
             } (0..8) ];
         push @$regions, $region;
     }

     for(my $row = 0; $row < 3; $row++){
         for(my $col = 0; $col < 3; $col++){
             my $region = [];

             for(my $x = 0; $x < 3; $x++){
                 for(my $y = 0; $y < 3; $y++){
                     push @$region,
                     [$row*3+$x, $col*3+$y];
                 }
             }

             push @$regions, $region;
         }
     }

     my $board =
         [ map { [ (-1) x 9 ] } (0) x 9 ];

     search($board, $regions, 0);
}

A sequence from further on in the solution space reads as follows:

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 9 6 7
6 9 7 2 1 3 4 8 5
4 8 5 9 6 7 2 3 1
7 3 2 5 4 1 6 9 8
9 6 1 7 3 8 5 4 2
5 4 8 6 9 2 7 1 3

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 9 6 7
6 9 7 2 1 3 4 8 5
4 8 5 9 6 7 2 3 1
7 3 2 5 9 1 6 4 8
9 6 8 7 4 2 5 1 3
5 4 1 6 3 8 7 9 2

1 2 4 3 5 6 8 7 9
3 5 6 8 7 9 1 2 4
8 7 9 1 2 4 3 5 6
2 1 3 4 8 5 9 6 7
6 9 7 2 1 3 4 8 5
4 8 5 9 6 7 2 3 1
7 3 2 6 9 1 5 4 8
9 6 8 5 4 2 7 1 3
5 4 1 7 3 8 6 9 2

Addendum Sat Nov 15 10:40:01 CET 2014. By way of responding to the challenge here is an optimized yet simple version of the above that produced 2600 solutions in one minute of computation time, not bad for an interpreted language and ten times as fast as the first version. I suspect if this were to be translated into C the performance would be quite striking.

#! /usr/bin/perl -w
#

sub search {
    my ($board, $incident, $sofar) = @_;

    if($sofar == 9*9){
        for(my $row = 0; $row < 9; $row++){
            for(my $col = 0; $col < 9; $col++){
                print " " if $col > 0;
                print $board->[$row][$col];
            }
            print "\n";
        }
        print "\n";

        return;
    }

    my $col = $sofar % 9; my $row = ($sofar-$col) / 9;

    for(my $val = 1; $val <= 9; $val++){
        my $key = "$row-$col";
        $board->[$row][$col] = $val;

        my $admit = 1;
        foreach my $region (@{ $incident->{$key} }){
            foreach my $slot (@$region){
                if($slot->[0] != $row || $slot->[1] != $col){
                    my $ent = $board->[$slot->[0]][$slot->[1]];

                    if($ent == $val){
                        $admit = undef;
                        last;
                    }
                }
            }

            last if not defined($admit);
        }

        if($row>=2){
            my @ap = (
                $board->[$row-2][$col],
                $board->[$row-1][$col],
                $board->[$row][$col]);
            if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
                $admit = undef;
            }
        }

        if($col>=2){
            my @ap = (
                $board->[$row][$col-2],
                $board->[$row][$col-1],
                $board->[$row][$col]);
            if($ap[2]-$ap[1] == $ap[1]-$ap[0]){
                $admit = undef;
            }
        }


        search($board, $incident, $sofar+1) 
            if defined($admit);

        $board->[$row][$col] = -1;
    }
}

 MAIN: {
     my $regions = [];

     for(my $line = 0; $line < 9; $line++){
         my $region = [ 
             map {
                 [$line, $_]
             } (0..8) ];
         push @$regions, $region;

         $region = [ 
             map {
                 [$_, $line]
             } (0..8) ];
         push @$regions, $region;
     }

     for(my $row = 0; $row < 3; $row++){
         for(my $col = 0; $col < 3; $col++){
             my $region = [];

             for(my $x = 0; $x < 3; $x++){
                 for(my $y = 0; $y < 3; $y++){
                     push @$region,
                     [$row*3+$x, $col*3+$y];
                 }
             }

             push @$regions, $region;
         }
     }

     my $incident = {};
     foreach my $region (@$regions){
         foreach my $slot (@$region){
             my $key = join('-', @$slot);
             push @{ $incident->{$key} }, $region;
         }
     }


     my $board = [ map { [ (-1) x 9 ] } (0) x 9 ];

     search($board, $incident, 0);
}

Related Questions in COMBINATORICS

Related Questions in NUMBER-THEORY

Related Questions in ALGORITHMS

Related Questions in ARITHMETIC

Related Questions in ARITHMETIC-COMBINATORICS

Trending Questions

Popular # Hahtags

second-order-logic numerical-methods puzzle logic probability number-theory winding-number real-analysis integration calculus complex-analysis sequences-and-series proof-writing set-theory functions homotopy-theory elementary-number-theory ordinary-differential-equations circles derivatives game-theory definite-integrals elementary-set-theory limits multivariable-calculus geometry algebraic-number-theory proof-verification partial-derivative algebra-precalculus

Popular Questions

Copyright © 2021 JogjaFile Inc.