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

rai_gandalf 26Dec2005 20:59

Sudoku Solving Program Using 'C'
 
1 Attachment(s)
I am a little new to this forum (& new to programmin as well). So, please excuse me if the Program that I am attaching contains source-code that is not required or too much of a complication.

I used to hate Sudoku because personally - I always failed at solving it - even the simplest of ones - So, i set out to make a 'C' program (that's the only language I hav mastered to Some extent) to solve Sudoku. The result is the program & my new-found love & respect for the game.

Now, please note that it can only solve the most rudimentary/simplest of Sudokus.
Even then, it scrambles up the answer or gives slightly incorrect solution. The actual program for Sudoku Solving that can handle the toughest of Sudokus will involve multiple recursions, which at the moment I am workin on.
So, it is NOT foolproof, in fact, jokingly it is not proof-at-all.

So, u can call this the ultra-BETA version. What I want u experts to do, is to analyse the program & tell me how efficiently & correctly I hav implemented this program.
Also, tell me the reason why, some of the simpler Sudoku problems are also NOT getting solved by my version.

I hav involved extensive documentation that u guys can refer to try to understand the logic more clearly. Please keep in mind that I am a beginner & u may find the Commenting/Documentation amateurish. My apologies for that. Also, that the Program is "Work in Progress", i.e. it is not yet completed.

Also, I have not used any function like "ikbhijit( )" for the purpose of printing/displaying. My program is coded indegeniously using complicated nested for loops. The reason is simply that I don't know how to use such functions - but inspite of that I am sure u will find the program quite user-friendly & detailed in I/P & O/P operations.

Please go thru the source code & documentation & giv me some feedback that I might incorporate to make it more efficient & accurate.

PS : LOOK AT SUBSEQUENT POSTINGS FOR A DE-BUGGED AND UPDATED VERSION (LOOK AT THE POST : "Rectified Code Segment") THAT SOLVES ALL EASY LEVEL SUDOKUS CONSISTENTLY

shabbir 26Dec2005 22:42

Re: Sudoku Solving Program Using 'C'
 
Quote:

Originally Posted by rai_gandalf
Please go thru the source code & documentation & giv me some feedback that I might incorporate to make it more efficient & accurate.

Hey I dont know how to play the game but never the less I just went through the codes and also ran the exec and I was impressed by the output of the board. Also its well documented and readable but its better if the code comments can be used to generate a documents that can be refered and so I Document your code thread might be useful to you if you havent gone through it before.

rai_gandalf 27Dec2005 00:37

Re: Sudoku Solving Program Using 'C'
 
Quote:

Originally Posted by shabbir
Hey I dont know how to play the game

I don't quite understand Shabbir - is it that u don't know to play the GAME or play the 'C' program. With the assumption that it is the latter, I proceed.

I apologize for not incorporating a "How to Play" option within/outside the program or along with the documentation (which I know is pretty amateurish).

So, I will try to elaborate on how to use the program :

How to get the Puzzle Solved by the Computer (Choice 1 of Main Menu)

1. Just select a suitable newspaper (preferrably Mumbai Mirror or some paper that gives a
minimum of 26-30 entries - anythin less & u will SURELY NOT get a proper solution)

2. Count the no. of entries that is GIVEN/made available in the paper's puzzle
(I am sorry the counting too has to be done manually - didn't give it much thought in the
beginning - now i realize, that its probably a little cumbersome - will make changes to
that)
This number must be entered in the "Enter the number of nos to be entered : " prompt

3. Now, just enter the entries in the following format :
RowNo <Space> ColNo <space> Entry_to_be_placed

4. If u dislike the above format of I/P, go to the "Change Settings" choice & change the I/P
settings, after which the I/P format becomes :
For Row 1:
ColNo <space> Entry_to_be_placed
.
.
.
0 <space> 0



For Row 2:
ColNo <space> Entry_to_be_placed
.
.
.
0 <space> 0


& So on....


Please Note, that the '0's indicate the termination of I/P for the present row. Also, note
that both 0's should be fed.


5. Sit back & let the program do ur work(hopefully)
Check if the solution presented on screen matches the solution in the paper (hopefully,
it will)

6. Also, the O/P mode by default shows all the Recursive calls. For those of us, who want
to view the final solution without knowing how the hell its been done, u can go to the
"Change Settings" option & change the O/P settings



How to Store the Puzzle & Solution to the Puzzle using the Prog (Choice 2 of Main Menu)

Steps 1 thru 3 remain same as above

NOTE: I hav NOT incorporated the 2nd I/P mode in this section (my memory - it fails me
sometimes). So, I hope that u can fill in that gap.



4. Now, feed in the Solution of the puzzle as I/P Row-wise
i.e.
Row 1:
C1 E1
C2 E2
C3 E3
.
.
C9 E9

Row 2:
C1 E1
C2 E2
C3 E3
.
.
C9 E9

.
.
.
.
Row 9:
C1 E1
C2 E2
C3 E3
.
.
C9 E9




Also, once u hav changed the settings, it doesn't go back to default settings automatically.
U must set it back to default settings by going to "Change Settings" choice & choosing the "Restore All Defaults" option


Hope that is sufficient guidelines to at least start getting acquainted with the I/P-O/P of the
prog.


Ciao,
Rajiv :)


