Sudoku Puzzle Generator

I've written a Sudoku puzzle generator. It currently runs through each line of the 9x9 grid and places numbers randomly if they're valid. It loops over all the numbers from 1-9 and then if it finds itself trapped in a corner with no valid answers it throws out the whole board and restarts.

I tested it by making 1000 puzzles and it took just under 100 seconds, so a single puzzle takes 0.1. In practical terms that's almost negligible but still seems wasteful to ditch the processing up to that point (as it takes, on average, hundreds of attempts to find a valid puzzle). I'm maybe just being impractical to want a more intelligent solution so I thought I'd ask how it looks to people on here and if anyone has suggestions on improving it.

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

def makeBoard():
board = None
while board is None:
board = attemptBoard()
return board

def attemptBoard():
board = [[None for _ in range(9)] for _ in range(9)]
for i in range(9):
for j in range(9):
checking = numbers[:]
random.shuffle(checking)
x = -1
loopStart = 0
while board[i][j] is None:
x += 1
if x == 9:
#No number is valid in this cell, start over
return None
checkMe = [checking[x],True]
if checkMe in board[i]:
#If it's already in this row
continue
checkis = False
for checkRow in board:
if checkRow[j] == checkMe:
#If it's already in this column
checkis = True
if checkis: continue
#Check if the number is elsewhere in this 3x3 grid based on where this is in the 3x3 grid
if i % 3 == 1:
if j % 3 == 0 and checkMe in (board[i-1][j+1],board[i-1][j+2]): continue
elif

1. Review

-
There are no docstrings. What do these functions do?

-
The Python style guide says, "limit all lines to a maximum of 79 characters." If the code followed this recommendation, then we wouldn't have to scroll it horizontally to read it here.

-
The board is not represented consistently. Looking at printBoard, it seems that each cell is represented by a list [a, b] where b is False if the cell is empty, and True if it contains the number a. But the initialization of the board in attemptBoard looks like this:

board = [[None for _ in range(9)] for _ in range(9)]

which represents empty cells as None, so that if I try to print this board, I get:

TypeError: 'NoneType' object is not subscriptable

I would recommend using a consistent board representation. In this case I think it makes more sense to use None for an empty cell and a number for a full cell (rather than a list). That's because (i) None and small numbers don't need any memory allocation, whereas a list needs to be allocated; (ii) testing a None or a number is quicker than testing a list.

-
In printBoard you have very repetitive code:

print ("|| {} | {} | {} || {} | {} | {} || {} | {} | {} ||".format(
            line[0][0] if line[0][1] else ' ',
            line[1][0] if line[1][1] else ' ',
            line[2][0] if line[2][1] else ' ',
            line[3][0] if line[3][1] else ' ',
            line[4][0] if line[4][1] else ' ',
            line[5][0] if line[5][1] else ' ',
            line[6][0] if line[6][1] else ' ',
            line[7][0] if line[7][1] else ' ',
            line[8][0] if line[8][1] else ' ',))

This can be rewritten using a loop:

print("|| {} | {} | {} || {} | {} | {} || {} | {} | {} ||"
      .format(*(number if full else ' ' for number, full in line)))

or, after simplifying the board representation as recommended above:

print("|| {} | {} | {} || {} | {} | {} || {} | {} | {} ||"
      .format(*(cell or ' ' for cell in line)))

-
The nested loops:

for i in range(9):
    for j in range(9):

can be combined into one using itertools.product:

for i, j in itertools.product(range(9), repeat=2):

-
The variable loopStart is never used.

-
Instead of this complex while loop:

x = -1
while board[i][j] is None:
    x += 1
    if x == 9:
        #No number is valid in this cell, start over
        return None
    checkMe = [checking[x],True]

    # ... loop body here ...

    #If we've reached here, the number is valid.
    board[i][j] = checkMe

write a for loop with an else:

for x in checking:
    # ... loop body here ...

    # If we've reached here, the number is valid.
    board[i][j] = x
    break
else:
    # No number is valid in this cell, start over.
    return None

-
The column check:

checkis = False
for checkRow in board:
    if checkRow[j] == checkMe:
        #If it's already in this column
        checkis = True
if checkis: continue

can be simplified using the built-in function any:

if any(row[j] == checkMe for row in board): continue

-
The code for checking against other cells in the 3×3 block is very repetitive:

if i % 3 == 1:
    if   j % 3 == 0 and checkMe in (board[i-1][j+1],board[i-1][j+2]): continue
    elif j % 3 == 1 and checkMe in (board[i-1][j-1],board[i-1][j+1]): continue
    elif j % 3 == 2 and checkMe in (board[i-1][j-1],board[i-1][j-2]): continue
elif i % 3 == 2:
    if   j % 3 == 0 and checkMe in (board[i-1][j+1],board[i-1][j+2],board[i-2][j+1],board[i-2][j+2]): continue
    elif j % 3 == 1 and checkMe in (board[i-1][j-1],board[i-1][j+1],board[i-2][j-1],board[i-2][j+1]): continue
    elif j % 3 == 2 and checkMe in (board[i-1][j-1],board[i-1][j-2],board[i-2][j-1],board[i-2][j-2]): continue

The reason you go to this trouble is to avoid testing against board[i-1][j] and board[i-2][j], which you know would be useless, because you already tested these cells when you checked the column. But in fact that's a false economy. You avoid an unnecessary test, but at the cost of a lot of extra code. It turns out to be just as fast, but a lot simpler, to test all the entries in previous rows of the block, like this:

i0, j0 = i - i % 3, j - j % 3 # origin of 3x3 block
if any(x in row[j0:j0+3] for row in board[i0:i]):
    continue

-
The code only works for 9×9 Sudoku grids made up of 3×3 blocks. But there's nothing special about the numbers 3 and 9 here: the algorithm would be essentially the same for 2 and 4, or 4 and 16. So why not make the code general?

1. Revised code

This isn't any faster than the original code, but it's a lot shorter and simpler, which makes it a better place to start when speeding it up:

```
import itertools
import random

def attempt_board(m=3):
"""Make one attempt to generate a filled m2 x m2 Sudoku board,
returning the board if successful, or None if not.

"""
n = m**2
numbers = list(range(1,

StackExchange Code Review Q#88849, answer score: 16