Thread: Could someone help explain this a little bit

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    36

    Could someone help explain this a little bit

    Hello guys.

    I decided i was going to make a sudoku solver in visual c++. So far I have a program which can solve easy/medium difficulty sudokus. I still have to implement one more piece of logic, as well as the whole brute force method if a guess is required to complete the puzzle.

    I would say im fairly new to programming, I have only done about a terms worth of c++ at university. The thing is my code at the moment is not even nearly finished, but it is getting very long and messy.

    I have been looking around the internet and found a site which seems quite usefull.

    http://compprog.wordpress.com/2007/10/31/sudoku-solver/

    I'm not sure wether its because he declares constants at the start and uses these throughout, but the code seems a bit too complex for me to understand at the minute. Could anyone explain some of the concepts he uses to avoid large and unecessary pieces of code?

    For example, once my program has found out which number goes into a certain square. It will pass the number and its x and y coordinates to the function below. The function then checks within the 3x3 block and calls another function 'blocklist'. This basically deletes the number from the possible list of values of all the other cells in that 3v3 grid.

    Code:
    void block(nodeptr pointerarr[9][9], int y,int x, int value)
    {
    	int i,j;
    	if(x <= 2){
    		if (y <= 2){
    			for (i=0;i<3;i++){
    				for (j=0;j<3;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    		}
    		else
    		{
    			if (y <= 5){
    				for (i=0;i<3;i++){
    				for (j=3;j<6;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    			}
    			else{
    				for (i=0;i<3;i++){
    				for (j=6;j<9;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    			}
    		}
    	}
    	else
    	{
    		if(x <= 5){
    		if (y <= 2){
    			for (i=3;i<6;i++){
    				for (j=0;j<3;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    		}
    		else
    		{
    			if (y <= 5){
    				for (i=3;i<6;i++){
    				for (j=3;j<6;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    			}
    			else{
    				for (i=3;i<6;i++){
    				for (j=6;j<9;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    			}
    		}
    	}
    
    
    		if(x >= 6){
    		if (y <= 2){
    			for (i=6;i<9;i++){
    				for (j=0;j<3;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    		}
    		else
    		{
    			if (y <= 5){
    				for (i=6;i<9;i++){
    				for (j=3;j<6;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    			}
    			else{
    				for (i=6;i<9;i++){
    				for (j=6;j<9;j++){
    				blocklist(pointerarr,value,i,j);
    				}
    			}
    			}
    		}
    	}
    }
    }
    Im obviously doing something wrong!! (or stupidly )

    Thanks for reading
    Last edited by rocketman50; 03-22-2008 at 08:24 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If you want to divide into smaller blocks [3 x 3 squares], then you can divide x and y by 3, and then count 0..2 on each of x and y onto that for doing the square. The starting square for each block is [(x / 3) * 3, (y / 3) * 3]

    The linked code uses three arrays to give the right coordinates within a one-dimensional array for rows, columns and "small blocks".

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Obviously you could calculate the x and y indexes from the given point, so you wouldn't need all the if ... else blocks and could traverse the 3*3 box with a single nested loop.

    It should be possible to replace this code with something like:
    Code:
    void block(nodeptr pointerarr[9][9], int y,int x, int value)
    {
        int x_start = x / 3 * 3, x_end = x_start + 3;
        int y_start = y / 3 * 3, y_end = y_start + 3;
        for (int i = x_start; i < x_end; ++i) {
            for (int j = y_start; j < y_end; ++j) {
                blocklist(pointerarr, value, i, j);
            }
        }
    }
    The main idea behind the three tables in the code you linked is that it lets you traverse the board in different "modes" in the same (similar) way. Particularly, traversing the zones is hard, because without such a table you'd need nested loops just to scan each item in a zone. In this case, if you need to scan the second zone - between "corner points" (0, 3) and (2, 5), you can linearly use the second line of zoneElements - { 3, 4, 5, 12, 13, 14, 21, 22, 23} - to find the indices into to main array.
    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
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    Ah yes, that makes much more sense to do it that way. That piece of code works perfectly!
    For some reason I thought that having floats appearing with integer variables would cause problems. I blame the lack of sleep!

    I think I will try using the three tables method soon, looks fun

    Thank you mats and anon

  5. #5
    Registered User
    Join Date
    Jan 2011
    Posts
    87
    heres how i did it, i just made a new thread so you can go look at my program if you want to
    Code:
    int xbox[3], ybox[3];
    switch x
    {
    case 1:{}
    case 2:{}
    case 3:
           {
                 xbox[0] = 1;
                 xbox[1] = 2;
                 xbox[2] = 3;
                 break;
           }
    case 4:{}
    case 5:{}
    case 6:
           {
                 xbox[0] = 4;
                 xbox[1] = 5;
                 xbox[2] = 6;
                 break;
           }
    case 7:{}
    case 8:{}
    case 9:
           {
                 xbox[0] = 7;
                 xbox[1] = 8;
                 xbox[2] = 9;
                 break;
            }
    and then the same for ybox, then i used xbox and ybox as the paremeters for the box


    note: i was using a array (sudokuboard[9][9]) as my board

  6. #6
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    dude. stop reviving all these old thread about sudoku. Your time is better spent with a better algo to solve it than looking for old threads.
    "All that we see or seem
    Is but a dream within a dream." - Poe

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical Operations on Bit Patterns
    By mthemapc in forum C++ Programming
    Replies: 7
    Last Post: 02-17-2008, 03:04 PM
  2. porting application from 32 bit to 64 bit error
    By gandalf_bar in forum Linux Programming
    Replies: 1
    Last Post: 09-14-2005, 09:20 AM
  3. Bit processing in C
    By eliomancini in forum C Programming
    Replies: 8
    Last Post: 06-07-2005, 10:54 AM
  4. Porting from 32 bit machine to 64 bit machine!
    By anoopks in forum C Programming
    Replies: 10
    Last Post: 02-25-2005, 08:02 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM