35
$\begingroup$

A sudoku net is a 9x9 grid where every cell is either (blank) or has a cross (block).

A random solved sudoku is chosen. The net is placed on top of the sudoku (in any of the 4 ways). We can only see the cells that have a blank over them and the cells with a block over them are covered.

A sudoku net is defined as 'solvable' if we can deduce the unique solution of the sudoku just by looking at the visible cells. This should be true in all cases, irrespective of the selected sudoku.

Create the sudoku net with maximum possible blocks (or crosses) such that this sudoku net is solvable for all sudoku puzzles. (Any arrangement of visible cells that result in a valid sudoku puzzle.)

$\endgroup$
  • 4
    $\begingroup$ The four net orientations aren't needed. $\endgroup$ – mdc32 Apr 9 '15 at 16:41
  • $\begingroup$ I added a clarification to your request since the question didn't specifically ask for a solvable sudoku net. $\endgroup$ – Ian MacDonald Apr 9 '15 at 18:59
  • $\begingroup$ Relevant: puzzling.stackexchange.com/q/100/1682 $\endgroup$ – Adam Davis Apr 9 '15 at 19:58
  • $\begingroup$ I'm a bit unclear on the uniqueness wording. Are we guaranteed that the original sudoku is uniquely solvable? $\endgroup$ – xnor Apr 9 '15 at 22:01
  • 5
    $\begingroup$ @xnor The original sudoku is already completely solved! So it is by definition a unique solution! $\endgroup$ – Falco Apr 10 '15 at 8:12

11 Answers 11

30
+150
$\begingroup$

Building off of Kevin's answer, I can get it to 33:

###|.#.|.#.
###|...|...
###|...|...
---+---+---
.#.|###|.#.
...|###|...
...|###|...
---+---+---
.#.|.#.|###
...|...|###
...|...|###

Keeping his assumption "that a completely empty 3x3 box can always be solved as long as there are four completely full 3x3 boxes in the same major row or column."

and we can solve for the single missing numbers in each square.

$\endgroup$
  • $\begingroup$ This looks like the best solution so far. Now the remaining question is whether this is optimal. $\endgroup$ – kasperd Apr 14 '15 at 18:11
  • 2
    $\begingroup$ It is easily shown that it is impossible to do better than 33 by starting out with the 27 squares masked out in Kevin's solution and masking out more squares after that. This is because masking out the 27 from Kevin's solution and 2 from any single of the remaining major 3x3 squares produce a potential ambiguous solution. But it still remains to be proven that it is impossible to do better than 33 in any other way. $\endgroup$ – kasperd Apr 14 '15 at 18:15
  • $\begingroup$ I'll award the bounty to you if nobody else has a better answer. $\endgroup$ – ghosts_in_the_code Sep 9 '15 at 9:52
  • $\begingroup$ Awesome, I hope nobody can beat it. Atleast I can't think of any other good way to go about it. $\endgroup$ – Spencerkatty Sep 10 '15 at 0:39
20
+500
$\begingroup$

I believe Spencerkatty's solution is maximal...

Any net may be constructed by choosing which of the 81 cells to mask. There are $\sum_{k=0}^{81}{81\choose k}=2^{81}$ ways to construct a net.

Rather than attempt to search this vast space we can attempt to partition the space in a way that will allow us to find out where we may need to look in more detail.

I will call a three by three square of chosen masks that could cover a block a "block-mask". There are $\sum_{k=0}^9{9\choose k}=2^9$ such block-masks.

Any net may instead be constructed by placing any one of these block-masks over each of the nine blocks in turn. $(2^9)^9 = 2^{81}$

Lopsy's post provided some base constraints - situations that certainly cause a potential ambiguity and hence any net containing a pattern of maskings breaking these constraints is not a valid net. I will label these constraints with lower case letters and further constraints either implied by these or via observation of block-mask properties with numbers. Changing slightly from Lopsy's post I will refer to horizontal lines of influence as "band-lines" and vertical ones as "stack-lines" and any such lines simply as "lines".

a) Asserting an already asserted line causes ambiguity.

(a) implies that: 1) Once a band (stack) contains a block-mask asserting all three band-lines (stack-lines) the other blocks in it's band (stack) may not assert any band-lines (stack-lines)

I will say that a band-line (stack-line) is "effectively-asserted" when the other two band-lines (stack-lines) in it's band (stack) are each asserted from different blocks (which are, necessarily, in it's band (stack)). This is the situation, prior to placing the third block-mask, in Lopsy's post where she says, "On the left, we have a block column with all three lines of influence exerted by pairs in three different boxes."

b) Asserting an effectively-asserted line causes ambiguity.

(a) and (b) imply that: 2) Once a band (stack) contains two block-masks each of which assert any band-lines (stack-lines) the third may not assert any band-lines (stack-lines)

Lopsy's observation "On the right, we have two lines of influence "reflecting" off a diagonal pair in the same box" also causes ambiguity. I will call the diagonal pair a "reflective-pair".

There are ${9\choose 2}=36$ possible pairs of maskings in a block-mask, 18 assert a line and the other 18 are "reflective-pairs", hence:

3) All block-masks containing more than one masking either assert at least one line or contain at least one reflective pair.

I will call any pattern of maskings causing ambiguity due to the presence of reflective-pairs a "reflective-path".

c) Completing a reflective-path causes ambiguity.

