AppletTalk.com Java discussions newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  sudoku          AppletTalk.com Forum Index -> Java Help View previous topic :: View next topic   Author Message Guest Posted: Thu Jun 08, 2006 4:08 am    Post subject: sudoku The rules are: " Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. " <http://www.sudoku.com/> Given an existing sudoku puzzle, how to solve it? I'm thinking to ignore the larger puzzle and focus on a single 3x3 matrix. My inclination is for a static class, along the lines of Math.sqrt(), which returns a 3x3 matrix which is correct. This I think could be done with brute force guessing. The fly in the ointment is that the particular solution returned might not be the only solution, that there may exist a second solution. There's also the inherent assumption that a given 3x3 matrix will have a solution, but let's just assume that there's at least one solution. So, how to capture *all* possible solutions to a given 3x3 matrix? here's a sample matrix: _ _ 7 82_ _91 so [0,0] is blank. Going with the brute force method, I'd put a 1 at [0,0]. Then, at [0,1] I'd also put a 1, but that'd be rejected because there's a 1 in that row (row zero). So, [0,1] would get a value of 2. Etc, etc for the other blanks. That'd be simplest way to generate *a* solution, given the assumption that a solution exists. However, what there's an alternate solution with [0,0] having a value of 2? So, this is as far as I've gotten towards this part of the puzzle. I know that I want to capture all possibilities. It's like: [0,0] has 6 possible answers: 1,2,3,4,5, 6 ,9 [0,1] has 5 possible answers: 1, 3,4,5,6, 8 minus whatever's in [0,0] Hmm, seems recursive. Could recursion play a role here? no, this isn't homework. Yes, I've intentionally not googled on this question. Just thinking aloud, feel free to join in :) -Thufir Back to top bH Guest Posted: Thu Jun 08, 2006 6:48 am    Post subject: Re: sudoku Hi, I did this earlier at this post : http://groups.google.com/group/comp.lang.java.help/browse_frm/thread/3de5a9abdc4eaa3c/9fad22fcce114056?q=suduko&rnum=2#9fad22fcce114056 The solution was originally mine. bH hawat.thufir (AT) gmail (DOT) com wrote: Quote: The rules are: " Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. " http://www.sudoku.com/ Given an existing sudoku puzzle, how to solve it? I'm thinking to ignore the larger puzzle and focus on a single 3x3 matrix. My inclination is for a static class, along the lines of Math.sqrt(), which returns a 3x3 matrix which is correct. This I think could be done with brute force guessing. The fly in the ointment is that the particular solution returned might not be the only solution, that there may exist a second solution. There's also the inherent assumption that a given 3x3 matrix will have a solution, but let's just assume that there's at least one solution. So, how to capture *all* possible solutions to a given 3x3 matrix? here's a sample matrix: _ _ 7 82_ _91 so [0,0] is blank. Going with the brute force method, I'd put a 1 at [0,0]. Then, at [0,1] I'd also put a 1, but that'd be rejected because there's a 1 in that row (row zero). So, [0,1] would get a value of 2. Etc, etc for the other blanks. That'd be simplest way to generate *a* solution, given the assumption that a solution exists. However, what there's an alternate solution with [0,0] having a value of 2? So, this is as far as I've gotten towards this part of the puzzle. I know that I want to capture all possibilities. It's like: [0,0] has 6 possible answers: 1,2,3,4,5, 6 ,9 [0,1] has 5 possible answers: 1, 3,4,5,6, 8 minus whatever's in [0,0] Hmm, seems recursive. Could recursion play a role here? no, this isn't homework. Yes, I've intentionally not googled on this question. Just thinking aloud, feel free to join in :) -Thufir Back to top bH Guest Posted: Thu Jun 08, 2006 7:10 am    Post subject: Re: sudoku oops, On a reread I see that I wrote that "the solution was originally mine." This was not the case, the solution was the work of someone else, and I got a lot of help from others here at this java programming help site, who were more informed than I. I am most appreciative of their help. bH bH wrote: Quote: Hi, I did this earlier at this post : http://groups.google.com/group/comp.lang.java.help/browse_frm/thread/3de5a9abdc4eaa3c/9fad22fcce114056?q=suduko&rnum=2#9fad22fcce114056 The solution was originally mine. bH hawat.thufir (AT) gmail (DOT) com wrote: The rules are: " Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. " http://www.sudoku.com/ Given an existing sudoku puzzle, how to solve it? I'm thinking to ignore the larger puzzle and focus on a single 3x3 matrix. My inclination is for a static class, along the lines of Math.sqrt(), which returns a 3x3 matrix which is correct. This I think could be done with brute force guessing. The fly in the ointment is that the particular solution returned might not be the only solution, that there may exist a second solution. There's also the inherent assumption that a given 3x3 matrix will have a solution, but let's just assume that there's at least one solution. So, how to capture *all* possible solutions to a given 3x3 matrix? here's a sample matrix: _ _ 7 82_ _91 so [0,0] is blank. Going with the brute force method, I'd put a 1 at [0,0]. Then, at [0,1] I'd also put a 1, but that'd be rejected because there's a 1 in that row (row zero). So, [0,1] would get a value of 2. Etc, etc for the other blanks. That'd be simplest way to generate *a* solution, given the assumption that a solution exists. However, what there's an alternate solution with [0,0] having a value of 2? So, this is as far as I've gotten towards this part of the puzzle. I know that I want to capture all possibilities. It's like: [0,0] has 6 possible answers: 1,2,3,4,5, 6 ,9 [0,1] has 5 possible answers: 1, 3,4,5,6, 8 minus whatever's in [0,0] Hmm, seems recursive. Could recursion play a role here? no, this isn't homework. Yes, I've intentionally not googled on this question. Just thinking aloud, feel free to join in :) -Thufir Back to top Guest Posted: Fri Jun 09, 2006 1:30 am    Post subject: Re: sudoku Oliver Wong wrote: [...] Quote: A typical sudoku is a 9x9 grid of numbers, which means there are 81 numbers in the entire grid. A 3x3 matrix has 9 numbers in it. Therefore, there must be 9 of these 3x3 grids to make up a full sudoku puzzle. I don't know what you mean by "stack of solutions", and "shuffling the stacks". A Sudoku is supposed to have exactly 1 solution. - Oliver I mean stack in the, err, english language sense. Suduko is 9x9, yes, but there are the smaller 3x3 boxes/grids/matrices, which I'm contemplating. For a given 3x3 matrix, there might be 4 solutions. I'm visualizing having all four solutions printed out on a piece of paper. If the first solution didn't work, try the second solution, then third, then the fourth. Of course, there are 9 different 3x3 matrices, and each might have four solutions. -Thufir Back to top Patricia Shanahan Guest Posted: Fri Jun 09, 2006 2:07 am    Post subject: Re: sudoku hawat.thufir (AT) gmail (DOT) com wrote: Quote: Oliver Wong wrote: [...] A typical sudoku is a 9x9 grid of numbers, which means there are 81 numbers in the entire grid. A 3x3 matrix has 9 numbers in it. Therefore, there must be 9 of these 3x3 grids to make up a full sudoku puzzle. I don't know what you mean by "stack of solutions", and "shuffling the stacks". A Sudoku is supposed to have exactly 1 solution. - Oliver I mean stack in the, err, english language sense. Suduko is 9x9, yes, but there are the smaller 3x3 boxes/grids/matrices, which I'm contemplating. For a given 3x3 matrix, there might be 4 solutions. I'm visualizing having all four solutions printed out on a piece of paper. If the first solution didn't work, try the second solution, then third, then the fourth. Of course, there are 9 different 3x3 matrices, and each might have four solutions. I thought I understood, but now I'm confused. If you are considering a 3x3 square in isolation, without looking at any other squares, which is what I thought you were doing initially, 4 is not a possible number of solutions. To get 4 solutions, you would have be using some additional data from outside the 3x3 square. Patricia Back to top Oliver Wong Guest Posted: Fri Jun 09, 2006 2:57 am    Post subject: Re: sudoku "Patricia Shanahan" <pats (AT) acm (DOT) org> wrote in message news:ok0ig.3275$o4.129 (AT) newsread2 (DOT) news.pas.earthlink.net... Quote: hawat.thufir (AT) gmail (DOT) com wrote: Oliver Wong wrote: [...] A typical sudoku is a 9x9 grid of numbers, which means there are 81 numbers in the entire grid. A 3x3 matrix has 9 numbers in it. Therefore, there must be 9 of these 3x3 grids to make up a full sudoku puzzle. I don't know what you mean by "stack of solutions", and "shuffling the stacks". A Sudoku is supposed to have exactly 1 solution. - Oliver I mean stack in the, err, english language sense. You mean like a stack of books? Is it meaningful in your usage of "stack" that the solutions are ordered (i.e. there's a solution at the top, one beneath it, one beneath that, and so on until the bottom)? Is it meaningful with a stack of books, it's difficult to take the bottom book out of the stack (thus causing the whole thing to collapse), but relatively easy to take a book off the top? Similarly, that it's easy to add a book at the top, but difficult to add to the middle of the stack, without knocking it over? Quote: Suduko is 9x9, yes, but there are the smaller 3x3 boxes/grids/matrices, which I'm contemplating. Right, but if you've played Sudoku, you'll know that you HAVE to look at cells outside of the 3x3 grid you're currently contemplating to gather enough clues to make any progress. Quote: For a given 3x3 matrix, there might be 4 solutions. I'm visualizing having all four solutions printed out on a piece of paper. If the first solution didn't work, try the second solution, then third, then the fourth. What if there are 362880 solutions for a given 3x3 grid? Would you try each one in turn? And if there are 9 of these grids, would you be trying all 362880^9 =~ 10^50 combinations of them? Quote: Of course, there are 9 different 3x3 matrices, and each might have four solutions. If each 3x3 matrix had 4 solutions, you're still looking at 4^9 = 262144 possible combinations of sub-solutions. As can be seen above, the number of combinations explodes (literally) exponentially. - Oliver Back to top Dale King Guest Posted: Sat Jun 10, 2006 7:10 am    Post subject: Re: sudoku hawat.thufir (AT) gmail (DOT) com wrote: Quote: The rules are: " Fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. " http://www.sudoku.com/ Given an existing sudoku puzzle, how to solve it? I'm thinking to ignore the larger puzzle and focus on a single 3x3 matrix. My inclination is for a static class, along the lines of Math.sqrt(), which returns a 3x3 matrix which is correct. This I think could be done with brute force guessing. The fly in the ointment is that the particular solution returned might not be the only solution, that there may exist a second solution. There's also the inherent assumption that a given 3x3 matrix will have a solution, but let's just assume that there's at least one solution. So, how to capture *all* possible solutions to a given 3x3 matrix? here's a sample matrix: _ _ 7 82_ _91 so [0,0] is blank. Going with the brute force method, I'd put a 1 at [0,0]. Then, at [0,1] I'd also put a 1, but that'd be rejected because there's a 1 in that row (row zero). So, [0,1] would get a value of 2. Etc, etc for the other blanks. That'd be simplest way to generate *a* solution, given the assumption that a solution exists. However, what there's an alternate solution with [0,0] having a value of 2? So, this is as far as I've gotten towards this part of the puzzle. I know that I want to capture all possibilities. It's like: [0,0] has 6 possible answers: 1,2,3,4,5, 6 ,9 [0,1] has 5 possible answers: 1, 3,4,5,6, 8 minus whatever's in [0,0] Hmm, seems recursive. Could recursion play a role here? no, this isn't homework. Yes, I've intentionally not googled on this question. Just thinking aloud, feel free to join in As many others have told you your solution is flawed. There are 2 different types of solvers as Oliver said. There are those that try to solve by simple logic. That means that they do not use trial and error. Unfortunately, some puzzles cannot be solved without trial and error (or backtracking) so these solvers do have to resort to trial and error. The preferred method of solving Sudoku is by converting it to an instance of Knuth's dancing links algorithm because Sudoku can be converted into an example of the exact matrix cover problem. Wikipedia has a very nice write up on Sudoku and the methods to solve it: http://en.wikipedia.org/wiki/Sudoku This site is a very good one on solving by logic: http://www.sudokusolver.co.uk/ For some example puzzles that cannot be solved by logic alone see: http://www.sudokusolver.co.uk/grids_nologic.html -- Dale King Back to top Guest Posted: Tue Jun 13, 2006 1:56 am    Post subject: Re: sudoku Dale King wrote: [...] Quote: As many others have told you your solution is flawed. There are 2 different types of solvers as Oliver said. There are those that try to solve by simple logic. That means that they do not use trial and error. Unfortunately, some puzzles cannot be solved without trial and error (or backtracking) so these solvers do have to resort to trial and error. The preferred method of solving Sudoku is by converting it to an instance of Knuth's dancing links algorithm because Sudoku can be converted into an example of the exact matrix cover problem. [...] Heh, lost me on that one. Specifically, that method might not work. How about the general idea of having a static class for the logic, though? Similar to how Math.tan() works, for example. -Thufir Back to top Oliver Wong Guest Posted: Tue Jun 13, 2006 2:27 am    Post subject: Re: sudoku <hawat.thufir (AT) gmail (DOT) com> wrote in message news:1150145789.043717.58480 (AT) h76g2000cwa (DOT) googlegroups.com... Quote: Dale King wrote: [...] As many others have told you your solution is flawed. There are 2 different types of solvers as Oliver said. There are those that try to solve by simple logic. That means that they do not use trial and error. Unfortunately, some puzzles cannot be solved without trial and error (or backtracking) so these solvers do have to resort to trial and error. The preferred method of solving Sudoku is by converting it to an instance of Knuth's dancing links algorithm because Sudoku can be converted into an example of the exact matrix cover problem. [...] Heh, lost me on that one. Specifically, that method might not work. How about the general idea of having a static class for the logic, though? Similar to how Math.tan() works, for example. You mean having a static method like SudokuSolver.solve()? That's could work. How about having sudoku grids capable of solving themselves? SudokuGrid initialGrid = new SudokuGrid(); SudokuGrid solution = initialGrid.solve(); - Oliver Back to top Guest Posted: Wed Jun 14, 2006 6:37 am    Post subject: Re: sudoku Oliver Wong wrote: [...] Quote: SudokuGrid initialGrid = new SudokuGrid(); SudokuGrid solution = initialGrid.solve(); [...] Yes, although I still would like to break it down further than "solve" :) Of course, I've yet to do a damn thing, so it's all hot air on my part. -Thufir Back to top Oliver Wong Guest Posted: Wed Jun 14, 2006 7:19 pm    Post subject: Re: sudoku <hawat.thufir (AT) gmail (DOT) com> wrote in message news:1150249058.517241.105370 (AT) i40g2000cwc (DOT) googlegroups.com... Quote: Oliver Wong wrote: [...] SudokuGrid initialGrid = new SudokuGrid(); SudokuGrid solution = initialGrid.solve(); [...] Yes, although I still would like to break it down further than "solve" When designing, I find it's useful to first think of how the user is going to use your class, and establish an interface from that, and only after having established that interface, do you start worrying about implementation. As a user of your Sudoku API, perhaps I'd very much would like a solve() method which returns a new, completely solved grid. The implementation of solve() could, of course, be "broken down" in the sense that it calls a bunch of other (private) methods. e.g. <pseudoCode> public SudokuGrid solve() { if (!isSolveable()) { throw new IllegalStateException("Sudoku grid is not solveable"); } SudokuGrid currentGrid = this; for (Solver s : getSolvers()) { if (currentGrid.isSolved()) { break; } currentGrid = s.solve(currentGrid); } assert currentGrid.isSolved(); return currentGrid; } private List<Solver> getSolvers() { List<Solver> returnValue = new LinkedList<Solver>(); returnValue.add(new SinglePositionSolver()); returnValue.add(new SingleCandidateSolver()); returnValue.add(new CandidateLinesSolver()); returnValue.add(new DoublePairSolver()); returnValue.add(new MultipleLinesSolver()); returnValue.add(new NakedPairSolver()); returnValue.add(new NakedTripletSolver()); returnValue.add(new HiddenPairSolver()); returnValue.add(new HiddenTripletSolver()); returnValue.add(new XWingSolver()); returnValue.add(new SwordFishSolver()); returnValue.add(new ForcingChainsSolver()); returnValue.add(new DancingChainsSolver()); } </pseudoCode> - Oliver Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         AppletTalk.com Forum Index -> Java Help All times are GMT Page 1 of 1   Jump to: Select a forum Java Newsgroups----------------Java DiscussionsWeb-based java games comp.lang.java 3D Graphics API's for Java Java: Support and criticism Java System Announcements comp.lang.java.api JavaBeans Java and CORBA Java and Databases comp.lang.java.developer Java GUI Toolkits Java Help comp.lang.java.javascript JVM, native methods and hardware comp.lang.java.misc Java Language Programming Security and Java comp.lang.java.setup Java Software Tools comp.lang.java.tech ibm.software.java.linux  Non-English Java Newsgroups----------------Java Language (German)Language Java (Français)Java (Italian)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.