Look at the 8x8 grid below at left. In the rows and columns there are repeated numbers. Erasing 19 of them, we achieve the grid at right, that has no repeated numbers in any row, in any column.

+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 5 | 7 | 1 | 2 | 5 | 4 | 4 | 3 |       |   | 7 | 1 |   | 5 |   | 4 | 3 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 4 | 3 | 1 | 2 | 7 | 5 | 6 | 3 |       | 4 | 3 |   | 2 | 7 | 5 | 6 |   |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 5 | 5 | 3 | 4 | 2 | 1 | 7 | 8 |       |   | 5 | 3 |   | 2 |   | 7 | 8 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 6 | 6 | 2 | 7 | 3 | 3 | 3 | 1 |       | 6 |   | 2 | 7 |   | 3 |   | 1 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 3 | 2 | 5 | 6 | 9 | 1 | 8 | 6 |       | 3 | 2 | 5 |   | 9 | 1 | 8 | 6 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 2 | 1 | 3 | 4 | 6 | 2 | 5 | 2 |       |   | 1 |   | 4 | 6 |   | 5 | 2 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 9 | 8 | 4 | 1 | 4 | 6 | 2 | 3 |       | 9 | 8 | 4 | 1 |   | 6 | 2 |   |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+
| 7 | 5 | 6 | 5 | 8 | 5 | 1 | 4 |       | 7 |   | 6 | 5 | 8 |   | 1 | 4 |
+---+---+---+---+---+---+---+---+       +---+---+---+---+---+---+---+---+

Do the same with this 8x8 grid, erasing the minimum number of squares.

                    +---+---+---+---+---+---+---+---+
                    | 8 | 4 | 6 | 5 | 3 | 5 | 7 | 4 |
                    +---+---+---+---+---+---+---+---+
                    | 6 | 5 | 5 | 4 | 7 | 8 | 3 | 1 |
                    +---+---+---+---+---+---+---+---+ 
                    | 5 | 7 | 2 | 5 | 5 | 4 | 8 | 7 |
                    +---+---+---+---+---+---+---+---+
                    | 8 | 6 | 5 | 3 | 2 | 5 | 4 | 4 |
                    +---+---+---+---+---+---+---+---+
                    | 3 | 8 | 1 | 4 | 8 | 6 | 5 | 2 |
                    +---+---+---+---+---+---+---+---+ 
                    | 5 | 3 | 7 | 6 | 4 | 2 | 2 | 2 |
                    +---+---+---+---+---+---+---+---+
                    | 5 | 8 | 7 | 7 | 6 | 2 | 1 | 3 |
                    +---+---+---+---+---+---+---+---+
                    | 1 | 1 | 3 | 7 | 6 | 4 | 6 | 8 |
                    +---+---+---+---+---+---+---+---+ 

This tabulation indicates the excess digits in 
a) each row (to the side of the grid) 
and 
b) each column (below the grid).

                                        1  2  3  4  5  6  7  8
   +---+---+---+---+---+---+---+---+
   | 8 | 4 | 6 | 5 | 3 | 5 | 7 | 4 |             1  1
   +---+---+---+---+---+---+---+---+                 
   | 6 | 5 | 5 | 4 | 7 | 8 | 3 | 1 |                1     
   +---+---+---+---+---+---+---+---+ 
   | 5 | 7 | 2 | 5 | 5 | 4 | 8 | 7 |                2     1
   +---+---+---+---+---+---+---+---+
   | 8 | 6 | 5 | 3 | 2 | 5 | 4 | 4 |             1  1
   +---+---+---+---+---+---+---+---+
   | 3 | 8 | 1 | 4 | 8 | 6 | 5 | 2 |                          1
   +---+---+---+---+---+---+---+---+ 
   | 5 | 3 | 7 | 6 | 4 | 2 | 2 | 2 |        2
   +---+---+---+---+---+---+---+---+
   | 5 | 8 | 7 | 7 | 6 | 2 | 1 | 3 |                      1
   +---+---+---+---+---+---+---+---+
   | 1 | 1 | 3 | 7 | 6 | 4 | 6 | 8 |    1               1
   +---+---+---+---+---+---+---+---+ 

 1

 2                       1       1

 3

 4               1       1       1 

 5   2       1   1       1

 6                   1 

 7           1   1

 8   1   1 

I began by casting out the 8's and the 6's in the last row.
Then I looked at the clusters of 7 and 2.  Using the table 
above as a guide I also removed 19 numbers.  It became clear
that there was no hard and fast rule as to which number in 
a group to eliminate so long as I was being "minimalistic"
each time.  Accordingly I'd suggest that culling by use of
a cross referenced grid (as above) is probably the best 
algorithm likely.

This is my attempt which differs from the others

   +---+---+---+---+---+---+---+---+
   |   | 4 | 6 | 5 | 3 |   | 7 |   |
   +---+---+---+---+---+---+---+---+
   | 6 | 5 |   | 4 | 7 | 8 | 3 | 1 |
   +---+---+---+---+---+---+---+---+ 
   |   | 7 | 2 |   | 5 |   | 8 |   |
   +---+---+---+---+---+---+---+---+
   | 8 | 6 | 5 | 3 | 2 |   |   | 4 |
   +---+---+---+---+---+---+---+---+
   | 3 |   | 1 |   | 8 | 6 | 5 | 2 |
   +---+---+---+---+---+---+---+---+ 
   | 5 | 3 | 7 | 6 | 4 |   | 2 |   |
   +---+---+---+---+---+---+---+---+
   |   | 8 |   |   | 6 | 2 | 1 | 3 |
   +---+---+---+---+---+---+---+---+
   | 1 |   | 3 | 7 |   | 4 | 6 | 8 |
   +---+---+---+---+---+---+---+---+ 

Posted by brianjn on 2008-08-20 23:40:54