Fill square

This is a discussion on Fill square within the C Programming forums, part of the General Programming Boards category; Ηelp... I have to make a program that fills a board perfect with numbers. The first cell should always starts ...

  1. #1
    ch4
    ch4 is offline
    Newbeer ch4's Avatar
    Join Date
    Jan 2007
    Posts
    142

    Fill square

    Ηelp... I have to make a program that fills a board perfect with numbers.
    The first cell should always starts with number 1.
    Each number should be placed only: vertically (three cells) or levelly (three cells) or across(two cells) of the previous number.

    E.X.
    if the given number is 5 then the result:
    Code:
      
    1    19    16    4     20
    14    24    8    11     23
    17    5    21    18      6
    2    10    15     3      9
    13    25     7    12     22
    Here is my attempt but i can see the mistake.

    Code:
    #include<stdio.h>
    #include<math.h>
    
    
    int table (int x,int y,int s,int n);
    int a[5][5];
    int main (void){
        int i,j,m;
        
        /*fill the table with zero*/
        for(i=0;i<5;i++){
                         for(j=0;j<5;j++){
                                          a[i][j]=0;
                                          }
                         }
        /*get number*/
        scanf("&#37;d",&m);
        m=m*m;
        
        /*function call*/
        table(0,0,1,m);
        
        /*print the board*/
        for(i=0;i<sqrt(m);i++){
                        for(j=0;j<sqrt(m);j++){
                                       printf("%d    ",a[i][j]);
                                       }
                        putchar('\n');putchar('\n');putchar('\n');
                        }
        
        getchar();getchar();
        return 0;
        }
    /*function that fills the board*/
    int table (int x,int y,int s,int n){
        
            /*check conditions*/
        if((s<=n)&&(x<sqrt(n))&&(x>=0)&&(y<sqrt(n))&&(y>=0)&&(a[x][y]==0)){
                                                                         a[x][y]=s;
                                                                         
                                                                         
                                                                    if(table(x,y+3,s+1,n)==1){                         /*check the next number three cells horizontally*/
                                                                                                      return 1;                    /*return 1 if every condition is correct*/
                                                                                              }
                                                                    else if (table(x+2,y+2,s+1,n)==1){
                                                                                                      return 1;
                                                                                                      }
                                                                    else if (table(x+3,y,s+1,n)==1){
                                                                                                      return 1;
                                                                                                    }
                                                                    else if (table(x+2,y-2,s+1,n)==1){
                                                                                                      return 1;
                                                                                                      }
                                                                    else if (table(x-3,y,s+1,n)==1){
                                                                                                      return 1;
                                                                                                    }
                                                                    else if (table(x-2,y-2,s+1,n)==1){
                                                                                                      return 1;
                                                                                                      }
                                                                    else if (table(x,y-3,s+1,n)==1){
                                                                                                      return 1;
                                                                                                    }
                                                                    else if (table(x-2,y+2,s+1,n)==1){
                                                                                                      return 1;
                                                                                                      }
                                                                    else{                                     /*if no condition is correct then delete the number and return 0*/
                                                                         a[x][y]=0;                         /*in order to check somewhere else*/
                                                                         return 0; }
                                                                         
                                                                         }
         
                       
         if(s<n)
                  return 2;
                   
         return 1;   
            }
    Last edited by ch4; 05-12-2007 at 05:58 AM.

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    I'm totally lost at what you're trying to do. Either I need to get some rest, or this makes little to no sense.

    I understand you want to build a table of some sort, but I don't know what the relationship of the numbers is, if any at all. Your table() function has some ugly calculations and recursion, and in its current form, is not easy to read.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Numbers are successively entered into the table, with each number located either 3 vertically, 3 horizontally, or 2 diagonally from the previous number. But it doesn't look easy to carry out.

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Aha, I finally understand it! I think I might celebrate.

    IMO, the first problem is that the table() function is way too complicated. If the algorithm could be simplified, it would probably help.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I was wondering what the heck "levelly" meant!

    Instead of one GIGANTIC if statement, and the World's LONGEST tab settings, why don't you bring this back down to earth with much simpler logic statements AND a tab setting of from 2 to 5 spaces.

    A few comments to describe just what you're doing/trying to do with your logic, in the table() function, would be very good to have, as well.

    I'm confused why 's' is always just 1, in the call to table() ?
    Last edited by Adak; 05-11-2007 at 10:20 AM.

  6. #6
    ch4
    ch4 is offline
    Newbeer ch4's Avatar
    Join Date
    Jan 2007
    Posts
    142
    Hi
    levelly it means horizontally.

    Check my example:
    ALWAYS in the first cell should be placed number 1
    2 is situated three cells donw vertically from 1
    3 is situated three cells left horizontaly from 2
    4 is situated three cells up vertically from 3
    5 is situated two cells across from 4 etc...

    The board should be filled perfect acording the rules without blanck cells.
    if you check my program for 5 you will see what i mean.

    It works flashbacking:
    it checks for each number the conditions for it's next.
    Last edited by ch4; 05-12-2007 at 05:51 AM.

  7. #7
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    And if your scanf() fails?

    You just continue on... So add some error checking!

  8. #8
    ch4
    ch4 is offline
    Newbeer ch4's Avatar
    Join Date
    Jan 2007
    Posts
    142
    i do not mind if scanf() fails i will fix the detail at the end

  9. #9
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    scanf("&#37;d", &m);
    m = m*m;
    /me thinks
    Code:
    char buf[16];
    fgets(buf, sizeof(buf); stdin);
    if(sscanf(buf, "%d", &m) != 1)
    {
        perror("m, not an int");
        return 1;
    }
    m *= m;
    I also wouldn't hardcode the bounds of your 2D array...
    Last edited by zacs7; 05-12-2007 at 06:17 AM.

  10. #10
    ch4
    ch4 is offline
    Newbeer ch4's Avatar
    Join Date
    Jan 2007
    Posts
    142
    Thanks Everyone.

    I made it. I built the program i was talking to.
    So grab the code and check it to see what i mean.

    Code:
    #include<stdio.h>
    #include<math.h>
    
    
    int table (int x,int y,int s,int n);
    int ** a;
    int main (void){
        int i,j,m;
        
         
        printf("\t\t\t*<-- SQUARES -->*\n\n");
        printf("Give the number , whom the square you want to be filled : ");
       
         
        scanf("&#37;d",&m);
        
         
        a=malloc (m * sizeof (int *));
        for(i=0;i<m;i++)
                        a[i]=malloc (m * sizeof (int));
                        
        putchar('\n');                
                        
         
         for(i=0;i<m;i++){
                         for(j=0;j<m;j++){
                                          a[i][j]=0;
                                          }
                         }
         
        m=m*m;
        
         
        table(0,0,1,m);
        
        
         
        for(i=0;i<sqrt(m);i++){
                        for(j=0;j<sqrt(m);j++){
                                               if(a[i][j]<10)
                                                            printf(" %d    ",a[i][j]);
                                               else
                                                            printf("%d    ",a[i][j]);
                                       }
                        putchar('\n');putchar('\n');putchar('\n');
                        }
        
        getchar();getchar();
        return 0;
        }
    
    int table (int x,int y,int s,int n){
        
         
        if((s<=n)&&(x<sqrt(n))&&(x>=0)&&(y<sqrt(n))&&(y>=0)&&(a[x][y]==0))
              {                                                           
               a[x][y]=s;                                                          
                                                                         
               if(table(x,y+3,s+1,n)==1){
                                                return 1;
                                        }
               else if (table(x+2,y+2,s+1,n)==1){
                                                return 1;
                                                 }
               else if (table(x+3,y,s+1,n)==1){
                                                return 1;
                                               }
               else if (table(x+2,y-2,s+1,n)==1){
                                                return 1;
                                                 }
               else if (table(x-3,y,s+1,n)==1){
                                                return 1;
                                               }
               else if (table(x-2,y-2,s+1,n)==1){
                                                return 1;
                                                 }
               else if (table(x,y-3,s+1,n)==1){
                                                return 1;
                                               }
               else if (table(x-2,y+2,s+1,n)==1){
                                                return 1;
                                                 }
               else{
                    a[x][y]=0;
                    return 0; 
                    }
                                                                         
              }                  
         else if(s<=n)            
                  return 0;
         else if(s==n+1)          
             return 1;            
    
            }
    Just try it for numbers >5
    Now my problem is to make it faster.

  11. #11
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    I don't understand why do you firstly make m = m*m
    and then here and there use sqrt(m)

    Use the original value, discard all uses of sqrt and calculate m*m anly where needed... (And I haven't read your algorithm...)
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  12. #12
    ch4
    ch4 is offline
    Newbeer ch4's Avatar
    Join Date
    Jan 2007
    Posts
    142
    I calculate m=m*m because i want to fill the table with all numbers from 1 to square of the given number.
    I use sqrt(n) in order to be sure that the program will not "look" out of my table.
    Take a look of my examples.

  13. #13
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    What vart means is this. Why not replace this
    Code:
        m=m*m;
        
         
        table(0,0,1,m);
        
        
         
        for(i=0;i<sqrt(m);i++){
                        for(j=0;j<sqrt(m);j++){
                                               if(a[i][j]<10)
                                                            printf(" &#37;d    ",a[i][j]);
                                               else
                                                            printf("%d    ",a[i][j]);
                                       }
                        putchar('\n');putchar('\n');putchar('\n');
                        }
        
        getchar();getchar();
        return 0;
        }
    with this?
    Code:
     /* m=m*m; */
        
         
        table(0,0,1,m*m);
        
        
         
        for(i=0;i<m;i++){
                        for(j=0;j<m;j++){
                                               if(a[i][j]<10)
                                                            printf(" %d    ",a[i][j]);
                                               else
                                                            printf("%d    ",a[i][j]);
                                       }
                        putchar('\n');putchar('\n');putchar('\n');
                        }
        
        getchar();getchar();
        return 0;
        }
    sqrt() is rather expensive to calculate, so it is best if you can avoid doing so, especially in a loop as you have it.

    Note that I didn't look too closely at your code, I just echoed what vart said.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tic Tac Toe Comp Move help
    By swgh in forum C++ Programming
    Replies: 5
    Last Post: 09-24-2008, 11:05 AM
  2. Loop seg error
    By Zishaan in forum Game Programming
    Replies: 2
    Last Post: 03-28-2007, 01:27 PM
  3. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  4. Help with my draughts game
    By Zishaan in forum C++ Programming
    Replies: 9
    Last Post: 03-24-2007, 07:33 AM
  5. Replies: 3
    Last Post: 12-22-2004, 06:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21