• C

How to calculate this math problem?

/*--------------------------------
  |     |  7  |      |     |     |  4  |
  |     |      |      |     |     |      |
  |-------------------------------|
  |     |      |  1  |     |     |      |
  |     |      |      |     |     |      |
  |-------------------------------|
  |     |      |      |     |     |  8  |
  |     |      |      |     |     |      |
  |---------------+---------------|
  |  5  |     |      |  6  |     |     |
  |      |     |      |     |      |     |
  |-------------------------------|
  |      |     |     |      |     |     |
  |      |     |     |      |     |     |
  |-------------------------------|
  |  9  |     |  2  |      |  3  |     |
  |      |     |      |      |     |     |
  |-------------------------------|

All empty boxes can be filled with digits from 1-9 and the sum of
each row or column equals to 30. In addition, each number
 from 1-9 can only be used 4 times including those that
 have already been put in place to start you off      */

If using a two-demensional array x[7][7] to express this 6x6 box,
then one of  the known facts is as below,
      x[1][2]=7;
      x[1][6]=4;
      x[2][3]=1;
      x[3][6]=8;
      x[4][1]=5;
      x[4][4]=6;
      x[6][1]=9;
      x[6][3]=2;
      x[6][5]=3

But I found it very difficult to caculate. The number of possibilities is
about 10**36 !!! Is there any better way to solve this problem?


shiqiAsked:
Who is Participating?
 
deightonprogCommented:
#include<stdio.h>                                

                   main()
                   {

                   int digits[10],c[10],babort,row1,row2,row3,col1,col2,col3;
                   int i,a1,a2,a3,a4,a5,a6,a7,a8,a9;
                   int sq[37],q,q1,q2;

                   for(a1=1;a1<10;a1++)
                   {
                   for(a2=7;a2<=7;a2++)
                   {
                   for(a3=1;a3<10;a3++)
                   {
                   for(a4=1;a4<10;a4++)
                   {
                   for(a5=1;a5<10;a5++)
                   {
                   for(a6=1;a6<=1;a6++)
                   {
                   for(a7=1;a7<10;a7++)
                   {
                   for(a8=3;a8<=3;a8++)
                   {
                   for(a9=1;a9<10;a9++)
                   {

                   digits[1] = a1;
                   digits[2] = a2;
                   digits[3] = a3;
                   digits[4] = a4;
                   digits[5] = a5;
                   digits[6] = a6;
                   digits[7] = a7;
                   digits[8] = a8;
                   digits[9] = a9;

                   for(i=1;i<10;i++)
                      c[i] = 0;

                   babort = 0;

                   for(i=1;i<10;i++)
                   {
                      ++c[digits[i]];
                      if (c[digits[i]] == 2)
                      {
                   babort = 1;
                   break;
                      }
                   }

                   if (babort == 0)
                   {
                      row1 = digits[1] + digits[2] + digits[3];
                      row2 = digits[4] + digits[5] + digits[6];
                      row3 = digits[7] + digits[8] + digits[9];
                      col1 = digits[1] + digits[4] + digits[7];
                      col2 = digits[2] + digits[5] + digits[8];
                      col3 = digits[3] + digits[6] + digits[9];

                      if (row1 == 15 && row2 == 15 && row3 == 15
                       && col1 == 15 && col2 == 15 && col3 == 15)
                      {

                   for(q1=0;q1<3;q1++){
                   for(q2=0;q2<3;q2++){
                        sq[q2*6 + q1 + 1] = digits[q2*3+q1+1];
                   }}

                      }

                   }





                   }}}}}}}}}


                   for(a1=1;a1<10;a1++)
                   {
                   for(a2=1;a2<10;a2++)
                   {
                   for(a3=4;a3<=4;a3++)
                   {
                   for(a4=1;a4<10;a4++)
                   {
                   for(a5=1;a5<10;a5++)
                   {
                   for(a6=1;a6<10;a6++)
                   {
                   for(a7=1;a7<10;a7++)
                   {
                   for(a8=1;a8<10;a8++)
                   {
                   for(a9=8;a9<=8;a9++)
                   {

                   digits[1] = a1;
                   digits[2] = a2;
                   digits[3] = a3;
                   digits[4] = a4;
                   digits[5] = a5;
                   digits[6] = a6;
                   digits[7] = a7;
                   digits[8] = a8;
                   digits[9] = a9;

                   for(i=1;i<10;i++)
                      c[i] = 0;

                   babort = 0;

                   for(i=1;i<10;i++)
                   {
                      ++c[digits[i]];
                      if (c[digits[i]] == 2)
                      {
                   babort = 1;
                   break;
                      }
                   }

                   if (babort == 0)
                   {
                      row1 = digits[1] + digits[2] + digits[3];
                      row2 = digits[4] + digits[5] + digits[6];
                      row3 = digits[7] + digits[8] + digits[9];
                      col1 = digits[1] + digits[4] + digits[7];
                      col2 = digits[2] + digits[5] + digits[8];
                      col3 = digits[3] + digits[6] + digits[9];

                      if (row1 == 15 && row2 == 15 && row3 == 15
                       && col1 == 15 && col2 == 15 && col3 == 15)
                      {
                   for (q = 1; q<10;q++)
                       sq[((q-1) / 3) * 6 + (q-1) % 3 + 4] = digits[q];
                      }

                   }





                   }}}}}}}}}


                   for(a1=5;a1<=5;a1++)
                   {
                   for(a2=1;a2<10;a2++)
                   {
                   for(a3=1;a3<10;a3++)
                   {
                   for(a4=1;a4<10;a4++)
                   {
                   for(a5=1;a5<10;a5++)
                   {
                   for(a6=1;a6<10;a6++)
                   {
                   for(a7=9;a7<=9;a7++)
                   {
                   for(a8=1;a8<10;a8++)
                   {
                   for(a9=2;a9<=2;a9++)
                   {

                   digits[1] = a1;
                   digits[2] = a2;
                   digits[3] = a3;
                   digits[4] = a4;
                   digits[5] = a5;
                   digits[6] = a6;
                   digits[7] = a7;
                   digits[8] = a8;
                   digits[9] = a9;

                   for(i=1;i<10;i++)
                      c[i] = 0;

                   babort = 0;

                   for(i=1;i<10;i++)
                   {
                      ++c[digits[i]];
                      if (c[digits[i]] == 2)
                      {
                   babort = 1;
                   break;
                      }
                   }

                   if (babort == 0)
                   {
                      row1 = digits[1] + digits[2] + digits[3];
                      row2 = digits[4] + digits[5] + digits[6];
                      row3 = digits[7] + digits[8] + digits[9];
                      col1 = digits[1] + digits[4] + digits[7];
                      col2 = digits[2] + digits[5] + digits[8];
                      col3 = digits[3] + digits[6] + digits[9];

                      if (row1 == 15 && row2 == 15 && row3 == 15
                       && col1 == 15 && col2 == 15 && col3 == 15)
                      {
                   for (q = 1; q<10;q++)
                       sq[((q-1) / 3 +3) * 6 + (q-1) % 3 + 1] = digits[q];
                      }

                   }





                   }}}}}}}}}

                   for(a1=6;a1<=6;a1++)
                   {
                   for(a2=1;a2<10;a2++)
                   {
                   for(a3=1;a3<10;a3++)
                   {
                   for(a4=1;a4<10;a4++)
                   {
                   for(a5=1;a5<10;a5++)
                   {
                   for(a6=1;a6<10;a6++)
                   {
                   for(a7=1;a7<10;a7++)
                   {
                   for(a8=3;a8<=3;a8++)
                   {
                   for(a9=1;a9<10;a9++)
                   {

                   digits[1] = a1;
                   digits[2] = a2;
                   digits[3] = a3;
                   digits[4] = a4;
                   digits[5] = a5;
                   digits[6] = a6;
                   digits[7] = a7;
                   digits[8] = a8;
                   digits[9] = a9;

                   for(i=1;i<10;i++)
                      c[i] = 0;

                   babort = 0;

                   for(i=1;i<10;i++)
                   {
                      ++c[digits[i]];
                      if (c[digits[i]] == 2)
                      {
                   babort = 1;
                   break;
                      }
                   }

                   if (babort == 0)
                   {
                      row1 = digits[1] + digits[2] + digits[3];
                      row2 = digits[4] + digits[5] + digits[6];
                      row3 = digits[7] + digits[8] + digits[9];
                      col1 = digits[1] + digits[4] + digits[7];
                      col2 = digits[2] + digits[5] + digits[8];
                      col3 = digits[3] + digits[6] + digits[9];

                      if (row1 == 15 && row2 == 15 && row3 == 15
                       && col1 == 15 && col2 == 15 && col3 == 15)
                      {
                       for(q1=0;q1<3;q1++){
                          for(q2=0;q2<3;q2++){
                         sq[q2*6 + q1 + 18+4] = digits[q2*3+q1+1];
                   }}

                      }

                   }





                   }}}}}}}}}

                   for (i=0;i<6;i++)
                   {
                   printf("\n");
                   for (q=0;q<6;q++){
                   printf("%i ",sq[i*6+q+1]);
                   }}



                   getch();
                   }



0
 
ozoCommented:
I count more like 10**21 possibilities. which a simple backtracking search should prune easily enough.
Why not post your code?
(you might even add more constraints, like getting a 15 sum in each quadrant, and solve it by hand)
0
 
ArvindtnCommented:
Is the total 30, hardcode ?
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
shiqiAuthor Commented:
The total possiblities is more like 36  nines time together, that is 9**36 , which is nearly equivelent to 10**36.  
I doubt it may take a very long time to calculate this problem.  Is there better
solution.

As for 30,  the sum of each row elements.    Sorry to cause confusion.
Let me explain other given facts.
The sum of all numbers in each column or
 row equals to 30. This applys to every column and row. That means,
for (i=1;i<=6;i++){
sum=0;
for (j=1;j<=6;j++) sum=sum+x[i][j];
if(sum!=30){printf("This does not match!\n"); exit}
else
   printf("Matched 30 for row %d\n",i);
}
for(j=1;j<=6;j++){
sum=0;
for(i=1;i<=6;i++)sum=sum+x[i][j];
if(sum!=30){printf("This does match!\n"); exit}
else
   printf("Matched 30 for column %d\n",j);
}
0
 
deightonprogCommented:
2 7 6 2 9 4
9 5 1 7 5 3
4 3 8 6 1 8
5 3 7 6 7 2
1 8 6 1 5 9
9 4 2 8 3 4
0
 
deightonprogCommented:
Here's code in .c rather than VB which I solved it in

#include<stdio.h>                                

main()
{

int digits[10],c[10],babort,row1,row2,row3,col1,col2,col3;
int i,a1,a2,a3,a4,a5,a6,a7,a8,a9;
int sq[37],q,q1,q2;

for(a1=1;a1<10;a1++)
{
for(a2=7;a2<=7;a2++)
{
for(a3=1;a3<10;a3++)
{
for(a4=1;a4<10;a4++)
{
for(a5=1;a5<10;a5++)
{
for(a6=1;a6<=1;a6++)
{
for(a7=1;a7<10;a7++)
{
for(a8=3;a8<=3;a8++)
{
for(a9=1;a9<10;a9++)
{

      digits[1] = a1;
      digits[2] = a2;
      digits[3] = a3;
      digits[4] = a4;
      digits[5] = a5;
      digits[6] = a6;
      digits[7] = a7;
      digits[8] = a8;
      digits[9] = a9;

      for(i=1;i<10;i++)
         c[i] = 0;

      babort = 0;

      for(i=1;i<10;i++)
      {
         ++c[digits[i]];
         if (c[digits[i]] == 2)
         {
            babort = 1;
            break;
         }
      }

      if (babort == 0)
      {
         row1 = digits[1] + digits[2] + digits[3];
         row2 = digits[4] + digits[5] + digits[6];
         row3 = digits[7] + digits[8] + digits[9];
         col1 = digits[1] + digits[4] + digits[7];
         col2 = digits[2] + digits[5] + digits[8];
         col3 = digits[3] + digits[6] + digits[9];

         if (row1 == 15 && row2 == 15 && row3 == 15
          && col1 == 15 && col2 == 15 && col3 == 15)
         {

             for(q1=0;q1<3;q1++){
             for(q2=0;q2<3;q2++){
                 sq[q2*6 + q1 + 1] = digits[q2*3+q1+1];
             }}

         }

      }





}}}}}}}}}


for(a1=1;a1<10;a1++)
{
for(a2=1;a2<10;a2++)
{
for(a3=4;a3<=4;a3++)
{
for(a4=1;a4<10;a4++)
{
for(a5=1;a5<10;a5++)
{
for(a6=1;a6<10;a6++)
{
for(a7=1;a7<10;a7++)
{
for(a8=1;a8<10;a8++)
{
for(a9=8;a9<=8;a9++)
{

      digits[1] = a1;
      digits[2] = a2;
      digits[3] = a3;
      digits[4] = a4;
      digits[5] = a5;
      digits[6] = a6;
      digits[7] = a7;
      digits[8] = a8;
      digits[9] = a9;

      for(i=1;i<10;i++)
         c[i] = 0;

      babort = 0;

      for(i=1;i<10;i++)
      {
         ++c[digits[i]];
         if (c[digits[i]] == 2)
         {
            babort = 1;
            break;
         }
      }

      if (babort == 0)
      {
         row1 = digits[1] + digits[2] + digits[3];
         row2 = digits[4] + digits[5] + digits[6];
         row3 = digits[7] + digits[8] + digits[9];
         col1 = digits[1] + digits[4] + digits[7];
         col2 = digits[2] + digits[5] + digits[8];
         col3 = digits[3] + digits[6] + digits[9];

         if (row1 == 15 && row2 == 15 && row3 == 15
          && col1 == 15 && col2 == 15 && col3 == 15)
         {
             for (q = 1; q<10;q++)
                sq[((q-1) / 3) * 6 + (q-1) % 3 + 4] = digits[q];
         }

      }





}}}}}}}}}


for(a1=5;a1<=5;a1++)
{
for(a2=1;a2<10;a2++)
{
for(a3=1;a3<10;a3++)
{
for(a4=1;a4<10;a4++)
{
for(a5=1;a5<10;a5++)
{
for(a6=1;a6<10;a6++)
{
for(a7=9;a7<=9;a7++)
{
for(a8=1;a8<10;a8++)
{
for(a9=2;a9<=2;a9++)
{

      digits[1] = a1;
      digits[2] = a2;
      digits[3] = a3;
      digits[4] = a4;
      digits[5] = a5;
      digits[6] = a6;
      digits[7] = a7;
      digits[8] = a8;
      digits[9] = a9;

      for(i=1;i<10;i++)
         c[i] = 0;

      babort = 0;

      for(i=1;i<10;i++)
      {
         ++c[digits[i]];
         if (c[digits[i]] == 2)
         {
            babort = 1;
            break;
         }
      }

      if (babort == 0)
      {
         row1 = digits[1] + digits[2] + digits[3];
         row2 = digits[4] + digits[5] + digits[6];
         row3 = digits[7] + digits[8] + digits[9];
         col1 = digits[1] + digits[4] + digits[7];
         col2 = digits[2] + digits[5] + digits[8];
         col3 = digits[3] + digits[6] + digits[9];

         if (row1 == 15 && row2 == 15 && row3 == 15
          && col1 == 15 && col2 == 15 && col3 == 15)
         {
             for (q = 1; q<10;q++)
                sq[((q-1) / 3 +3) * 6 + (q-1) % 3 + 1] = digits[q];
         }

      }





}}}}}}}}}

for(a1=6;a1<=6;a1++)
{
for(a2=1;a2<10;a2++)
{
for(a3=1;a3<10;a3++)
{
for(a4=1;a4<10;a4++)
{
for(a5=1;a5<10;a5++)
{
for(a6=1;a6<10;a6++)
{
for(a7=1;a7<10;a7++)
{
for(a8=3;a8<=3;a8++)
{
for(a9=1;a9<10;a9++)
{

      digits[1] = a1;
      digits[2] = a2;
      digits[3] = a3;
      digits[4] = a4;
      digits[5] = a5;
      digits[6] = a6;
      digits[7] = a7;
      digits[8] = a8;
      digits[9] = a9;

      for(i=1;i<10;i++)
         c[i] = 0;

      babort = 0;

      for(i=1;i<10;i++)
      {
         ++c[digits[i]];
         if (c[digits[i]] == 2)
         {
            babort = 1;
            break;
         }
      }

      if (babort == 0)
      {
         row1 = digits[1] + digits[2] + digits[3];
         row2 = digits[4] + digits[5] + digits[6];
         row3 = digits[7] + digits[8] + digits[9];
         col1 = digits[1] + digits[4] + digits[7];
         col2 = digits[2] + digits[5] + digits[8];
         col3 = digits[3] + digits[6] + digits[9];

         if (row1 == 15 && row2 == 15 && row3 == 15
          && col1 == 15 && col2 == 15 && col3 == 15)
         {
                for(q1=0;q1<3;q1++){
                   for(q2=0;q2<3;q2++){
                        sq[q2*6 + q1 + 18+4] = digits[q2*3+q1+1];
                         }}

         }

      }





}}}}}}}}}

for (i=0;i<6;i++)
{
printf("\n");
for (q=0;q<6;q++){
printf("%i ",sq[i*6+q+1]);
}}



getch();
}
0
 
deightonprogCommented:
deighton changed the proposed answer to a comment
0
 
shiqiAuthor Commented:
Are you adopting an algorithm to break 6x6 matrix into four separated
3x3 matrix and  making an assumption that  the sum of each row element and the sum of each column element must equal 15 within each smaller matrix?   Will this lose some other possibilities?   I ran you program and
 only got one choice.   Is there only one answer for this question?   Are there any other alternatives to solve this problem?
   Can you explain your program in detail?



 
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.