[newbie] Recursive algorithm - review

W

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 (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[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.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. :)
 
T

Terry Reedy

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 (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[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.append(0) # I don't know how to do this with
# list comprehension (one inside


[0]*size] is fine for one row

towers = [[0]*size] for i in range(size)]

should do what you want for a 2-d array instead of the above.

I cannot look at the rest right now.
 
W

Wiktor

[0]*size] is fine for one row

towers = [[0]*size] for i in range(size)]

should do what you want for a 2-d array instead of the above.

Right. Thank you also.
 
W

Wiktor


OK, another question. This time, I think, closer to the original subject
(recursive algorithm).

Thanks to Terry's and Chris' advises I refined script. Then I thought, that
with some changes and with minimal effort I can force this script to generate
Sudoku board (again: filled out, 'solved' one).
Well, I was wrong. ;-) It actually took me 2 hours to make this script
working fine - even though changes weren't so big. And another one hour to make
it clear enough to share here.


Idea is still the same. I start with 2d array

[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]

And then I fill it up one number by one (exception: first row). At every step
checking if current column is unique (0's not counted) and if also current
segment 3x3 is unique. If that condition is True I call another instance of
generate(), passing to it a) the board, b) the position in which I last putted
number, and c) a list of numbers that in next step this function can choose
from (if empty, function will generate new list). And so on.
If that condition is False, I try another number from list of available
numbers, and check again. If all numbers fail, I go back one level and try
another number on previous position.


I'll paste code now, and under that I'll write what's mine concern now.
(if you uncomment hashed lines it will print out entire process of generating
board, but watch out - it can be several thousands of lines)


###
import random


attempt_global = 0


def check(board, x=None, sudoku=False):
global attempt_global
attempt_global += 1

if sudoku and len(board) == 9 and x is not None:
c = x % len(board)
r = x // len(board)

# print('Attempt #{}; Checking ({}x{})'.format(attempt_global,
# r, c))
# for row in board:
# print(row)
# print()

column = [t[c] for t in board if t[c]]

br_min, br_max = r//3 * 3, r//3 * 3 + 3
bc_min, bc_max = c//3 * 3, c//3 * 3 + 3
block = [t[bc_min:bc_max] for t in board[br_min:br_max]]
block_flat = [item for row in block for item in row if item]

return len(column) == len(set(column)) and \
len(block_flat) == len(set(block_flat))

elif x is not None:
c = x % len(board)
column = [t[c] for t in board if t[c]]
return len(column) == len(set(column))

elif sudoku and len(board) == 9:
return all((check(board, i, sudoku) for i in range(0,
len(board)**2,
4)))

else:
return all((check(board, i) for i in range(len(board))))


def generate(size=4, board=None, row=None, x=0, sudoku=False):
if not row:
row = [a for a in range(1, size+1)]
random.shuffle(row)

if not board:
board = [[0]*size for _ in range(size)]
board[0] = row[:]
random.shuffle(row)
x = size - 1

if x + 1 < size**2:
repeat = True
attempt = 0

while repeat:
x += 1
num = row.pop(0)
board[x // size][x % size] = num
repeat = not check(board, x, sudoku)

if repeat:
row.append(num)
board[x // size][x % size] = 0
x -= 1
attempt += 1

if attempt > len(row) - 1:
return False
else:
if not generate(size, board, row, x, sudoku):
repeat = True
row.append(num)
board[x // size][x % size] = 0
x -= 1
attempt += 1

if attempt > len(row) - 1:
return False

return board


def main():

global attempt_global
sudoku_board = generate(9, sudoku=True)

for row in sudoku_board:
print(row)

print('Attempts:', attempt_global)


if __name__ == "__main__": main()

###



OK, it works fine. Most of the time it generates board in less than 400
attempts, so not so bad. But sometimes it takes over thousand tries to generate
board.

For example, one time, at attempt #46 it validates last putted '1', and of
course it passes,

Attempt #46; Checking (4x1)
[1, 5, 3, 9, 4, 2, 8, 6, 7]
[2, 7, 6, 5, 8, 1, 3, 9, 4]
[9, 8, 4, 7, 3, 6, 1, 5, 2]
[8, 9, 5, 3, 7, 4, 6, 2, 1]
[7, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]

then fills out entire row, and starting from attempt #61...

Attempt #61; Checking (5x0)
[1, 5, 3, 9, 4, 2, 8, 6, 7]
[2, 7, 6, 5, 8, 1, 3, 9, 4]
[9, 8, 4, 7, 3, 6, 1, 5, 2]
[8, 9, 5, 3, 7, 4, 6, 2, 1]
[7, 1, 2, 8, 6, 9, 4, 3, 5]
[3, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]

... through attempt #1055 it struggles whith so many combinations in that one
segment 3x3:
8 9 5
7 1 2
A B C
and entire row 4, to find out, that only solution is go back to position (4x1)
and replace '1' with another number. In this case '6' was fine.

Attempt #1056; Checking (4x1)
[1, 5, 3, 9, 4, 2, 8, 6, 7]
[2, 7, 6, 5, 8, 1, 3, 9, 4]
[9, 8, 4, 7, 3, 6, 1, 5, 2]
[8, 9, 5, 3, 7, 4, 6, 2, 1]
[7, 6, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]

Final board in this case looked like that:

Attempt #1251; Checking (8x8)
[1, 5, 3, 9, 4, 2, 8, 6, 7]
[2, 7, 6, 5, 8, 1, 3, 9, 4]
[9, 8, 4, 7, 3, 6, 1, 5, 2]
[8, 9, 5, 3, 7, 4, 6, 2, 1]
[7, 6, 2, 8, 1, 9, 4, 3, 5]
[4, 3, 1, 2, 6, 5, 7, 8, 9]
[6, 2, 7, 4, 5, 3, 9, 1, 8]
[3, 4, 9, 1, 2, 8, 5, 7, 6]
[5, 1, 8, 6, 9, 7, 2, 4, 3]

It takes so much time, obviously, because every time number on position A (in
segment 3x3) doesn't match, it doesn't jump back to 2 (above C), but instead it
walks through entire recursion tree.

Now, my question is - should I implement mechanism that recognises this kind
of situation, and jumps back (let's say) 9 levels of recursion at once? My
guess is that it will take me at least several hours to solve this properly.
Also, now it's simple algorithm, and if I start to tamper with it, it will
overgrow by many conditions, and extra arguments. Won't be so clear anymore.
Or maybe I should accept that this is how recursion works, and let go?
What would you do?

Or maybe there's better way to generate pseudo-random Sudoku board? Not by
recursion. Or maybe by recursion, but nicer with less attempts in those kind of
situation? I guess that some kind of you have done this before. ;-)
Any tips?

TIA
 
W

Wiktor

I guess that some kind of you have done this before. ;-)
^^^^

Damn it. This 'kind' shouldn't be there. Now it sounds silly,
even offensive. ;-) Normally I would supersede it, but probably attached
mailing-list doesn't recognize those Usenet articles (Chris previously answered
to my superseded article).
 
C

Chris Angelico

On Sat, 4 Jan 2014 01:16:14 +0100, Wiktor wrote:
Idea is still the same. I start with 2d array
And then I fill it up one number by one (exception: first row). At every step
checking if current column is unique (0's not counted) and if also current
segment 3x3 is unique. If that condition is True I call another instance of
generate(), passing to it a) the board, b) the position in which I last putted
number, and c) a list of numbers that in next step this function can choose
from (if empty, function will generate new list). And so on.
If that condition is False, I try another number from list of available
numbers, and check again. If all numbers fail, I go back one level and try
another number on previous position.

That's a reasonable brute-force algorithm. I'll get onto some
alternatives down below.
def check(board, x=None, sudoku=False):

You seem here to have two completely different programs that share
almost no code. This is going to cause confusion, more than anything
else. I recommend saving away the other program and making the Sudoku
one completely separate.programs.
if sudoku and len(board) == 9 and x is not None:
c = x % len(board)
r = x // len(board)

Your algorithm involves a *lot* of division. This may be a premature
optimization (I haven't measured to see if that's actually a
bottleneck), but I would consider rejigging things to minimize this.
(Edit: It almost certainly *is* premature to try to cut out division.
Much better targets elsewhere.)
br_min, br_max = r//3 * 3, r//3 * 3 + 3
bc_min, bc_max = c//3 * 3, c//3 * 3 + 3
block = [t[bc_min:bc_max] for t in board[br_min:br_max]]

You can define max in terms of min, here. I think it'd be clearer than
doing the division again (plus it might be faster, see above):

