----------------------------------- wtd Sun Jul 24, 2005 5:53 pm Logic Puzzle Challenge ----------------------------------- I have a 9 by 9 grid. Each space may contain a number between 1 and 9. Each row and rolumn may only contain unique numbers. The grid is further divided into 9 3 by 3 grids. Each of these smaller grids may only contain unique numbers. You start out with: *681*3*** *5**64*3* 2*****846 7**2**18* 1*56**7** 8**75***4 ****8**52 *84*9***7 *72**63** Where asterisks represent unknowns. Write a computer program which computes the unknowns. ----------------------------------- 1of42 Sun Jul 24, 2005 6:09 pm ----------------------------------- O.M.F.G. This is the puzzle that's sweepnig through Canada in the Globe, isn't it? (Name escapes me at the moment). I'll have to give it a try though. ----------------------------------- Hikaru79 Sun Jul 24, 2005 6:12 pm ----------------------------------- 1of42, yes it is, but don't say the name because then people might be tempted to cheat by looking up existing algorithms. Security by obscurity ;) I'm working on it too :D ----------------------------------- wtd Sun Jul 24, 2005 6:12 pm ----------------------------------- The example is the July 22nd puzzle. :) Oh, and the output should be the same as the input, but with the final values in place of asterisks. ----------------------------------- Delos Sun Jul 24, 2005 6:13 pm ----------------------------------- I've solved a couple of them. Remind me of my precious Rubicks cube in many respects. Since they are all computer generated, I figure there must be an algorithm to *create* them, thus there ought to be one to solve them. I have some ideas, though most are pretty long and tedious. One word removed to maintain a fair competition. ----------------------------------- wtd Sun Jul 24, 2005 6:17 pm ----------------------------------- I know it can be solved. $ wc grid_solver.py 100 314 3174 grid_solver.py $ ;) ----------------------------------- MysticVegeta Mon Jul 25, 2005 9:15 am Re: Logic Puzzle Challenge ----------------------------------- Where asterisks represent unknowns. Write a computer program which computes the unknowns. What do you mean? We dont know the relations between the numbers, how to compute the asterisks??? :? ----------------------------------- wtd Mon Jul 25, 2005 11:24 am Re: Logic Puzzle Challenge ----------------------------------- Where asterisks represent unknowns. Write a computer program which computes the unknowns. What do you mean? We dont know the relations between the numbers, how to compute the asterisks??? :? The same number may not occur twice in any row, column, or smaller 3 by 3 grid. ----------------------------------- rizzix Mon Jul 25, 2005 4:45 pm ----------------------------------- Aight, took me 17 whole min... __________________ |4-6-8 |1-2-3-|5-7-9-| |9-5-7-|8-6-4-|2-3-1-| |2-3-1-|9-7-5-|8-4-6-| |~~~~|~~~~|~~~~| |7-4-6-|2-3-9-|1-8-5-| |1-9-5-|6-4-8-|7-2-3-| |8-2-3-|7-5-1-|9-6-4-| |~~~~|~~~~|~~~~| |6-1-9-|3-8-7-|4-5-2-| |3-8-4-|5-9-2-|6-1-7-| |5-7-2-|4-1-6-|3-9-8-| ~~~~~~~~~~~~~~ ----------------------------------- wtd Mon Jul 25, 2005 4:48 pm ----------------------------------- Yes, I can solve it by had in around 10 minutes. Now, show me the program you used to programmatically generate that answer. :) ----------------------------------- rizzix Mon Jul 25, 2005 4:51 pm ----------------------------------- i didn;t... it was by hand... :P i'll work on an algorithm later.. right now i just did that to kill time, altough i got soo much stuff to do pfft... ----------------------------------- Hikaru79 Mon Jul 25, 2005 8:34 pm ----------------------------------- I'm almost done my Python program. Awesome challenge, wtd, I really feel like my Python improved from doing this! I'll send it to you as soon as it is done, wtd. ----------------------------------- wtd Tue Jul 26, 2005 3:01 am ----------------------------------- I'm almost done my Python program. Awesome challenge, wtd, I really feel like my Python improved from doing this! I'll send it to you as soon as it is done, wtd. Great. I'm working on retooling mine to be more object-oriented... and... you know... work. The messy one works. The clean, elegant one... not so much. Yet. ----------------------------------- bugzpodder Tue Jul 26, 2005 9:41 pm ----------------------------------- i am assuming this is an attempt to show that python is much better than C++ in doing this. since i dont know python i'll have to stick to what i know. when i have time this weekend, I'll churn up something in C++. Stay tuned. ----------------------------------- wtd Tue Jul 26, 2005 9:57 pm ----------------------------------- Any language works. I just picked Python because it has a handy feature in its standard library for this problem. No, I'm not going to tell you what the handy feature is, because that would give away how to solve the problem. :) ----------------------------------- bugzpodder Tue Jul 26, 2005 10:02 pm ----------------------------------- i figured so ;) ----------------------------------- bugzpodder Tue Jul 26, 2005 10:46 pm ----------------------------------- #include #include using namespace std; int main(){ int r[9],c[9],i,j,arr[9][9],rev[512]; char ch; bool flag; memset(r,0,sizeof(r)); // row sum memset(c,0,sizeof(c)); // col sum for (i=0;ich; if (ch=='*') arr[i][j]=-1; else { arr[i][j]=ch-'1'; //0 based r[i]+=1 0 then initialPossible (col, row, grid (i, row)) := false end if if grid (col, i) > 0 then initialPossible (col, row, grid (col, i)) := false end if end for for i : 1 .. 3 for j : 1 .. 3 if grid (((col - 1) div 3) * 3 + i, ((row - 1) div 3) * 3 + j) > 0 then initialPossible (col, row, grid (((col - 1) div 3) * 3 + i, ((row - 1) div 3) * 3 + j)) := false end if end for end for end if end for end for end loadGrid proc solve (possible : array 1 .. 9, 1 .. 9, 1 .. 9 of boolean, c, r : int) if r = 10 then for row : 1 .. 9 for col : 1 .. 9 put grid (col, row), " " .. end for put "" end for return end if if grid (c, r) < 0 then var tempPossible := possible for i : 1 .. 9 if tempPossible (c, r, i) then grid (c, r) := i for j : 1 .. 9 tempPossible (j, r, grid (c, r)) := false tempPossible (c, j, grid (c, r)) := false end for for j : 1 .. 3 for k : 1 .. 3 tempPossible (((c - 1) div 3) * 3 + j, ((r - 1) div 3) * 3 + k, grid (c, r)) := false end for end for if c < 9 then solve (tempPossible, c + 1, r) else solve (tempPossible, 1, r + 1) end if tempPossible := possible grid (c, r) := -1 end if end for else if c < 9 then solve (possible, c + 1, r) else solve (possible, 1, r + 1) end if end if end solve loadGrid ("grid2.txt") solve (initialPossible, 1, 1) put "\n\n", Time.Elapsed have fun :wink: ----------------------------------- rizzix Tue Nov 29, 2005 12:26 pm ----------------------------------- Hi there guys... just to bring back this good old topic so as to let you know.. my algorithm fails against the Top95 sudoku puzzles (well at least against the 1st two anyway): Here, test your solutions against these: [url=http://magictour.free.fr/top95]Top 95 and the so-called [url=http://home.comcast.net/~mshelor/files/impossible.db]Impossible 520 Edit: I'm tying running zylum's solution against the 2nd of the Top95 and.. well on my old 450mhz cpu.. it's taking a really long time.. although i'm pretty sure it will solve it... (right?).. at some point anyway.. ----------------------------------- rizzix Tue Nov 29, 2005 1:08 pm ----------------------------------- finally! solved! (took around 40min): solution to the 2nd one: 5 2 7 3 1 6 4 8 9 8 9 6 5 4 2 7 3 1 3 1 4 9 8 7 5 6 2 1 7 2 4 5 3 8 9 6 6 8 9 2 7 1 3 5 4 4 5 3 6 9 8 2 1 7 9 4 1 8 2 5 6 7 3 7 6 5 1 3 4 9 2 8 2 3 8 7 6 9 1 4 5 ...it was solved using zylum's code btw. ----------------------------------- wtd Tue Nov 29, 2005 1:35 pm ----------------------------------- I've been continuing to work on this using Python, and I have two possibility reduction techniques successfully implemented in my new, cleaner codebase. They're fairly simple. The first simply removes any possibilities that already occur in the row, column or zone (3x3 square). The second checks to see if an unsolved cell contains a possibility that is not present in the rest of the row, column, or zone. I can get from: 92 |83 | | | 1| 7 |85 ---+---+--- 13 | | 8 8| 4 |6 4 | | 97 ---+---+--- 16| 8 |4 | | | 17| 69 To: 92 |83 | | |9 41| 7 |85 ---+---+--- 13 | | 48 8| 4 |6 46 | 8| 97 ---+---+--- 16| 8 |4 | | 8 | 17| 69 Without guessing. A third strategy would allow me to proceed further, but I have not yet been able to successfully implement it. Consider the bottom left zone. In it, there is only one row where 9 can occur. Knowing that, I can cast it's "shadow" across the bottom middle zone. The fourth strategy would be to look for the resulting square created by cells at row 3 column 4, row 3 column 6, row 7 column 4 and row 7 column 6. Knowing that 9 is a possibility in all four of these, we can deduce that It has to occur in both of these rows and columns. Aside from these cells, 9 can be eliminated as a possibility from the other cells in those rows and columns. That makes it possible to deduce that the cell at row 4 column 5 has a value of 9. From that we can determine that row 5, column 2 has a value of 9. And from that we can figure out that row 8, column 3 has a value of 9. ----------------------------------- rizzix Wed Nov 30, 2005 1:51 am ----------------------------------- Constraint Programming: [url=http://today.java.net/pub/a/today/2005/11/29/solving-sudokus-in-java.html]Solving Sudoku (a recent article on java.net) ----------------------------------- TheZsterBunny Tue Dec 13, 2005 8:03 pm ----------------------------------- just got around to posting now. fixed up my algorithm a bit. uh, its working in swing, which is nice, but its limited as of now to 9x9, possible puzzles (of _any_ difficulty) here's the meat of the code, the rest is attached. public void solve() { foundSolution = false; findSolution((byte) 0, grid); } private void findSolution(byte b, byte[][] param0) { if (b == 81) { foundSolution = true; solvedGrid = param0; return; } byte[][] temp= new byte [9][9]; for (byte i = 0; i < 9; i++) { for (byte j = 0; j < 9; j++) { temp[i][j] = param0[i][j]; } } for (Byte t : getPossibleValues(param0,(byte) (b / 9), (byte) (b % 9))) { if (!foundSolution) { temp[b / 9][b % 9] = t; findSolution((byte)(b+1), temp); } else { return; } } } private TreeSet getPossibleValues(byte [] [] param0, byte x, byte y) { TreeSet returnable = new TreeSet(); if (gridChk[x][y] != CELL_LOCKED) { for (byte i = 0; i 0 then initialPossible (col, row, grid (i, row)) := false end if if grid (col, i) > 0 then initialPossible (col, row, grid (col, i)) := false end if end for for i : 1 .. 3 for j : 1 .. 3 if grid (((col - 1) div 3) * 3 + i, ((row - 1) div 3) * 3 + j) > 0 then initialPossible (col, row, grid (((col - 1) div 3) * 3 + i, ((row - 1) div 3) * 3 + j)) := false end if end for end for end if end for end for end loadGrid proc solve (possible : array 1 .. 9, 1 .. 9, 1 .. 9 of boolean, c, r : int) if r = 10 then for row : 1 .. 9 for col : 1 .. 9 put grid (col, row), " " .. end for put "" end for return end if if grid (c, r) < 0 then var tempPossible := possible for i : 1 .. 9 if tempPossible (c, r, i) then grid (c, r) := i for j : 1 .. 9 tempPossible (j, r, grid (c, r)) := false tempPossible (c, j, grid (c, r)) := false end for for j : 1 .. 3 for k : 1 .. 3 tempPossible (((c - 1) div 3) * 3 + j, ((r - 1) div 3) * 3 + k, grid (c, r)) := false end for end for if c < 9 then solve (tempPossible, c + 1, r) else solve (tempPossible, 1, r + 1) end if tempPossible := possible grid (c, r) := -1 end if end for else if c < 9 then solve (possible, c + 1, r) else solve (possible, 1, r + 1) end if end if end solve loadGrid ("grid2.txt") solve (initialPossible, 1, 1) put "\n\n", Time.Elapsed have fun :wink: Still no edit button :( Zylum, please take a minute to explain the confusing recursion you used here.. I am trying hard to understand it but getting nowehre. Thanks a lot, Its way better than the random plugin solution lol. ----------------------------------- zylum Tue Dec 27, 2005 1:43 am ----------------------------------- its not that confusing... if the column is 10 that means i have filled in the last number and i print out the grid. otherwise i plug in one of the possiblilities for the current cell and then move on to the next cell... thats about it... along the way i update the possible numbers for the other cells to speed things up. ----------------------------------- MysticVegeta Tue Dec 27, 2005 11:20 am ----------------------------------- along the way i update the possible numbers for the other cells to speed things up. Ah thats the only part I am missing. and whats the logic behind updating the possible numbers? Because For example: Cell 1: Possibilities : 2,4. Taken #: 2 Cell 2: Posssibilities: 5, 7. Taken #: 5 Cell 3 : Possibilities : none because of some error in cell 1 and cell 2. So, what would you update because Either (2 is right and 5 is wrong) or (2 is wrong 5 is right) or (2 is wrong and 5 is wrong) ----------------------------------- Bored Tue Jan 31, 2006 11:07 pm ----------------------------------- I've created a Turing sudoku solver that uses recursion to solve the puzzle. It can solve any sudoku you throw at it because it can potentially check every possible solution until it fins the right one. I've compiled it incase you don't have turing and I've also added the source code that even if you don't know turing you should be able to follow. It works fairly fast but some puzzles may take quite a few seconds to solve. It starts by having you input a puzzle using arrow keys to move along the grid, numbers to input values, 0 or delete to delete a value and enter to solve puzzle. Try whatever soduko you can find and just try to beat it (with a solvable suduko). ----------------------------------- Bored Tue Jan 31, 2006 11:21 pm ----------------------------------- Fewww, Now that I look through I'm gald I didn't look past page 2 cus some people had already posted answers. Now that I look back I see the first post of a recursive solution. I had that same problem with mine where it would erase some of the clues. Turned out when it was reseting values back to zero whether they where a clue or not and I just had to move the 3 lines that reset the values back to 0.