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 |
+---+---+---+---+---+---+---+---+
Of the 64 original squares, 24 are "safe" in that even with no removals they will be unique in their rows and columns. Of the remaining 40, I have found a pattern which removes 19, keeping 45 squares. This is my "working minimum" and I'll present it here, though I feel this is not optimal (especially I believe I am removing too many of the 5's.
x46x357x
65xx7831
x72x548x
86532x4x
3x148652
x3x64x2x
587x6213
x137xx68
No good algorithm here: just tried to see that for each one "erased" at least one other open choice was preserved. A very few allowed preserving two. (This is the same number of removals as on the sample presented, though that should allow more since it used digits 1..9, whereas the actual problem used just 1..8 for each cell.
As a Start...
