Page 4 of 6« First<23456> Show 40 post(s) from this thread on one page

Go4Expert (http://www.go4expert.com/)
-   Game Programming (http://www.go4expert.com/articles/game-programming/)
-   -   Sudoku Solving Program Using 'C' (http://www.go4expert.com/articles/sudoku-solving-program-using-c-t541/)

 tailhook123 27May2007 22:46

Re: Sudoku Solving Program Using 'C'

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.

 honeybun 8Sep2007 19:22

Re: Sudoku Solving Program Using 'C'

nice shabiir

 vaibhav_89 14Oct2007 23:39

Re: Sudoku Solving Program Using 'C'

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.

 tailhook123 15Oct2007 00:18

Re: Sudoku Solving Program Using 'C'

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 a spreadsheet that illustrates what is going on:

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.

 vaibhav_89 15Oct2007 21:53

Re: Sudoku Solving Program Using 'C'

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 .....

 vaibhav_89 18Oct2007 21:57

Re: Sudoku Solving Program Using 'C'

can u show me aprogram that works on this principle & can solve sudoku.this method can not be made

Re: Sudoku Solving Program Using 'C'

Nice one.

 Zero2Infinity 21Feb2008 20:18

Re: Sudoku Solving Program Using 'C'

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 ?...

 shabbir 21Feb2008 22:04

Re: Sudoku Solving Program Using 'C'

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