Go4Expert

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/)

Peter_APIIT 13Apr2007 08:39

Re: Sudoku Solving Program Using 'C'
 
How to add GUI in C program because they all say C is API. I don't understand what is it.

shabbir 13Apr2007 11:16

Re: Sudoku Solving Program Using 'C'
 
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.)

Peter_APIIT 13Apr2007 14:34

Re: Sudoku Solving Program Using 'C'
 
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.

shabbir 13Apr2007 14:37

Re: Sudoku Solving Program Using 'C'
 
API is application programming interface. In a simple sense some functions which you can use as per your need.

Peter_APIIT 14Apr2007 11:51

Re: Sudoku Solving Program Using 'C'
 
Thanks for your information and explanation. I have better understand after your explanations.

tailhook123 23May2007 18:48

Re: Sudoku Solving Program Using 'C'
 
I was playing with sudoku's a while back and made the following spreadsheet.

http://spreadsheets.google.com/ccc?k...HIh_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.

shabbir 23May2007 20:27

Re: Sudoku Solving Program Using 'C'
 
tailhook123, Nice sheet but you tend to not come to the solution in this manner.

tailhook123 23May2007 21:34

Re: Sudoku Solving Program Using 'C'
 
Quote:

Originally Posted by shabbir
tailhook123, Nice sheet but you tend to not come to the solution in this manner.

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.

shabbir 24May2007 08:09

Re: Sudoku Solving Program Using 'C'
 
Yup I totally agree its a harder way to go about it.

tailhook123 27May2007 22:14

Re: Sudoku Solving Program Using 'C'
 
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;
}



All times are GMT +5.5. The time now is 23:30.