Error in recursive function

[lastchance]

Hello @Civer1999,

For an upper bound on rows r, with n bricks, note that you will have to fit
r * ( n - 1 )
total joints into either
n(n+1)/2 + (n-1) -2
slots if joints have unit thickness (what you didn't like) or
n(n+1)/2 - 1
slots if joints have zero thickness.

However, all this does is tell you that a certain number of rows will be impossible - it doesn't actually guarantee that anything less than or equal to the upper bound will actually have a solution. (But it does allow you to stop bothering for large numbers of rows). So I don't really use this bound as part of my code (although I do use the number of slots).

I'm afraid I didn't follow your code, and it may or may not be appropriate to use recursion here (I couldn't actually see how to).

FWIW, my algorithm runs roughly as:
- set up a 2-dimensional array mortar[rows][bricks-1] to hold the 'slot' of a particular mortar joint; also keep a bool array of dimension 'slots' to tally which positions have already been taken;
- sequentially position the first mortar joint in each row, then the second in each row, etc.
- each time, aim to position in the leftmost legitimate position (one that hasn't been taken and doesn't re-use a brick length;
- if this reaches a dead end, then back up and increase the previous row's last brick length.

If it works then it produces a solution (solutions aren't unique) in a time too short to measure. If it doesn't then it will eventually tell you so, but it is a huge number of trials first.

[Civer1999]

FWIW, my algorithm runs roughly as:
- set up a 2-dimensional array mortar[rows][bricks-1] to hold the 'slot' of a particular mortar joint; also keep a bool array of dimension 'slots' to tally which positions have already been taken;
- sequentially position the first mortar joint in each row, then the second in each row, etc.
- each time, aim to position in the leftmost legitimate position (one that hasn't been taken and doesn't re-use a brick length;
- if this reaches a dead end, then back up and increase the previous row's last brick length.

I just tested it and it really is incredibly fast! Even for huge inputs such as n = 250 it only takes around 15 seconds, truly amazing.
Btw is that the same algorithm you used when you wrote that you can't find a solution for n = 20 which has 11 rows?

[lastchance]

Yes, it is the same algorithm. For n = 20 and 11 rows it isn't excluded by combinatorics, but I didn't find a solution (or prove that there wasn't one) in a sensible time.

The algorithm works pretty well the same whether the joints are unit thickness or zero thickness, with minor variation in code. However, drawing a representation of the wall at the end is much more messy with zero-thickness joints.

[Civer1999]

Alright, I don't know what I did different, but I get a result for n = 20 with 11 rows in not even a second, did you use the zero thickness joints or the ones which take up a space?
Nevermind, made a mistake somewhere.

Drawing a representation of the wall at the end is much more messy with zero-thickness joints

That's true, took some thinking to actually get it to look decent.

[lastchance]

@Civer1999

Your picture doesn't portray a valid solution.

Your fifth row has two bricks of length 4.

Your tenth row (the penultimate one) has two bricks of length 3. This could be split to give the missing 1 and 2 length bricks ... but would then clash with other rows.

There are several others like this. Unsurprisingly, they tend to involve problems with the last brick.

Maybe you should throw your code at small cases where we know there are no solutions - e.g. 4 bricks, 4 rows.

The algorithm is fine for determining solutions with rows much less than the upper bound, but not good for proving the negative (since it would effectively require you to check about half the maximum number of permutations of bricks to prove that a solution didn't exist). There has got to be a better method ...

[jonnin]

is this correct for N = 4?

#|##|###|#### //1234
###|##|####|# //3241
##|####|#|### //2413

and if so, is it correct that you can't start a row with 4 because it collides with the first row?

#|##|###|####  //1234
####| 

if these are correct, then the sum of the terms including 1 for the spacer can't be the same...
1+2+1 is 3
3+2+1 is 6
2+4+1 is 7

or you can ignore the spacers and do the same thing with just the terms
1+2
3+2
2+4
etc

and each time you add a brick you can't violate the sums.
Seems like that would lend itself to an efficient solution. I am going to take a crack at it now, I have a little free time finally.

I had initially discarded columns with the same number twice and was unable to get solutions... that is clearly not a valid constraint... I didnt see it clearly...

[Civer1999]

#|##|###|#### //1234
###|##|####|# //3241
##|####|#|### //2413

No, this is not correct, as I just found out two days ago that the joints have no thickness whichs means, that in your solution the first two rows would have an overlapping joint:

|- - - - - - - - - -|
| |   |     |       |
|- - - - - - - - - -|
|     |   |       | |
|- - - - - - - - - -|

[lastchance]

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int thick;         // thickness of mortar joint (0 or 1)
int n;             // number of bricks
int rows;          // number of rows
int width;         // number of positions filled by either brick or mortar
int last;          // last index in availability array

//========


int next( int r, int level, const vector< vector<int> > &mortar, const vector<bool> &avail, const vector< vector<bool> > &brick, int &length )
{
   int prev = -1;                                                  // Effective position of left end stop for level 0
   if ( level > 0 ) prev = mortar[r][level-1];                     // Otherwise, mortar position to the left

   int pos = max( prev + thick, mortar[r][level] ) + 1;            // First trial; must leave minimum brick space and increase any current
   int posmax = min( last, prev + n + thick );                     // Maximum trial position
   while ( pos <= posmax )                                         // Search all possible next positions
   {
      if ( avail[pos] )                                            // ... that haven't been used yet
      {
         length = pos - prev - thick;                              // The length of a brick, given these mortar positions
         if ( brick[r][length] ) return pos;                       // If this brick still available, use it
      }
      pos++;
   }
   return -1;                                                      // Failed to place one
}


//========


void draw1( const vector< vector<int> > &mortar )
{
   string layer = '|' + string( width, '-' ) + '|';

   for ( int r = 0; r < rows; r++ )
   {
      string line = layer;
      for ( int i = 0; i < n - 1; i++ ) line[ 1 + mortar[r][i] ] = '|';
      cout << line << '\n';
   }
}


//========


void draw0( const vector< vector<int> > &mortar )
{
   string layer = "|-";
   for ( int i = 1; i <= width - 1; i++ ) layer += " -";
   layer += '|';

   string line0 = "| " + string( 2 * ( width - 1 ), ' ' ) + '|';

   cout << layer << '\n';
   for ( int r = 0; r < rows; r++ )
   {
      string line = line0;
      for ( int i = 0; i < n - 1; i++ ) line[ 2 + 2 * mortar[r][i] ] = '|';
      cout << line  << '\n' << layer << '\n';
   }
}


//========


int main()
{
   cout << "Enter the joint thickness ( 0 or 1 ): ";   cin >> thick;
   cout << "Enter the number of bricks ( > 1 ): "  ;   cin >> n;
   width = n * ( n + 1 ) / 2 + ( n - 1 ) * thick;
   int maxrows = ( width - 1 - thick ) / ( n - 1 );                            // Upper bound (not necessarily achievable)
   cout << "Enter the number of rows: ( <= " << maxrows << " ): ";   cin >> rows;

   last = width - 2;                                                           // Last index available for mortar
   vector<bool> avail( last + 1 , true );                                      // Slots available for mortar
   if ( thick == 1 ) avail[0] = false;

   vector< vector<int> > mortar( rows, vector<int>( n - 1, -1 ) );             // Mortar positions by row and level; -1 means not set
   vector< vector<bool> > brick( rows, vector<bool>( n + 1, true ) );          // Brick lengths still available ([0] component isn't used)


   // ALGORITHM: find lowest legitimate slot; if dead end then back up one by one and retry
   int length = 0;                                                             // Length of a brick (if placeable)
   int r = 0;                                                                  // r is row
   int level = 0;                                                              // Level is mortar number in that row (counting from 0)

   while ( true )                                                              
   {
      int m = next( r, level, mortar, avail, brick, length );                  // Lowest legitimate slot (ignoring current, if any)

//    cout << level << " " << r << " " << m << endl;
      if ( r == 0 && level == 0 && m < 0 )                                     // This can take a ... VERY ... LONG ... time!
      {
         cout << "Impossible" << endl;
         return 1;
      }

      if ( m >= 0 )                                                            // If there is a slot available
      {
         mortar[r][level] = m;                                                 // ... fill it with mortar
         avail[m] = brick[r][length] = false;                                  // ... make it unavailable
         r++;   if ( r == rows ) { r = 0; level++; }                           // ... move to next row
      }
      else                                                                     // If there isn't one ...
      {
         mortar[r][level] = -1;                                                // ... cancel this spot
         r--;   if ( r < 0 ) { r = rows - 1; level--; }                        // ... and move back a row
         length = mortar[r][level] - thick - ( level == 0 ? -1 : mortar[r][level-1] );
         avail[mortar[r][level]] = brick[r][length] = true;                    // Clear this position, as we must update it next loop
      }
      if ( level == n - 1 ) break;                                             // All mortar in place
   }

   if ( thick == 0 ) draw0( mortar );
   else              draw1( mortar );
}

Enter the joint thickness ( 0 or 1 ): 0
Enter the number of bricks ( > 1 ): 10
Enter the number of rows: ( <= 6 ): 6
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
| |           |         |             |       |               |                 |                   |   |     |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|   |           |             |         |               |       |                 |     |                   | |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|     |           |         |             |       |                 | |   |                   |               |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|       |           |             |         |               |     |                 | |   |                   |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|         |           |             |               | |                 |                   |   |     |       |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|           |             |     |               |         |                 | |                   |       |   |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|

Enter the joint thickness ( 0 or 1 ): 0
Enter the number of bricks ( > 1 ): 4
Enter the number of rows: ( <= 3 ): 3
|- - - - - - - - - -|
| |     |   |       |
|- - - - - - - - - -|
|   |     |       | |
|- - - - - - - - - -|
|     |       | |   |
|- - - - - - - - - -|

Enter the joint thickness ( 0 or 1 ): 0
Enter the number of bricks ( > 1 ): 4
Enter the number of rows: ( <= 3 ): 4
Impossible