tag:blogger.com,1999:blog-6555947.post111722941507251427..comments2023-03-22T02:10:06.522-06:00Comments on The Geomblog: Sudoku OK, kudos UKSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-6555947.post-1378968876018211152009-11-08T01:11:46.644-07:002009-11-08T01:11:46.644-07:00I would be very interested in seeing that php sudo...I would be very interested in seeing that php sudoku generator, Im running an excellent one at a <a href="http://dailysudoku.info" rel="nofollow">dailysudoku</a> website, perhaps I can help you improve upon it.Sudoku Solverhttp://sudokusolver.infonoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1155542751511412322006-08-14T02:05:00.000-06:002006-08-14T02:05:00.000-06:00I recently created a PHP version of a Sudoku gener...I recently created a PHP version of a Sudoku generator. The results can be found on my website. The class uses an elimination strategy. I have created a debug page so you can see what it's doing each step of the way. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.crmacd.biz/projects_blog" REL="nofollow" TITLE="crmacd at crmacd dot biz">Chris</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1154905949028360142006-08-06T17:12:00.000-06:002006-08-06T17:12:00.000-06:00I'm interested in learning that if all typical con...I'm interested in learning that if all typical constraints aren't met, does the puzzle have more than one solution? Using logic you'd expect that this would be the case. Has anyone ever looked at the relationship between the ability of a puzzle to be solved completely by constraints versus the requirement of being solved by a brute-force goal-seeking algorithm. I've written both of these in C using gcc if anyone wants to take a peek, but I've not done all the research. The concern I have with using azfodel's method is that is only covers "most" puzzles and not all puzzles. This was one of the reasons I wrote my own solver, most solvers I've use out there crash when you give it "difficult" input.<BR/> --Mike Neuliep <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2005/05/sudoku-ok-kudos-uk.html" REL="nofollow" TITLE="mike at illiana dot net">Mike Neuliep</A>Mike Neuliephttps://www.blogger.com/profile/08112499605686321198noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1140709655577355782006-02-23T08:47:00.000-07:002006-02-23T08:47:00.000-07:00I found a way of calculating the solution to (most...I found a way of calculating the solution to (most) sudoku puzzles, which does not involve "logic" or "trial and error," and which is in fact brain-dead simple; it makes me wonder whether sudoku is really a lot simpler than it seems (perhaps that's the wide appeal: it looks hard, but it's not TOO hard). You can read about PSS, my probabilistic sudoku solver by clicking on the ling below.<BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.feynmanlectures.info/pss/sudoku.html" REL="nofollow" TITLE="codelieb at mail dot com">Michael A. Gottlieb</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1139578809486068572006-02-10T06:40:00.000-07:002006-02-10T06:40:00.000-07:00do you want a 64x64 sudoku ? Posted by azfode...do you want a 64x64 sudoku ?<BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="sudoku.romaghi.net" REL="nofollow" TITLE="sodoku at romaghi dot net">azfodel</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1135589323037047662005-12-26T02:28:00.000-07:002005-12-26T02:28:00.000-07:00I am in love with this game. This daily sudoku sit...I am in love with this game. This daily sudoku site has it all...<BR/><BR/>Engoy <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.daily-sudoku.com/" REL="nofollow" TITLE="aalior at hotmail dot com">Keren Simpson</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1131057610836808922005-11-03T15:40:00.000-07:002005-11-03T15:40:00.000-07:00Well, but the fact that sudoku (and latin squares)...Well, but the fact that sudoku (and latin squares) belong to the NP-complete class does involve any important consequence on the whole class itself ? Does it shade new light on the deep nature of NP and its relationship to P ? <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnthonyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1122977554569407682005-08-02T04:12:00.000-06:002005-08-02T04:12:00.000-06:00http://www.yogi.net/sudoku generates random puzzle...http://www.yogi.net/sudoku generates random puzzles <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="woodax@gmail.com" REL="nofollow" TITLE="wood">alex</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1120604346248253172005-07-05T16:59:00.000-06:002005-07-05T16:59:00.000-06:00I also wrote a quick 200-line solver in ruby. I tr...I also wrote a quick 200-line solver in ruby. I tried at first for a closed solution, but in the end I found a recursive brute-force method to be easier. It's fixed for 9x9, but everything but the code I use to print it in ASCII should translate easily to nxn.<BR/>I'm in pretty much the same boat as you, chris. I can "create" puzzles by blanking out a pattern of numbers from a complete board, but these aren't "real" puzzles like (i assume) they have in the papers.<BR/><A HREF="http://www.pro.or.jp/~fuji/java/puzzle/numplace/makesudoku/sudoku01.html.en<br/>" REL="nofollow">This</A>  website offers a somewhat-cryptic algorithm for creating the puzzles the "right way", but I think there must be something more elegant out there somewhere.<BR/>Oh, and if anybody wants to see my code, just drop me an email. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2005/05/sudoku-ok-kudos-uk.html" REL="nofollow" TITLE="42aqk9s02 at sneakemail dot com">peter</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1119226169277411992005-06-19T18:09:00.000-06:002005-06-19T18:09:00.000-06:00Some background knowledge you might be interested ...Some background knowledge you might be interested in, Chris:<BR/>wikipedia.org/wiki/Sudoku has a nice article on both solving and creation of Sudokus.<BR/>The largest sudokus that seem to exist are 49x49, published by a Japanese magazine.<BR/>There are many programs on the web that solve and create Sudokus, but sudoku.com is a good place to start. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2005/05/sudoku-ok-kudos-uk.html" REL="nofollow" TITLE="asafspades at gmail dot com">aceofspades</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1118134206086746032005-06-07T02:50:00.000-06:002005-06-07T02:50:00.000-06:00Well, thank you - it is fascinating to see how you...Well, thank you - it is fascinating to see how you became hooked on this.<BR/><BR/>My first reaction on discovering them was to complete the puzzle but before I completed it, I realised that it would be more fun to write a program to solve them, which I did after a little thought to the algorithm over lunch.<BR/><BR/>Then the Independent issued a 16 x 16 Super Sudoku puzzle, so having foolishly programmed with absolutes, I had to re-write using a table-driven algorithm. So now, when we get the Christmas 25 x 25 or worse, I can modify the program very quickly to add these options, and everything down to the type sizes should automatically change.<BR/><BR/>The problem I have found is with creation. I haven't managed to determine a creation algorithm so ended up by using my solver in the background to create a random puzzle then removing all but a fixed proportion of the answers, leaving a symmetrical pattern of numbers behind for the solver to solve, more for the "easy" puzzles than for the "difficult" ones.<BR/><BR/>I haven't worked out yet how to determine the difficulty of a puzzle and in solving them and building them with my method, one could unwittingly create a puzzle with multiple solutions, although again, how to determine that in less than a couple of seconds of processing would be difficult. Some newspapers guarantee that there is only one solution, but they are simple puzzles with only one solution route, solved by my solver in a single pass, whereas those with a choice take two or even three passes.<BR/><BR/>I did find that the processing was greatly speeded up by adding an algorithm to remove alternative options from two doubles or three triples within each row and/or column and/or cube, but the 16 x 16 still take over one second to complete and even longer to create using a randomised two-level table.<BR/><BR/>My current version is available under the StedmanTim ID on eBay or from the www.LexingSoftware.com website, but if anyone has any suggestions for improvements in creation, and in particular can provide a creation algorithm, I'd be a friend for life!!<BR/><BR/>Having solved the problem with a workable solution, I'm slightly losing interest, but this would be revived with suggestions for improvement or a better mathematician's input to the algorithm.<BR/><BR/>And now, 2,866 lines of VB6 code later, I'll go away and do something more useful, like feeding the ducks.<BR/><BR/>Thank you, Graham, for letting me respond - I'd be most grateful to hear from anyone else.<BR/><BR/>Chris. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="www.LexingSoftware.com" REL="nofollow" TITLE="Chris at LexingSoftware dot com">Chris Stedman</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117681341788439882005-06-01T21:02:00.000-06:002005-06-01T21:02:00.000-06:00Wow -- so no danger of the brit newspapers of runn...Wow -- so no danger of the brit newspapers of running out of puzzles to run!<BR/><BR/>cheers<BR/>graham <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>Graham CormodeAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117666027661430912005-06-01T16:47:00.000-06:002005-06-01T16:47:00.000-06:00There are 288 Sudoku-2 boards, found by enumeratin...There are 288 Sudoku-2 boards, found by enumerating the 12 boards which have 1234 as the first row by hand, and noting that all other boards are obtained from one of these by replacing 1, 2, 3, and 4 by one of the 4! permutations of them.<BR/><BR/>The number of Sudoku-3 boards is > 3*10^14, and < 5524751496156892842531225600 ~= 5*10^27: lower bound from enumeration (before I killed it), upper bound from the number of 9x9 latin squares (from Neil Sloane's <A HREF="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002860" REL="nofollow">OEIS</A> ).<BR/><BR/>In fact, the enumeration had found >10^9 boards starting:<BR/> 123|456|789<BR/> 456|789|123<BR/> 789|123|456<BR/> ---+---+---<BR/> 2<BR/>when I put it out of its misery.  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>David ApplegateAnonymousnoreply@blogger.com