W

#### Wiktor

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 (filled out) 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

*[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

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

*[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. ;-)

towerscolumn = [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

*.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.# 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.