Lopsy's example of a reflective-path is only one case.

A reflective-path exists not only when the crossing lines are both asserted but also when either, or both, are effectively-asserted, for example here a reflective-pair across two effectively asserted lines causes ambiguity:

...|...|...    ...|...|...    ...|...|...
...|...|.##    ...|...|.12    ...|...|.21
...|...|...    ...|...|...    ...|...|...
---+---+---    ---+---+---    ---+---+---
...|...|##.    ...|...|12.    ...|...|21.
...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...
---+---+---    ---+---+---    ---+---+---
...|.#.|#..    ...|.1.|2..    ...|.2.|1..
..#|.#.|...    ..1|.2.|...    ..2|.1.|...
..#|...|..#    ..2|...|..1    ..1|...|..2

It is possible to create a longer reflective-paths between two asserted or effectively-asserted lines, so long as the maskings only ever occupy zero or two cells per block, zero or two cells per row, and zero or two cells per column, for example here is a double-reflection between two effectively-asserted lines:

...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...
---+---+---    ---+---+---    ---+---+---
#..|...|#..    2..|...|1..    1..|...|2..
...|#..|..#    ...|1..|..2    ...|2..|..1
#..|#..|...    1..|2..|...    2..|1..|...
---+---+---    ---+---+---    ---+---+---
...|.#.|#..    ...|.1.|2..    ...|.2.|1..
..#|.#.|...    ..1|.2.|...    ..2|.1.|...
..#|...|..#    ..2|...|..1    ..1|...|..2

A chain of reflections may also create a circular reflective-path, although this probably wont be required to show if there are or are not valid nets with greater than 33 maskings. Such circular paths only cause ambiguity when one traversal of the circuit does not invert the polarity of the pair (or, equivalently, if the sum of the slopes of the reflective-pairs is zero), for example:

...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...
---+---+---    ---+---+---    ---+---+---
...|#..|#..    ...|1..|2..    ...|2..|1..
...|...|...    ...|...|...    ...|...|...
...|.#.|..#    ...|.2.|..1    ...|.1.|..2
---+---+---    ---+---+---    ---+---+---
...|.#.|..#    ...|.1.|..2    ...|.2.|..1
...|...|...    ...|...|...    ...|...|...
...|#..|#..    ...|2..|1..    ...|1..|2..

but not, for example, these ones (following a pair through one traversal will swap the positions; or the sum of the slopes are non-zero):

...|...|...    ...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...    ...|...|...
---+---+---    ---+---+---    ---+---+---    ---+---+---
...|#..|..#    ...|#..|#..    ...|#..|#..    ...|.#.|..#
...|...|...    ...|...|...    ...|...|...    ...|...|...
...|.#.|#..    ...|.#.|..#    ...|.#.|..#    ...|#..|#..
---+---+---    ---+---+---    ---+---+---    ---+---+---
...|.#.|..#    ...|.#.|#..    ...|#..|..#    ...|#..|..#
...|...|...    ...|...|...    ...|...|...    ...|...|...
...|#..|#..    ...|#..|..#    ...|.#.|#..    ...|.#.|#..

(1), (3) and (c) imply that: 4) Once a block has a block-mask in it's band that asserts all three band-lines and a block-mask in it's stack that asserts all three stack-lines then it may not be masked by a block-mask containing more than one masking.

(2), (3) and (c) imply that: 5) Once a block has two block-masks in it's band (stack) each of which assert any band-lines (stack-lines), and either two block-masks in it's stack (band) each of which assert any stack-lines (band-lines) or a block-mask in it's stack (band) which asserts all three stack-lines (band-lines) then it may not be masked by a block-mask containing more than one masking.

If we inspect the block-masks containing exactly three maskings we may observe that 27 assert no band-lines and 27 assert no stack-lines, and furthermore that: 6) All block-masks that contain three maskings which do not assert any band-lines (stack-lines) either assert or reflect onto every stack-line (band-line)

(1), (6) and (c) imply that: 7) Once a block has a block-mask in it's band (stack) that asserts all three band-lines (stack-lines) and a block-mask in it's stack (band) that asserts any stack-lines (band-lines) it may not be masked by a block-mask containing more than two maskings.

(2), (6) and (c) imply that: 8) Once a block has two block-masks in it's band (stack) each of which assert any band-lines (stack-lines) and a block-mask in it's stack (band) that asserts any stack-lines (band-lines) it may not be masked by a block-mask containing more than two maskings.

There are nine possible crossings of lines in a block-mask, each of which has two associated reflective-pairs; if a block-mask does not assert either line or contain either of these reflective-pairs then it contains at most four maskings, therefore: 9) Once a block has a block-mask in it's band that asserts any band-line and a block-mask in it's stack that asserts any stack-line it may not be masked by a block-mask containing more than four maskings.

Upon further inspection of the domain of block-masks it may be observed that: 10) All block-masks containing at least seven maskings assert all three band-lines and all three stack-lines; 11) All block-masks containing at least six maskings assert all three lines in one direction and at least one line in the other; 12) There are block-masks containing five maskings that assert only one line in each direction. 13) All block-masks containing at least four maskings assert at least one line in each direction.

So, if we wish to place a block-mask with at least some number of maskings we necessarily assert some minimum number of lines in each of the two directions:

minimum maskings  minimal assertions
       9               3, 3
       8               3, 3
       7               3, 3
       6               1, 3
       5               1, 1
       4               1, 1
       3               0, 0
       2               0, 0
       1               0, 0
       0               0, 0

When placing a block-mask we are constrained to some maximum number of maskings by the combinations of currently placed block-masks in the block's band and stack:

     stack blocks asserting: 0 & 0  0 & 1  0 & 3  1 & 1
band blocks asserting:
                     0 & 0     9      6      3      3      
                     0 & 1     6      4      2      1                       
                     0 & 3     3      2      1      1
                     1 & 1     3      1      1      1

This analysis ignores the effects of blocks asserting two band-lines or two stack-lines and the specifics of which lines in particular are asserted, but the maximums still hold since asserting more lines for a block never allows us to use more maskings in it's block-mask.

Now, rather than excluding specific nets due to them either causing ambiguity, or not containing enough maskings - we may instead exclude nets of certain forms due to them either causing ambiguity or not being able to contain enough maskings.

Note that any valid net is also valid under any combination of permutations of: bands, stacks, in-band rows, and in-stack columns - since if it were not then a sudoku causing ambiguity in the permuted net could be transformed inversely (which is also necessarily a valid soduku) to cause ambiguity in the original net.

When implementing the search, to avoid isomorphisms, we can first place the main diagonal from top-left to bottom-right such that no placed block-mask has maximal masking greater than the previous one placed (since we could permute bands) and then place two more block-masks completing a second diagonal (e.g. place middle-right and bottom-centre, completing a second diagonal with top-left) such that this second diagonal does not maximally mask more than the main diagonal (since we could permute stacks). Furthermore we should only place a main diagonal if it may contain more than 11 maskings - since we aim to find solutions where the total is greater than 33 and therefore at least one positive diagonal must contain more than 33/3 (the same would be true of any partition into three sets of size three including stacks, bands, and negative diagonals).

Running a search starts starts like so:

                     3                  3                  3
  9   9   9         393  3   3         393  1   3         393  1   1
                     3                  3                  3
                                            3                  3  
  9   9   9          3   9   9          1  393  3          1  393  1
                                            3                  3  
                                                                   3
  9   9   9          3   9   9          3   3   9          1   1  393
                                                                   3

max:  81                 57                 41                  33

and yields a single form we need to investigate:

  3   0   0
 393 010 030
  3   0   0

  0   3   0
 010 393 030
  0   3   0

  0   0   0
 030 030 030
  0   0   0

This has a maximal masking of 35.

If a nine were reduced to an eight that block-mask would still assert all three lines in both directions.

Top-right and middle-right both have all their band-lines asserted, so by (1) may not assert any band-lines; and by (7), if one of them asserts any stack-lines the other may only contain a maximum of two maskings.

Similarly bottom-left and bottom-centre have all their stack-lines asserted, so by (1) may not assert any stack-lines; and by (7), if one of them asserts any band-lines the other may only contain a maximum of two maskings.

So, to achieve greater than 33 at least one of these pairs of blocks would need to contain a block-mask containing three maskings which asserts no lines.

However, by (3), (6) and (c), the other of the pair would be reduced to only allowing one masking - here are two (of the 18 ambiguous cases) for each of three of the (six) ways we could place top-right.

..#|...|#..    ..#|...|#..    ..!|...|..!    ..!|...|..!    ..#|...|#..    ..#|...|#..
..!|...|..!    ..!|...|..!    ..#|...|#..    ..#|...|#..    ..!|...|.!.    ..!|...|.!.
..!|...|.!.    ..!|...|.!.    ..!|...|.!.    ..!|...|.!.    ..!|...|..!    ..!|...|..!
---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---
...|!..|.!.    ...|!..|..!    ...|!..|.!.    ...|!..|..!    ...|!..|.!.    ...|!..|..!
...|!..|..!    ...|!..|.!.    ...|!..|..!    ...|!..|.!.    ...|!..|..!    ...|!..|.!.
...|#..|...    ...|#..|...    ...|#..|...    ...|#..|...    ...|#..|...    ...|#..|...
---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---
...|...|...    ...|...|...    ...|...|...    ...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...    ...|...|...    ...|...|...    ...|...|...
...|...|...    ...|...|...    ...|...|...    ...|...|...    ...|...|...    ...|...|...

The maximum achievable across each of these two pairs of blocks is now four rather than six reducing this form's maximal masking to 33 (without even needing to consider bottom-right).

Hence, Spencerkatty's solution is maximal.

python code for the search:

from copy import deepcopy
from itertools import product

# lookups for the maximal masking possible due to crossing of band-line assertions and stack-line assertions from two blocks.
CONSTRAIN_MASKINGS = [[9, 6, 6, 3], [6, 4, 4, 2], [6, 4, 4, 2], [3, 2, 2, 1]]

# lookup for maximal band-line and stack-line assertions that may be made given a crossing of band-line assertions and stack-line assertions from two blocks.
CONSTRAIN_ASSERTIONS = [[(3, 3), (3, 1), (3, 1), (0, 0)], [(1, 3), (1, 1), (1, 1), (0, 0)], [(1, 3), (1, 1), (1, 1), (0, 0)], [(0, 0), (0, 0), (0, 0), (0, 0)]]


