[newbie] Recursive algorithm - review

[Wiktor]

Hi,
it's my first post on this newsgroup so welcome everyone. :)

I'm still learning Python (v3.3), and today I had idea to design (my first)
recursive function, that generates board to 'Towers' Puzzle:
http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/towers.html
(so I could in future write algorithm to solve it ;-))

I'm pretty proud of myself - that it works, and that took me only 4 hours
to debug. ;-)
But on Project Euler site sometimes I'm also proud, that I solved some
problem in 30-line script, and then on forum there's one lined solution...

So maybe You might look at this script, and tell me if this can be more
pythonic. It's nothing urgent. I can wait - it works after all. ;-)


Idea is that function "generate()" 'finds' one number at a time (well,
besides first row), then checks if there are no repetitions in column
(because in row there cannot be by design - I pop out numbers from shuffled
list [1, 2, 3, ..., size] for every row.)
If no repetition - calls the same function to find next number, and so on.
If there is repetition at some point - recursion jumps back, and try
different number on previous position.



import random


def check(towers, x=None):
    if x:
        c = x % len(towers)                       # check only column with
        column = []                               # value added on pos. x
        for i in range(len(towers)):
            column.append(towers[i][c])
        column = [x for x in column if x != 0]
        # print(column)                           # debugging leftovers ;-)
        return len(column) == len(set(column))
    else:
        for c in range(len(towers)):              # 'x' not provided,
            column = []                           # so check all columns
            for i in range(len(towers)):
                column.append(towers[i][c])
            column = [x for x in column if x != 0]
            # print(column)
            if len(column) != len(set(column)):
                return False
        return True


def generate(size=4, towers=None, row=None, x=0):
    if not towers:                             # executed only once.
        row = [a for a in range(1, size+1)]    # Then I'll pass towers list
        random.shuffle(row)                    # at every recursion
        towers = []
                                       # not so pretty way to generate
        for i in range(size):          # matrix filled with 0's
            towers.append([])          # I tried: towers = [[0]*size]*size
            for j in range(size):      # but this doesn't work. ;-)
                towers[i].append(0)    # I don't know how to do this with
                                       # list comprehension (one inside
        row_ = row[:]                  # other?)
        towers[0] = row_    # after adding first row, columns will be
        row = []            # always unique, so I add entire row at once.
        x = size - 1        # Then I will be adding only one num at time.
                            # 'x' is pretty much position of last added el.
    if not row:
        row = [a for a in range(1, size+1)]
        random.shuffle(row)

    if x + 1 < size**2:
        repeat = True
        attempt = 0
        while repeat:
            # print(towers, row, x)
            x += 1
            num = row.pop(0)                   # take num from right, and
            towers[x // size][x % size] = num  # if doesn't match - put
            repeat = not check(towers, x)      # back (append) on left -
                                               # - to rotate
            if repeat:                       # I'll repeat 'matching' next
                row.append(num)              # number as long as last
                x -= 1                       # changed column is unique
                attempt += 1
                                             # after some attempts I give
                if attempt > len(row) - 1:   # up and jump back from
                    return False             # current recursion
            else:
                if not generate(size, towers, row, x):
                    repeat = True
                    row.append(num)          # after some failed attempts
                    x -= 1                   # on this 'level' I give up
                    attempt += 1             # again...

                    if attempt > len(row) - 1:
                        return False            # ...and jump back one
                                                # more time...
    return towers


def main():
    towers6by6 = generate(6)
    # print(check(towers6by6))
    print(towers6by6)

if __name__ == "__main__": main()



Footnote: English isn't my native language, so forgive me my bad grammar
and/or vocabulary. :-)  

-- 
Best regrds,      Wiktor Matuszewski
'py{}@wu{}em.pl'.format('wkm', 'ka')  # spam trap