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

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    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
     

    Attached Files:

    Last edited: Feb 18, 2006
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    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.
     
  3. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    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. :)
     
    Last edited: Dec 26, 2005
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    I dont know how to play the sudoku.
     
  5. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    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 :)
     
    Last edited: Dec 27, 2005
  6. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
  7. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    Updates '1'

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

    Attached Files:

  8. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    I just googled it out and bookmarked the link but when I get a bit of time will see and play to it.
     
  9. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    Rectfied Code Segment

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

    Attached Files:

    Last edited: Feb 7, 2007
  10. khasmoth

    khasmoth New Member

    Joined:
    Mar 15, 2006
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  11. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    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."
     
    Last edited: Mar 15, 2006
  12. wizardrycon

    wizardrycon New Member

    Joined:
    Jul 13, 2006
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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!!):

    [​IMG]

    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);
    		}
    	}
    }
    
    
     
  13. wizardrycon

    wizardrycon New Member

    Joined:
    Jul 13, 2006
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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...
     
  14. gamehunter101

    gamehunter101 New Member

    Joined:
    Jun 19, 2006
    Messages:
    14
    Likes Received:
    0
    Trophy Points:
    0
  15. anshul gupta

    anshul gupta New Member

    Joined:
    Aug 17, 2006
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    noida
    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
     
  16. anshul gupta

    anshul gupta New Member

    Joined:
    Aug 17, 2006
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    noida
    by the way excellent work man.....
     
  17. BlasterBlang

    BlasterBlang New Member

    Joined:
    Nov 13, 2006
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
  18. durgaprasad

    durgaprasad New Member

    Joined:
    Dec 9, 2006
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    good work gandalf
     
  19. durgaprasad

    durgaprasad New Member

    Joined:
    Dec 9, 2006
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    mr.gandalf irequest u to write a program in c that allows the user to play tic tac toe with computer
     
  20. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    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.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice