Thread: sudoku

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    73
    it si a sudoku program....
    i.e, it takes a 9x9 sparse array... and inputs for the array...

    using the rules it has to output the solution....
    RULES:
    1.no element can repeat itself in a row.
    2.no element can repeat itself in the column.
    3.all elements 1-9 should be present in every row n column....

  2. #2
    Registered User
    Join Date
    Nov 2007
    Posts
    73

    sudoku

    guys there!!!!!!!!! this is a sudoku prg 9x9...

    it works for the first iteration....
    i.e, further calls of sol_pos() dont take place.....


    Code:
    #include<iostream.h>
    #include<stdio.h>
    int chk_pos(int i,int j,int n);    //checks whether a num is a possibilty in pos i,j or not
    void sol_pos(void);                //puts all 1 possibility nums into their places....
    int a[10][10][10]={0};
    int chk(int i,int j,int n)
    {
    	int suc=0;
    	for(int col=0;col<9;col++)
    		if(a[i][col][0]==n)
    		{
    			suc=1;break;
    		}
    	for(int row=0;row<9;row++)
    		if(a[row][j][0]==n)
    		{
    			suc=1;break;
    		}
    	i=i/3;j=j/3;
    	for(row=3*i;row<3*(i+1);row++)
    		for(col=3*j;col<3*(j+1);col++)
    			if(a[row][col][0]==n)
    				suc=1;
    	if(suc==0)
    		return n;
    	else
    		return 0;
    
    }
    
    
    void sol_pos(void)
    {
    	int i,j,k,fail=0;
    	for(i=0;i<9;i++)
    		for(j=0;j<9;j++)
    			for(k=1;k<9;k++)
    				a[i][j][k]=0;
    	for(i=0;i<9;i++)
    	{
    		for(j=0;j<9;j++)
    		{
    			k=1;
    			if(a[i][j][0]==0)
    			{
    				for(int num=1;num<=9;num++)
    				{
    					if(chk(i,j,num)!=0)
    						a[i][j][k++]=num;
    				}
    			}
    		}
    	}
    	for(i=0;i<9;i++)
    	{
    		for(j=0;j<9;j++)
    		{
    			if(a[i][j][0]==0 && a[i][j][2]==0)
    			{
    				fail=1;
    				a[i][j][0]=a[i][j][1];
    			}
    		}
    	}
    	if(fail==1)
    		sol_pos();
    }
    
    
    
    
    int main()
    {
    	int rown,coln,n;
    	cout<<"enter rown coln n :0 to exit:";
    	do{
    		cin>>rown>>coln>>n;
    		if(rown>9 || coln>9 || n>9 || n<1)
    			cout<<"invalid input";
    		else
    			a[rown-1][coln-1][0]=n;
    	}while(n!=0);
    	sol_pos();
    	for(int i=0;i<9;i++)
    	{
    		for(int j=0;j<9;j++)
    			cout<<a[i][j][0]<<" ";
    		cout<<"\n";
    	}
    	return 0;
    }
    Last edited by ElemenT.usha; 02-12-2008 at 01:18 PM.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You need to get a newer compiler!

    In C++ the headers are
    Code:
    #include<iostream>
    #include<cstdio>
    And variables declared in a for loop go out of scope at the end of the loop. So you'll need to declare new loop counters in other loops:
    Code:
    	int suc=0;
    	for(int col=0;col<9;col++)
    		if(a[i][col][0]==n)
    		{
    			suc=1;break;
    		}
    	for(int row=0;row<9;row++)
    		if(a[row][j][0]==n)
    		{
    			suc=1;break;
    		}
    	i=i/3;j=j/3;
    	for(int row=3*i;row<3*(i+1);row++)
    		for(int col=3*j;col<3*(j+1);col++)
    			if(a[row][col][0]==n)
    				suc=1;
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by anon View Post
    You need to get a newer compiler!

    In C++ the headers are
    Code:
    #include<iostream>
    #include<cstdio>
    Thats a style choice only, since AFAIK there is nothing in the standard that mandates headers use the .h extension. In fact there are quite a few headers out there that use .hpp

  5. #5
    pwns nooblars
    Join Date
    Oct 2005
    Location
    Portland, Or
    Posts
    1,094
    The standard dictates the name of the standard headers, which are as anon said, without the .h

  6. #6
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    The name, but not the extension. If this were the case then the file itself would be iostream with no extension, which is not the case.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by abachler View Post
    The name, but not the extension. If this were the case then the file itself would be iostream with no extension, which is not the case.
    I'm not aware of a compiler that doesn't have iostream (plain, no extension), but I've only looked at gcc on linux, gcc/mingw, and microsoft visual studio 98 and 2003.

  8. #8
    pwns nooblars
    Join Date
    Oct 2005
    Location
    Portland, Or
    Posts
    1,094
    http://ece-www.colorado.edu/~pfeffer...si/hfiles.html
    http://www.informit.com/guides/conte...lus&seqNum=382
    2 mins on google, abachler, lets do a little research before you post again.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your logic is (naturally) much different than what I use for the game. Are you getting the correct possibles for each square in the 3rd dimension of the array?

    That's first!

    Second, what logic are you using to actually try to solve the puzzle, after getting the possibles listed correctly?

    You'll want something like "The rule of pairs" (inside and/or outside), to assist with that, after you've handled the "solo's" (must be's, can't be's), correctly.

    After every square that you solve (correctly), you need to re-apply all the logic to help eliminate or elevate the impossible "possibles", whether they're "must be's" (elevate to solutions for a square), or "can't be's", (that get removed from the list of possibles for the square in question), and then lastly, run through the rule of pairs, again.

    The last paragraph above, makes sure that any change you make in one square, can "propagate" the correct changes, to every applicable square, anywhere on the board.

    Even though it's "just a simple puzzle", it's important to double check the accuracy of each function you code, before going onto the next one. If not you can wind up with hundreds of lines of code, a dozen or so functions, and no idea of where to start de-bugging first!

    A few comments in the code, or before the function, are always good, as well. You'd be surprised how foreign it can all look in a few years.

    Lastly, it's a huge help on the forum, if you show the output - what it should be, and what it is, for a sample.

  10. #10
    Registered User
    Join Date
    Nov 2007
    Posts
    73
    i am getting the possiblities correctly.... but after that i dont know how to proceed.....

    and Adak i didnt quite get the point of must be's and cant be's ....can you try and elucidate..??
    or redirect me ...??? i know my code lacks the logic after the possibilities...

    and i will surely correct my mistake by adding comments..........

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by ElemenT.usha View Post
    i am getting the possiblities correctly.... but after that i dont know how to proceed.....

    and Adak i didnt quite get the point of must be's and cant be's ....can you try and elucidate..??
    or redirect me ...??? i know my code lacks the logic after the possibilities...

    and i will surely correct my mistake by adding comments..........
    Each row, column and box MUST have exactly ONE digit between 1 and 9. So in a simple example:
    Code:
    123|456|789
    =========
    1__|_4_|_8_
    ___|__7|_2_
    ___|___|___
    In the upper left hand box of 9 squares, (say, 2, 2), if your list of possibles had a (1, 3) only, for any square's possibles, then that square would be a "must be" of 3, because you can't have two one's in any one box of 9 squares, and you "must" have some number for that square. If you only have one possible, then it's a "must be", of the first order!

    Every change in the board, even just removing one possible from one square, requires a full re-run through the basic logic, again. Otherwise, that change will not propagate to other changes, across the entire board, as it should.

    I have a rather long (OK, LONG) write up of my program, I'll hunt around and post it up. It has an example of all the logic I used. (and since I'd never played Sudoku before, starting to program the game,), it's pretty easy to understand I think.

    If you google "Sudoku", you'll get a zillion websites, some aimed exactly at how to solve the puzzle. My program is long, and goes into a few odd idea's, because I wanted two ways to solve the puzzle: a very fast way, and a much slower way, using an "odometer" approach.

    The odometer approach is a laugh riot, but it WILL solve the puzzle (hard one's may take a few seconds to a few years to complete, though).

  12. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A relatively simple way to solve sudoku is by backtracking. Basically you try a candidate for each cell and if you get to a dead end (a cell for which there are no candidates left), you go back to the previous cell and try the next possible candidate for that (or if you have tried all candidates, back once more) etc. In the end, either all 81 cells are filled in correctly, or there are no more candidates to try for the first cell - in which case this puzzle is unsolvable).

    This can solve any puzzle (even without any clues - I use it to generate random solutions) and usually fairly quickly. (With certain unsolvable puzzles where the offending cell is towards the end of the search tree, it might take forever. Therefore you might need to do some tests (that there are no cells with no possible candidates) first.

    I think the brute-force "odometer" approach means that a full permutation of the grid is generated and tested etc. This approach is different in that it checks the correctness of the grid so far for each value it tries for each cell. Therefore dead ends are discovered early and a massive number of impossible permutations are skipped each time the algorithm traces back.

    The solution for the empty grid might look like this (trying candidates sequentially, left to right, top to bottom):

    123456789
    456789123
    789123456
    214365897
    365897214
    897214365
    531642978
    642978531
    978531642
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is the contents of my Sudoku program's, detail pages, with
    the formatting data, removed, for easier reading.

    Code:
     * Welcome to the Details Pages * 
     
     I began coding this program the same day I began playing Sudoku for
     the first time. I've rewritten the first couple of functions which
     were somewhat unclear. This was a program of discovery for me, not
     a carfully designed algorithm I was already familiar with. I wanted
     to include two things - an odometer function, and a very fast function
     to solve the puzzle, when desired.
    
     
     Three arrays of possibles are built up, for every square - row, column,
     and box. These three array elements are then compared. Only numbers 
     that are in all three arrays, are kept. The rest are deleted, since
     they can't be a valid number for that square.
    
     
     Now the second phase begins. Squares with just a single possible
     (solo's), are elevated to permanent status. Every other square in
     that square's unit (row, column or box), is checked to see if it's
     possibles need to be changed as a result.
    
     
     Next, each unit is checked for 'must be's'. These exist when a unit
     has only * one * three (for example), in all it's squares' possibles.
     That means that square must be a three, regardless of other possibles.
     In the MustBe functions, these are found, and elevated. Each affected
     unit squares' possibles, are updated as well.
    
     
     The outside rule of pairs is used next, to look for matching pairs
     of possibles, which may be shared by other squares' possible values.
     In a unit like this row:
     
     1    2    3    4    5    6    7    8    9   <== Column #'s
     ==========================================
     25   13   478  389  16   256  89   25   49  <== Possibles
     
     The outside rule of pairs function finds #1 and #8 to have the same
     pair of values. Knowing this, #1 must be either a 2 or a 5 and #8 must
     be the other number. So * no * other valid possibles can be a 2 or a
     5! Which means #6 is changed to just a 6, which makes it a solo, and gets
     #6 elevated. Which means also that #5 can't have a 6 in it's possibles.
     It becomes just a solo 1, which in turn means that #2 becomes just
     a solo 3. 
    
    
    * Welcome to More Details *
     
     In Sudoku, everything you change, can change many other things. Which is 
     why it's important to loop back through stage two and later functions, 
     after you've made changes. In this program, looping back through stage two 
     and above, twice, is required. Three times is never helpful, however. 
     
     Each new puzzle grid that you want checked for a solution, will require all 
     these functions to be called, from stage one, right on up. This sounds  
     like a rude waste of time, but it's the only way, using my algorithm. These 
     functions run very fast! 
     
    
     Easy puzzles are solved outright by stage two. Most puzzles need a bit 
     of trial and error, however. This is the last stage of the program. 
     
     I solve this with two functions, each uses a different approach to the 
     problem. The first one is a virtual odometer function. The squares  
     with no known value, are 'strung' virtually, next to each other, like 
     the wheels of an odometer. The possibles for each square, are the numbers 
     on each wheel. Now we turn the wheels, just like an odometer, and test each 
     resulting puzzle, to see if it's the solution. To make this work, the 
     lowest possible original values are assigned to the squares, by Odometer. 
     The actual incrementing is done by the Increment function, which is called 
     by Odometer, at the first square it can't assign a good number to. If  
     Increment can find a good value, it's assigned, and the program returns 
     to Odometer, for further assignments. It's a back and forth dance, by two 
     functions working together. 
    
     
     Odometer can solve puzzles which have their solutions in the lower part of 
     the puzzles search space, with adequate speed. Puzzles which have their  
     solution in the upper part of their search space, and particularly if that 
     search should require 'driving' the odometer from the 8th or 9th row -  
     are a sheer horror! 
     
     The second function is MagicTouch, an efficient speed-burner at solving. 
     It scans the board and id's some squares with only two possibles left. That  
     squares's array subscript is put into a small array called least(n). Now   
     MagicDat is called to prepare the dat file templates MagicTouch will use 
     to set the values of each of the least squares possible value. For example, 
    
    * Welcome to Still More Details * 
     
     the first template will be:  
     
     1 1 1  
     1 1 2   is next, all the way to: 
              
     2 2 2.   
     
     These template numbers tell MagicTouch which square should be assigned 
     to it's first possible value, and which square should be assigned it's 
     second possible number.  
     
     Ironically, MagicDat uses an odometer logic, to create these templates. 
     
     MagicTouch now makes the assignments of possibles to each paired square,  
     according to the next template in the dat file. The resulting puzzle values 
     are all then given a preliminary test; by row, column, and box. Only 
     puzzles which have passed the previous test(s), are tested further. 
     
     At this point, many of the squares still have no known value! This is  
     designed to remove obvious conflicts * only *, in the assignments made. 
     
     Proposed solutions which pass all three of these preliminary tests, are 
     passed to the stage one, stage two, and stage three functions, to see if 
     they really will succeed in solving the entire puzzle. 
     
     In early testing, MagicTouch solves every puzzle in less than half a second, 
     on my P3 laptop, using just interpreted BASIC. No particular optimizations 
     have been made. Compiled versions of Magic Sudoku are up to 10 times faster, 
     solving puzzles in limited testing. 
     
     An empty Sudoku puzzle, is not a Sudoku puzzle. It is an empty puzzle, 
     waiting for it's initial values to be given. I had never heard of that  
     being presented as a puzzle to solve, and this program does not have code 
     that will support that concept.
    The "odometer" function, tries to solve the puzzle, by using each square of the puzzle, like a wheel on your
    car's odometer. Beginning with square 1, 1 (the top left square), it finds the lowest number in the squares
    list of "possibles", and assigns that value to the square. It then does the same to the next square 2, 1, and
    tests to see if that combo of values is legal; continuing in this way until it finds a square whose assigned value
    is NOT legal.

    Then it begins incrementing that squares values, through it's range of possibles, from lower to higher values.
    If no legal value is found, it moves to the left (back the way it came from), and begins incrementing that wheel's
    values, after setting the value of the last wheel, to it's lowest possible value.

    This is repeated, all the way back to the first square 1,1, if needed. Since it does no early testing, and only works
    it's way up the squares in a very sequential manner, it's deadly slow to solve a problem which has the wrong
    value on it's first squares, and that isn't discovered until the odometer function is working with squares down
    on the middle or (worse), lowest squares of the puzzle. Then you're REALLY in for a LONG (perhaps days), wait,
    for it to solve the puzzle.
    Last edited by Adak; 02-15-2008 at 01:47 AM.

  14. #14
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by ElemenT.usha View Post
    it si a sudoku program....
    i.e, it takes a 9x9 sparse array... and inputs for the array...

    using the rules it has to output the solution....
    RULES:
    1.no element can repeat itself in a row.
    2.no element can repeat itself in the column.
    3.all elements 1-9 should be present in every row n column....
    You are missing an important rule...

    Each 3x3 sub grid should contain all elements 1-9

    otherwise, this would be valid, shift position by 1 each row like:

    123456789
    234567891
    345678912
    456789123
    567891234
    678912345
    789123456
    891234567
    912345678

    Here is a solver I wrote a while back

  15. #15
    Banned
    Join Date
    Nov 2007
    Posts
    678

    Wow Adak! Impressive!

    And you say you are just a Hobby programmer. Wonder what would you do if you were some professional
    programmer!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku 4 by 4 combination lister?
    By iskate4 in forum C++ Programming
    Replies: 2
    Last Post: 02-19-2009, 01:56 PM
  2. malloc, structures, arrays and sudoku!!
    By AmbliKai in forum C Programming
    Replies: 13
    Last Post: 10-15-2008, 03:05 AM
  3. sudoku - arrays
    By rocketman50 in forum C++ Programming
    Replies: 2
    Last Post: 03-21-2008, 09:20 AM
  4. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  5. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 11:39 PM