br = r//3 * 3
bc = c//3 * 3
block = [t[bc:bc+3] for t in board[br:br+3]]
return len(column) == len(set(column)) and \
len(block_flat) == len(set(block_flat))

Style point: In Python, it's more normal to bracket conditions like
that, rather than use a backslash.

return (len(column) == len(set(column)) and
len(block_flat) == len(set(block_flat)))
elif sudoku and len(board) == 9:
return all((check(board, i, sudoku) for i in range(0,
len(board)**2,
4)))

Ultimately, this is testing to see if the board state is valid. It
does this in 81 steps (len(board) squared), each one checking the
column and the block for validity, and not checking the row, because
you assume that to be valid elsewhere. (This last bit is worthy of a
code comment, I think.) Instead, you could simply check the nine
columns and the nine blocks, iteratively.
def generate(size=4, board=None, row=None, x=0, sudoku=False):
while repeat:
x += 1
num = row.pop(0)
board[x // size][x % size] = num
repeat = not check(board, x, sudoku)

if repeat:
row.append(num)
board[x // size][x % size] = 0
x -= 1
attempt += 1

if attempt > len(row) - 1:
return False
else:
if not generate(size, board, row, x, sudoku):
repeat = True
row.append(num)
board[x // size][x % size] = 0
x -= 1
attempt += 1

if attempt > len(row) - 1:
return False

return board

Code's getting complicated, I'm getting bogged down in the indentation
levels. Is it possible to break out some of this into separate
functions? You're calling the same function in different modes;
stuff's getting a bit messy.
OK, it works fine. Most of the time it generates board in less than 400
attempts, so not so bad. But sometimes it takes over thousand tries to generate
board.

That's the result of a brute-force algorithm. You're working top-down
and rolling back step by step. It's simple but not fast.

Here's the code for my Binary Sudoku engine. It's not in Python (it's
Pike - semantically similar, but uses a C-like syntax), but hopefully
you should be able to see what it's doing.

https://github.com/Rosuav/binary

There are three distinct parts to it:
1) Validate a state
2) Attempt to solve, by logic
3) Generate a puzzle

The key here is that step 2 uses the same techniques that a human
would use. In the case of Sudoku, that would basically mean
implementing the techniques you'd find on a Sudoku solving help web
site (eg figuring out that the only digit legal in this spot is a 3).
That's going to be far FAR more efficient than brute force, and it'll
take you a long way.

Then in step 3, you simply do this:
1) Place a random digit at a random position on the grid.
2) Attempt to solve (call the previous function).
2a) If, at any time, the state comes up invalid, remove this digit.
2b) Otherwise, this digit is now canon. Make it part of the puzzle.
3) While there are empty spaces on the grid, go to 1.

(In step 2b, I distinguish between the current solved state and the
printed puzzle. That's an optional distinction.)
Now, my question is - should I implement mechanism that recognises this kind
of situation, and jumps back (let's say) 9 levels of recursion at once? My
guess is that it will take me at least several hours to solve this properly.
Also, now it's simple algorithm, and if I start to tamper with it, it will
overgrow by many conditions, and extra arguments. Won't be so clear anymore.
Or maybe I should accept that this is how recursion works, and let go?
What would you do?
Or maybe there's better way to generate pseudo-random Sudoku board? Not by
recursion. Or maybe by recursion, but nicer with less attempts in those kind of
situation? I guess that some kind of you have done this before. ;-)
Any tips?

Messing with a brute-force algorithm can get really hairy. Changing
algorithm completely is far more effective. :) My method as described
above is still recursive, but by solving by rules rather than brute
force, it's guaranteed to resolve more quickly.

The brute force method you're using will shuffle a row and then
attempt each one, which is pretty much the same as the absolute
simplest method: place every possible digit in every possible slot.
That means that the worst-case is 10**81 attempts, which is faintly
ridiculous :)

By attempting to solve it at each iteration, your iterations will be
slower, but you'll have 10*81 (multiplication rather than
exponentiation) possibilities. Or alternatively, you could part-solve
the grid and pick whichever slot has the least possibilities (if it's
0, the state's unsolvable, if it's 1, you have a certainty, and
otherwise you try them all). That would be a reasonably simple
algorithm that'd probably average out at about 3**81 attempts to
brute-force the grid. Much better! :)

ChrisA
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top