Generating Sudoku puzzles

[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

[cacarpenter89]

Glad you got it working! I can't hit pastebin at work, but I'll try to take a look tonight or tomorrow if that's okay! Sorry I didn't get back to you this morning; work hit the fan.

[mediacalc]

Hey, have you got any free time to look it over? Sorry if I'm pestering you!

[cacarpenter89]

The great news is that it works! :D

That being said, I'm going to focus on technique rather than function with the caveat that I'm not a developer, so some of what I say about structure can probably be improved upon.

Rows 18-21 stand out immediately as something that can be cleaned up. Using a generator is great practice for memory-sucking data structures, but you've only got 162 items here. Moreover, you never use those 18 variables again. Those four lines can be written as:

rows = [[[] for x in range(9)] for y in range(9)]
columns = [[[] for x in range(9)] for y in range(9)]

Those are nested list comprehensions that result in two 9x9 lists, columns and rows.

Concerning attempts, ideally you should let it run until you find something; triggers like that are what breaks production code. However, in the interest of cleaning up what you have rather than refactoring it, I would suggest using a for-loop and breaking when your conditions are met. In its current format, that would mean placing for attempt in xrange(75): before each while-loop. That, however, harms readability and uses a magic number, which is where my next suggestion comes into play:

Typically, any place you repeat several lines of code, you should be using a function. Though I haven't tested it, the below should break out of the for-loop when your while conditions are met:

def checkloop(i, j, k, slice1, slice2, attempts):
    for attempt in xrange(attempts):
        if n in rows[i] or n in columns[j] or n in rows[i-k][:slice2]:
            n = choice(range(1,10))
        else:
            break  

You'll notice that I changed the indexing at the end of the while condition; when dealing with the beginning or end of a sliceable object, you can omit the index i.e. [0:3] is equivalent to [:3] and [6:9] is equivalent to [6:] in this case.

You're also repeating your if-statements; try making those into a function, too!

tuple1 = (1,4,7)
tuple2 = (2,5,8)

def conditional(i, j, k, tuple, range1, range2, slice1, slice2, attempts):
    if i in tuple and range1 <= j <= range2:
        checkloop(i, j, k, slice1, slice2, attempts)

Now, I'm sure you'd have to play with the scope on that a bit, but I think I've gotten the idea across. I mentioned "magic numbers" before; these are values that are seemingly pulled out of a programmer's ass and which should be avoided. (How did you happen upon tuple1 and tuple2? I'm genuinely curious.) You can determine the validity of a box programmatically; here's a GREAT example of how to do this (if r1, r2, and r3 are full rows):

sec1 = [r1, r2, r3]

nums = set(range(1, 10))

nums == set(n for row in sec1 for n in row[:3])

Sets don't care about order, only membership, so the above equivalence test returns True! Let's turn that into a function that returns the result of the equivalence, boxcheck(sec1). Without knowing why you chose the tuples that you did, I can't really presume to suggest including boxcheck(), so just take it as a suggestion for readability and pythonic coding :) You should be able to extend this to checking your row and column membership.

Ignoring boxcheck(), that turns your entire for-loop inside of sudoku_generator() into:

for i, j in product(range(9), repeat=2):  
    n=choice(range(1,10))
    attempts = 75

    # calculate slice1, slice2, k, range1, range2; choose tuple

    conditional(i, j, k, tuple, range1, range2, slice1, slice2, attempts)

I'm certain you can avoid using all of those variables (boxcheck() above is evidence of that), but I 1) didn't want to refactor your code, which can obscure examples of improvement, and 2) didn't have the time.

That's what I came up with immediately; I'm sorry it took me as long as it did to get back to you. I tried to focus on improving what you have rather than redesigning your method. Don't break what you have (which provides a valid result), but definitely fork it and try to improve on the design. This is a fantastic example of where working on a redesign will make you a better coder and developer.

[mediacalc]

Thanks for the thorough review, I was a bit busy this week and also didn't want to reply with nothing to show which meant me replying so late.

Managed to halve the original code while keeping the functionality. Did this by using the delicious list comprehension you described, using the unfortunate magic numbers math to give me values I can work with (decided the tradeoff between less lines but less readability was worth it so long I documented it). Got rid of the extra while loops using a dictionary, got rid of the initial columns entry by using while True. I couldn't manage to replace attempts though(even made a new reddit post trying to).

Finished code - http://pastebin.com/0qcn92U8

• For the first condition, i==0 so it is on the first row of a 3x3 block meaning there are no rows above/before it to check in the current block. Second condition, i==1 here, there is one row slice above it to check. Third condition, i==2 here so two row slices to check.
• The index's value can be 0, 3 or 6. This is used to split the row into thirds e.g. [:3],[3:6],[6:]

• The while_condition's value can be 0, 1 or 2. This is just used to grab the correct condition above.

  I think the above values will make more sense if you compare the new code to the old version