tag:blogger.com,1999:blog-3722233.post112376370967395498..comments2023-03-29T09:38:56.563-05:00Comments on Computational Complexity: Sudoku RevisitedLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-53717815141645850612011-02-01T12:58:50.149-06:002011-02-01T12:58:50.149-06:00Perhaps it's silly to post a comment on an alm...Perhaps it's silly to post a comment on an almost six year old blog entry but anyways:<br /><br />I'm not sure that the conclusions you drew with USAT are correct. USAT does not promise that there is exactly one satisfying assignment, it promises that there is exactly one satisfying assignment OR there are none. http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT<br /><br />So you see, from that angle USAT is not applicable to the problem 2 of "Given a partially completed grid that has a unique valid completion, find that completion" since this does promises that there is a guaranteed unique solution.Junier Olivahttps://www.blogger.com/profile/02589764251109710569noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1141636396244511342006-03-06T03:13:00.000-06:002006-03-06T03:13:00.000-06:00Anonymous said "in practice a few simple heuristic...Anonymous said "in practice a few simple heuristics can solve all sudoku puzzles". I think this is no true, because for the hardest one, there are no known methodologies. This can be seen with "Computer Aided Sudoku" free excel helper solver game to download at http://perso.wanadoo.fr/sudoku.laviron . When no methods are available it uses bactracking.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126261497573981032005-09-09T05:24:00.000-05:002005-09-09T05:24:00.000-05:00What if the generator of the partial grid was desi...What if the generator of the partial grid was designed such that the solution can be found fast using a given algorithm? <BR/><BR/>For instance, I could generate USat instances such that the satisfying assignment is always built satisfying the "first" (take first as you like) literal in every clause. <BR/><BR/>Those instances are easily solvable. <BR/><BR/>My guess is that Sudoku generators are of such a family of generators.<BR/><BR/>What do you think?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1124438958178353052005-08-19T03:09:00.000-05:002005-08-19T03:09:00.000-05:00There is an acm-programming-contest problem which ...There is an acm-programming-contest problem which ask you to generate a uniquely solvable Sudoku. For a 9x9 grid, either solving a Sudoku or generating a Sudoku puzzle could be done very fast. Here is the problem:<BR/>http://acm.uva.es/p/v108/10893.html<BR/>Here is the timing of the program which generates 20 uniquely solvable Sudoku puzzle.<BR/>http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10893Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123880668449340092005-08-12T16:04:00.000-05:002005-08-12T16:04:00.000-05:00In practice a few simple heuristics can solve all ...In practice a few simple heuristics can solve all sudoku puzzles, and there are many cheater scripts online which will rapidly find solutions for you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123808138904666972005-08-11T19:55:00.000-05:002005-08-11T19:55:00.000-05:00How do the people who generate the puzzles even ch...How do the people who generate the puzzles even check whether their puzzle admits a unique solution? It seems to be NP-hard to determine, even given one solution, whether or not other solutions are possible.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123801941095776442005-08-11T18:12:00.000-05:002005-08-11T18:12:00.000-05:00-- What if the partial grid was generated by a pol...-- What if the partial grid was generated by a polynomial time machine ? Can it be easier than the original problem ?<BR/><BR/>Unlikely. We showed that in general even restrictions to subcases generated by DFAs (regular languages) fail to guarantee polynomiality of NP-complete problems [SODA 2001]. This result has been extended to CFLs as well [Tran, COCOON 2001].<BR/><BR/>Alex Lopez-OrtizAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123790849895839822005-08-11T15:07:00.000-05:002005-08-11T15:07:00.000-05:00What if the partial grid was generated by a polyno...What if the partial grid was generated by a polynomial time machine ? Can it be easier than the original problem ?Anonymousnoreply@blogger.com