1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Sudoku Solving Program Using 'C'

Discussion in 'Game Programming' started by rai_gandalf, Dec 26, 2005.

?

How did you like the O/P Format of the Sudoku Board??

  1. Very elaborate & impressive

    57.8%
  2. More could have been done

    10.9%
  3. Hav not run it yet

    31.3%
  1. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    How to add GUI in C program because they all say C is API. I don't understand what is it.
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
    You need to be using the Win32 API for Windows and for Linux you can use something like QT (Dont quote me is I have misspelled it.)
     
  3. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    I think Qt is not applicable to C. We can use GTk++ and many more to program GUI using C or C++.

    By the way, what is API ?

    Sorry for my stupidness.

    Thanks you.

    Your help is greatly appreciated by me and others.
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
    API is application programming interface. In a simple sense some functions which you can use as per your need.
     
  5. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Thanks for your information and explanation. I have better understand after your explanations.
     
  6. tailhook123

    tailhook123 New Member

    Joined:
    May 23, 2007
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    I was playing with sudoku's a while back and made the following spreadsheet.

    http://spreadsheets.google.com/ccc?key=p9zFWog7Fv98vCWHIh_g1XA&pli=1

    There are 3 grids.. the upper left grid starts with the original puzzle and as you discover answers you fill it in.

    Now.. if the answer in the left grid is found.. each cell in the upper right grid will have that value. If the answer in the left grid is not found.. the cell will contain every number from its corresponding cell in the left grid that is horizontal, vertical, and in the same 9 block cell from it. It does this just by treating them as text and concatenating them together.

    Finally.. for each cell in the lower right grid.. check its corresponding cell in the upper right grid. If its less than 10.. its the solution. If its greater than 10 then build a string out of every number not used. These are the possible numbers that can be in that cell.

    The upper right grid in a program can probably be dropped. Its pretty redundant but the formula in this form would have exploded had I tried to do it in one pass. Now.. i've included a sudoku unless someone has changed it and you'll notice when you put one in that the lower right will end up having cells which break down to one number. When this happens you take that number and put it in its corresponding cell in the upper left. This will then have a cascade effect and drop out more numbers.
     
  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
    tailhook123, Nice sheet but you tend to not come to the solution in this manner.
     
  8. tailhook123

    tailhook123 New Member

    Joined:
    May 23, 2007
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    Its not meant as a one button solution. I thought it interesting and was something I built as a visual helper for solving sudoku's. I've done the hardest of the hard sudoku's with it. The further permutations were a bit much for a spreadsheet. Once you have the lower right:

    1) check to see if any cells only had one solution. Carry that up to the upper left and enter it.
    2) go by row and column and check to see if a number appears only once.. if it does.. that cell is that number.
    3) go by cell block and see if a number appears only once.. if it does.. that cell is that number.
    4) if a number in a cell block appears in only one row OR one column of a cell block... remove that number as a possibility from that row or column in any other cell block.
    5) if a number in a row appears in only one cell block.. remove that number as a possibility from the other two rows in that cell block.
    6) if a number in a column appears in only one cell block.. remove that number as a possibility from the other two columns in that cell block.

    I've done up through hard with those 6. If you hit a wall(usually 'evil' puzzles) you have to do selective solutioning. What that means is you find a cell for which there are 2 possibilities. You preferably want one for which if you choose a specific one of the two numbers... another cell will solve. When that happens the grid will start to collapse under the 6 passes above and it will typically either solve or break. A break is when you picked the wrong one of the two options. When this happens you will get a cell with no possibilities and in turn prove the other option in the original 50/50 cell was correct.

    The lower right grid makes solving these things much, MUCH easier. People doing this just without help do variations on that grid with dots and whatever to keep track of possibilities.
     
  9. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
    Yup I totally agree its a harder way to go about it.
     
  10. tailhook123

    tailhook123 New Member

    Joined:
    May 23, 2007
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    This is my first time trying code blocks. Have no idea how its going to turn out but giving it a try.

    Figured I'd post some code snippets from a Sudoku class i've been writing. The solver code is now complete but it doesn't do input/output yet as i've been focusing on the guts. Its now able to solve any. I'll post more about this code in the next post to hopefully keep things clean and readable. Important parts are in the Solve method and specifically Selective Solutioning where the real funky stuff happens.

    Code:
    class SudokuGrid
    {
    	SudokuCell Cell[81];
    
    	char Find_Cellblock(char, char);
    	void Remove_Row_Possibilities(char, int, int);
    	void Remove_Col_Possibilities(char, int, int);
    	void Remove_CellBlock_Possibilities(char, int, int);
    	void Remove_RowColBlock_Possibilities(int, int);
    	char Solve_RowSingles();
    	char Solve_ColumnSingles();
    	char Solve_CellBlockSingles();
    	int Solve_GridSingles();
    	char Get_Offset(char, int);
    	char Get_Col_Offset(char, int);
    	char Remove_CellBlock_Row_Possibilities(char, char, int);
    	char Remove_CellBlock_Col_Possibilities(char, char, int);
    	char Remove_Row_Possibilities(char, char, int);
    	char Remove_Col_Possibilities(char, char, int);
    	char Remove_Row_CellBlock_Isolation_Possibilities();
    	char Remove_Col_CellBlock_Isolation_Possibilities();
    	char Remove_CellBlock_Row_Isolation_Possibilities();
    	char Remove_CellBlock_Col_Isolation_Possibilities();
    	char Selective_Solutioning();
    
    public:
                    int Get_Cell_Value(int, int);
                    void Set_Cell_Value(int, int, int);
    	SudokuCell *Get_Cell(int);
    	void Set_Cell(int, SudokuCell *);
    	void Read_File(char *Filename);
    	char Is_Solved();
    	char Is_Broken();
    	char Solve();
    
    	void Set_Sudoku_Grid(SudokuGrid *);
    	SudokuGrid(SudokuGrid *);
    	SudokuGrid(void);
    	~SudokuGrid(void);
    };
    Code:
    class SudokuCell
    {
    	int value;
    	char *Possibilities;
    	char Solved;
    
    public:
    	int Get_Value();
    	void Set_Value(int);
    	char *Get_Possibilities();
    	void Set_Possibilities(char *);
    	char Get_Solved();
    	void Get_Solved(char);
    	char Is_Solved();
    	char Is_Broken();
    	void Set_Solved(char);
    	int Get_Possibility(char);
    	int OnlyOnePossibility();
    	char Num_Possibilities();
    	char NotPossibility(int);
    	char IsPossibility(int);
    
    	SudokuCell(SudokuCell &);
    	SudokuCell(void);
    	~SudokuCell(void);
    };
    Main Solver Loop

    Code:
    char SudokuGrid::Solve()
    {
        char Something_Changed, Solved = FALSE;
        char Broken = FALSE, a = 0, retval = UNSOLVED;
    
        while(Solved == FALSE && Broken == FALSE && retval == UNSOLVED)
        {
            Something_Changed = FALSE;
    
            while(Solve_GridSingles()) {}
            Something_Changed |= Solve_RowSingles();
            Something_Changed |= Solve_ColumnSingles();
            Something_Changed |= Solve_CellBlockSingles();
    
            Broken = Is_Broken();		
            Solved = Is_Solved();
    
            if (Something_Changed == FALSE && Solved == FALSE && Broken == FALSE)
            {
                Something_Changed |= Remove_Row_CellBlock_Isolation_Possibilities();
                Something_Changed |= Remove_Col_CellBlock_Isolation_Possibilities();
                Something_Changed |= Remove_CellBlock_Row_Isolation_Possibilities();
                Something_Changed |= Remove_CellBlock_Col_Isolation_Possibilities();
    
                Broken = Is_Broken();
                Solved = Is_Solved();
    
                if (Something_Changed == FALSE && Solved == FALSE && Broken == FALSE)
                   retval = Selective_Solutioning();
            }
        }
        if (Solved)
            retval = SOLVED;
        if (Broken)
            retval = BROKEN;
        return retval;
    }
    And where the magic happens once the logic deductions have failed. What this is is basically a brute force method of solving the remaining grid. Its also where most people who try to do this with C functions fall down and go boom. Calling your Solve Method from a Method in your Solve function is $$.

    Code:
    char SudokuGrid::Selective_Solutioning()
    {
        char x = 0, y = 0, CellFound = FALSE, SomethingChanged = FALSE;
        char tVal1 = 0, tVal2 = 0, retval = UNSOLVED, tPoss;
        SudokuGrid *WorkGrid;
        SudokuCell *tCell;
    
        while (x < 81 && retval != SOLVED && SomethingChanged == FALSE)
        {
             if (Cell[x].Is_Solved() == FALSE)
             {
                tPoss = Cell[x].Num_Possibilities();
    
                y = 1;
                while (y <= tPoss && retval != SOLVED)
                {
                   WorkGrid = new SudokuGrid(this);
                   tCell = WorkGrid -> Get_Cell(x);
    
                   tVal1 = Cell[x].Get_Possibility(1);
                   tCell -> Set_Value(tVal1 - 48);
    
                   retval = WorkGrid -> Solve();
                   if (retval == BROKEN)
                       Cell[x].NotPossibility(tVal1 - 48);
                   else if (retval == SOLVED)
                       Set_Sudoku_Grid(WorkGrid);
                   delete WorkGrid;
                   y++;
                }
                if (retval == UNSOLVED)
                   retval = BROKEN;
             }
             x++;
         }
         return retval;
    }
     
  11. tailhook123

    tailhook123 New Member

    Joined:
    May 23, 2007
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  12. honeybun

    honeybun New Member

    Joined:
    Sep 8, 2007
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    studying
    Location:
    india
    nice shabiir
     
  13. vaibhav_89

    vaibhav_89 New Member

    Joined:
    Oct 14, 2007
    Messages:
    15
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  14. tailhook123

    tailhook123 New Member

    Joined:
    May 23, 2007
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    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?key=p9zFWog7Fv98vCWHIh_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: Oct 14, 2007
  15. vaibhav_89

    vaibhav_89 New Member

    Joined:
    Oct 14, 2007
    Messages:
    15
    Likes Received:
    0
    Trophy Points:
    0
    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 .....
     
  16. vaibhav_89

    vaibhav_89 New Member

    Joined:
    Oct 14, 2007
    Messages:
    15
    Likes Received:
    0
    Trophy Points:
    0
    can u show me aprogram that works on this principle & can solve sudoku.this method can not be made
     
  17. Nadr

    Nadr New Member

    Joined:
    Oct 16, 2007
    Messages:
    165
    Likes Received:
    1
    Trophy Points:
    0
    Nice one.
     
  18. Zero2Infinity

    Zero2Infinity New Member

    Joined:
    Feb 8, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  19. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
    Visit the section you want your article / code to be in and click on [​IMG] . Also you can refer to Article submission guidelines
     
  20. lead.smart34

    lead.smart34 New Member

    Joined:
    Feb 14, 2008
    Messages:
    77
    Likes Received:
    0
    Trophy Points:
    0

Share This Page