class BlockMaskCategory:

    def __init__(self):
        self.isPlaced = False
        self.bandAssertions = 3
        self.stackAssertions = 3
        self.maxMaskings = 9

    def __repr__(self):
        return '''
  {0} 
 {1}{2}{1}
  {0} '''.format(not self.isPlaced and ' ' or self.stackAssertions, not self.isPlaced and ' ' or self.bandAssertions, self.maxMaskings)

    def constrain(self, othersInBand, othersInStack):
        inBandPlaced = [o.bandAssertions for o in othersInBand if o.isPlaced] 
        inStackPlaced = [o.stackAssertions for o in othersInStack if o.isPlaced]
        inBandAsserting = [a for a in inBandPlaced if a]
        inStackAsserting = [a for a in inStackPlaced if a]
        if (len(inBandAsserting) == 2 or 3 in inBandAsserting) and (len(inStackAsserting) == 2 or 3 in inStackAsserting):
            maxMaskings = 1
            bandAssertions = 0
            stackAssertions = 0
        elif inStackAsserting and (len(inBandAsserting) == 2 or 3 in inBandAsserting):
            maxMaskings = 2
            bandAssertions = 0
            stackAssertions = 0
        elif inBandAsserting and (len(inStackAsserting) == 2 or 3 in inStackAsserting):
            maxMaskings = 2
            bandAssertions = 0
            stackAssertions = 0
        else:
            if len(inBandAsserting) == 2:
                maxMaskings = 3
                b = 3
                s = 0
            elif len(inStackAsserting) == 2:
                maxMaskings = 3
                b = 0
                s = 3
            else:
                maxMaskings = 9
                b = 0
                s = 0
            for bandAssertions, stackAssertions in product(inBandPlaced or [0], inStackPlaced or [0]):
                m = CONSTRAIN_MASKINGS[bandAssertions][stackAssertions]
                if m < maxMaskings:
                    maxMaskings = m
                    b = bandAssertions
                    s = stackAssertions
            bandAssertions, stackAssertions = CONSTRAIN_ASSERTIONS[b][s]

        if self.isPlaced:
            if self.maxMaskings > maxMaskings:
                return False
        else:
            self.maxMaskings = maxMaskings
            self.bandAssertions = bandAssertions
            self.stackAssertions = stackAssertions
        return True

    def choices(self):
        if self.maxMaskings > 6:
            return [(3, 3, self.maxMaskings), (3, 1, 6), (1, 3, 6), (1, 1, 5), (1, 1, 4), (0, 0, 3), (0, 0, 2), (0, 0, 1)]
        if self.maxMaskings == 6:
            return [(self.bandAssertions, self.stackAssertions, self.maxMaskings), (1, 1, 5), (1, 1, 4), (0, 0, 3), (0, 0, 2), (0, 0, 1)]
        if self.maxMaskings > 3:
            return [(1, 1, m) for m in range(self.maxMaskings, 3, -1)] + [(0, 0, 3), (0, 0, 2), (0, 0, 1)]
        return [(0, 0, m) for m in range(self.maxMaskings, 0, -1)]


class Net:

    def __init__(self):
        iters = tuple(range(3))
        self.blocks = [[BlockMaskCategory() for stack in iters] for band in iters]
        self.otherStackIndexes = [tuple((stack - 1, stack - 2)) for stack in iters]
        self.otherBandIndexes = [tuple((band - 1, band - 2)) for band in iters]
        self.othersInBand = [[[self.blocks[band][si] for si in self.otherStackIndexes[stack]] for stack in iters] for band in iters]
        self.othersInStack = [[[self.blocks[bi][stack] for bi in self.otherBandIndexes[band]] for stack in iters] for band in iters]

    def __repr__(self):
        return '\n'.join(['\n'.join([''.join(s) for s in zip(*[blockMask.__repr__().split('\n') for blockMask in band])]) for band in self.blocks]) + '    = {0}\n'.format(self.maxMaskings())

    def maxMaskings(self):
        return sum(sum(blockMask.maxMaskings for blockMask in band) for band in self.blocks)

    def update(self, band, stack, bandAssertions, stackAssertions, maxMaskings, remove=False):
        block = self.blocks[band][stack]
        block.bandAssertions = bandAssertions
        block.stackAssertions = stackAssertions
        block.maxMaskings = maxMaskings
        block.isPlaced = not remove
        for otherInBand, si in zip(self.othersInBand[band][stack], self.otherStackIndexes[stack]):
            if not otherInBand.constrain(self.othersInBand[band][si], self.othersInStack[band][si]):
                return False
        for otherInStack, bi in zip(self.othersInStack[band][stack], self.otherBandIndexes[band]):
            if not otherInStack.constrain(self.othersInBand[bi][stack], self.othersInStack[bi][stack]):
                return False
        return True

    def iterSolutions(self, verbose=False):
        queue = [(1, 0), (0, 1), (2, 0), (0, 2), (2, 1), (1, 2), (2, 2), (1, 1), (0, 0)]
        return self._iterSolutions(queue, 0, verbose)

    def _iterSolutions(self, queue, last, verbose):
        if not queue:
            if verbose:
                print("** found a solution, yielding it...")
            yield deepcopy(self)
            return
        if len(queue) == 6:
            if sum(self.blocks[i][i].maxMaskings for i in (0, 1, 2)) <= 11:
                if verbose:
                    print("symmetry restriction: main diagonal is below the average requirement")
                return
        elif len(queue) == 4:
            if sum(self.blocks[i][i].maxMaskings for i in (0, 1, 2)) < sum(self.blocks[b][s].maxMaskings for (b, s) in ((0, 0), (1, 2), (2, 1))):
                if verbose:
                    print("symmetry restriction: second placed diagonal is more maximally masking than the main diagonal")
                return
        cmpLast = 6 < len(queue) < 9
        band, stack = queue.pop()
        block = self.blocks[band][stack]
        bandAssertionsPrior = block.bandAssertions
        stackAssertionsPrior = block.stackAssertions
        maxMaskingsPrior = block.maxMaskings
        for bandAssertions, stackAssertions, maxMaskings in block.choices():
            if cmpLast and maxMaskings > last:
                if verbose:
                    print("symmetry restriction: main diagonal not in descending order; {0} > {1}".format(maxMaskings, last))
                continue
            if self.update(band, stack, bandAssertions, stackAssertions, maxMaskings):
                if verbose:
                    print("update to:")
                    print(self)
                if self.maxMaskings() > 33:
                    for solution in self._iterSolutions(queue[:], maxMaskings, verbose):
                        yield solution
                elif verbose:
                    print("dead end: {0} <= 33".format(self.maxMaskings()))
            elif verbose:
                print("Symmetry restriction: adding {0} (asserting {1} band-lines and {2} stack-lines) at band {3}, stack {4} would further constrain an already placed block-mask".format(maxMaskings, bandAssertions, stackAssertions, band, stack))
            if not self.update(band, stack, bandAssertionsPrior, stackAssertionsPrior, maxMaskingsPrior, True):
                raise RuntimeError("Failed to remove block-mask")
            # if verbose:
                # print("back track")
                # print(self)


if __name__ == "__main__":
    n = Net()
    for solution in n.iterSolutions():
        solution

python code for producing the block-mask domain so as to be able to investigate potential partitions: Note - a blockMask's representation shows lines asserted and maskings on the left, reflections with their polarities (an x being both) in the middle and reflections that matter on the right (since if a block mask asserts one of the crossing lines the reflection is of no consequence in the case of single reflections).

SIZE = 3
ITEMS = tuple(range(SIZE))
PAIRS = tuple((a, b) for a in ITEMS for b in ITEMS if a < b)
NO_MASKINGS = [[False for col in ITEMS] for row in ITEMS]
OPAQUE_CHARS = ('1', '#')
TRANSPARENT_CHARS = ('0', '.')

class BlockMask:

    def __init__(self, maskings=NO_MASKINGS):
        if isinstance(maskings, str):
            maskingChars = OPAQUE_CHARS + TRANSPARENT_CHARS
            vals = [maskingChar in OPAQUE_CHARS for maskingChar in maskings if maskingChar in maskingChars]
            if len(vals) != SIZE ** 2:
                raise ValueError("Expected 9 characters from OPAQUE_CHARS + TRANSPARENT_CHARS = {0} + {1}".format(OPAQUE_CHARS, TRANSPARENT_CHARS))
            vals = [[vals[SIZE * row + col] for col in ITEMS] for row in ITEMS]
        elif len(maskings) == SIZE ** 2:
            vals = [[maskings[SIZE * row + col] and True or False for col in ITEMS] for row in ITEMS]
        elif len(maskings) == SIZE:
            vals = []
            for bandMaskings in maskings:
                if len(bandMaskings) != SIZE:
                    raise ValueError("Got an Iterable of length {0} but one of it's members was not also of length {0}".format(SIZE))
                vals.append([masking and True or False for masking in bandMaskings])
        else:
            raise ValueError("Expected either a string representation, a flat Iterable of length {0}, or a nested Iterable length {1} containing Iterables of length {1}".format(SIZE ** 2, SIZE))

        assertsBandLines = set()
        for bandLine, (rowA, rowB) in enumerate(PAIRS):
            for col in ITEMS:
                if vals[rowA][col] and vals [rowB][col]:
                    assertsBandLines.add(bandLine)
                    break


        assertsStackLines = set()
        for stackLine, (colA, colB) in enumerate(PAIRS):
            for row in ITEMS:
                if vals[row][colA] and vals [row][colB]:
                    assertsStackLines.add(stackLine)
                    break

        reflectionsFromBandLines = [set() for band in ITEMS]
        reflectionsFromBandLinesExclusive = [set() for band in ITEMS]
        reflectionsBandLinesExclusive = set()
        reflectionsFromStackLines = [set() for stack in ITEMS]
        reflectionsFromStackLinesExclusive = [set() for band in ITEMS]
        reflectionsStackLinesExclusive = set()
        reflectionPolarities = {}
        reflectionPolaritiesExclusive = set()
        for bandLine, (rowA, rowB) in enumerate(PAIRS):
            excludedBandLine = bandLine in assertsBandLines
            for stackLine, (colA, colB) in enumerate(PAIRS):
                neg = vals[rowA][colA] and vals [rowB][colB]
                pos = vals[rowB][colA] and vals [rowA][colB]
                if neg or pos:
                    reflectionsFromBandLines[bandLine].add(stackLine)
                    reflectionsFromStackLines[stackLine].add(bandLine)
                    reflectionPolarities[(bandLine, stackLine)] = pos - neg
                    if not (excludedBandLine or stackLine in assertsStackLines):
                        reflectionsFromBandLinesExclusive[bandLine].add(stackLine)
                        reflectionsBandLinesExclusive.add(bandLine)
                        reflectionsFromStackLinesExclusive[stackLine].add(bandLine)
                        reflectionsStackLinesExclusive.add(stackLine)
                        reflectionPolaritiesExclusive.add((bandLine, stackLine, pos - neg))

        self.maskings = vals
        self.nMaskings = sum(sum(row) for row in vals)
        self.assertsBandLines = assertsBandLines
        self.assertsStackLines = assertsStackLines
        self.reflectionsFromBandLines = reflectionsFromBandLines
        self.reflectionsFromBandLinesExclusive = reflectionsFromBandLinesExclusive
        self.reflectionsBandLinesExclusive = reflectionsFromBandLinesExclusive
        self.reflectionsFromStackLines = reflectionsFromStackLines
        self.reflectionsFromStackLinesExclusive = reflectionsFromStackLinesExclusive
        self.reflectionsStackLinesExclusive = reflectionsStackLinesExclusive
        self.reflectionPolarities = reflectionPolarities
        self.reflectionPolaritiesExclusive = reflectionPolaritiesExclusive

    def __repr__(self):
        r = '\n '
        rla = ' '
        for y in ITEMS:
            rla += y in self.assertsStackLines and '|' or ' '
        r += rla + '\n '
        for x in ITEMS:
            bla = x in self.assertsBandLines and '-' or ' '
            r += bla
            for y in ITEMS:
                r += self.maskings[x][y] and '#' or '.'
            r += bla + '   '
            for y in ITEMS:
                r += y in self.reflectionsFromBandLines[x] and ('x', '+', '-')[self.reflectionPolarities[(x, y)]] or '.'
            r += '    '
            for y in ITEMS:
                r+= y in self.reflectionsFromBandLinesExclusive[x] and ('x', '+', '-')[self.reflectionPolarities[(x, y)]]  or '.'
            r += '\n '
        r += rla + '\n'
        return r


