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 sourcecode 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 newfound 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 proofatall. So, u can call this the ultraBETA 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 userfriendly & 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 DEBUGGED AND UPDATED VERSION (LOOK AT THE POST : "Rectified Code Segment") THAT SOLVES ALL EASY LEVEL SUDOKUS CONSISTENTLY 
Re: Sudoku Solving Program Using 'C'
Quote:

Re: Sudoku Solving Program Using 'C'
Quote:
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 2630 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 Rowwise 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/PO/P of the prog. Ciao, Rajiv :) PS : A very eventful Bday to you. :) 
Re: Sudoku Solving Program Using 'C'
Quote:

Re: Sudoku Solving Program Using 'C'
Well, in that case, u can just refer any Newspaper'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 subblocks. 2. The Board can be divided into 9 subgrids, each of which consists of 3 Rows, 3 Columns  i.e. 9 subblocks (For more idea on the subgrids, 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 Subgrid must contain all the numbers from 1 to 9 > NO Repetition of numbers must take place along a Row/Column or in a SubGrid What is Given to u : > Some of the Numbers varying from 1 to 9 are placed in different subblocks & 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 2830 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 :) 
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 
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 :) 
Re: Sudoku Solving Program Using 'C'
Quote:

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 Nonrecursively, thereby increasing timespace efficiency of the program. Now, I think, you experts might find it worthwhile to go through the program & give me a feedback. Ciao, Rajiv :) 
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. 
Re: Sudoku Solving Program Using 'C'
The GUI in this program is Textmode based. It is NonBGI. So, it isn't that very appealing to the eyes, yet reasonably userfriendly & elaborate to use. Download the code & read the documentation to understand the logic of the Textbased 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." 
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; 
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... 
Re: Sudoku Solving Program Using 'C'
Good work man

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 
Re: Sudoku Solving Program Using 'C'
by the way excellent work man.....

Re: Sudoku Solving Program Using 'C'
thanks

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

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

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

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

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

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

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. 
Re: Sudoku Solving Program Using 'C'
tailhook123, Nice sheet but you tend to not come to the solution in this manner.

Re: Sudoku Solving Program Using 'C'
Quote:
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. 
Re: Sudoku Solving Program Using 'C'
Yup I totally agree its a harder way to go about it.

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 Code:
class SudokuCell Code:
char SudokuGrid::Solve() Code:
char SudokuGrid::Selective_Solutioning() 
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. 
Re: Sudoku Solving Program Using 'C'
nice shabiir

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

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

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

Re: Sudoku Solving Program Using 'C'
nice

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