View Poll Results: How did you like the O/P Format of the Sudoku Board??
Very elaborate & impressive 45 54.22%
More could have been done 8 9.64%
Hav not run it yet 30 36.14%
Voters: 83. You may not vote on this poll
0
tailhook123's Avatar, Join Date: May 2007
Go4Expert Member
Ok.. that worked cool.

The concept I went on is just like the spreadsheet I posted. There are 8 different logic deductions at use. The first Solve_GridSingles() is the only one able to actually solve any cells... all the rest just remove possibilities.

Solve_GridSingles() is the only method able to solve a cell. All the rest just drop possibilities from cells. When there is only one possibility.. this method will solve it and in solving that cell will remove that possibility from all other cells in its Row, Column, and Cell Block. Its wrapped in a while loop because there is a fair likelihood that the removal of possibilities just caused another cell to have only one possibility. It continually keeps running until there are no cells for which there are only one possibility.

Solve_RowSingles() looks at cells in each Row to determine if there is only one possible location in that row for a number. If it finds one.. the Possibilities for that cell are set to that value only. The GridSingles will solve it on the next pass.

Solve_ColumnSingles() looks at cells in each Column to determine if there is only one possible location in that column for a number. If it finds one.. the Possibilities for that cell are set to that value only. The GridSingles will solve it on the next pass.

Solve_CellBlockSingles() looks at each Cell Block to determine if an unsolved number is possible in only one cell in a Cell Block. If true... the Possibilities for that cell are set to that value only. The GridSingles will solve it on the next pass.

These are the 4 'basics'. I've broken out the more advanced once with an if. Basically if anything in the 4 basics changes anything.. the 4 basics need to get run again.

The 4 advanced deductions are a bit harder to explain.

Remove_Row_CellBlock_Isolation_Possibilities

Look at a row. If an unsolved number is possible in only one cell block, that number can not appear in any other row of the cell block.

Remove_Col_CellBlock_Isolation_Possibilities

Look at a Column. If an unsolved number is possible in only one cell block, that number can not appear in any other Column of the cell block.

Remove_CellBlock_Row_Isolation_Possibilities

Look at a CellBlock. If an unsolved number is possible in only one row of a cell block, that number can not appear in any other cell in that row in any other Cell Block.

Remove_CellBlock_Col_Isolation_Possibilities

Look at a CellBlock. If an unsolved number is possible in only one column of a cell block, that number can not appear in any other cell in that column in any other Cell Block.

Once again.. keep looping until all 8 have failed. At this point the rubber has met the road. Selective Solutioning is in order.

Selective Solutioning which I provided the method for does the following. It will loop through every unsolved cell. It will grab the first unsolved cell.. loop based on the number of possible numbers that cell can have... pull out the first possibility, and then the magic happens. It will create a completely new grid based on the old grid, force that cell to have the value of the first possibility, and then call the Solve() for the grid. Solve() returns 2 possible values.. it either Solves or Breaks. A Break is what happens when there are no possibilities for a cell. At this point you picked the wrong value and if it breaks... on return remove that value as a possibility from our grid, delete the grid, and then try the next possibility. If all possibilities fail.. its just as broken so thats the set of retval after the loop.

Now.. once it goes into the solve it'll repass the 8 methods to deduce as much as possible. But you could just as likely deadlock and end up in Selective Solutioning again. No worries.. SS will do exactly what it did above.
0
honeybun's Avatar, Join Date: Sep 2007
Newbie Member
nice shabiir
0
vaibhav_89's Avatar
Go4Expert Member
what is the concept you are using so that you are able to solve even simple sudoku's plzz tel me.

actually i m trying to develop a program which can solve sudoku's.but i m unable to understand the relation between the numbers that are given in a certain sudoku problem.
0
tailhook123's Avatar, Join Date: May 2007
Go4Expert Member
Quote:
Originally Posted by vaibhav_89
what is the concept you are using so that you are able to solve even simple sudoku's plzz tel me.

actually i m trying to develop a program which can solve sudoku's.but i m unable to understand the relation between the numbers that are given in a certain sudoku problem.
Well.. lets start out with the basics. A solved 3x3 sudoku will use all of the numbers 1-9 exactly once in any single row, column, or cell block.

In order to solve a sudoku you need to understand that what you know(solved cells) isn't as important as what you don't know(unsolved cells). As such you have to keep a running track of exactly which numbers are possible in any blank cell at any one time.. and when those possibilities reach only one... that value is the value of the cell.

There are 8 logic deductions used to remove possibilities from blank cells. 4 basic ones and 4 advanced ones. Once all fail you need to solve it by brute force. Brute force involves recursion.

I've allready provided all of the logic in a class in one of these threads for a sudoku class which will solve any sized sudoku.

Here is the thread:

http://www.go4expert.com/showthread.php?t=4492

Here is a spreadsheet that illustrates what is going on:

http://spreadsheets.google.com/pub?k...v98vCWHIh_g1XA

Upper left grid is the grid to be solved... upper right grid fills in the blanks with all the numbers that CANT be in the blank cell.. and the lower right grid uses this to provide only the possibilities for each blank cell. If the # of possibilities is one then replace appropriate blank cell in the upper left with it.

Last edited by tailhook123; 15Oct2007 at 00:31..
0
vaibhav_89's Avatar
Go4Expert Member
yaar ppl plzzzzzzzz help me how to calculate the relation between the numbers given.or
i have to check again & again using recursion function .that is using and calling the function again & again .....
0
vaibhav_89's Avatar
Go4Expert Member
can u show me aprogram that works on this principle & can solve sudoku.this method can not be made
0
Nadr's Avatar, Join Date: Oct 2007
Ambitious contributor
Nice one.
0
Zero2Infinity's Avatar
Newbie Member
Hello rai_gandalf & Admin,
One thing that impressed me is the way khasmoth has written sudoku code. I think its difficult to write a code the especially in c and handle its flow is difficult .... But i found its very difficult to enter each and every values along with its row and col number. i think you have to provide some kind of convincing way to enter all the grid details. But at the end it way good . i can say better than me... I am also working on this sudoku (especially inspired by this forum). Finally, find the solution but its very difficult to handle entire code...So just want to test by you and comment on my code.

To Admin : how do I upload my code to this forum ?...

thanks in advance.
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by Zero2Infinity
To Admin : how do I upload my code to this forum ?...
Visit the section you want your article / code to be in and click on . Also you can refer to Article submission guidelines
0
lead.smart34's Avatar, Join Date: Feb 2008
Contributor
nice