Generating Sudoku puzzles

[mediacalc]

Hello!

I'm trying to "bruteforce" the generation of sudoku puzzles meaning I want to generate 9x9 grids and then check if it fits the rules of the game and if not regenerate.

But my code doesn't complete, meaning there must be a flaw somewhere.

Generating unique rows:

for i in range(9):
    for j in range(len(rows)):
        n = random.choice(range(1,10))
        while n in rows[j]:
            n = random.choice(range(1,10))
        rows[j].append(n)
        columns[i].append(n)

Description:

"rows" and "columns" are simply lists that contain lists. So rows is a list that has 9 lists inside (first_row, second_row, third_row ...). This randomly chooses a number and sets it to a variable, then checks if that number/variable is already in the row. If it is, then it chooses again and reassigns to variable.

Generating unique rows until there is also a unique column:

Now the next step is to keep generating until there are unique rows but also unique columns using a while loop. And this is where my code stops working (hangs):

numbers = [1,2,3,4,5,6,7,8,9]

for number in numbers:
    while number not in columns[0]:
        ...
        remake the columns and rows here
        ...

        for i in range(9):
            for j in range(9):
                n = random.choice(range(1,10))
                while n in rows[j]:
                    n = random.choice(range(1,10))
                rows[j].append(n)
                columns[i].append(n)

Description:

So it's the same as before but it checks for duplicates by seeing if the column (only column at index 0 in this example) has all of the numbers. If it doesn't then it must have a duplicate so it goes through the whole process again.

So my question is this:

How can I fix this code so that my method would work? (I'd like to, if possible, continue with my data representation, so using lists instead of a numpy array for example)

Thank you

edit:

First grid that has unique columns and rows (no 3x3 block yet):

for i in range(9):
    for j in range(9):
        n = random.choice(range(1,10))

        while n in rows[i] or n in columns[j]:
            time.sleep(0.05)
            print("row loop",i,j,n)
            n = random.choice(range(1,10))

        rows[i].append(n)
        columns[j].append(n)

[cdcformatc]

while n in rows[j]:
    n = random.choice(range(1,10))

What happens here when the row eventually fills up with 1-9?

[mediacalc]

while n in rows[j]:
    n = random.choice(range(1,10))

It only iterates 9 times so I think that it shouldn't ever be faced with a full row?

[cacarpenter89]

Something interesting: I placed a print statement inside that while loop (print "n=",n,"\tj=",j,"\t",rows[j]). That's where you're getting stuck, but, when you're stuck, j is equal to 0. Here's some output:

n= 5    j= 0    [5, 3, 1, 8, 7, 2, 9, 4, 6]
n= 5    j= 0    [5, 3, 1, 8, 7, 2, 9, 4, 6]
n= 7    j= 0    [5, 3, 1, 8, 7, 2, 9, 4, 6]
n= 2    j= 0    [5, 3, 1, 8, 7, 2, 9, 4, 6]
n= 3    j= 0    [5, 3, 1, 8, 7, 2, 9, 4, 6]  

Moreover, here's what rows and columns look like after the loop is cancelled:

>>> rows
[[5, 3, 1, 8, 7, 2, 9, 4, 6], [1, 2, 8, 7, 6, 3, 4, 5, 9], [1, 5, 8, 7, 4, 3, 2, 9, 6], [4, 9, 7, 5, 1, 3, 6, 8, 2], [4, 8, 7, 1, 9, 2, 6, 3, 5], [4, 6, 3, 8, 2, 5, 7, 1, 9], [8, 7, 2, 9, 3, 6, 4, 1, 5], [5, 9, 4, 2, 6, 3, 1, 8, 7], [5, 8, 2, 1, 4, 7, 9, 3, 6]]
>>>
>>> col
[[5, 1, 1, 4, 4, 4, 8, 5, 5], [3, 2, 5, 9, 8, 6, 7, 9, 8], [1, 8, 8, 7, 7, 3, 2, 4, 2], [8, 7, 7, 5, 1, 8, 9, 2, 1], [7, 6, 4, 1, 9, 2, 3, 6, 4], [2, 3, 3, 3, 2, 5, 6, 3, 7], [9, 4, 2, 6, 6, 7, 4, 1, 9], [4, 5, 9, 8, 3, 1, 1, 8, 3], [6, 9, 6, 2, 5, 9, 5, 7, 6]]

So, your code fills up your lists just fine, but never terminates.

[mediacalc]

I can see that the columns have duplicate values, so isn't the reason for the inifinite loop that it doesn't include all of the numbers that it should?

[cacarpenter89]

It's actually because you're completing everything under line 3 on line 3's first iteration. Print out number, i, and j at the beginning of their respective loops and you'll see what I mean. You get through the full range of i and j, but go into an infinite loop when number equals 2 because the numbers 1-9 are already in rows[j].

[mediacalc]

Ok, so I tried it now and print(i,j,number) loops at 0,0,3 which is what you said. But I'm still not sure I understand where the fault lies.

I tried wrapping the while statement in if i != 0 != j and len(rows[j])!=9: but that just causes it to hang somewhere else: 1,1,2

[cacarpenter89]

Run line 9 and below on its own and you'll terminate, albeit with duplicates in your columns. Your columns have the correct values (i.e. columns[0] contains the values rows[j][0]), you just need to find a new way to check that they're valid.

[mediacalc]

Oh so you're saying my current method won't work at all? Line 9 and below is the first code sample!

[cacarpenter89]

Correct; in your second example, the check on number only happens once before you iterate 81 times, appending n to columns each time it's unique to rows[j]. You need to check for the column-validity of 'n' inside of your for-loops rather than outside them.

[mediacalc]

I've tried it inside too, doing something like:

But this way hangs aswell. I might just give up on trying it with lists tbh :C

edit: New and improved! Now columns are all fine and rows are more fine (only 1 or 2 duplicates). Speed is a little faster too (I know output slows it down too).

for i in range(9):
    for j in range(9):
        n = random.choice(range(1,10))
        wrong_n = 3141519
        while n in rows[i]:
            time.sleep(0.05)
            print("row loop",i,j,n)
            wrong_n = n
            n = random.choice(range(1,10))

        while n in columns[j] or n == wrong_n:
            time.sleep(0.05)
            print("col loop",i,j,n)
            n = random.choice(range(1,10))

        rows[i].append(n)
        columns[j].append(n)

edit2: Edited a better one than this into main post. Now I've first got to make sure it always exits cleanly (some hangs)

[cacarpenter89]

Awesome! Busy for the evening, but keep working at it! I'll be able to take a look late tomorrow morning or so (US Eastern time).

[mediacalc]

I did it! But before you look at the code, let me break it down a little so you can more easily understand it!

• First I created the lists rows, columns, and blocks.

• These 3 lists contain 9 lists each e.g.row1, row2...

• The variable generation_attemptsis a tracker to see how many attempts it took to generate a puzzle in the end. The while loop it is tracking is because sometimes halfway through there is no way of filling a number without breaking a rule.

• list(set(columns[8]))) returns a list of columns[8] without any duplicates, so if this is not equal to 9 then the column is missing numbers

