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)):

    #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 = '')

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



  • 10
    \$\begingroup\$ 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. \$\endgroup\$
    – Riker
    Jun 3, 2019 at 2:22
  • \$\begingroup\$ Isn't proof-golf on-topic? \$\endgroup\$
    – Adám
    Jun 3, 2019 at 7:16
  • \$\begingroup\$ @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. \$\endgroup\$
    – The T
    Jun 3, 2019 at 11:23
  • \$\begingroup\$ 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. \$\endgroup\$
    – isaacg
    Oct 17, 2019 at 17:09
  • \$\begingroup\$ 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. \$\endgroup\$
    – isaacg
    Oct 17, 2019 at 17:09
  • \$\begingroup\$ @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 \$\endgroup\$
    – The T
    Oct 19, 2019 at 1:41

1 Answer 1


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.

For more details, read What topics can I ask about here? in our Help Center.

  • \$\begingroup\$ So proof-golf is off-topic? \$\endgroup\$
    – Adám
    Jun 3, 2019 at 7:17
  • \$\begingroup\$ @Adám "generally" :P More specifically, proof-golf is an exception, and is currently very rare (only one user has posted such challenges). Obviously, exceptions always exist. Another example is showcase, where there's no winning criterion at all, because the community has decided to keep it open. As for your intention in your comment under the question, no, that's not proof-golf, where "There should be a complete and unambiguous set of well-defined axioms and a definition of what constitutes a single valid step in the proof." \$\endgroup\$ Jun 3, 2019 at 11:24
  • \$\begingroup\$ @EriktheOutgolfer Oh, I'm just in time! :) Wow, maybe in a special case this question could be asked (after some improvements) to show what kind of proof I'm looking for. Predicate Logic with lim function was the best I got, but it only should have proved that non-finite n x m Sudokus can be generated by this algorithm. But, it wasn't enough to prove n^2 x n^2. \$\endgroup\$
    – The T
    Jun 3, 2019 at 11:27
  • 1
    \$\begingroup\$ @TravisWells That's... not really encouraged. Even if you manage to convert your code into a mathematical formulation, a proof-golf question isn't intended for asking for a proof or disproof, but not knowing which one is true. Instead, proof-golf is for challenges where you're given some axioms and a theorem that's known to be provable only with the given axioms, and you're asked to use the least steps possible (lemmas don't shorten the proof) to prove the theorem. \$\endgroup\$ Jun 3, 2019 at 11:32
  • 1
    \$\begingroup\$ To help clarify, any challenge in which the goal is simply "be the first person to provide a valid answer" is considered off-topic. \$\endgroup\$
    – PhiNotPi
    Jun 3, 2019 at 14:44
  • \$\begingroup\$ It is worth noting that a proof in sufficiently mathemetized systems is a computer program (link) in a different sort of language. Which is, by the way, the justification for it being on topic in the first place. \$\endgroup\$
    – Wheat Wizard Mod
    Jun 9, 2019 at 0:55
  • \$\begingroup\$ @SriotchilismO'Zaic The slight difference from atomic-code-golf is that the "program" is actually a sequence of axioms (proof) that doesn't execute as a program, that's why it's kinda an exception. :P \$\endgroup\$ Jun 9, 2019 at 4:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .