[newbie] Recursive algorithm - review

[Wiktor]

On Sat, 4 Jan 2014 01:16:14 +0100, Wiktor wrote:

> Hi,

  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

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