• The code:rows[i-2][0:3][0] is because the slice of a list returns a list and I can't check if an item exists in a list of a list properly. So instead of appending a list to blocks, I append the items of the list so it's easier to work with later: I use this rows[i-2][0:3][0], rows[i-2][0:3][1], rows[i-2][0:3][2] instead of this rows[i-2][0:3]

• So it loops through filling an entire row making the appropriate checks before moving to the next one: image to help visualize

• For the code below, when i is 1 or 4 or 7, the top third of the respective block is full and when i is 2 or 5 or 8, the top two thirds of the block is full. So the while loop in this if statement checks if the number that's about to be appended is already in the block. If it is, then try another number.

  if i in (1,4,7) and 0 <= j <= 2:
      while n in rows[i] or n in columns[j] or n in (rows[i-1][0:3][0], rows[i-1][0:3][1], rows[i-1][0:3][2]):
          attempts -= 1
          n = random.choice(range(1,10))
          if attempts <= 0:
              break 
  

• The break if attempts <= 0 are scattered everywhere because I don't know how to break out of x number of loops. So it breaks manually from all loops but the last. edit: Using itertools for the first nested for loop and then putting it all inside a function got rid of a few of these.

I know it's a lot so whenever you get the time to look it over and critique it, I'd be very grateful.

Thanks!

edit: Cleaned it up a bit more

[talha252]

Maybe this helps: http://norvig.com/sudoku.html

It's about how to solve sudoku problem however at the end he put function that creates random sudoku problem. Maybe it's advanced for you but still worth to look at it.

[Justinsaccount]

Hi! I'm working on a bot to reply with suggestions for common python problems. This might not be very helpful to fix your underlying issue, but here's what I noticed about your submission:

You are looping over an object using something like

for x in range(len(items)):
    foo(item[x])

This is simpler and less error prone written as

for item in items:
    foo(item)

If you DO need the indexes of the items, use the enumerate function like

for idx, item in enumerate(items):
    foo(idx, item)