# Would this be on topic for this site?

## Disprove that this code generate valid n^2 x n^2 Sudoku Grids

I'm complete with my Sudoku Project and others have been skeptical that I can generate pre-filled valid Sudoku grids in poly-time.

Now, disprove formally that this code won't print one out of n! valid grids sequentially of 9 x 9, 12 x 12, ..... ---- > n^2 x n^2

Remember, the rules for a 12 x 12. it would be 3 x 4 squares. You'll have to know how a valid Sudoku grid would map out for a n x n. eg. 9 x 9 would be 3 x 3.

A 9 x 9 grid would follow a list that has a length of non-repeating 9 elements.

You are asked for input to map out valid grid in O(n^2) time.

HINT: If you generate larger grids than 9 x 9, you'll need to make sure your input is given for human readability eg.['[01]','[02]'...]

print('enter with [1,2,3...] brackets')
tup = input()[1:-1].split(',')
x = input('Enter mapping 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 ... 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('')


If you can't disprove, then prove it. And, if it is non-finite subsets of n^2 x n^2 but with some sets not mappable then prove that as well.

Gratitude and Appreciation would be much given as an award.

I have a link to an improved code-https://codereview.stackexchange.com/a/221537/194047

instructions

• Regardless of this being off-topic, thanks for asking about it first! It's much easier for both sides to ask whether it's on-topic before having your question be downvoted & closed after the fact. Jun 3, 2019 at 2:22
• Isn't proof-golf on-topic?
Jun 3, 2019 at 7:16
• @Adám Probably, would require some kind of predicate logic with a lim function or something like that. I'm not good at math that's why I wanted to share. Jun 3, 2019 at 11:23
• By the way, this program does not run in n^2 time - the output is size n^4, so it's obviously not in n^2 time. It looks like it runs in n^6 time. Also, there is a very simple algorithm that runs in n^4 time to output a valid n^2 x n^2 solved sudoku grid: For the first row, output the numbers in order: 1234... For the next row, rotate by n: n, n+1, n+2, .... For the first n rows, increase the rotation amount by n each time. For the next set of n rows, start at a rotation of 1, then increase by n each time. In general, the i*n+jth row should be rotated by j*n+i, where i<n, j<n. Oct 17, 2019 at 17:09
• Finally, neither this simpler program nor your original are "poly-time", since the input is of size log n, and the runtime is polynomial in n, and therefore exponential in the size of the input. Oct 17, 2019 at 17:09
• @isaacg I don't see how its exponential if the input x exceeds in length compared to what the other variables are doing. Take a look at this link. It should be O(n^4) by bitlength. i.imgur.com/VvXh4bA.png Oct 19, 2019 at 1:41

Welcome to Programming Puzzles & Code Golf Stack Exchange, and thanks for asking! Unfortunately, this question wouldn't be on-topic here, since we generally accept two kinds of questions:

• Challenges where the answerers are asked to write code to solve a specified task. These are competitions with a specified objective winning criterion (i.e. the measure of comparison between two answers to find out which one performs better or if they tie, also included as a tag on the question, usually ).
• Non-challenge questions where the asker wants on how to optimize their code so that it compares better with a specified objective winning criterion. We also have questions for golfing tricks in specific languages, as well as a general one.