I have a question about my Theoretical Computer Science Stack Exchange post: Generating n^2 x n^2 valid and pre-solved Sudoku's in $O(n^3)$ time is inconsequential?
Should I quit this question?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Up to you, really. It looks like you got some helpful comments from @mhum so maybe be satisfied with those.
answered Jun 8, 2019 at 22:10
-
$\begingroup$ Well, I was considering showing that this algorithm solves any $n$-size special cases of the 3-coloring problem. And it can also generate k-coloring "Puzzles" in poly-time. Sorta like Sudoku. Every Sudoku Puzzle of any $n^2 x n^2$ size; when its top $n x n$ box is validly solved. Its remaining squares can be solved under constraint in poly-time. Because, ALL valid Sudoku solutions follow their own cyclic permutation pattern. Which can be used to generate a $O(n^k)$ time grid generator. Update: It can generate easy instances of k-coloring, but it hasn't been hard-coded yet. Just for Sudoku. $\endgroup$ Jun 9, 2019 at 14:36
-
$\begingroup$ May be trivial, but should have sparked interest on this stack. :( $\endgroup$ Jun 9, 2019 at 14:36