OK, I'll trust your claim that it is not current homework, and show you the generic recursive brute force approach to a wide range of similar problems.
This approach is a randomized guess and check. It is used when the programmer understands only the basic constraints of the problem and not the implications of those constraints. In larger problems the run time might be hopelessly long, because it is doing a depth first search of the possibilities. But for a lot of problems, the fact that a CPU is incredibly fast means a "brute force" (stupid) search is fine.
Code:
#include <cstdlib>
#include <iostream>
#include <time.h>
using namespace std;
bool ok( int A[4][4], int r, int c, int k )
{
for (int i = 0; (i < c); i++)
if ( A[r][i] == k )
return false;
for (int i = 0; (i < r); i++)
if ( A[i][c] == k )
return false;
return true;
}
bool fill( int A[4][4], int r, int c )
{
int x = rand() % 4;
for ( int i=x; i<x+4; ++i )
{
int k = (i%4)+1;
if ( ok( A, r, c, k ) )
{
A[r][c] = k;
if ( c<3 )
{
if ( fill( A, r, c+1 ) )
return true;
}
else if ( r<3 )
{
if ( fill( A, r+1, 0 ) )
return true;
}
else
return true;
}
}
return false;
}
int main ()
{
int A[4][4];
srand (time(NULL) );
fill(A,0,0);
for (int r=0; r<4; ++r)
{
for (int c=0; c<4; ++c)
{
cout << A[r][c] << " ";
}
cout << endl;
}
return 0;
}
The ok(A, r, C, k) function checks the constraint: Whether it is OK based on previous choices to place value k at position A[r][c]. It checks both the portion of row r to the left of c and the portion of column c above r.
The fill(A, r, c) function is the heart of the program. It assumes that all rows above r have already been filled and all columns of row r to the left of c have already been filled. Then it tries to fill the rest of the matrix recursively. If it succeeds it returns true. If it fails it returns false. A return of false implies some earlier guess made the solution impossible.
fill() selects a random starting guess, then tries each of the four possibilities from that starting guess (if it tries 3 first, it will try 4, 1, and 2 in that sequence next). For each guess, if it can place that value, it does so and then recursively tests to see if the whole rest of the solution is possible after placing that value. If so, it can return true. If not, it continues to the next guess. If all four guesses fail, it returns false indicating some outer layer in the recursion must change its guess.
main() should be obvious.
It should also be obvious how to use the recursive guess and check structure for a wide range of different problems.
If you have a much better understanding of the subtleties of the specific problem, you can find a much less "brute force" program, possibly something less far removed from your original. Sometimes as a programmer, you just need to be good at programming and solve the problem as I did here, without trying for any insight into the problem. Other times, you need to also be a topic expert. In this case that would mean understanding why certain guesses paint you into a corner such that no answer is valid for the rest. Then find a way to get a solution reliably without back tracking. In this particular problem, I don't think much of a lesson would be learned by understanding the problem better. "Brute force" is a better lesson to learn this time.
In this problem, the entire search space is four to the sixteenth power, which means it would take only a few seconds to search the entire space. But there are many solutions and it stops when it finds one, which cuts the search time to a fraction, and at each level of the recursion most of the bad choices can be detected without going deeper, which combinatorialy cuts out almost all of the search space. So the actual "brute force" search turns out to be pretty trivial.
