Timeline for Algorithms for Fixing Sudokus
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2018 at 23:33 | comment | added | Joshua Grochow | Yes, but you can ask a similar kind of question for many NP-complete problems, and in all examples I know of, the analogous questions for other NP-complete problems remain NP-complete. So, I agree with Gerhard Paseman, your probably is very likely NP-complete. (More technically, it is an NP-optimization problem that is NP-hard.) | |
| Mar 17, 2018 at 20:18 | answer | added | Taneli Huuskonen | timeline score: 1 | |
| Mar 17, 2018 at 15:21 | comment | added | Manfred Weis | @GerhardPaseman even if the problem of solving a Sudoku is in NP, verifying a solution is in P, and the question is, whether my problem is more related to finding a solution or to verifying a solution. | |
| Mar 17, 2018 at 15:18 | comment | added | Manfred Weis | @JoshuaGrochow but my question is not aimed at actually solving a Sudoku, but rather at removing entries of a partially filled Sudoku to restore solvability; is that problem also of the same complexity? | |
| Mar 17, 2018 at 15:11 | comment | added | Joshua Grochow | In general solving n x n Sudoku is NP-complete. If you are promised there's a unique solution (as is often the case with actual Sudoku puzzles) it is in UP, but still hard for NP under randomized poly-time reductions. | |
| Mar 17, 2018 at 15:03 | comment | added | Gerhard Paseman | Is it known whether solving a Sudoku is in NP? If so, then this problem is likely of the same complexity. I imagine this is equivalent to finding a maximal set of consistent constraints in a CSP system. Gerhard "Coffee: Foundational To My Consistency" Paseman, 2018.03.17. | |
| Mar 17, 2018 at 14:51 | comment | added | Manfred Weis | @BrendanMcKay good point; I simply overlooked that. I now edited the question, so that possible answers will be more interesting. | |
| Mar 17, 2018 at 14:48 | history | edited | Manfred Weis | CC BY-SA 3.0 |
provided a generalization of Sudoku, th which the question shall refer
|
| Mar 17, 2018 at 10:25 | history | edited | YCor |
edited tags
|
|
| Mar 17, 2018 at 10:17 | history | edited | Emil Jeřábek |
edited tags
|
|
| Mar 17, 2018 at 10:07 | comment | added | Brendan McKay | It takes constant time, because there are only finitely many possibilities. Perhaps you meant to consider some generalization of Sudoku to arbitrarily large boards, but there is more than one way to generalise and you need to specify which you want. | |
| Mar 17, 2018 at 9:12 | history | asked | Manfred Weis | CC BY-SA 3.0 |