def blockMaskIter(nMaskings, cur=[0 for i in range(9)]):
    if nMaskings < 1:
        yield BlockMask(cur)
        return
    if 1 in cur:
        s = 9 - cur[::-1].index(1)
    else:
        s = 0
    for pos in range(s, 10 - nMaskings):
        next = cur[:]
        next[pos] = 1
        for mask in blockMaskIter(nMaskings - 1, next):
            yield mask

def domainIter():
    for nMaskings in range(9, -1, -1):
        for blockMask in blockMaskIter(nMaskings):
            yield blockMask
$\endgroup$
  • $\begingroup$ @JonathanAllan wow that answer... SUPER! $\endgroup$ – RudolfJelin Apr 13 '16 at 17:25
  • 1
    $\begingroup$ What does it mean to "assert" a line? $\endgroup$ – 2012rcampion Apr 23 '16 at 17:21
  • $\begingroup$ @2012rcampion - As per Lopsy's post "exerted" (assert / activate / turn on). I shall define "Assert a line" here again for clarity... Assert (a line [of influence]) - During construction of a net the act of placing two maskings such that they reside within the same block and are horizontally or vertically adjacent. [block - one of the nine 3x3 areas marked out in the sudoku] $\endgroup$ – Jonathan Allan Apr 23 '16 at 22:08
  • $\begingroup$ The above is not quite accurate - "During construction of a net the act of placing two maskings such that they reside either within the same block and row or within the same block and column" (i.e. not necessarily directly adjacent). Lopsy's post gives pictures. $\endgroup$ – Jonathan Allan Apr 30 '16 at 8:04
13
$\begingroup$

I think you can do 27.

###|...|...
###|...|...
###|...|...
---+---+---
...|###|...
...|###|...
...|###|...
---+---+---
...|...|###
...|...|###
...|...|###

... Assuming that a completely empty 3x3 box can always be solved as long as there are four completely full 3x3 boxes in the same major row or column.

$\endgroup$
  • 2
    $\begingroup$ Your assumption is correct. Start with a solved sudoku, remove numbers from one 3x3 box, try to solve. Will be obvious that each number can only go in one spot. $\endgroup$ – Joel Rondeau Apr 9 '15 at 18:41
  • 1
    $\begingroup$ Your wording is a bit awkward. It sounds like you are saying it can be solved if 'there are four filled in 3x3 boxes in the same column or if there are four filled in 3x3 boxes in the same row'. I would rephrase it to say something more along the lines of 'when all four of the 3x3 boxes in the same row and column are completely filled'. Edit- Basically I think 'and' works better here than 'or' $\endgroup$ – Warlord 099 Apr 10 '15 at 14:12
5
$\begingroup$

Here's a glimmer of hope of actually proving a solution optimal. This answer proves an upper bound of $45$ covered cells and shows off techniques that might improve this bound.

A block means one of the nine outlined 3x3 subsquares. Consider what happens if we cover a pair of cells in the same block and the same row or column. This diagram has three examples. enter image description here

I've drawn in red lines of influence exerted by each pair. In lieu of a formal definition, let's prove a theorem.
Claim: Every possible line of influence can only be exerted once.
Proof: Suppose a line of influence is exerted twice. See the diagram:

enter image description here

The pairs exerting the line form a 2x2 box. If filled with [1,2,2,1], this box has two possible solutions. So the solution is ambiguous, which is not allowed. QED: each line of influence can only be exerted once.

Each block row and block column contains three possible lines of influence, one for each of the (3 choose 2) ways to choose two rows/columns. So there are 18 lines of influence total.

This already gives an upper bound. One can check with casework that a block containing $n$ covered cells must exert at least $n-3$ lines of influence. Therefore, there are at most $18+3\times9=45$ covered cells.

But I'm sure we can extend these techniques to do even better. Consider the following diagram: enter image description here

It shows off two illegal configurations. On the left, we have a block column with all three lines of influence exerted by pairs in three different boxes. If filled with [1,2,1,2,1,2], this is ambiguous. So, this can never happen. On the right, we have two lines of influence "reflecting" off a diagonal pair in the same box. Again, if filled with [1,2,1,2,1,2], this is ambiguous, so it can never happen.

I'm sure the $45$ bound can be improved by taking these forbidden patterns into account, possibly using a small amount of casework. But can it be improved all the way to $33$?

$\endgroup$
4
$\begingroup$

To start it off with a very low-scoring guess, I can get at least 21. The format is:

.#.|...|...
###|.#.|.#.
.#.|...|...
---+---+---
...|.#.|...
.#.|###|.#.
...|.#.|...
---+---+---
...|...|.#.
.#.|.#.|###
...|...|.#.

The six blocks that are alone in their 3x3 square can automatically be filled in. Next, each of the blocks in the cross shape can be filled in as they are the only blocks in their respective row or column. Finally, the remaining 3 squares can be filled in.

$\endgroup$
  • $\begingroup$ @Spencer has an improvised solution of yours. $\endgroup$ – ghosts_in_the_code Apr 14 '15 at 5:20
4
$\begingroup$

Lemma 1: http://pastebin.com/X0uqZMRm
Lemma 2: http://pastebin.com/rcHX6JLk

These two lemmas prove that if we try to build on Kevin's answer, we cannot do better than Spencer's answer. This is because no matter what way we cover two cells in the same empty block, we will create one of the shapes prohibited by the lemmas.

If we want to beat 33, we need a new strategy. It's possible to block 18 cells of a chute without creating any bad rectangles or half-bad trapezoids, so maybe that could be useful. It also might help to find other unsolvable shapes.

$\endgroup$
  • $\begingroup$ Your 18 cells has it's own issue. Take the first column of each square and put 1,2 in the 2 blocked cells. All 3 can be swapped. However, +1 for the proper explanation of Kevin's answer, which I still believe to be best. $\endgroup$ – Joel Rondeau Apr 14 '15 at 17:47
  • $\begingroup$ @JoelRodeau, Yes, you're right. That's another unsolvable shape then.. I also believe that Spencer's answer is the best possible. $\endgroup$ – Ben Frankel Apr 14 '15 at 17:53
  • $\begingroup$ @Ben You can get 100 rep if you prove it mathematically. $\endgroup$ – ghosts_in_the_code Sep 9 '15 at 9:54
3
$\begingroup$

I think I can do 35 (building on 33 solution above). Logic-as long as unknowns in the (r1, C2) square doesn't share the unknown values in same row/col with (r1, c3) and (r3,c2), the indeterminism of these 2 unknowns can be resolved when the (r1, c1) square is done. Same applies to square (r2, c3).

###|...|..#
###|...|...
###|##.|...
---+---+---
#..|###|...
...|###|..
...|###|##.
---+---+---
.#.|...|###
...|...|###
...|..#|###
$\endgroup$
  • $\begingroup$ Can the (1,1) square be solved before filling the (1,2)? $\endgroup$ – JiK Apr 10 '15 at 7:32
  • $\begingroup$ I don't think this net works. Unfortunately, comment formatting doesn't let me post the counterexample, but there are simple cases where you can switch the contents of the two cells in the upper middle block, change a few other cells' contents to match, and wind up with another solution to the puzzle. $\endgroup$ – user2357112 Apr 10 '15 at 9:45
  • 7
    $\begingroup$ Actually, here, have a Pastebin. That link has the counterexample. $\endgroup$ – user2357112 Apr 10 '15 at 9:48
  • 2
    $\begingroup$ Looking at the counterexample from @JiK, column 5, rows 2-3 and column 7, rows 2-3 show that putting the unknowns into a single row/column doesn't fix this. The updated solution also isn't valid. $\endgroup$ – Joel Rondeau Apr 10 '15 at 21:34
  • 3
    $\begingroup$ Your current solution contains a 2x2 box straddling a line. If this box is filled with 1,2,2,1, then the solution is totes not unique. $\endgroup$ – Lopsy Apr 11 '15 at 6:13
2
$\begingroup$

At least 64 - if the question was completely different!

In my haste I totally misread the question and rushed off to find supporting info for what I knew was the minimum number of clues in a sudoku. That is NOT what is being asked, but I'll leave this here to prevent any other fools making the same mistake (and maybe because someone might find it interesting or useful.)

Various websites generate sudoku puzzles and 17 clues is the smallest number I have seen from my (admittedly brief) search.

The best reference I found on solving sudoku including the details of various strategies employed is http://www.sudokuwiki.org/sudoku.htm

It includes a step by step solution to any puzzle you provide as well a generating puzzle that require a range of strategies for their solution.

At least one puzzle exists with 17 clues (64 blank squares) that can be solved using only the most basic strategy.

....41...
.6....2..
.........
32.6.....
....5..41
7........
...2..3..
.48......
5.1......

Puzzles with a smaller number of clues may exist that can be solved by a brute search algorithm although it is a search method that may present multiple possible solutions given that such puzzles are ambiguous due to their small amount of starting information.

In 2012 a team from University College Dublin published the results of search that took the best part of a year, announcing that no 16 clue solvable sudoku exists. Their method iterated all possible grids searching for one which was could be solved. This is not what mathematicians like to describe as a proof although in does constitute a definitive answer.

http://www.technologyreview.com/view/426554/mathematicians-solve-minimum-sudoku-problem/

I believe at this time no such proof exists.

$\endgroup$
  • 3
    $\begingroup$ You're solving the wrong question - you're solving the question of 'what is the fewest number of clues a sudoku can possibly have?' rather than 'what is the smallest grid that allows you to solve any (legal) sudoku given the clues on that grid?'. $\endgroup$ – Steven Stadnicki Apr 14 '15 at 16:51
2
$\begingroup$

I could be completely wrong, still i'm posting this (possible) solution which i have got after hit and trial and messing with the grid here and there :P


##.|#.#|#.#
.##|.##|.##
#.#|#.#|##.
---+---+---
###|###|#.#
.#.|#.#|.#.
#.#|###|###
---+---+---
.##|#.#|#.#
##.|##.|##.
#.#|#.#|.##

! That would be 55 blocks

To verify, I took a few solved sudoko's and used a sudoku solver to check if they have a unique solution.

As far as my technique goes... there is a better solution... I'll try that only if the one I've provided is correct

Then again... I don't have a proof... but go ahead try it :)

$\endgroup$
  • 3
    $\begingroup$ This doesn't work. It contains many non-unique subconfigurations, such as a 2x2 square straddling a line. $\endgroup$ – Lopsy Apr 15 '15 at 19:40
1
$\begingroup$

Well i dont want to be abnoxious but i dont think kevin's answer can work out neither the enhaced grid do.

  • its not about uniqueness but it is all about validity of solution .

this is a counter-example:

###|123|456
###|456|789
###|789|123
---+---+---
147|###|562
258|###|394
369|###|817
---+---+---
471|562|###
582|394|###
693|817|###
  • this grid looks resolvable from the first look-at but it isnt when you try to solve it.

minimally the problem can be solved with 27 blocks in independant places

how independant ?

blocks are dispersed enough from a one whole line or 3X3 square like this:

.##|..#|...
##.|...|...
#.#|#..|..#
---+---+---
#..|.##|...
...|##.|.#.
...|#.#|#..
---+---+---
..#|...|.##
.#.|...|##.
...|.#.|#.#

proof of uniqueness:

lets denote a group $(L, *)$ where $L$ is the set of $9$ random chosen primes '*' is ordinary multiplication.

for $n$ variables , we need $n$ equations applied on different vars to solve the system . which is the case of 18 lines + 9 squares.

for exple:

$$a*b*c=30$$

$$a*b=15$$

$$b*c=10$$

this system has unique solution:

$(15/b)*b*(10/b)=30$

$b=150/30=5$

-notes:

  • to point it out again , there s no two equations applied on same variables, neither a cyclic equation without variables like : $\prod_9=\prod_9$ to guarantee system functioning.

  • There s difinitely soduko with more blocks if a such commutative ring :(L,+,°) can be found .

$\endgroup$
  • 2
    $\begingroup$ Your example is not valid. In the top-left block, the "1" must go in the middle cell. Likewise, the "2" and the "3" must also go in that same cell. $\endgroup$ – user3294068 Apr 21 '15 at 16:22
  • $\begingroup$ i said this example looks regular from first look, but u fail when u try to solve it. idk whether the op considered that not all net-grids are solvable $\endgroup$ – Abr001am Apr 21 '15 at 19:12
  • $\begingroup$ The op did say that we're only interested in valid sudoku arrangements. We need our mask to show through enough cells that we can differentiate between any two valid arrangements. $\endgroup$ – user3294068 Apr 21 '15 at 19:36
  • $\begingroup$ ah, ok i thought the grid is filled with randomly béfore the cross-cells would be solved with unique values $\endgroup$ – Abr001am Apr 21 '15 at 19:50
0
$\begingroup$

The most cells that can be covered up are 45.

Proof:

First, let's define some variables:
N is the number of squares the sudoku side is long,
X is the number of covered cells,
O is the number of uncovered cells.

For N = 1, we get a "sudoku" of 1x1 cells. A grid for it can cover up all the squares (1), and it'll still have 1 unique solution.

For N = 2, we get a mini-sudoku with 4 squares. If we cover up all but one cell, we still have one solution.

For N = 3 (9-square sudoku), we can cover up at most 6 cells. Example:

1 | _ | 3  
 - + - + -  
_ | _ | _  
- + - + -  
_ | 3 | _

( And 63 other possible ways of covering up 6 cells so that the sudoku has 1 solution.)

Let's make a table:

N | 1 | 2 | 3  
- - - - - - - -  
X | 1 | 3 | 6   
- - - - - - - -  
O | 0 | 1 | 3  

With a bit of calculation, we get a function:

X = (N*(N+1)/2  

And since O = N*N - X,

O = (N*(N-1))/2  

For N = 9, a full sudoku, we get that

X = (9*(9+1))/2 = 45

(and O = 36)

45 cells at most can be covered up, and 36 at least must be visible.

Q.E.D.

$\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.