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.


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