PS : A very eventful B-day to you. :)

shabbir 27Dec2005 07:54

Re: Sudoku Solving Program Using 'C'
 
Quote:

Originally Posted by rai_gandalf
I don't quite understand Shabbir - is it that u don't know to play the GAME or play the 'C' program. With the assumption that it is the latter, I proceed.

I dont know how to play the sudoku.

rai_gandalf 27Dec2005 11:20

Re: Sudoku Solving Program Using 'C'
 
Well, in that case, u can just refer any News-paper's Sudoku section. They give the rules along with the puzzle - that should be sufficient for u to understand or u can search in Google for the Rules.

To make your work easier, I will describe the rules here :


Board Layout :
1. 9 Row, 9 Column Board - i.e. board with 81 sub-blocks.

2. The Board can be divided into 9 sub-grids, each of which consists of 3 Rows, 3 Columns - i.e. 9 sub-blocks (For more idea on the sub-grids, refer the documentation - its given their pictorially)



Objective/Mission :
U must fill the Sudoku Board with numbers 1 to 9 using the following guidlines :
> Each Row must contain all the numbers from 1 to 9
> Each Column must contain all the numbers from 1 to 9
> Each Sub-grid must contain all the numbers from 1 to 9
> NO Repetition of numbers must take place along a Row/Column or in a Sub-Grid



What is Given to u :
---> Some of the Numbers varying from 1 to 9 are placed in different sub-blocks &
are already made availble initially - we must place the remaining numbers correctly

---> Depending upon the number of nos. already made available (AND ALSO THEIR
PLACEMENTS)- Sudoku's r classified as Easy, Medium, Hard & Evil

---> Easy Sudoku implies that at least 28-30 entries will be given to u, that too placed in
such a way, that the puzzle is easy to solve. My program can only ATTEMPT to solve
such puzzles.



Hope that is sufficient to at least get u introduced to the Game.

Anyways, the program doesn't need u to be an xpert in it. It isn't an interactive platform, where u can play the game - what it does, it SOLVES (or attempts to) a given (Easy Level) Sudoku Puzzle, when the numbers already given in the Puzzle r fed as I/P.


Ciao,
Rajiv :)

rai_gandalf 27Dec2005 11:31

Re: Sudoku Solving Program Using 'C'
 
Also, visit the Site I hav mentioned in the "Credits" section to understand the Algorithm used.

And visit the sites to know more bout the game/rules & if u want to try ur hand at Sudoku :
1. http://www.lovatts.com.au/sudoku/sudoku.htm
2. http://jayisgames.com/archives/2005/06/web_sudoku.php


Ciao,
Rajiv

rai_gandalf 27Dec2005 13:21

Updates '1'
 
1 Attachment(s)
Hello guys, I am attaching a Zip File that contains :

1. "sud_use_as_base.c" - This is a 'C' file that u can use to build ur own Sudoku Programs - it does the work of I/P & O/P. So half of ur coding work is reduced.

2. "coded_ip_4_sdku.rtf" - This is a Wordpad file that contains some Sudoku's in the coded form (coded as per the I/P requirements of the program)

3. "save_sud_sols.txt" - This is a text/Notepad file that contains the Questions & Solutions to some Sudoku Puzzles, which u can try as Test I/Ps for the Sudoku Program. U can then match & see if the solution matches or not & can hav a better understanding of where the program fails.


Note : Use the 2nd & 3rd file simultaneoulsy - use the 2nd one for I/P & 3rd file for checking the O/P.


Hope that helps u guys to analyse the prog better!

Ciao,
Rajiv :)

shabbir 27Dec2005 13:28

Re: Sudoku Solving Program Using 'C'
 
Quote:

Originally Posted by rai_gandalf
Well, in that case, u can just refer any News-paper's Sudoku section. They give the rules along with the puzzle - that should be sufficient for u to understand or u can search in Google for the Rules.

I just googled it out and bookmarked the link but when I get a bit of time will see and play to it.

rai_gandalf 1Jan2006 16:59

Rectfied Code Segment
 
1 Attachment(s)
Hello guys,
Happy New Year 2006 to u all !!

Right, then, after settling that, I come to the point. I have found out why the code wasn't working.

I am attaching the rectified Program, along with updated documentation, to reflect the innumerable, small changes I hav made to the code.

Also, the main logical function : "solve_easy_level( )" is NOT a Recursive Function any more - I found that it could be implemented Non-recursively, thereby increasing time-space efficiency of the program.

Now, I think, you experts might find it worthwhile to go through the program & give me a feedback.

Ciao,
Rajiv :)

khasmoth 15Mar2006 09:07

Re: Sudoku Solving Program Using 'C'
 
Do you have GUI for this program as well.Im interested to see how it looks like.
Befor I've tried doing this program.Using not so good GUI.

rai_gandalf 15Mar2006 17:04

Re: Sudoku Solving Program Using 'C'
 
The GUI in this program is Text-mode based. It is Non-BGI. So, it isn't that very appealing to the eyes, yet reasonably user-friendly & elaborate to use. Download the code & read the documentation to understand the logic of the Text-based GUI of this program.

Ciao,
Rajiv

PS : BGI can be used to develop an actual Graphics interface that is detailed & developed, for this program. :)


"Don't take life too seriously; No one gets out alive."

wizardrycon 14Jul2006 01:41

Re: Sudoku Solving Program Using 'C'
 
I have also been writing a Sudoku solving program but I have been using C# .NET.

When I clean up the objects that do the solve (it will solve a complete puzzle of mediumn complexity. I need to add other algorhythyms to solve for the harder level puzzles). I will post them on this thread for review/comments.

However in the mean time I need some help with my GUI object for this whole project.

I am pretty new to .NET programming and was hoping someone could tell me why this is not working right.

Any help you guys could give me would be greatly appreciated!!!

Source Notes: I am creating 9 panels which divide the main 9x9 grid into 9 smaller 3x3 grids (just like the Sudoku Puzzle). I am hoping by creating the GUI this way, it will be easier to implement the object connections to the actual cell data that will connected to each grid button.

I am also interested in making the buttons size dynamically depending on how big the form is. If anyone can point me in the right direction to do that I will try to implement that feature as well.

