[newbie] Recursive algorithm - review

[Chris Angelico]

On Sun, Jan 5, 2014 at 6:07 AM, Wiktor <look at signature.invalid> wrote:
> 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