# Generate n^2 x n^2 Sudoku in poly-time

## Introduction

I have created an algorithm that generates n! Sudoku Grids in poly-time.I verified the correctness of my grids with a SAT solver up to 50x50. I'm awaiting a review for improvements. It seems that it's in $$\O(n^3)\$$ time. I am saying valid complete Puzzles can be generated in poly-time, not solving arbitrary puzzles in poly-time.

## Working Code

Here's a link to my code. It's working and input should be like a list [1,2,3,4,5,6,7,8,9]. Brackets needed for input.

Input should be like a list. [1,2,3....] and no repeating elements.

There is input because 9 x 9 is not the only valid Sudoku it can generate. It can generate 50 x 50, 12 x 12, 10 x 10

tup = input()[1:-1].split(',')

x = input('Enter mapping to generate valid Sudoku eg. 3 for 9 x 9')
e = input('Enter 9 for 9 x 9 ...12 for 12 x 12')
f = input('Enter 3 if its a 9 x 9 and corresponding for n^2 x n^2')

x = int(x)
e = int(e)
f = int(f)

squares = []

for index in range(len(tup)):
tup.append(tup.pop(0))
squares.append(tup.copy())

#Everything below here is just printing

for s in range(x):
for d in range(0,e,f):
for si in range(s,e,f):
for li in range(d,d+f):
print(squares[si][li], end = '')
print('')


## Conclusion

Side note: If you want to create 12 x 12 or any larger Sudoku's, you'll need to edit the input so that the values are readable (e.g. ['[01]','[02]',....]).

Larger Valid Grid

I was wondering if you can point out my mistakes in the code?

• Yes, it is indeed O(n^3) time. And, that is poly-time. For pop(0) for shifting the elements is T ∈ Θ(n). The append and copy is O(1). And the remaining mapping part of the algorithm is taking 3 more inputs. So that makes T(n)=T(n/2)+Θ(n3) or O(n^3). So, it must be cubic time. – Travis Wells Jun 2 at 6:19
• That linked output is 50x25, which is not n² x n². 50 isn't even n² on its own. Maybe it's a n x m Soduku, if such a thing exists. – Thomas Weller Jun 2 at 22:14
• @ Then it's allowed. Sat Solver says valid. There is probably human error in its input. 100 x 100 resulted into valid outputs. – Travis Wells Jun 2 at 22:17
• @ThomasWeller My error. Probably my mapping input was incorrect. I'll accept that I make mistakes. – Travis Wells Jun 2 at 22:21
• I'm not sure what to do for those who don't understand the script. What should I do? I don't want to receive a question block unduly. – Travis Wells Jun 3 at 0:18

tup = input()[1:-1].split(',')


It's really bad style to require interactive input without the slightest hint about the expected format.

x = input('Enter mapping to generate valid Sudoku eg. 3 for 9 x 9')
e = input('Enter 9 for 9 x 9 ...12 for 12 x 12')
f = input('Enter 3 if its a 9 x 9 and corresponding for n^2 x n^2')


These variable names are horrible. Do not use single-letter variable names unless you are using the exact names as they appear in a mathematical paper. And in that case, always provide a comment that links to the paper.

• Why and how did you choose the variable name x?
• Why and how did you choose the variable name e?
• Why and how did you choose the variable name e?
• What is the difference between x and f? For a 9×9 sudoku, both should be 3.
• Why do you make the user of the program enter the value anyway? If there's only one valid value, there is no reason to annoy the user with unnecessary questions.

x = int(x)
e = int(e)
f = int(f)

squares = []

for index in range(len(tup)):
tup.append(tup.pop(0))
squares.append(tup.copy())


It's unexpected that the code modifies tup here. The code can be written in an alternative form that doesn't modify tup:

for i in range(len(tup)):
squares.append(tup[i:] + tup[:i])


To give the readers of the code some hints about the structure, you should define separate functions for the different tasks. In this case, these are:

• reading the parameters from the input
• generating the square
• printing the square

By doing this, it becomes immediately clear which parameters are needed for generating the square, and which parameters are only needed for printing it. For example:

def generate_square(symbols):
square = []
for i in range(len(symbols)):
square.append(symbols[i:] + symbols[:i])
return square


Or, a little shorter:

def generate_square(symbols):
return [symbols[i:] + symbols[:i] for i in range(len(symbols))]


I did a test run of your program:

1,2,3,4,5,6,7,8,9
Enter mapping to generate valid Sudoku eg. 3 for 9 x 93
Enter 9 for 9 x 9 ...12 for 12 x 1211
Enter 3 if its a 9 x 9 and corresponding for n^2 x n^23
2345678Traceback (most recent call last):
File "a.py", line 28, in <module>
main()
File "a.py", line 24, in main
print(squares[si][li], end = '')
IndexError: list index out of range


Doing that I noticed:

• if I hadn't read the code before, I would not know what to type in the first line
• in the second line, in 9 x 93, it is not clearly visible what is the prompt and what is the input. The prompt should end with 3 for 9 x 9:.
• there is no input validation. As I said before, if there is only one valid input, the program should not ask for it.
• because of the missing input validation, the program crashes.

Next test run:

1,2,3,4,5,6,7,8,9
Enter mapping to generate valid Sudoku eg. 3 for 9 x 93
Enter 9 for 9 x 9 ...12 for 12 x 129
Enter 3 if its a 9 x 9 and corresponding for n^2 x n^23
2345678
5678234
8234567
3456782
6782345
2345678
4567823
7823456
2345678


The program outputs 7×9 digits. That's not a sudoku. There is a bug in the printing part. This bug is so obvious that it makes your question off-topic on this site. This site is only for code that is regarded as working.

• If I'm coming off arrogant, its not my intentions and I apologize for that. I wanted to make sure that I'm direct as I myself wouldn't expect to understand cues over the internet. My intentions are not to be unfriendly. – Travis Wells Jun 3 at 11:03
• Again, I apologize. And, no I'm not apologizing just for others to see. Thank you for the review. The critique is needed for improvement so I won't confuse users when I continue practicing coding. – Travis Wells Jun 3 at 11:11
• The code is meant to take lists with brackets in their input, maybe that's why you got an invalid sudoku. My fault, for not being clear enough. That's why we have Code-Review. – Travis Wells Jun 3 at 11:12
• Here's a link to improved working code. repl.it/repls/TubbyPrestigiousFirm – Travis Wells Jun 3 at 22:39