Numbers in a Matrix
Question: I tried to solve the following problem with Python:

[![enter image description
here](http://i.stack.imgur.com/TK8zK.png)](http://i.stack.imgur.com/TK8zK.png)

But I got stuck at generating a single valid table. I was expecting the
program to display a valid matrix, but in order for the program to continue
and not print `None`, I had to assign a `7` for a square that has no
possibles. What should be fixed?

My code so far:

    
    
    from pprint import pprint
    import sys
    import random
    
    sys.setrecursionlimit(10000)
    
    def getPossiblesForSquare(sqx,sqy,matrix):
        '''Gets the possible entries of matrix[sqy][sqx].
    Assumes it equals 0.'''
        assert matrix[sqy][sqx]==0
        # get the row that it is on
        rowon=matrix[sqy]
        # columns are a little trickier
        colon=[matrix[row][sqx] for row in range(5)]
    
        # find the possibilities!
        possibles=list(range(1,7))
    
        for item in list(set(rowon+colon)): # remove duplicates
            if not (item == 0) and (item in possibles):
                del possibles[possibles.index(item)]
    
        random.shuffle(possibles)
    
        return possibles
    
    def getPossiblesForMatrix(matrix):
        '''Gets all the possible squares for a matrix.'''
        possiblesdict={}
        for y in range(6):
            for x in range(6):
                if matrix[y][x]==0:
                    possiblesdict[(y,x)]=getPossiblesForSquare(x,y,MATRIX)
        return possiblesdict
    
    def flattenList(matrix):
        result=[]
        for i in matrix:
            if not isinstance(i,list):
                result+=[i]
            else:
                result+=flattenList(i)
        return result
    
    def getPossibleMatrix(startMatrix, iteration=0, yon=1, prevZeroInd=None):
        if 0 not in flattenList(startMatrix):
            print('RESULT:\n\n')
            return startMatrix
        else:
            # find&fill in the first blank one
            ind=flattenList(startMatrix).index(0)
            y=ind//6
            x=ind%6
            if (x,y)==prevZeroInd:
                startMatrix[y][x]=7
            else:
                possibles=getPossiblesForSquare(x,y,startMatrix)
                if len(possibles)==0:
                    startMatrix[y][x]=7
                else:
                    startMatrix[y][x]=possibles[0]
                if iteration <= 6:
                    return getPossibleMatrix(startMatrix, iteration+1, yon, (x,y)) # <<BUG
                else:
                    if yon!=4:
                        return getPossibleMatrix(startMatrix, 0, yon+1, (x,y))
    
    
    MATRIX=[[1,2,3,4,5,6],
            [2,0,0,0,0,5],
            [3,0,0,0,0,4],
            [4,0,0,0,0,3],
            [5,0,0,0,0,2],
            [6,5,4,3,2,1]]
    
    result=getPossibleMatrix(MATRIX)
    pprint(result)
    


Answer: ## Why your script hangs:

* * *

Essentially your script encounters problems here:

    
    
    for item in list(set(rowon + colon)):  # remove duplicates
        if not (item == 0) and (item in possibles):
            del possibles[possibles.index(item)]
    

  * At the third iteration, for the third cell your if condition is evaluated as true for all possible values `[1 to 6]` (if you output the matrix you will see that the `set()` you are creating contains all elements), so you always return zero, re-check the values, return zero [**_ad infinitum_**](https://en.wikipedia.org/wiki/Ad_infinitum). 

If you're looking to brute-force a solution out of this, you might want to
update the `sqx` and `sqy` to go to a different cell when possibles is empty.

Another additional small mistake I located was:

    
    
    # you are checking values 1-5 and not 1-6!
    possibles = list(range(1, 6)) # should be range(7) [exclusive range] 
    

  * Don't forget that range is exclusive, it doesn't include (excludes) the upper limit.

There exist of course, different ways to tackle this problem.

* * *

## A possible -alternate- solution:

> Read this for the general, alternate view of how to solve this. If you do
> not want to see a possible solution, skip the 'code' part.

* * *

The solution matrix (one of the possible ones) has this form (unless I am
making a horrible mistake):

    
    
    MATRIX = [[1, 2, 3, 4, 5, 6],
              [2, 3, 6, 1, 4, 5],
              [3, 1, 5, 2, 6, 4],
              [4, 6, 2, 5, 1, 3],
              [5, 4, 1, 6, 3, 2],
              [6, 5, 4, 3, 2, 1]]
    

The Logic is as follows:

You must observe the symmetry present in the matrix. Specifically, every row
and every column displays a 'flip and reverse' symmetry. For example, the
first and last rows are connected by this equation :

    
    
    row[0] = REV(flip(row[n]))
    

Similarly, all additional rows (or columns) have their corresponding
counterpart:

    
    
    row[1] = REV(flip(row[n-1]))
    

and so on.

So, for `n=6` this essentially boils down to finding the `(n / 2) -1` (because
we already know the first and last row!) and afterwards flipping them (not the
finger), reversing them and assigning them to their corresponding rows.

In order to find these values we can observe the matrix as a combination of
smaller matrices:

These make the first two (unknown) rows of the matrix:

    
    
    sub_matrix = [[1, 2, 3, 4, 5, 6],
                  [2, 0, 0, 0, 0, 5],
                  [3, 0, 0, 0, 0, 4],
                  [6, 5, 4, 3, 2, 1]]
    

and the other two rows can be made by finding the correct values for these
two.

Observe the restrictions in hand:

In column `[1][1]` and `[1][m-1]` we cannot:

  * place a `2` or a `5`

In columns `[1][2]` and `[1][m-2]` we cannot:

  * place the previous values (`[2, 5]`) along with (`[3, 4]`) so, we cannot have a value `in` `[2,3,4,5]`

For the inner columns we're left with the set `set(1-6) - set(2-5) = [1, 6]`
and since we get a normal row and a **_single_** inverted and flipped row for
this, we can arbitrarily select a value and add it as a column value.

By using another list we can keep track of the values used and fill out the
rest of the cells.

* * *

### Coding this: (Spoilers)

* * *

**Note** : I did not use `numpy` for this. You **can** and **should** though.
(Also, `Python 2.7`)

Also, I did not use recursion for this (you can try to, by finding the same
matrix for bigger values of `n` [I believe it's a good fit for a recursive
function].

First, in order to not type this all the time, you can create a `n x n` matrix
as follows: (This isn't much of a spoiler.)

    
    
    # our matrix must be n x n with n even.
    n = 6
    
    # Create n x n matrix.
    head = [i for i in xrange(1, n + 1)]   # contains values from 1 to n.
    zeros = [0 for i in xrange(1, n-1)]    # zeros
    tail = [i for i in xrange(n, 0, -1)]   # contains values from n to 1.
    
    
    # Add head and zeros until tail.
    MATRIX = [([j] + zeros + [(n+1)-j]) if j != 1 else head for j in xrange(1, n)]
    # Add tail
    MATRIX.append(tail)
    

Then, create the smaller `(n/2 + 1) x n` array:

    
    
    # Split matrix and add last row.
    sub_matrix = MATRIX[:(n / 2)] + [tail]
    

Afterwards, a small function called `sub = fill_rows(sub_matrix)` comes in and
takes care of business:

    
    
    def fill_rows(mtrx):
    
        # length of the sub array (= 4)
        sub_n = len(mtrx)
    
        # From 1 because 0 = head
        # Until sub_n -1 because the sub_n - 1 is = tail (remember, range is exclusive)
        for current_row in xrange(1, sub_n - 1):
            print "Current row: " + str(current_row)
    
            # -- it gets messy here --
            # get values of inner columns and filter out the zeros (matrix[row][n / 2] == 0 evaluates to False)
            col_vals_1 = [mtrx[row][n / 2] for row in xrange(0, sub_n) if mtrx[row][(n / 2)]]
            col_vals_2 = [mtrx[row][(n / 2) - 1] for row in xrange(0, sub_n) if mtrx[row][(n / 2) - 1]]
    
            col_vals = col_vals_1 + col_vals_2
            # print "Column Values = " + str(col_vals)
    
            row_vals = [mtrx[current_row][col] for col in xrange(0, n) if mtrx[current_row][col]]
            # print "Row Values = " + str(row_vals)
    
            # Find the possible values by getting the difference of the joined set of column + row values
            # with the range from (1 - 6).
            possible_values = list(set(xrange(1, n + 1)) - set(row_vals + col_vals))
    
            print "Possible acceptable values: " + str(possible_values)
    
            # Add values to matrix (pop to remove them)
            # After removing add to the list of row_values in order to check for the other columns.
            mtrx[current_row][(n-1)/2] = possible_values.pop()
            row_vals.append(mtrx[current_row][(n - 1) / 2])
            mtrx[current_row][(n-1)/2 + 1] = possible_values.pop()
            row_vals.append(mtrx[current_row][(n-1) / 2 + 1])
    
            # New possible values for remaining columns of the current row.
            possible_values = list(set(xrange(1, n + 1)) - set(row_vals))
            print "Possible acceptable values: " + str(possible_values)
    
            # Add values to the cells.
            mtrx[current_row][(n - 2)] = possible_values.pop()
            mtrx[current_row][1] = possible_values.pop()
    
        # return updated sub-matrix.
        return mtrx
    

The only thing left to do now is take those two rows, flip them, reverse them
and add the head and tail to them:

    
    
    print '=' * 30 + " Out " + "=" * 30
    
    # Remove first and last rows.
    del sub[0]
    sub.pop()
    
    # reverse values in lists
    temp_sub = [l[::-1] for l in sub]
    # reverse lists in matrix.
    temp_sub.reverse()
    
    # Add them and Print.
    pprint([head] + sub + temp_sub + [tail])
    

This outputs what, I hope, is the right matrix:

    
    
    ============================== Out ==============================
    
    [[1, 2, 3, 4, 5, 6],
     [2, 3, 6, 1, 4, 5],
     [3, 1, 5, 2, 6, 4],
     [4, 6, 2, 5, 1, 3],
     [5, 4, 1, 6, 3, 2],
     [6, 5, 4, 3, 2, 1]]
    

* * *

### Additionally

* * *

By using this way of solving it the answer to the problem in hand becomes more
easy. Viewing the matrix as a combination of these sub-matrices you can tell
how many of these combinations might be possible.

As a closing note, it would be a good work-out to modify it a bit in order to
allow it to find this array for an arbitrary (**_but even_**) number of `n`.