OUTPUT (Note only 1 panel paints the buttons, they all paint the same way and I can't for the life of me figure out why the other 8 panels are missing the buttons!!):

http://www.iwebnow.com/SudokuFormScreen.GIF

SOURCE:

Code:

using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;

namespace SudokuGridFormA
{
        public class SudokuGridForm : System.Windows.Forms.Form
        {
                private System.Windows.Forms.GroupBox groupBox1;
                private System.Windows.Forms.Panel [,] panel = new Panel[3,3];
                private System.Windows.Forms.Button [,] GridBtn = new Button[9,9];
                private int TABINDEXNUM = 0;
               

                public SudokuGridForm()
                {
                        InitializeComponent();
                }

                private int TABINDEX()
                {
                        TABINDEXNUM++;
                        return(TABINDEXNUM);
                }

                private void AddPanel(int panelNumX, int panelNumY, int x1, int x2, int y1, int y2)
                {
                        this.panel[panelNumX,panelNumY].BorderStyle = System.Windows.Forms.BorderStyle.FixedSingle;

                        for(int y=y1; y<=y2; y++)
                                for(int x=x1; x<=x2; x++)
                                {
                                        this.GridBtn[x,y] = new System.Windows.Forms.Button();
                                        this.panel[panelNumX,panelNumY].Controls.Add(this.GridBtn[x,y]);
                                }

                        this.panel[panelNumX,panelNumY].Location = new System.Drawing.Point(24+(panelNumX*96),32+(panelNumY*96));
                        this.panel[panelNumX,panelNumY].Name = "panel" + panelNumX.ToString()+panelNumY.ToString();
                        this.panel[panelNumX,panelNumY].Size = new System.Drawing.Size(96, 96);
                        this.panel[panelNumX,panelNumY].TabIndex = TABINDEX();

                        for(int y=y1; y<=y2; y++)
                                for(int x=x1; x<=x2; x++)
                                {
                                        this.GridBtn[x,y].Location = new System.Drawing.Point(0+(x*32), 0+(y*32));
                                        string BtnName = "GridBtn"+panelNumX.ToString()+panelNumY.ToString()+x.ToString()+y.ToString();
                                        this.GridBtn[x,y].Name = BtnName;
                                        this.GridBtn[x,y].Size = new System.Drawing.Size(32, 32);
                                        this.GridBtn[x,y].Text = panelNumX.ToString()+panelNumY.ToString()+x.ToString()+y.ToString();
                                        this.GridBtn[x,y].TabIndex = TABINDEX();
                                }
                }

                private void InitializeComponent()
                {
                        this.groupBox1 = new System.Windows.Forms.GroupBox();
                        this.groupBox1.SuspendLayout();
                        this.SuspendLayout();

                        for(int y = 0; y<3; y++)
                                for(int x = 0; x<3; x++)
                                {
                                        this.panel[x,y] = new System.Windows.Forms.Panel();
                                        this.panel[x,y].SuspendLayout();
                                }

                        for(int y = 0; y<3; y++)
                                for(int x = 0; x<3; x++)
                                this.groupBox1.Controls.Add(this.panel[x,y]);
                       
                        this.groupBox1.Location = new System.Drawing.Point(16, 24);
                        this.groupBox1.Name = "groupBox1";
                        this.groupBox1.Size = new System.Drawing.Size(336, 344);
                        this.groupBox1.TabIndex = TABINDEX();
                        this.groupBox1.TabStop = false;

                        for(int y = 0; y<3; y++)
                                for(int x = 0; x<3; x++)
                                        AddPanel(x,y,x*3,2+(x*3),y*3,2+(y*3));                       
                       
                        this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
                        this.ClientSize = new System.Drawing.Size(368, 382);
                        this.Controls.Add(this.groupBox1);
                        this.Name = "SudokuGridForm";
                        this.Text = "SudokuGridForm";
                        this.groupBox1.ResumeLayout(false);
                        for(int y = 0; y<3; y++)
                                for(int x = 0; x<3; x++)
                                        this.panel[x,y].ResumeLayout(false);
                        this.ResumeLayout(false);
                }
        }
}


wizardrycon 14Jul2006 13:58

Re: Sudoku Solving Program Using 'C'
 
Nevermind... It was an error in the positioning and not a painting error. I didn't reset it to 0,0 for each panel other than the first one.

Thanks for looking if you were trying to figure it out...

gamehunter101 16Jul2006 11:04

Re: Sudoku Solving Program Using 'C'
 
Good work man

anshul gupta 17Aug2006 15:41

Re: Sudoku Solving Program Using 'C'
 
hi rai
even i have worked on a sudoku generator but my basic problem is the time that the problem takes to generate a sudoku.
the logic behind the problem is pretty simple and it is not recurssive in nature .
its like fitting in a solution rather than generatin it.
i will like to take a look at ur basic strategy behind the problem...
plz u can mail me at anshulgolu123@gmail.com

anshul gupta 17Aug2006 15:43

Re: Sudoku Solving Program Using 'C'
 
by the way excellent work man.....

BlasterBlang 14Nov2006 13:45

Re: Sudoku Solving Program Using 'C'
 
thanks

durgaprasad 24Jan2007 17:02

Re: Sudoku Solving Program Using 'C'
 
good work gandalf

durgaprasad 24Jan2007 17:10

Re: Sudoku Solving Program Using 'C'
 
mr.gandalf irequest u to write a program in c that allows the user to play tic tac toe with computer

shabbir 24Jan2007 18:06

Re: Sudoku Solving Program Using 'C'
 
Quote:

Originally Posted by durgaprasad
mr.gandalf irequest u to write a program in c that allows the user to play tic tac toe with computer

Why do you want him to write for you when we already have couple of threads having the same.

Tic-Tac-Toe Game in C
TicTacToe in Plain C without using BGI graphics

Also dont jump into some article with your query. Instead try giving your query a new thread with good title to get good responses.

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;
}


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

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

Nadr 20Oct2007 11:46

Re: Sudoku Solving Program Using 'C'
 
Nice one.

Zero2Infinity 21Feb2008 20:18

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

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 http://www.go4expert.com/images/butt...mitarticle.gif . Also you can refer to Article submission guidelines

lead.smart34 26Feb2008 18:19

Re: Sudoku Solving Program Using 'C'
 
nice


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