Solved

How to calculate this math problem?

Posted on 2000-02-18
8
342 Views
Last Modified: 2010-04-15
/*--------------------------------
  |     |  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?


0
Comment
Question by:shiqi
8 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 2537516
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
 

Expert Comment

by:Arvindtn
ID: 2537873
Is the total 30, hardcode ?
0
 

Author Comment

by:shiqi
ID: 2541318
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
 
LVL 18

Expert Comment

by:deighton
ID: 2542051
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
Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

 
LVL 18

Expert Comment

by:deighton
ID: 2542439
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
 
LVL 18

Expert Comment

by:deighton
ID: 2542569
deighton changed the proposed answer to a comment
0
 
LVL 18

Accepted Solution

by:
deighton earned 80 total points
ID: 2542573
#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
 

Author Comment

by:shiqi
ID: 2553598
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

Featured Post

New My Cloud Pro Series - organize everything!

With space to keep virtually everything, the My Cloud Pro Series offers your team the network storage to edit, save and share production files from anywhere with an internet connection. Compatible with both Mac and PC, you're able to protect your content regardless of OS.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
c language help - file paths 7 141
Macro will not compile after project converted from IAR to Microchip xc8 (in MPLab) 3 176
Adjust Mfcapp 29 160
Grammars for C C++ and java 1 114
Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

863 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now