Creating a solved 9x9 Sudoku based on certain rules

Question

The question:

A rectangular fence is a set of 4 cells on a solved sudoku grid with co-ordinates $(i,j)$, $(m,j)$, $(m,n)$ and $(i,n)$. You can visualize this as the 4 corners of a rectangle.

A symmetric rectangular fence is a rectangular fence where opposite corners hold the same value. Meaning $grid(i,j)=grid(m,n)$ and $grid(m,j)=grid(i,n)$

Make a 9x9 completely-filled sudoku that has a minimum number of symmetric rectangular fences.

Why I asked?

I have been trying to prove that there exists no 16-hint solvable sudoku. I realized that if there exists a symmetric rectangular fence (as I have termed it), then it becomes necessary to give at least one of the 4 cells as a hint. So, minimizing the number of such occurences would make it possible to create lesser-hint sudoku's and maybe throw some light on why 17 hints are still required.

For puzzlers, the question in section 1 is complete by itself; you need not bother about the rest. You may use a program to find the answer, but there are many, many possibilities, so you will still have to use some logical approach to it.

Answer 1

Here's one I just created with zero symmetrical rectangular fences.

Answer 2

I just did the easiest construction that I could—I put the numbers 1-9 in order on each row, and then shifted the rows to avoid block or column duplicates. This appears to produce a grid with no "symmetric rectangular fences," but I don't know the minimum number of hints required to solve it.

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

Answer 3

There's a method described in Sudoku: Bagging a Difficulty Metric & Building Up Puzzles for generating a solved Sudoku board. You take the 12 order three latin squares (using values of 0, 1, and 2). Of these 12, you select 9 with replacement that are placed on a 3x3 board and then a 10th is the 'over board'. Each value is then read as trinary when converting to base 10, and then some specific swaps are done.

Here's where I'm guessing, and I haven't done the full analysis of the resulting board. Unfortunately, I don't have the math background to be able to prove that that such is the case.

I am a programmer though, and so I whipped up a quick bit of code:

#!/usr/bin/perl

use strict;

use List::Util qw(shuffle);

my @squares = shuffle (
[[0,1,2],[1,2,0],[2,0,1]],
[[0,1,2],[2,0,1],[1,2,0]],
[[0,2,1],[1,0,2],[2,1,0]],
[[0,2,1],[2,1,0],[1,0,2]],

[[1,0,2],[0,2,1],[2,1,0]],
[[1,0,2],[2,1,0],[0,2,1]],
[[1,2,0],[0,1,2],[2,0,1]],
[[1,2,0],[2,0,1],[0,1,2]],

[[2,1,0],[0,2,1],[1,0,2]],
[[2,1,0],[1,0,2],[0,2,1]],
[[2,0,1],[0,1,2],[1,2,0]],
[[2,0,1],[1,2,0],[0,1,2]],
);


my @board;
my @final;
my $outer = shift @squares;

for my $i (0 .. 2) {
    for my $j (0 .. 2) {
        $board[$i][$j] = shift @squares;

        for my $x (0 .. 2) {
        for my $y (0 .. 2) {
            $final[$i * 3 + $x][$j * 3 + $y] = 
                3 * $outer->[$i][$j] + $board[$i][$j][$x][$y] + 1;
            }
        }
    }
}

# now, swap R2 & R4; R3 & R7; R6 & R8

for my $i (0 .. 8) {
($final[1][$i], $final[3][$i]) = ($final[3][$i], $final[1][$i]);
($final[2][$i], $final[6][$i]) = ($final[6][$i], $final[2][$i]);
($final[5][$i], $final[7][$i]) = ($final[7][$i], $final[5][$i]);
}

foreach my $r (@final) {
foreach my $c (@{$r}) {
    print "$c ";
    }
    print "\n";
}

And running it a few times I get:

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


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


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


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

I'm taking the shortcut of not doing the replacement in my code. There are some properties of these puzzles... if you note, the 7, 8, and 9 are always in the same set of three, as are the 1, 2, 3 and the 4, 5, 6. The fact that its a latin square on the over board too, then makes the swaps such that I believe that the rectangular fence cannot form.

If you have the process only use one latin square, the grid looks like:

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

This next one (another one grid generation) is one that is probably closest to the other solutions that have been provided and allows a clear picture of the patterns that are formed in this type of generation.

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

Though, while I am confident that these do not have rectangular fences, and the generation method precludes them, I am not sure that such is the case.

The key part is in order to form a rectangular fence, I need to swap two columns somewhere (either in a single 3x3, or in the over grid):

? A B
? B A
? ? ? 

The thing is that this pattern does not happen in any of the latin squares because that would force the third element of the square to be in the same row or column as itself, which is a violation of the definition of the latin square. ... but, as I said, I'm not sure I have a proof there.