I have to fill in a 2^n by 2^n board that has a hole in it with tiles that look like the example below. The tile we have to use is the combination of the 1's in the image below and the 0 is the hole (cause I really don't know how to explain it).
2x2 board

I've got the whole code done, but it only works for boards of 2x2, 4x4, 8x8. Anything bigger and it doesn't fill it in completely. I've tried a bunch of things and can't fix it.

Anyone see where I'm messing something up or any suggestions on how I should change my program so it's cleaner.


Below are the printout for the 4x4 and 8x8 so you can see how it's suppose to look like.
4x4 board, 8x8 board

And here's the code:

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

struct hole
{
   int row;
   int col;
};


void initialize (int, int**, hole);
void decor(int);
void print(int, int**);
int fill (int, int**, hole, int, int, int, int, int, int, int&);
void check (int**, int, int, int);
void norm (int&, int&, int&, int&);
void state (int&, int, int, int);

main ()
     { int m = 3, row=1, col=1, start = 1;
       hole space;
       int n = (1 << m);
       int** array = new int*[n];
       for (int i = 0; i < n; i++)
           { array[i] = new int[n]; }
          
       space.row = row-1;
       space.col = col-1;      
       initialize (n, array, space);
             
       fill (n, array, space, 0, 0, 0, 0, 0, 0, start, start);
       print (n, array);

       //free the array space
       for(int i = 0; i < n; i++)
          { delete array[i]; }
       delete array;
       system ("pause");
       return 0;
     }
     
void initialize (int n, int** array, hole a)
{ for (int x = 0; x < n; ++x)
      { for (int y = 0; y < n; ++y)
            { array[x][y] = 99; } 
      }
  array[a.row][a.col] = 0;
}

void norm (int& row, int& col, int& r, int& c)
{  r = row % 2;
   c = col % 2; 
}

void state (int& h, int c, int p, int b)
     { if (h+c <= b)
          { h += c + p; }
     }

int fill (int n, int **a, hole now, int xh, int yh, int xc, int yc, int pxc, int pyc, int& num)
{ static int o = n/2;
  if (n==2)
     { int row, col;
       state (xh, xc, 0, o);
       state (yh, yc, 0, o);
       norm (now.row, now.col, row, col);
       if (row == 0)
          { if (col == 0) { check (a, xh, yh+1, num); }
            if (col == 1) { check (a, xh, yh, num); }
            check (a, xh+1, yh, num);
            check (a, xh+1, yh+1, num);
          }
       if (row == 1)
          { if (col == 0) { check (a, xh+1, yh+1, num); }
            if (col == 1) { check (a, xh+1, yh, num); }
            check (a, xh, yh, num);
            check (a, xh, yh+1, num);
          }
     }
  else 
     { int half = (n/2);
       int x, y;
       pxc += xc;
       pyc += yc;
       xc = xh;
       yc = yh;
       xh += half;
       yh += half;
       if (now.row < xh) x = 1;
       else x = 2;
       if (now.col < yh) y = 1;
       else y = 2;
       hole q1, q2, q3, q4;
       // Space for switch
       switch (x+y)
              { case 2:
                     q1.row = now.row;
                     q1.col = now.col;
                     q2.row = (xh-1);
                     q3.col = (yh-1);
                     q2.col =  q4.col = yh;
                     q3.row = q4.row = xh;
                     a[xh-1][yh] = a[xh][yh-1] = a[xh][yh] = num;   
                     break;
                case 3:
                     if (x == 1)  // if row 1 col 2
                        { q3.col = (yh-1);
                          q3.row = xh;
                          q2.row = now.row;
                          q2.col = now.col;
                          a[xh][yh-1] = num;
                        }
                     else   // row 2 col 1
                        { q2.row = (xh-1);
                          q2.col = yh;
                          q3.row = now.row;
                          q3.col = now.col;
                          a[xh-1][yh] = num;
                        }
                    q1.row = (xh-1);
                    q1.col = (yh-1);
                    q4.row = xh;
                    q4.col = yh;
                    a[xh][yh] = a[xh-1][yh-1] = num;
                    break;
               case 4:
                    q4.row = now.row;
                    q4.col = now.col;
                    q1.row = q2.row = (xh-1);
                    q3.row = xh;
                    q1.col = q3.col = (yh-1);
                    q2.col = yh;                   
                    a[xh-1][yh-1] = a[xh-1][yh] = a[xh][yh-1] = num;
                    break;
            } // End Switch
       fill(half, a, q1, 0,  0,  xc, yc, pxc, pyc, ++num);
       fill(half, a, q2, 0,  yh, xc, yc, pxc, pyc, ++num);
       fill(half, a, q3, xh, 0,  xc, yc, pxc, pyc, ++num);
       fill(half, a, q4, xh, yh, xc, yc, pxc, pyc, ++num);
     }  
}

void decor(int n)
     { cout << "\n-";
       for (int i = 0; i < n; i++)
           { cout << "-----"; }
       cout << endl;
     }

void print(int n , int **ar)
     { decor(n);
       for (int x = 0; x < n; x++)
           { for (int y = 0; y < n; y++)
                 { cout << "|" << setw(3) << ar[x][y] << " "; }
             cout << "|"; 
             decor(n);
           }
     }

void check (int **ar, int x, int y, int num)
     { if (ar[x][y] == 99)
          { ar[x][y] = num; }
     }

> Anything bigger and it doesn't fill it in completely.
As in it crashes with some error message, or some other reason?

Why do you have a 'static' in fill()?
There's only ONE variable, not a separate copy for each recursive invocation.

It doesn't crash, it just doesn't fill in the board completely. For a 16x16, it fills in the first 8x8 quadrant fine, but the others don't fill in completely.

Basically, something in my program takes the number and either tries to place it in the first quadrant or it doesn't do anything at all.

It ends up looking like this (the 99 are there to show it didn't work).
16x16 Board

Hi before going into your code ..whick looks rather big :D
could u please explain us in few words how u defined:

  • the recursion base case
  • the recursion step(s)

for your task.

Furthermore, did u prove that your recursion function is correct using induction?

Unless these are not defined properly, there wont be any efficient code, I think :d

So it does reach the far corner then.

> fill(half, a, q1, 0, 0, xc, yc, pxc, pyc, ++num);
My guess is each of these should be num+1, not num++ (or even ++num)

But then again, I can't see why it would need to be a reference either.

@ sidatra79
My base case is that if n is 2, you fill in the spaces that aren't the hole with the number.

The recursive steps are suppose to be, if n does not equal 2, take n and divide it by 2 so it brakes the board up into 4 quadrants of (n/2)x(n/2) {like in the case of a 4x4 board, it breaks it up into 4 2x2 boards}, hence the fill being called 4 times at the end of of else fill.
Before fill is called again though, you place one tile in the middle of the board so that it creates a "hole" in each quadrant (look at 4x4, the 3 1's is that step) and then figure out what the new "holes" for each quadrant is.

i.e. In the 4x4, the original hole is in cell a[0][0], so there is already a hole in that quadrant. To create a so called "hole" in the other quadrants so the first half of fill will fill them in, you place a tile at the exact center of the 4x4 so that no pieces are in the first quadrant, meaning a[1][2], a[2][1], and a[2][2] should be where the 1's are placed. Then, you send the first quadrant to fill (a[0][0], a[0][1], a[1][0], a[1][1]). When it comes back, you send the second quadrant to fill (a[0][2], a[0][3], a[1][2], a[1][3]), then the third, and then the fourth.

For a larger board (like 8x8, 16x16, etc) it should just do the same thing, but the thing it has to keep in mind is that, for a 8x8, the 2 quadrant needs to add 4 to the col number so that it gets a[0][4] instead of a[0][0] and for some reason, it seems to be messing this up for anything larger then 8x8 (I've only check 16x16, but if it doesn't work there, I doubt it's gonna work elsewhere).


@ Salem
Yeah, it does. It's not the num that's messing up, it's not taking into consideration that this is the 2nd quadrant of a 16x16 (meaning it needs to add 8 to the col number, 8 to row for quadrant 3, and 8 to both col and row for quadrant 4). If actually originally had 25 over the top right corner until I wrote the check function that stopped it from doing that so I could see where the issue was.

I think I originally tried to compensate for the different quadrants, but I think it messed it up when I was trying to fix other issues.

Actually. I might have just figured it out. I'll check it completely when I get home.

This question has already been answered. Start a new discussion instead.