Hidden Tuples

If you are going to write a Sudoku solver, write a brute force, depth first search. You can get it running fast enough.

But what if you couldn’t? What if the puzzles were so big that solving them by brute force was not computationally feasible? A Sudoku puzzle is build on a basis of 3: The Blocks are 3X3, there are 3X 3 of them in the puzzle, and the rows and columns are are 9 cells (3 * 3) long. This approach scales up. If you were to do a basis of 4, you could use the Hexadecimal digits, and have 16 X 16 puzzles.

A Basis of K leads to a puzzle size of (K^4). The basis can be any integer. A Basis of 10 would lead to a puzzle size of 1000.

The Sudoku puzzle shows exponential growth. https://en.wikipedia.org/wiki/Combinatorial_explosion#Sudoku

What could you do for a complex puzzle? Use heuristics to reduce the problem set to the point where a the brute force algorithm can complete.

One of the most powerful heuristics to use is the Hidden Tuples algorithm, and I recently went through the process of implementing it. I’ll post the code, but first, a bit on notation.

I am going to use the term house to refer to a row, block, or column. It is a generic term to mean any one of them, or, when I say houses, all three of them.

The simplest format for storing a Sudoku puzzle is as a string. You can mark the solved cells with a single digit, and an unsolved cell as a blank. However, to calculate operations on a column you need to do the math to find the column’s location. It turns out that most programming languages do exactly this for two dimensional arrays. So the logical way to store it in memory while working on the puzzle is as a 2 D array.

Thus a puzzle defined like this:

sample_puzzle = ("800000000" +
                 "003600000" +
                 "070090200" +
                 "050007000" +
                 "000045700" +
                 "000100030" +
                 "001000068" +
                 "008500010" +
                 "090000400")

Would be layed out logically like this:

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

Another way of interpreting the blank cell is that it can potentially be any value, 1-9 for a Basis of 3, 1 through Basis^2 for larger puzzles. However, those blank cells can be rewritten as arrays of digits. You can then remove each digit once it is no longer viable. Thus, a solved cell is one that contains one digit in it, and an unsolved cell contains more than one digit. This is one of the techniques used when solving a puzzle by hand. But when solving it computationally, it is actually easier to go ahead an expand out a blank board to be filled with:

[‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9’]

Now, when you write your puzzle on the board, as you write each solved digit into its location you also go ahead and remove that digit from all of the other cells in the same column, row, and block. Thus, a partial solution looks like this:

┏━━━━━━━━━┯━━━━━━━━━┯━━━━━━━━━┳━━━━━━━━━┯━━━━━━━━━┯━━━━━━━━━┳━━━━━━━━━┯━━━━━━━━━┯━━━━━━━━━┓
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃    8    │   1246  │  24569  ┃   2347  │  12357  │   1234  ┃  13569  │   4579  │ 1345679 ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┠─────────┼─────────┼─────────╂─────────┼─────────┼─────────╂─────────┼─────────┼─────────┨
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃  12459  │   124   │    3    ┃    6    │  12578  │   1248  ┃   1589  │  45789  │  14579  ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┠─────────┼─────────┼─────────╂─────────┼─────────┼─────────╂─────────┼─────────┼─────────┨
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃   1456  │    7    │   456   ┃   348   │    9    │   1348  ┃    2    │   458   │  13456  ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┣━━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━╋━━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━╋━━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━┫
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃  123469 │    5    │   2469  ┃   2389  │   2368  │    7    ┃   1689  │   2489  │  12469  ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┠─────────┼─────────┼─────────╂─────────┼─────────┼─────────╂─────────┼─────────┼─────────┨
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃  12369  │  12368  │   269   ┃   2389  │    4    │    5    ┃    7    │   289   │   1269  ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┠─────────┼─────────┼─────────╂─────────┼─────────┼─────────╂─────────┼─────────┼─────────┨
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃  24679  │   2468  │  24679  ┃    1    │   268   │   2689  ┃   5689  │    3    │  24569  ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┣━━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━╋━━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━╋━━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━┫
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃  23457  │   234   │    1    ┃  23479  │   237   │   2349  ┃   359   │    6    │    8    ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┠─────────┼─────────┼─────────╂─────────┼─────────┼─────────╂─────────┼─────────┼─────────┨
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃  23467  │   2346  │    8    ┃    5    │   2367  │  23469  ┃    39   │    1    │   2379  ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┠─────────┼─────────┼─────────╂─────────┼─────────┼─────────╂─────────┼─────────┼─────────┨
┃         │         │         ┃         │         │         ┃         │         │         ┃
┃  23567  │    9    │   2567  ┃   2378  │  123678 │  12368  ┃    4    │   257   │   2357  ┃
┃         │         │         ┃         │         │         ┃         │         │         ┃
┗━━━━━━━━━┷━━━━━━━━━┷━━━━━━━━━┻━━━━━━━━━┷━━━━━━━━━┷━━━━━━━━━┻━━━━━━━━━┷━━━━━━━━━┷━━━━━━━━━┛

We can further reduce the above puzzle by running additional algorithms run against it. At the simplest, we can just search for and singletons: numbers that appear in only one cell in a house.

The most complex algorithm I have heard of people actually using is hidden tuple removal. I use the word tuple to cover the three lengths that are most valuable; pairs, triplets, and quads. A Hidden pair is a pair of digits that only exist in 2 cells in a house. When these are identified, you can remove any other numbers from the cell where the pair resides. More powerfully, you can extrapolate into the other houses; if both of those cells from a row or column reside in the same block, you can remove those two numbers from all of the other cells in that block.

When we scale this pattern up to the quad tuple, it gets even more powerful. See, no one cell needs to hold all four numbers. We just need 4 cells. These cells can contain other numbers, but the numbers in this set must be constrained to those four cells. Thus, if one cell has [1,2,8,9] another has [1,3,8,9] another has [2,3,4,8,9] a fourth has [4,8,9], and both 8 and 9 appear in other cells, we can define the tuple as [1,2,3,4] and remove the 8 and the 9 from all of these cells.

The algorithm is expensive. Basically, create an exhaustive list of sets, figure out which cells have a subset of that set, and then look for sets of the right length e.g. 4 for hidden quads.

def find_and_reduce_hidden_tuples(board, n):
    found = find_hidden_tuples(board, n)
    reduce_hidden_tuples(board, found, n)

First lets talk about finding the hidden tuples. Generate a map and look through it for sets of length 4.

def find_hidden_tuples(board, k):
    tuple_map = generate_hidden_tuple_map(board, k)
    found = dict()
    for (key, values) in tuple_map.items():
        if len(values) == k:
            found[key] = values
    return found

To Generate the map, we need to generate an exhausitive list of all the subsets, then iterate through each cell on the board. If a cell contains a non-null subset of the initial set, we add it to the potential matches.

def generate_hidden_tuple_map(board, k): tuples = gen_subsets(common.FULL_SET, k) tuple_map = dict() for cell in BoardCellIterator(board): if len(cell.get()) == 1: continue for tuple in tuples: for digit in tuple: if digit in cell.get(): append_to_tuple_map( tuple_map, cell.r, cell.c, tuple, board) break return tuple_map

To create the exhaustive list of sets:

# select k from n.  Number of elements will be
# n!/(k! - (n-k)!)
def gen_subset_indexes(n, k):
    subsets = []
    max = 1 << n
    for i in range(max):
        indexes = []
        for x in range(9):
            if (i >> x) & 1 == 1:
                indexes.append(x)
        if len(indexes) == k:
            subsets.append(indexes)
    return subsets
 
 
# generates all subsets of length k
def gen_subsets(allset, k):
    subsets = []
    indexes = gen_subset_indexes(len(allset), k)
    for i in indexes:
        subset = []
        for j in i:
            subset.append(allset[j])
        subsets.append(subset)
    return subsets

I am kind of proud of this code. It uses the fact that a subset can be implemented as a bit map, a technique I remember learning from Programming Pearls. Basically, look for (9 bit long) bytes where the there number of bits set is 4. Those bits map to the indexes of the subset characters…which happen to be their digit values as well.

Once we have all of the subsets, we look for the matches. These will go in a map. I created a custom type for the key for this map:

class TupleKey:
    def __init__(self, house, location, tuple):
        self.house = house
        self.location = location
        self.tuple = tuple
 
    def __eq__(self, other):
        if not isinstance(other, TupleKey):
            return False
        return ((self.house == other.house) and
                (self.location == other.location) and
                (self.tuple == other.tuple))
 
    def __hash__(self):
        return hash(self.__str__())
 
    def __repr__(self):
        return self.__str__()
 
    def __str__(self):
        return "%s %s %s" % (self.house, self.location, self.tuple)

This key is tuned to how we need to look up the value at the end; it contains all of the information that makes it unique, and it provides a way to find the value in the overall board. Note that the location field is tuned to the house; if the house is a row, we store the row, if it is a block, we store a composite value that uniquely identifies the block.

Appending it to the map involves ignoring singletons; these are cells that are already solved, and thus remove the tuple in question from being a potential match.

def append_to_tuple_map(tuple_map, r, c, tuple, board):
    def no_singletons(board, itr):
        ok = True
        for cell in itr:
            if not ok:
                break
            for digit in tuple:
                if cell.get() == digit:
                    ok = False
                    break
        return ok
 
    tuple_str = ""
    for i in tuple:
        tuple_str += i
    keys = []
 
    if no_singletons(board, RowCellIterator(board, r)):
        keys.append(TupleKey('r', r, tuple_str))
 
    if no_singletons(board, ColCellIterator(board, c)):
        keys.append(TupleKey('c', c, tuple_str))
 
    if no_singletons(board, BlockCellIterator(board, r, c)):
        keys.append(TupleKey('b', block_for_rc(r, c), tuple_str))
 
    for key in keys:
        if tuple_map.get(key) is None:
            tuple_map[key] = []
        tuple_map[key].append((r, c))
 
 
def block_for_rc(row, col):
    sg_row = math.floor(row / common.BASIS)
    sg_col = math.floor(col / common.BASIS)
    return [sg_row, sg_col]

Now that we have a map that contains all the hidden tuples, we reduce the cells affected by each hidden tuple:

def reduce_hidden_tuples(board, found, n):
    for (key, cells) in found.items():
        digits_in = key.tuple
        digits_out = common.FULL_SET
        for c in digits_in:
            digits_out = digits_out.replace(c, '')
 
        itr = None
        if key.house == 'b':
            itr = BlockCellIterator(board, cells[0][0], cells[0][1])
        elif key.house == 'r':
            itr = RowCellIterator(board, cells[0][0])
        elif key.house == 'c':
            itr = ColCellIterator(board, cells[0][1])
        else:
            assert(itr is not None)
 
        for cell in itr:
            ct = (cell.r, cell.c)
            if ct in cells:
                cell.set(cell.remove_from_set(digits_out))
            else:
                cell.set(cell.remove_from_set(digits_in))

The digits_out removal is, I think, ineffectual. I convinced myself that I needed it when I wrote it, but I am fairly certain that the cells out side of the found list will never contain those numbers.

I am not certain if it makes sense to run this algorithm unless it is coupled with other techniques that make use of the small reductions found by it to do larger reductions on the whole board.

If we go back to our Sudoku puzzles with basis > 3, the tuples found by this technique can be larger than 4. I suspect that there is a relationship of the the nature Basis+1. Thus, for our basis of 10, we probably could expect to find matches with a tuple size of 11, slightly greater than one in ten cells in a house.

But this algorithm is expensive. The tuple map grows with the number of elements on the board. I’ve not calculated the growth, but I suspect it is of the nature of n^2. Still that should be better than N! or exponential.

The number of distinct subsets of size k from a set of size n is

n!/((k!)(n-k)!) which means, among other things, that the number of subsets is roughly the same regardless of the size of k.

However, as the size of n grows, the number of subsets of different lengths we need to generate to also grows. A 9 X 9 Sudoku only needs subsets of lengths 2,3, and 4. If we assume that we should not cross the halfway boundary, A 25 * 25 will need lengths from 2 through 12.

Well, not “need” but rather “benefit from.” You can limit it to hidden “quads” and lower. But the larger puzzle is also going to have larger percentages of hit rates at all tuple sizes. I don’t think I’m prepared to advise what would be the right way to scale it.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.