数学研发论坛

 找回密码
 欢迎注册
楼主: 0→∞

[求助] 果树问题讨论:这两个问题等价么?

  [复制链接]
发表于 2008-8-21 09:59:19 | 显示全部楼层
Now let's summarize the progress on orchard planting problem with 4 trees per row.
And the latest version of C++ code used to solve the problem is provided in the next two posts: 102# and 103#
We know that optimal packing of $K_4$'s into a $K_n$ is an upbound for the
orchard planting problem, and $u(n)=[{[{n-1}/3]n}/4]$ is upbound for both of the two problems.
First, A C++ program is written to try to enumerate all non-equivalent method to packing at least u(n)-"MAX_FREEDOM" $K_4$ into $K_n$
in attachment file at 11#, the result for $12<=n<=14$ with MAX_FREEDOM=3 is first privided.
Next in 33#, the result for n=11 with 6 rows is transformed into equations and WxMaxima used to solve the correspondent equations.
We could find a solution for planting 6 rows with total 11 trees (4 trees per row) . Also WxMaxima helped to verify that for n=12, we could plant 6 rows of trees; but we could not plant 8 rows of trees.
But WxMaxima complains that those equations for 7 rows are too complex so that it gives up.
In 38# I found that if we project one row of trees into line at infinity (so that there'll be four infinity points and four groups of parallel straight lines in the result), it could greatly reduce the complexity of the equations.
We could even manually solve all those equations for n=13 with at least 11 rows trees.
With the help of WxMaxima, it is proved that we could plant at most 9 rows of trees (4 trees per row) when there're total 13 trees in 42#
And at the sametime, we could find a solution to plant total 13 trees in 9 rows. (It is used to check the correctness of the C++ code used to find all method to packing $K_4$ into $K_n$ too).
After projecting one rows of trees into infinity line and select another two lines as axises in the affine plane, the equations are 2 order multivariate polynomial (each variable is x or y coordinate of a tree)
And we could know in advance that all of those variables are non-zero since the coordinate of all trees in X or Y axises is known in advance and they're not used as variables in the equations.
So if we could find a linear combination of those equations and each non-zero term of the linear combination contains a given variable, we could divide the given variable from the linear combination to form a linear relationship among those variables.
In 51# an algorithm is designed to use the idea to simplify/prove no solution/solve those nonlinear equations [But it may fail in some times].
and in 82# it is used to prove that we could plant at most 9 rows with 13 trees and at most 10 rows with 14 trees.
And in 83# an example to plant10 rows with 14 trees is found by the program (used to verify correctness of the code).
And in 84# it is proved that we could plant at most 12 rows with 15 trees.

In 67# the C++ source code to enumerate all non-equivalent method to pack at leat u(n)-"MAX_FREEDOM" $K_4$ into $K_n$ is attached.
A C++ template class node_edge_set is defined to generate a unique representation for a method to pack $K_4$ into $K_n$:
    i)First we will classify all nodes in the graph into mulitiple groups according degrees of the node and attach all those nodes with the correspondent group id (in the ascedent order of degrees)
    ii)We could classify all those $K_4$ in the graph according to the group id of nodes in the $K_4$ and sorting those groups by lexicographic ordering of group id's in the $K_4$
    iii)We could classify all nodes in the graph by group id of $K_4$ using the node and sorting those gropus by lexicographic ordering of group id of $K_4$ too
    iv) repeat step ii) and iii) until the number of groups remains unchanged.
    v) If the multiple nodes are assign with same group id, select a group with mulitple nodes (heristic method to select the one with minimal group id)
          for each node in the group, attach a special feature to the node(let the node uses a unique group id) and repeat step iii)-V) until each node is assigned with a unique group id.
          For each choice of the node, we could result in a representation of the packing $K_4$ into $K_n$ configuration. (Each node is represented by the group id)
          Select the one which is minimal in lexicographic ordering as the unique representation of the method to packing $K_4$ into $K_n$.

The C++ program could search for the problem up to15 trees. But it will fail when there're more trees because a temp file generated by the program will be more than 2G.
In 93# the program is improved so that it will use multiple files to keep those temp data.
and in 96# the program is successfully generate all method to pack at least 16 $K_4$ into $K_16$. (And it will generate temp files up to 10G)
and the C++ equation simplifer(the 2nd program) proved that none of them could form a correspondent solution to plant no less than 16 rows with 16 trees.
So we have proved that we could plant at most 15 rows with 16 trees. According to the result in wolfram, we could result in that
the 13 to 16 items of A006065 are 9,10,12,15.

A bug in source found at Ot 23, 2008. After the bug fix, the new code verified that the items 13 to 16 remains unchanged.
In 167#, a result of planting 15 trees in 12 rows provided.
In 171#and 172#, 2 result of planting 16 trees in 15 rows provided. And the coordinates of another two solutions are provided. And all solutions for planting 16 treesin 15 rows are here if result under projection is treated as same result.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 10:00:53 | 显示全部楼层
The C++ source code to enumerate all non-equivalent method to packing at least u(n)-"MAX_FREEDOM" $K_4$ into $K_n$
Changing macro NUM_NODES to other value to search result for differrent 'n'.
Make sure you have enough free hard disk space to run the code with larger n or MAX_FREEDOM.
I have only tested the code with NODES_PER_EDGE equal to 4.

  1. #include <time.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <sys/stat.h>
  6. #include <sys/types.h>
  7. #include <dirent.h>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <set>
  11. using namespace std;
  12. template <int TNODES,int NODES_PER_EDGE=4>
  13. class node_edge_set{
  14.     public:
  15.         static const int max_edges_per_node = (TNODES-1)/(NODES_PER_EDGE-1);
  16.         static const int max_total_edges = (((TNODES-1)/(NODES_PER_EDGE-1))*TNODES)/NODES_PER_EDGE;
  17.         struct final_edge_set{
  18.             static int num_edges;
  19.             char edges[max_total_edges][NODES_PER_EDGE];
  20.             static void set_curr_num_edges(int n){num_edges=n;}
  21.             bool operator<(const final_edge_set& s)const{
  22.                 int i,j;
  23.                 for(i=0;i<num_edges;i++)for(j=0;j<NODES_PER_EDGE;j++){
  24.                     if(edges[i][j]<s.edges[i][j])return true;
  25.                     if(edges[i][j]>s.edges[i][j])return false;
  26.                 }
  27.                 return false;
  28.             }
  29.             bool operator==(const final_edge_set& s)const{
  30.                 int i,j;
  31.                 for(i=0;i<num_edges;i++)for(j=0;j<NODES_PER_EDGE;j++){
  32.                     if(edges[i][j]!=s.edges[i][j])return false;
  33.                 }
  34.                 return true;
  35.             }
  36.             void show()const{
  37.                 int i,j;
  38.                 for(i=0;i<num_edges;i++){
  39.                     for(j=0;j<NODES_PER_EDGE;j++){
  40.                         printf("%c",'A'+edges[i][j]);
  41.                     }
  42.                     printf(" ");
  43.                 }
  44.                 printf("\n");
  45.             }
  46.             void show(char *outbuf)const{
  47.                 int i,j;
  48.                 for(i=0;i<num_edges;i++){
  49.                     for(j=0;j<NODES_PER_EDGE;j++){
  50.                         outbuf[i*NODES_PER_EDGE+j]='A'+edges[i][j];
  51.                     }
  52.                 }
  53.                 outbuf[i*NODES_PER_EDGE]='\0';
  54.             }
  55.             void show(int step_id)const{
  56.                 char tname[100];
  57.                 char obuf[1000];
  58.                 char tbuf[1000];
  59.                 int i,j;
  60.                 int checksum=0;
  61.                 for(i=0;i<num_edges;i++)for(j=0;j<NODES_PER_EDGE;j++){
  62.                     checksum+=edges[i][j]*(i+1);
  63.                 }
  64.                 sprintf(tname,"data/t%d/%d",step_id,checksum);
  65.                 FILE *pOutput=fopen(tname,"a+");
  66.                 if(pOutput==NULL){
  67.                     fprintf(stderr,"Cannot write to file %s\n",tname);
  68.                     exit(-1);
  69.                 }
  70.                 for(i=0;i<num_edges;i++){
  71.                     for(j=0;j<NODES_PER_EDGE;j++){
  72.                         tbuf[i*NODES_PER_EDGE+j]='A'+edges[i][j];
  73.                     }
  74.                 }
  75.                 tbuf[(num_edges)*NODES_PER_EDGE]='\n';
  76.                 tbuf[(num_edges)*NODES_PER_EDGE+1]='\0';
  77.                 if(fseek(pOutput,-(num_edges*NODES_PER_EDGE+2),SEEK_END)==0){
  78.                     fread(obuf,num_edges*NODES_PER_EDGE+2,1,pOutput);
  79.                     if(obuf[0]=='\n'&&strncmp(obuf+1,tbuf,(num_edges-2)*NODES_PER_EDGE)==0){
  80.                         fclose(pOutput);
  81.                         return;
  82.                     }
  83.                 }else if(fseek(pOutput,0,SEEK_SET)==0){
  84.                     fread(obuf,num_edges*NODES_PER_EDGE+1,1,pOutput);
  85.                     if(strncmp(obuf,tbuf,num_edges*NODES_PER_EDGE+1)==0){
  86.                         fclose(pOutput);
  87.                         return;
  88.                     }
  89.                 }
  90.                 fseek(pOutput,0,SEEK_END);
  91.                 fwrite(tbuf,num_edges*NODES_PER_EDGE+1,1,pOutput);
  92.                 fclose(pOutput);
  93.             }
  94.             void show(FILE *pFile)const{
  95.                 int i,j;
  96.                 for(i=0;i<num_edges;i++){
  97.                     for(j=0;j<NODES_PER_EDGE;j++){
  98.                         fprintf(pFile,"%c",'A'+edges[i][j]);
  99.                     }
  100.                 }
  101.                 fprintf(pFile,"\n");
  102.             }
  103.         };
  104.         struct node_group_type{
  105.             char groupid;
  106.             char group_counter;
  107.             char tedges;
  108.             char eids[max_edges_per_node];
  109.             bool operator<(const node_group_type& n)const{
  110.                 int i;
  111.                 if(tedges<n.tedges)return true;
  112.                 if(tedges>n.tedges)return false;
  113.                 for(i=0;i<tedges;i++){
  114.                     if(eids[i]<n.eids[i])return true;
  115.                     if(eids[i]>n.eids[i])return false;
  116.                 }
  117.                 return false;
  118.             }
  119.             bool operator==(const node_group_type& n)const{
  120.                 int i;
  121.                 if(tedges<n.tedges)return false;
  122.                 if(tedges>n.tedges)return false;
  123.                 for(i=0;i<tedges;i++){
  124.                     if(eids[i]<n.eids[i])return false;
  125.                     if(eids[i]>n.eids[i])return false;
  126.                 }
  127.                 return true;
  128.             }
  129.             void show()const{
  130.                 int i;
  131.                 printf("%d*{ ",group_counter);
  132.                 if(eids[0]==-1){
  133.                     printf("D=%d ",tedges);
  134.                 }else{
  135.                     for(i=0;i<tedges;i++){
  136.                         printf("%d ",eids[i]);
  137.                     }
  138.                 }
  139.                 printf("}");
  140.             }
  141.         };
  142.         struct edge_group_type{
  143.             char groupid;
  144.             char group_counter;
  145.             char nids[NODES_PER_EDGE];
  146.             bool operator<(const edge_group_type& e)const{
  147.                 int i;
  148.                 for(i=0;i<NODES_PER_EDGE;i++){
  149.                     if(nids[i]<e.nids[i])return true;
  150.                     if(nids[i]>e.nids[i])return false;
  151.                 }
  152.                 return false;
  153.             }
  154.             bool operator==(const edge_group_type& e)const{
  155.                 int i;
  156.                 for(i=0;i<NODES_PER_EDGE;i++){
  157.                     if(nids[i]<e.nids[i])return false;
  158.                     if(nids[i]>e.nids[i])return false;
  159.                 }
  160.                 return true;
  161.             }
  162.             void show()const{
  163.                 int i;
  164.                 printf("%d*{ ",group_counter);
  165.                 for(i=0;i<NODES_PER_EDGE;i++)printf("%d ",nids[i]);
  166.                 printf("}");
  167.             }
  168.         };
  169.     private:
  170.         int  num_of_edges;///Number of total edges. The number of total nodes is TNODES
  171.         char edges_info[max_total_edges][NODES_PER_EDGE];///nodes in each edge.
  172.         char nodes_info[TNODES][max_edges_per_node];///edges in each node
  173.         char nodes_degree[TNODES];///number of edges in each node
  174.         class group_infos{
  175.             private:
  176.                 int  edge_groups_count;///number of edge groups
  177.                 int  node_groups_count;///number of node groups
  178.                 node_group_type node_groups[TNODES];///the info of each group of node
  179.                 edge_group_type edge_groups[max_total_edges];///the info of each group of edge
  180.                 char node_group_id[TNODES];///The node group id of a node
  181.                 char edge_group_id[max_total_edges];///The edge group id of an edge
  182.                 node_edge_set *node_edges;
  183.             public:
  184.                 void show_edges()const{
  185.                     int i;
  186.                     for(i=0;i<edge_groups_count;i++){
  187.                         edge_groups[i].show();
  188.                     }
  189.                     printf("\n");
  190.                     printf("id:{ ");
  191.                     for(i=0;i<node_edges->num_of_edges;i++){
  192.                         printf("%d ",edge_group_id[i]);
  193.                     }
  194.                     printf("}\n");
  195.                 }
  196.                 bool simple_case(int node_id)const{
  197.                      int i,j;
  198.                     if(node_edges->nodes_degree[node_id]==0)
  199.                         return true;
  200.                     if(node_edges->nodes_degree[node_id]>1)
  201.                         return false;
  202.                     int ngid=node_group_id[node_id];
  203.                     int e=node_edges->nodes_info[node_id][0];
  204.                     for(j=0;j<NODES_PER_EDGE;j++){
  205.                         int n=node_edges->edges_info[e][j];
  206.                         if(node_group_id[n]==ngid)continue;
  207.                         if(node_groups[node_group_id[n]].group_counter>1)
  208.                             break;
  209.                     }
  210.                     return j==NODES_PER_EDGE;
  211.                 }
  212.                 void show_nodes()const{
  213.                     int i;
  214.                     for(i=0;i<node_groups_count;i++){
  215.                         node_groups[i].show();
  216.                     }
  217.                     printf("\n");
  218.                     printf("id:{ ");
  219.                     for(i=0;i<TNODES;i++){
  220.                         printf("%d ",node_group_id[i]);
  221.                     }
  222.                     printf("}\n");
  223.                 }
  224.                 group_infos(node_edge_set *ne):node_edges(ne){}
  225.                 group_infos(const group_infos& g){
  226.                     int i;
  227.                     node_edges=g.node_edges;
  228.                     edge_groups_count=g.edge_groups_count;
  229.                     node_groups_count=g.node_groups_count;
  230.                     for(i=0;i<node_groups_count;i++)node_groups[i]=g.node_groups[i];
  231.                     for(i=0;i<edge_groups_count;i++)edge_groups[i]=g.edge_groups[i];
  232.                     for(i=0;i<TNODES;i++)node_group_id[i]=g.node_group_id[i];
  233.                     for(i=0;i<node_edges->num_of_edges;i++)edge_group_id[i]=g.edge_group_id[i];
  234.                 }
  235.                 int get_edge_groups_count()const{return edge_groups_count;}
  236.                 int get_node_groups_count()const{return node_groups_count;}
  237.                 int get_node_group_id(int nid)const{
  238.                     return node_group_id[nid];
  239.                 }
  240.                 int get_edge_group_id(int eid)const{
  241.                     return edge_group_id[eid];
  242.                 }
  243.                 int get_edge_group_counter(int gid)const{
  244.                     return edge_groups[gid].group_counter;
  245.                 }
  246.                 void assign_node_edge_id(char new_node_id[TNODES], int& next_node_id){
  247.                     int i;
  248.                     for(i=0;i<TNODES;i++){
  249.                         if(new_node_id[i]==-1){
  250.                             if(node_groups[node_group_id[i]].group_counter==1){
  251.                                 new_node_id[i]=next_node_id++;
  252.                             }
  253.                         }
  254.                     }
  255.                 }
  256.                 int undetermined_node_group()const{
  257.                     int i;
  258.                     int smaller=TNODES+1;
  259.                     int si=-1;
  260.                     for(i=0;i<node_groups_count;i++){
  261.                         if(node_groups[i].tedges>0&&node_groups[i].group_counter>1){
  262.                             if(node_groups[i].group_counter<smaller){
  263.                                 smaller-node_groups[i].group_counter;
  264.                                 si=i;
  265.                             }
  266.                         }
  267.                     }
  268.                     return si;
  269.                 }
  270.             private:
  271.                 void sort_node_group()///sort node_groups
  272.                 {
  273.                     int i;
  274.                     char tmp2[TNODES];
  275.                     for(i=0;i<node_groups_count;i++)node_groups[i].groupid=i;
  276.                     sort(&node_groups[0],&node_groups[node_groups_count]);
  277.                     for(i=0;i<node_groups_count;i++)tmp2[node_groups[i].groupid]=i;
  278.                     for(i=0;i<TNODES;i++)node_group_id[i]=tmp2[node_group_id[i]];
  279.                 }
  280.                 void sort_edge_group()///sort edge_groups
  281.                 {
  282.                     int i;
  283.                     char tmp2[max_total_edges];
  284.                     for(i=0;i<edge_groups_count;i++)edge_groups[i].groupid=i;
  285.                     sort(&edge_groups[0],&edge_groups[edge_groups_count]);
  286.                     for(i=0;i<edge_groups_count;i++)tmp2[edge_groups[i].groupid]=i;
  287.                     for(i=0;i<node_edges->num_of_edges;i++)edge_group_id[i]=tmp2[edge_group_id[i]];
  288.                 }
  289.                 void set_edge_group()///reset edge group according to node group
  290.                 {
  291.                     int i,j;
  292.                     edge_groups_count=0;
  293.                     for(i=0;i<node_edges->num_of_edges;i++){
  294.                         edge_group_type eg;
  295.                         for(j=0;j<NODES_PER_EDGE;j++){
  296.                             eg.nids[j]=node_group_id[node_edges->edges_info[i][j]];
  297.                         }
  298.                         sort(&eg.nids[0],&eg.nids[NODES_PER_EDGE]);
  299.                         for(j=0;j<edge_groups_count;j++){
  300.                             if(eg==edge_groups[j])
  301.                                 break;
  302.                         }
  303.                         if(j<edge_groups_count){///Matchs
  304.                             edge_group_id[i]=j;
  305.                             edge_groups[j].group_counter++;
  306.                         }else{
  307.                             edge_groups[edge_groups_count]=eg;
  308.                             edge_groups[edge_groups_count].group_counter=1;
  309.                             edge_group_id[i]=edge_groups_count++;
  310.                         }
  311.                     }
  312.                     sort_edge_group();
  313.                 }
  314.                 void set_node_group()
  315.                 {
  316.                     int i,j;
  317.                     char old_id[TNODES];
  318.                     for(i=0;i<TNODES;i++)old_id[i]=node_group_id[i];
  319.                     node_groups_count=0;
  320.                     for(i=0;i<TNODES;i++){
  321.                         node_group_type ng;
  322.                         ng.tedges=node_edges->nodes_degree[i];
  323.                         for(j=0;j<ng.tedges;j++){
  324.                             ng.eids[j]=edge_group_id[node_edges->nodes_info[i][j]];
  325.                         }
  326.                         sort(&ng.eids[0],&ng.eids[ng.tedges]);
  327.                         for(j=0;j<node_groups_count;j++){
  328.                             if(ng==node_groups[j]&&
  329.                                     old_id[i]==node_groups[j].groupid)break;
  330.                         }
  331.                         if(j<node_groups_count){
  332.                             node_group_id[i]=j;
  333.                             node_groups[j].group_counter++;
  334.                         }else{
  335.                             node_groups[node_groups_count]=ng;
  336.                             node_groups[node_groups_count].group_counter=1;
  337.                             node_groups[node_groups_count].groupid = old_id[i];///save old id
  338.                             node_group_id[i]=node_groups_count++;
  339.                         }
  340.                     }
  341.                     sort_node_group();
  342.                 }
  343.             public:
  344.                 void promote_searched(int searched){
  345.                     int old_node_id[TNODES];
  346.                     int node_id_map[TNODES];
  347.                     int i;
  348.                     if(searched<=0)return;
  349.                     int gcount=0;
  350.                     for(i=0;i<TNODES;i++){
  351.                         old_node_id[i]=node_group_id[i];
  352.                     }
  353.                     sort(&old_node_id[0],&old_node_id[searched]);
  354.                     sort(&old_node_id[searched],&old_node_id[TNODES]);
  355.                     for(i=1;i<TNODES;i++){
  356.                         if(old_node_id[i]!=old_node_id[i-1]){
  357.                             old_node_id[++gcount]=old_node_id[i];
  358.                         }
  359.                     }
  360.                     gcount++;
  361.                     for(i=0;i<gcount;i++){
  362.                         node_id_map[old_node_id[i]]=i;
  363.                     }
  364.                     for(i=0;i<gcount;i++)old_node_id[i]=-1;
  365.                     for(i=0;i<gcount;i++){
  366.                         if(old_node_id[i]==-1){///Order not changed.
  367.                             node_group_type backupn=node_groups[i];
  368.                             int start=i;
  369.                             if(node_id_map[start]!=start){
  370.                                 do{
  371.                                     int next=node_id_map[start];
  372.                                     node_group_type t=node_groups[next];
  373.                                     node_groups[next]=backupn;
  374.                                     old_node_id[start]=1;
  375.                                     backupn=t;
  376.                                     start=next;
  377.                                 }while(start!=i);
  378.                             }
  379.                         }
  380.                     }
  381.                     for(i=0;i<TNODES;i++){
  382.                         node_group_id[i]=node_id_map[node_group_id[i]];
  383.                     }
  384.                     set_edge_group();
  385.                 }
  386.                 void init_group_info(int searched){
  387.                     int i,j;
  388.                     node_groups_count=0;
  389.                     ///first initialize node groups via degrees;
  390. #ifdef OUTPUT
  391.                     printf("start init group info\n");
  392. #endif
  393.                     for(i=0;i<searched;i++){
  394.                         for(j=0;j<node_groups_count;j++){
  395.                             if(node_groups[j].tedges==node_edges->nodes_degree[i])
  396.                                 break;
  397.                         }
  398.                         if(j<node_groups_count){
  399.                             node_group_id[i]=j;
  400.                             node_groups[j].group_counter++;
  401.                         }else{
  402.                             node_groups[node_groups_count].group_counter=1;
  403.                             node_groups[node_groups_count].tedges=node_edges->nodes_degree[i];
  404.                             node_groups[node_groups_count].eids[0]=-1;
  405.                             node_group_id[i]=node_groups_count++;
  406.                         }
  407.                     }
  408.                     int searched_groups=node_groups_count;
  409.                     for(;i<TNODES;i++){
  410.                         for(j=searched_groups;j<node_groups_count;j++){
  411.                             if(node_groups[j].tedges==node_edges->nodes_degree[i])
  412.                                 break;
  413.                         }
  414.                         if(j<node_groups_count){
  415.                             node_group_id[i]=j;
  416.                             node_groups[j].group_counter++;
  417.                         }else{
  418.                             node_groups[node_groups_count].group_counter=1;
  419.                             node_groups[node_groups_count].tedges=node_edges->nodes_degree[i];
  420.                             node_groups[node_groups_count].eids[0]=-1;
  421.                             node_group_id[i]=node_groups_count++;
  422.                         }
  423.                     }
  424.                     sort_node_group();
  425. #ifdef OUTPUT
  426.                     printf("Init node info:\n");
  427.                     show_nodes();
  428. #endif

  429.                     int old_node_group;

  430.                     do{
  431.                         old_node_group=node_groups_count;
  432.                         set_edge_group();
  433. #ifdef OUTPUT
  434.                         printf("edge info:\n");
  435.                         show_edges();
  436. #endif
  437.                         set_node_group();
  438. #ifdef OUTPUT
  439.                         printf("node info:\n");
  440.                         show_nodes();
  441. #endif
  442.                     }while(node_groups_count!=old_node_group);
  443. #ifdef OUTPUT
  444.                     printf("end init\n");
  445. #endif
  446.                 }
  447.                 bool unique_in_group(int nid){
  448.                     int group=node_group_id[nid];
  449.                     return (node_groups[group].group_counter==1);
  450.                 }
  451.                 void split_node(int nid){
  452.                     int old_group=node_group_id[nid];
  453.                     int i;
  454.                     node_groups[old_group].group_counter--;
  455.                     node_groups[node_groups_count].group_counter=1;
  456.                     node_groups[node_groups_count].tedges=node_groups[old_group].tedges;
  457.                     for(i=0;i<node_groups[old_group].tedges;i++){
  458.                         node_groups[node_groups_count].eids[i]=node_groups[old_group].eids[i];
  459.                     }
  460.                     node_group_id[nid]=node_groups_count++;
  461.                     int old_node_group;
  462.                     do{
  463.                         old_node_group=node_groups_count;
  464.                         set_edge_group();
  465.                         set_node_group();
  466.                     }while(node_groups_count!=old_node_group);
  467. #ifdef OUTPUT
  468.                     printf("split node %d\n",nid);
  469.                     printf("nodes:");
  470.                     show_nodes();
  471.                     set_edge_group();
  472.                     printf("edges:");
  473.                     show_edges();
  474. #endif
  475.                 }
  476.         };

  477.         void add_result(final_edge_set& final_edges, const group_infos& g)
  478.         {
  479.             int edges=g.get_edge_groups_count();
  480.             if(edges!=final_edges.num_edges){
  481.                 int i;
  482.                 for(i=0;i<final_edges.num_edges;i++){
  483.                     printf("e[%d]=%d ",i,g.get_edge_group_id(i));
  484.                 }
  485.                 printf("\n");
  486.                 for(i=0;i<edges;i++){
  487.                     printf("c[%d]=%d ",i,g.get_edge_group_counter(i));
  488.                 }
  489.                 printf("\n");
  490.                 for(i=0;i<TNODES;i++){
  491.                     printf("n[%d]=%d ",i,g.get_node_group_id(i));
  492.                 }
  493.                 printf("\n");
  494.                 g.show_edges();
  495.                 throw exception();
  496.             }
  497.             int i;
  498.             final_edge_set e;
  499.             char rev[max_total_edges];
  500.             for(i=0;i<edges;i++){
  501.                 rev[g.get_edge_group_id(i)]=i;
  502.             }
  503.             for(i=0;i<edges;i++){
  504.                 int j;
  505.                 for(j=0;j<NODES_PER_EDGE;j++){
  506.                     e.edges[i][j]=g.get_node_group_id(edges_info[rev[i]][j]);
  507.                 }
  508.                 sort(&e.edges[i][0],&e.edges[i][NODES_PER_EDGE]);
  509.             }
  510. #ifdef OUTPUT
  511.             printf("Find: ");
  512.             e.show();
  513. #endif
  514.             if(e<final_edges)final_edges=e;
  515.         }
  516.         
  517.         void find_all_edges(final_edge_set& final_edges,const group_infos& g, int searched)
  518.         {
  519.             int next_id = g.undetermined_node_group();
  520.             if(next_id<0){///All identify is found
  521.                 group_infos ng(g);
  522.                 if(searched>0){
  523.                     ng.promote_searched(searched);
  524.                 }
  525.                 add_result(final_edges,ng);
  526.             }else{
  527.                 int i;
  528.                 for(i=0;i<TNODES;i++){
  529.                     if(g.get_node_group_id(i)==next_id){
  530.                         bool simple = g.simple_case(i);
  531.                         group_infos ng(g);
  532.                         ng.split_node(i);
  533.                         find_all_edges(final_edges,ng,searched);
  534.                         if(simple)
  535.                             break;
  536.                     }
  537.                 }
  538.             }
  539.         }
  540.     public:
  541.         node_edge_set(int nedges, char info[][NODES_PER_EDGE]){
  542.             int i,j;
  543.             num_of_edges=nedges;
  544.             for(i=0;i<nedges;i++){
  545.                 for(j=0;j<NODES_PER_EDGE;j++){
  546.                     edges_info[i][j]=info[i][j];
  547.                 }
  548.             }
  549.             for(i=0;i<TNODES;i++)nodes_degree[i]=0;
  550.             for(i=0;i<num_of_edges;i++){
  551.                 for(j=0;j<NODES_PER_EDGE;j++){
  552.                     char the_nid=info[i][j];
  553.                     nodes_info[the_nid][nodes_degree[the_nid]++]=i;
  554.                 }
  555.             }
  556.         }


  557.         void find_all_node_types( int searched, char group[TNODES]){
  558.             int i,j;
  559.             final_edge_set finals[TNODES];
  560.             for(i=0;i<TNODES;i++){
  561.                 group[i]=-1;
  562.                 for(j=0;j<num_of_edges;j++){
  563.                     int k;
  564.                     for(k=0;k<NODES_PER_EDGE;k++){
  565.                         finals[i].edges[j][k]=TNODES;
  566.                     }
  567.                 }
  568.             }
  569.             group_infos g(this);
  570.             g.init_group_info(searched);
  571.             final_edge_set::set_curr_num_edges(num_of_edges);
  572.             for(i=searched;i<TNODES;i++){
  573.                 if(g.unique_in_group(i))
  574.                     continue;
  575.                 group_infos ng(g);
  576.                 ng.split_node(i);
  577.                 find_all_edges(finals[i],ng,searched);
  578.             }
  579.             for(i=searched;i<TNODES;i++){
  580.                 if(g.unique_in_group(i)){
  581.                     group[i]=1;
  582.                     continue;
  583.                 }
  584.                 for(j=searched;j<i;j++){
  585.                     if(finals[j]==finals[i])break;
  586.                 }
  587.                 if(j==i){
  588.                     group[i]=1;
  589.                 }
  590.             }
  591.         }

  592.         final_edge_set normalize(int searched){
  593.             group_infos g(this);
  594.             g.init_group_info(searched);
  595.             int i;
  596.             final_edge_set::set_curr_num_edges(num_of_edges);
  597.             final_edge_set final_edges;
  598.             for(i=0;i<num_of_edges;i++){
  599.                 int j;
  600.                 for(j=0;j<NODES_PER_EDGE;j++)
  601.                     final_edges.edges[i][j]=TNODES;//set it to maxiaml node
  602.             }
  603.             find_all_edges(final_edges, g,searched);
  604.             return final_edges;
  605.         }
  606. };

  607. template <int TNODES,int NODES_PER_EDGE>
  608. int node_edge_set<TNODES,NODES_PER_EDGE>::final_edge_set::num_edges;
  609. #if 0
  610. #define NUM_EDGES 23
  611. #define NUM_NODES 25
  612. char init_value[NUM_EDGES][5]={
  613.     "BIFS","BOLG","BMPH","BQNJ","EBCD",
  614.     "AIET","EMOF","EQPS","EKNH","CKMA",
  615.     "CQOT","CNPG","CJHS","DQMI","DNOA",
  616.     "DPLF","DJGT","MRGS","NRFT","IORH",
  617.     "JPRA","AFGH","KQRL"
  618. };
  619. char init_v2[NUM_EDGES][4];
  620. typedef node_edge_set<NUM_NODES> NESET;

  621. int main()
  622. {
  623.     int i,j;
  624.     for(i=0;i<NUM_EDGES;i++)for(j=0;j<4;j++){
  625.         init_v2[i][j]=init_value[i][j]-'A';
  626.     }
  627.     NESET nes(NUM_EDGES,init_v2);
  628.     NESET::final_edge_set e=nes.normalize(4);
  629.     printf("final result:\n");
  630.     e.show();
  631.     return 0;
  632. }
  633. #endif

  634. #define NUM_NODES 16
  635. #define NODES_PER_EDGE   4
  636. #define MAX_FREEDOM      4

  637. #define MAX_EDGES_PER_NODE  ((NUM_NODES-1)/(NODES_PER_EDGE-1))
  638. #define MAX_TOTAL_EDGES     ((MAX_EDGES_PER_NODE*NUM_NODES)/NODES_PER_EDGE)
  639. #define MAX_FREE_EDGES   (MAX_FREEDOM*NODES_PER_EDGE)

  640. char chessboard[NUM_NODES][NUM_NODES];
  641. char used[NUM_NODES];
  642. char line_buf[MAX_TOTAL_EDGES][NODES_PER_EDGE];
  643. int line_count;
  644. int cur_free_edge;
  645. int cur_max_degree;
  646. typedef node_edge_set<NUM_NODES,NODES_PER_EDGE> NESET;

  647. void reorder_node(int orig_node, int new_node)
  648. {
  649.     int i,j;
  650.     char tmp;
  651.     if(orig_node==new_node)return;
  652.     for(i=0;i<NUM_NODES;i++){
  653.         tmp=chessboard[orig_node][i];
  654.         chessboard[orig_node][i]=chessboard[new_node][i];
  655.         chessboard[new_node][i]=tmp;
  656.     }
  657.     for(i=0;i<NUM_NODES;i++){
  658.         tmp=chessboard[i][orig_node];
  659.         chessboard[i][orig_node]=chessboard[i][new_node];
  660.         chessboard[i][new_node]=tmp;
  661.     }
  662.     tmp=used[orig_node];
  663.     used[orig_node]=used[new_node];
  664.     used[new_node]=tmp;
  665.     for(i=0;i<line_count;i++){
  666.         for(j=0;j<NODES_PER_EDGE;j++){
  667.             if(line_buf[i][j]==orig_node){
  668.                 line_buf[i][j]=new_node;
  669.             }else if(line_buf[i][j]==new_node){
  670.                 line_buf[i][j]=orig_node;
  671.             }
  672.         }
  673.     }
  674. }
  675. int last_line_count;
  676. NESET::final_edge_set last_e;
  677. void output_cur(int step)
  678. {
  679.     int i;
  680.     int changed=0;
  681.     for(i=step;i<NUM_NODES;i++){
  682.         if(used[i]>used[step-1])
  683.             return;
  684.     }
  685.     if(last_line_count!=line_count){
  686.         changed=1;
  687.     }
  688.     last_line_count=line_count;
  689.     {
  690.         NESET nes(line_count, line_buf);
  691.         NESET::final_edge_set e=nes.normalize(step);
  692.         if(!changed&&e==last_e)
  693.             return;
  694.         last_e=e;
  695.         e.show(step);
  696.     }
  697. }

  698. void init()
  699. {
  700.     int i,j;
  701.     line_count=0;
  702.     for(i=0;i<NUM_NODES;i++)for(j=0;j<NUM_NODES;j++){
  703.         chessboard[i][j]=0;
  704.     }
  705.     for(i=0;i<NUM_NODES;i++)used[i]=0;
  706. }

  707. char test(int x,int y,int z, int w)
  708. {
  709.     if(chessboard[x][y]||chessboard[x][z]||
  710.             chessboard[x][w]||chessboard[y][z]||
  711.             chessboard[y][w]||chessboard[z][w])
  712.         return 0;
  713.     return 1;
  714. }

  715. void set_to(int x,int y, int z,int w, int value)
  716. {
  717.     chessboard[x][y]=chessboard[x][z]=chessboard[x][w]=
  718.         chessboard[y][x]=chessboard[y][z]=chessboard[y][w]=
  719.         chessboard[z][x]=chessboard[z][y]=chessboard[z][w]=
  720.         chessboard[w][x]=chessboard[w][y]=chessboard[w][z]=value;
  721. }

  722. void setv(int x,int y,int z,int w)
  723. {
  724.     set_to(x,y,z,w,1);
  725.     used[x]++;
  726.     used[y]++;
  727.     used[z]++;
  728.     used[w]++;
  729.     line_buf[line_count][0]=x;
  730.     line_buf[line_count][1]=y;
  731.     line_buf[line_count][2]=z;
  732.     line_buf[line_count][3]=w;
  733.     line_count++;
  734. }

  735. void unsetv(int x,int y,int z,int w)
  736. {
  737.     set_to(x,y,z,w,0);
  738.     used[x]--;
  739.     used[y]--;
  740.     used[z]--;
  741.     used[w]--;
  742.     line_count--;
  743. }

  744. void create_step_one()
  745. {
  746.     char filename[100];
  747.     mkdir("data/s1",-1);
  748.     FILE *pFile=fopen("data/s1/0","w");
  749.     int i,j;
  750.     for(i=MAX_EDGES_PER_NODE;i>=1;i--){
  751.         if((MAX_EDGES_PER_NODE-i)*NUM_NODES>MAX_FREE_EDGES)
  752.             break;
  753.         for(j=0;j<i;j++){
  754.             fprintf(pFile,"A%c%c%c",j*3+'B',j*3+'C',j*3+'D');
  755.         }
  756.         fprintf(pFile,"\n");
  757.     }
  758.     fclose(pFile);
  759. }

  760. void search(int u)
  761. {
  762.     int v,w,z;
  763.     if((MAX_EDGES_PER_NODE-used[u])*(NUM_NODES-u)<=cur_free_edge){
  764.         output_cur(u+1);
  765.     }
  766.     if(used[u]>=cur_max_degree)return;
  767.     for(v=u+1;v<NUM_NODES;v++){
  768.         if(used[v]>=cur_max_degree)continue;
  769.         if(chessboard[u][v])continue;
  770.         for(w=v+1;w<NUM_NODES;w++){
  771.             if(used[w]>=cur_max_degree)continue;
  772.             if(chessboard[u][w]||chessboard[v][w])continue;
  773.             for(z=w+1;z<NUM_NODES;z++){
  774.                 if(used[z]>=cur_max_degree)continue;
  775.                 if(chessboard[u][z]||chessboard[v][z]||chessboard[w][z])
  776.                     continue;
  777.                 setv(u,v,w,z);
  778.                 search(u);
  779.                 unsetv(u,v,w,z);
  780.             }
  781.         }
  782.     }
  783. }

  784. void process_one_line(int step, char *input)
  785. {
  786.     int i;
  787.     init();
  788.     for(i=0;;i++){
  789.         char c=input[i*4];
  790.         if(c>='A'&&c<='Z'){
  791.             setv(input[i*4]-'A',input[i*4+1]-'A',input[i*4+2]-'A',input[i*4+3]-'A');
  792.         }else{
  793.             break;
  794.         }
  795.     }
  796.     cur_free_edge=0;
  797.     cur_max_degree=0;
  798.     for(i=0;i<step-1;i++){
  799.         cur_free_edge+=MAX_EDGES_PER_NODE - used[i];
  800.         if(cur_max_degree<used[i]){
  801.             cur_max_degree=used[i];
  802.         }
  803.     }
  804.     for(;i<NUM_NODES;i++){
  805.         if(used[i]>cur_max_degree)
  806.             return;
  807.     }
  808.     cur_free_edge = MAX_FREE_EDGES - cur_free_edge;
  809.     if(cur_free_edge<0){
  810.         fprintf(stderr,"Warning, invalid input\n");
  811.         return;
  812.     }
  813.     char group[NUM_NODES];
  814.     for(i=0;i<NUM_NODES;i++)group[i]=1;
  815. /*    if(step<(NUM_NODES-1)/3){
  816.        NESET nes(line_count, line_buf);
  817.        NESET::final_edge_set e=nes.normalize(step);
  818.        nes.find_all_node_types(step-1,group);
  819.     }*/

  820.     for(i=step-1;i<NUM_NODES;i++){
  821.        if(group[i]>0){
  822.             reorder_node(i,step-1);
  823.             search(step-1);
  824.             reorder_node(i,step-1);
  825.         }
  826.     }
  827. }

  828. void sort_step(int step)
  829. {
  830.     char tname[100];
  831.     char cmdline[200];
  832.     sprintf(tname,"data/t%d",step);
  833.     DIR *dirs=opendir(tname);
  834.     if(dirs==NULL){
  835.         fprintf(stderr,"Failed to open dir %s\n",tname);
  836.         return;
  837.     }
  838.     struct dirent *flist;
  839.     while(flist=readdir(dirs)){
  840.         if(flist->d_name[0]<'0'||flist->d_name[0]>'9')
  841.             continue;
  842.         sprintf(cmdline,"sort -u data/t%d/%s -o data/s%d/%s",step,flist->d_name, step, flist->d_name);
  843.         system(cmdline);
  844.     }
  845.     closedir(dirs);
  846.     sprintf(cmdline,"rm -rf data/t%d",step);
  847.     system(cmdline);
  848. }

  849. #define LINE_BUF_SIZE (MAX_TOTAL_EDGES*(NODES_PER_EDGE+1)+20)
  850. void create_step(int step)
  851. {
  852.     char sname[100];
  853.     char line[LINE_BUF_SIZE];
  854.     FILE *pRead, *pWrite;
  855.     sprintf(sname,"data/t%d",step);
  856.     mkdir(sname,-1);
  857.     sprintf(sname,"data/s%d",step);
  858.     mkdir(sname,-1);
  859.     sprintf(sname,"data/s%d",step-1);
  860.     DIR *dirs=opendir(sname);
  861.     if(dirs==NULL){
  862.         fprintf(stderr,"Failed to open dir %s\n",sname);
  863.         return;
  864.     }
  865.     struct dirent *flist;
  866.     while(flist=readdir(dirs)){
  867.         if(flist->d_name[0]<'0'||flist->d_name[0]>'9')
  868.             continue;
  869.         sprintf(sname,"data/s%d/%s",step-1,flist->d_name);
  870.         pRead=fopen(sname,"r");
  871.         if(pRead==NULL){
  872.             fprintf(stderr,"Cannot read input file %s\n",sname);
  873.             exit(-1);
  874.         }
  875.         while(fgets(line,LINE_BUF_SIZE,pRead)){
  876.             process_one_line(step,line);
  877.         }
  878.         fclose(pRead);
  879.     }
  880.     closedir(dirs);
  881.     sort_step(step);
  882. }

  883. int main(char argc, char *argv[])
  884. {
  885.     int step=atoi(argv[1]);
  886.     if(step<1){
  887.         fprintf(stderr,"step should be no less than 1\n");
  888.         return -1;
  889.     }
  890.     if(step==1){
  891.         mkdir("data",-1);
  892.         create_step_one();
  893.     }else{
  894.         create_step(step);
  895.     }
  896.     return 0;
  897. }
复制代码



And a perl script is used to repeat the code by NUM_NODES times. Let's assuming that the binary file name is pm

  1. #!/usr/bin/perl
  2. \$NUM_NODES=16
  3. for(\$i=1;\$i<=\$NUM_NODES;\$i++){
  4.    system("./pm \$i");
  5. }
  6. system("cat data/s\$NUM_NODES/* > data/output.all");
复制代码


BUGS found on Sep 10,2008,
#define MAX_FREE_EDGES   (MAX_FREEDOM*NODES_PER_EDGE)
should be changed to
#define MAX_FREE_EDGES   (MAX_FREEDOM*NODES_PER_EDGE+MAX_EDGES_PER_NODE*NUM_NODES-MAX_TOTAL_EDGES*NODES_PER_EDGE)
and it is lucky that the two macro generate same values for n between 12 and 16
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 10:02:17 | 显示全部楼层
The C++ source code to simplify/prove no solution/solve candidate equations for orchard planting problem.
Changin the macro NUM_NODES to correspondent value too when trying to solve equations for different number of trees.

  1. #include <time.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <sys/stat.h>
  6. #include <sys/types.h>
  7. #include <gmp.h>
  8. #include <vector>
  9. using namespace std;
  10. #define ASSERT(x)
  11. typedef char cinfo[2];
  12. class ssolver{
  13.     short _n;//number of variables
  14.     short _m;//number of equations
  15.     short _t;//original number of equations
  16.     int   m;///number of columns
  17.     int   lc;//left column count
  18.     bool  _valid;
  19.     short **columnid;
  20.     short *left_column;
  21.     cinfo *column_info;
  22.     mpq_t tmp1,tmp2;
  23.     mpq_t **_matrix;
  24.     char  *row_var;
  25.     char  *row_evar;
  26.     short  *ctmp;
  27.     short  *ctmp2;

  28.     void init_memory(){
  29.         int i,j;
  30.         m=_n*(_n+1)/2;
  31.         columnid=new short *[_n];
  32.         columnid[0]=new short[_n*_n];
  33.         for(i=1;i<_n;i++)columnid[i]=columnid[i-1]+_n;
  34.         memset(columnid[0],0,sizeof(short)*m);
  35.         left_column=new short[m];
  36.         column_info=new cinfo[m];
  37.         _matrix = new mpq_t*[_m];///_m equations
  38.         row_var =new char[_m];
  39.         row_evar = new char[_m];
  40.         ctmp =new short[m];
  41.         ctmp2=new short[m];
  42.         _matrix[0]=new mpq_t[m*_m];
  43.         for(i=0;i<_m;i++){
  44.             if(i>0)
  45.             _matrix[i]=_matrix[i-1]+m;
  46.             for(j=0;j<m;j++){
  47.                 mpq_init(_matrix[i][j]);
  48.             }
  49.         }
  50.         for(i=0;i<_m;i++){row_var[i]=-1;row_evar[i]=-1;}
  51.         mpq_init(tmp1);mpq_init(tmp2);
  52.         set_column_index();
  53.         _t=_m;
  54.     }

  55.     void set_column_index(){
  56.         int i,j,s=0;
  57.         for(i=0;i<_n;i++){
  58.             for(j=0;j<=i;j++){
  59.                 column_info[s][0]=j;
  60.                 column_info[s][1]=i;
  61.                 columnid[i][j]=columnid[j][i]=s;
  62.                 s++;
  63.             }
  64.         }
  65.     }

  66.     void init_left_columns(){
  67.         int i,j;
  68.         for(i=0,lc=0;i<m;i++){
  69.             for(j=0;j<_m;j++){
  70.                 if(mpq_sgn(_matrix[j][i])!=0)
  71.                     break;
  72.             }
  73.             if(j<_m){
  74.                 left_column[lc++]=i;
  75.             }
  76.         }
  77.         _valid=true;
  78.     }

  79.     void remove_empty_rows(){
  80.         int i,j;
  81.         for(i=0;i<_m;i++){
  82.             for(j=0;j<lc;j++){
  83.                 int cid=left_column[j];
  84.                 if(mpq_sgn(_matrix[i][cid])!=0){
  85.                     break;
  86.                 }
  87.             }
  88.             if(j==lc){
  89.                 swap_row(i,_m-1);
  90.                 i--;
  91.                 _m--;
  92.             }
  93.         }
  94.     }

  95.     int try_reduce_var(int varid);
  96.     int reduce_iterator();
  97.     int reduce_inorder();

  98.     void simplify_result(){
  99.         int i,j;
  100.         for(i=_m;i<_t;i++){
  101.             if(row_evar[i]==-1)continue;///empty line
  102.             int mvar=row_var[i];
  103.             int evar=row_evar[i];
  104.             int c=0;
  105.             for(j=0;j<_n;j++){
  106.                 if(j==evar)continue;
  107.                 int cid=columnid[mvar][j];
  108.                 if(mpq_sgn(_matrix[i][cid])==0)continue;
  109.                 ctmp2[c]=j;
  110.                 ctmp[c++]=cid;
  111.             }
  112.             for(j=i+1;j<_t;j++){
  113.                 int mmvar=row_var[j];
  114.                 if(mmvar==-1)continue;
  115.                 int ncid=columnid[mmvar][evar];
  116.                 int k;
  117.                 if(mpq_sgn(_matrix[j][ncid])==0)continue;
  118.                 mpq_set(tmp1,_matrix[j][ncid]);
  119.                 mpq_set_ui(_matrix[j][ncid],0,1);///clear it to zero
  120.                 for(k=0;k<c;k++){
  121.                     int ecid=columnid[mmvar][ctmp2[k]];
  122.                     mpq_mul(tmp2,tmp1,_matrix[i][ctmp[k]]);
  123.                     mpq_sub(_matrix[j][ecid],_matrix[j][ecid],tmp2);
  124.                 }
  125.             }
  126.         }
  127.         if(row_evar[_t-1]!=-1){
  128.             for(i=_m;i<_t-1;i++){
  129.                 if(row_evar[i]==-1){
  130.                     swap_row(i, _t-1);///Make sure the last line is empty
  131.                     break;
  132.                 }
  133.             }
  134.         }
  135.     }

  136.     int eliminate_row(int row, int cid){///return v to be eliminated, return -1 if invalid row find
  137.         int i;
  138.         char mvar = row_var[row];
  139.         int evar;
  140.         int ecid;
  141.         if(column_info[cid][0]==mvar){
  142.             evar=column_info[cid][1];
  143.         }else{
  144.             ASSERT(column_info[cid][1]==mvar);
  145.             evar=column_info[cid][0];
  146.         }
  147.         row_evar[row]=evar;
  148.         mpq_set(tmp1,_matrix[row][cid]);
  149.         mpq_set_ui(_matrix[row][cid],1,1);
  150.         ecid=cid;
  151.         int c=0;
  152.         for(i=0;i<lc;i++){
  153.             cid=left_column[i];
  154.             if(cid==ecid)continue;
  155.             if(mpq_sgn(_matrix[row][cid])!=0){
  156.                 ctmp[c++]=cid;
  157.                 if(column_info[cid][0]==mvar){
  158.                     ctmp2[c-1]=column_info[cid][1];
  159.                 }else{
  160.                     ASSERT(column_info[cid][1]==mvar);
  161.                     ctmp2[c-1]=column_info[cid][0];
  162.                 }
  163.                 mpq_div(_matrix[row][cid],_matrix[row][cid],tmp1);///normalize the line
  164.             }
  165.         }
  166.         if(c==0){
  167.             _valid=false;
  168. #ifdef OUTPUT
  169.             printf("Invalid row %d\n",row);
  170.             output();
  171. #endif
  172.             return -1;///no solution
  173.         }
  174.         if(row!=_m-1){
  175.             swap_row(row,_m-1);
  176.         }
  177.         row=--_m;

  178.         for(i=0;i<lc;i++){
  179.             int cid=left_column[i];
  180.             int ovar=-1;
  181.             if(column_info[cid][0]==evar&&column_info[cid][1]==evar){
  182.                 int u,v,j;
  183.                 for(j=0;j<_m;j++){
  184.                     mpq_set(tmp1, _matrix[j][cid]);
  185.                     mpq_set_ui(_matrix[j][cid],0,1);//clear to zero
  186.                     if(mpq_sgn(tmp1)!=0){
  187.                         for(u=0;u<c;u++)for(v=u;v<c;v++){
  188.                             int ncid=columnid[ctmp2[u]][ctmp2[v]];
  189.                             mpq_mul(tmp2,_matrix[row][ctmp[u]],_matrix[row][ctmp[v]]);
  190.                             if(u!=v){
  191.                                 mpq_add(tmp2,tmp2,tmp2);
  192.                             }
  193.                             mpq_mul(tmp2,tmp2,tmp1);
  194.                             mpq_add(_matrix[j][ncid],_matrix[j][ncid],tmp2);
  195.                         }
  196.                     }
  197.                 }
  198.                 continue;
  199.             }else if(column_info[cid][0]==evar){
  200.                 ovar=column_info[cid][1];
  201.             }else if(column_info[cid][1]==evar){
  202.                 ovar=column_info[cid][0];
  203.             }
  204.             if(ovar>=0){
  205.                 int u,j;
  206.                 for(j=0;j<_m;j++){
  207.                     mpq_set(tmp1,_matrix[j][cid]);
  208.                     mpq_set_ui(_matrix[j][cid],0,1);
  209.                     if(mpq_sgn(tmp1)!=0){
  210.                         for(u=0;u<c;u++){
  211.                             int ncid=columnid[ctmp2[u]][ovar];
  212.                             mpq_mul(tmp2, _matrix[row][ctmp[u]],tmp1);
  213.                             mpq_sub(_matrix[j][ncid],_matrix[j][ncid],tmp2);
  214.                         }
  215.                     }
  216.                 }
  217.             }
  218.         }
  219.         init_left_columns();
  220.     }

  221.     void swap_row(int x,int y){
  222.         if(x==y)return;
  223.         int i;
  224.         for(i=0;i<lc;i++){
  225.             int cid=left_column[i];
  226.             mpq_set(tmp1, _matrix[x][cid]);
  227.             mpq_set(_matrix[x][cid],_matrix[y][cid]);
  228.             mpq_set(_matrix[y][cid],tmp1);
  229.         }
  230.         char c=row_var[x];
  231.         row_var[x]=row_var[y];
  232.         row_var[y]=c;
  233.         c=row_evar[x];
  234.         row_evar[x]=row_evar[y];
  235.         row_evar[y]=c;
  236.     }

  237. public:
  238.     ssolver(short n,short m){_n=n,_m=m;init_memory();}

  239.     ~ssolver(){
  240.         int i,j;
  241.         mpq_clear(tmp1);mpq_clear(tmp2);
  242.         for(i=0;i<_t;i++){
  243.             for(j=0;j<m;j++){
  244.                 mpq_clear(_matrix[i][j]);
  245.             }
  246.         }
  247.         delete []_matrix[0];
  248.         delete []_matrix;
  249.         delete []columnid[0];
  250.         delete []columnid;
  251.         delete []left_column;
  252.         delete []column_info;
  253.         delete []row_var;
  254.         delete []row_evar;
  255.         delete []ctmp;
  256.         delete []ctmp2;
  257.     }

  258.     void output()const{
  259.         int i,j;
  260.         if(_m>0){
  261.             for(i=0;i<_n;i++){
  262.                 ctmp[i]=0;
  263.             }
  264.             for(i=0;i<lc;i++){
  265.                 int cid=left_column[i];
  266.                 ctmp[column_info[cid][0]]=1;
  267.                 ctmp[column_info[cid][1]]=1;
  268.             }
  269.             printf("solve([");
  270.             for(i=0;i<_m;i++){
  271.                 int s;
  272.                 if(i!=0)printf(",");
  273.                 for(j=0;j<lc;j++){
  274.                     int cid=left_column[j];
  275.                     if((s=mpq_sgn(_matrix[i][cid]))!=0){
  276.                         if(s>0){
  277.                             printf("+");
  278.                         }
  279.                         mpq_out_str(stdout,10,_matrix[i][cid]);
  280.                         if(column_info[cid][0]>0){
  281.                             if(column_info[cid][0]&1){//X
  282.                                 printf("*%c_X",column_info[cid][0]/2+'A');
  283.                             }else{
  284.                                 printf("*%c_Y",(column_info[cid][0]-2)/2+'A');
  285.                             }
  286.                         }
  287.                         if(column_info[cid][1]>0){
  288.                             if(column_info[cid][1]&1){//X
  289.                                 printf("*%c_X",column_info[cid][1]/2+'A');
  290.                             }else{
  291.                                 printf("*%c_Y",(column_info[cid][1]-2)/2+'A');
  292.                             }
  293.                         }
  294.                     }
  295.                 }
  296.             }
  297.             printf("],[");
  298.             int start=1;
  299.             for(i=1;i<_n;i++){
  300.                 if(ctmp[i]){
  301.                     if(start)start=0;
  302.                     else printf(",");
  303.                     if(i&1){//X
  304.                         printf("%c_X",i/2+'A');
  305.                     }else{
  306.                         printf("%c_Y",(i-2)/2+'A');
  307.                     }
  308.                 }
  309.             }
  310.             printf("])\n");
  311.         }
  312.         for(i=_m;i<_t;i++){
  313.             int varid=row_var[i];
  314.             if(varid==-1)continue;
  315.             for(j=0;j<_n;j++){
  316.                 int cid=columnid[varid][j];
  317.                 int s;
  318.                 if((s=mpq_sgn(_matrix[i][cid]))!=0){
  319.                     if(s>0)printf("+");
  320.                     mpq_out_str(stdout,10,_matrix[i][cid]);
  321.                     if(j>0){
  322.                         if(j&1){//X
  323.                             printf("*%c_X",j/2+'A');
  324.                         }else{
  325.                             printf("*%c_Y",(j-2)/2+'A');
  326.                         }
  327.                     }
  328.                 }
  329.             }
  330.             printf("\n");
  331.         }
  332.     }
  333.     bool isValid()const{return _valid;}

  334.     void insert_item(int row, int v1, int v2, mpq_t value){
  335.         int cid=columnid[v1][v2];
  336.         mpq_add(_matrix[row][cid],_matrix[row][cid],value);
  337.     }

  338.     void simplify();
  339. };

  340. #define MAKE_ITEM(item_1, item_2)   ((((item_1)+1)<<16)|((item_2)+1))
  341. #define GET_ITEM_1(x)               (((x)>>16)-1)
  342. #define GET_ITEM_2(x)               (((x)&0xFFFF)-1)
  343. #define MAKE_SAFE_ITEM(item_1, item_2)  ((item_1)>(item_2)?MAKE_ITEM(item_1,item_2):MAKE_ITEM(item_2,item_1))

  344. #define NUM_NODES 16
  345. #define NODES_PER_EDGE   4

  346. #define MAX_EDGES_PER_NODE  ((NUM_NODES-1)/(NODES_PER_EDGE-1))
  347. #define MAX_TOTAL_EDGES     ((MAX_EDGES_PER_NODE*NUM_NODES)/NODES_PER_EDGE)
  348.                                                                                     
  349. char chessboard[NUM_NODES][NUM_NODES];
  350. char used[NUM_NODES];
  351. char line_buf[MAX_TOTAL_EDGES][NODES_PER_EDGE];
  352. int line_count;
  353. int cur_free_edge;
  354. int cur_max_degree;
  355. int curr_comb_id;
  356. int curr_line_num;
  357. int last_comb_id;
  358. int last_line_num;


  359. void output_cur()
  360. {
  361.     int i,j;
  362.     for(i=0;i<line_count;i++)for(j=0;j<NODES_PER_EDGE;j++){
  363.         printf("%c",'A'+line_buf[i][j]);
  364.     }
  365.     printf("\n");
  366. }

  367. void init()
  368. {
  369.     int i,j;
  370.     line_count=0;
  371.     for(i=0;i<NUM_NODES;i++)for(j=0;j<NUM_NODES;j++){
  372.         chessboard[i][j]=-1;
  373.     }
  374.     for(i=0;i<NUM_NODES;i++)used[i]=0;
  375.     curr_comb_id=0;
  376.     curr_line_num=0;
  377. }
  378. void init_mem(){
  379. }

  380. char test(int x,int y,int z, int w)
  381. {
  382.     if(chessboard[x][y]>=0||chessboard[x][z]>=0||
  383.             chessboard[x][w]>=0||chessboard[y][z]>=0||
  384.             chessboard[y][w]>=0||chessboard[z][w]>=0)
  385.         return 0;
  386.     return 1;
  387. }

  388. void set_to(int x,int y, int z,int w, int value)
  389. {
  390.     chessboard[x][y]=chessboard[x][z]=chessboard[x][w]=
  391.         chessboard[y][x]=chessboard[y][z]=chessboard[y][w]=
  392.         chessboard[z][x]=chessboard[z][y]=chessboard[z][w]=
  393.         chessboard[w][x]=chessboard[w][y]=chessboard[w][z]=value;
  394. }

  395. void setv(int x,int y,int z,int w)
  396. {
  397.     set_to(x,y,z,w,line_count);
  398.     used[x]++;
  399.     used[y]++;
  400.     used[z]++;
  401.     used[w]++;
  402.     line_buf[line_count][0]=x;
  403.     line_buf[line_count][1]=y;
  404.     line_buf[line_count][2]=z;
  405.     line_buf[line_count][3]=w;
  406.     line_count++;
  407. }

  408. void unsetv(int x,int y,int z,int w)
  409. {
  410.     set_to(x,y,z,w,-1);
  411.     used[x]--;
  412.     used[y]--;
  413.     used[z]--;
  414.     used[w]--;
  415.     line_count--;
  416. }

  417. enum value_type{ SET_CONST,UNSET,SET_INDEX,SET_INFTY};

  418. void sort_by_feature(char nodes[NODES_PER_EDGE], int fx[NUM_NODES],int fy[NUM_NODES]){
  419.     int i,j;
  420.     for(i=0;i<NODES_PER_EDGE;i++){
  421.         for(j=i+1;j<NODES_PER_EDGE;j++){
  422.             if(fx[nodes[i]]>fx[nodes[j]]||
  423.                     fx[nodes[i]]==fx[nodes[j]]&&fy[nodes[i]]>fy[nodes[j]]){
  424.                 char t=nodes[i];
  425.                 nodes[i]=nodes[j];
  426.                 nodes[j]=t;
  427.             }

  428.         }
  429.     }
  430. }


  431. void output_node_x(char a, int fx[],int x[])
  432. {
  433.     if(fx[a]==UNSET){
  434.         printf("%c_x",a+'A');
  435.     }else if(fx[a]==SET_CONST){
  436.         printf("%d",x[a]);
  437.     }else{
  438.         fprintf(stderr,"Invalid \n");
  439.         exit(-1);
  440.     }
  441. }

  442. void output_node_y(char a, int fy[],int y[])
  443. {
  444.     if(fy[a]==UNSET){
  445.         printf("%c_y",a+'A');
  446.     }else if(fy[a]==SET_CONST){
  447.         printf("%d",y[a]);
  448.     }else{
  449.         fprintf(stderr,"Invaid\n");
  450.         exit(-1);
  451.     }
  452. }

  453. int ssolver::try_reduce_var(int varid)
  454. {
  455.     int cur_row=0;
  456.     int i,j,k;
  457. #ifdef OUTPUT
  458.     if(varid==0){
  459.         printf("try reduce constant\n");
  460.     }else if(varid&1){
  461.         printf("try reduce %c_X\n",'A'+varid/2);
  462.     }else{
  463.         printf("try reduce %c_Y\n",'A'+(varid-2)/2);
  464.     }
  465. #endif
  466.     for(i=0;i<lc;i++){
  467.         int cid=left_column[i];
  468.         if(column_info[cid][0]==varid||column_info[cid][1]==varid)continue;
  469.         for(j=cur_row;j<_m;j++){
  470.             if(mpq_sgn(_matrix[j][cid])!=0)
  471.                 break;
  472.         }
  473.         if(j==_m)continue;
  474.         if(j!=cur_row){
  475.             swap_row(j,cur_row);
  476.         }
  477.         mpq_set(tmp1, _matrix[cur_row][cid]);
  478.         for(j=0;j<lc;j++){///normalize the line
  479.             int cid2=left_column[j];
  480.             if(mpq_sgn(_matrix[cur_row][cid2])!=0){
  481.                 mpq_div(_matrix[cur_row][cid2],_matrix[cur_row][cid2],tmp1);
  482.             }
  483.         }
  484.         for(k=0;k<_m;k++){///searching all rows except this
  485.             if(k==cur_row)continue;
  486.             if(mpq_sgn(_matrix[k][cid])!=0){
  487.                 mpq_set(tmp1,_matrix[k][cid]);
  488.                 for(j=0;j<lc;j++){
  489.                     int cid2=left_column[j];
  490.                     if(mpq_sgn(_matrix[cur_row][cid2])!=0){
  491.                         mpq_mul(tmp2,tmp1,_matrix[cur_row][cid2]);
  492.                         mpq_sub(_matrix[k][cid2],_matrix[k][cid2],tmp2);
  493.                     }
  494.                 }
  495.             }
  496.         }
  497.         cur_row++;
  498.         if(cur_row==_m)break;
  499.     }
  500.     if(cur_row==_m)return 0;
  501.     for(i=cur_row;i<_m;i++){
  502.         row_var[i]=varid;
  503.     }
  504.     int fr=0;
  505.     int end_row=cur_row;
  506.     for(i=_m-1;i>=end_row;i--){
  507.         int j;
  508.         int have_const=0,have_varid=0;
  509.         for(j=0;j<lc;j++){
  510.             int cid=left_column[j];
  511.             if(varid!=0&&(column_info[cid][0]==0||column_info[cid][1]==0)){
  512.                 if(mpq_sgn(_matrix[i][cid])!=0){
  513.                     have_const=1;
  514.                 }
  515.             }else if(column_info[cid][0]==varid&&column_info[cid][1]==varid){
  516.                 if(mpq_sgn(_matrix[i][cid])!=0){
  517.                     have_varid=1;
  518.                 }
  519.             }else if(mpq_sgn(_matrix[i][cid])!=0)break;
  520.         }
  521.         if(j==lc){
  522.             if(!have_const&&!have_varid){///empty row
  523.                 if(i!=_m-1){
  524.                     swap_row(i,_m-1);
  525.                 }
  526.                 row_var[_m-1]=-1;
  527.                 --_m;
  528.             }else if(!have_const||!have_varid){
  529.                 return -1;
  530.             }else{
  531.                 if(i!=end_row){
  532.                     swap_row(i,end_row);
  533.                 }
  534.                 end_row++;
  535.             }
  536.             continue;
  537.         }
  538.         int r=eliminate_row(i,left_column[j]);
  539.         if(r==-1)return -1;
  540.         fr=1;
  541.     }
  542.     if(cur_row<end_row){///Need to eliminate varid
  543.         int cid_const=columnid[0][varid];
  544.         int cid_var=columnid[varid][varid];
  545.         mpq_div(tmp1, _matrix[cur_row][cid_const], _matrix[cur_row][cid_var]);
  546.         for(i=cur_row+1;i<end_row;i++){
  547.             mpq_div(tmp2,_matrix[i][cid_const],_matrix[i][cid_var]);
  548.             if(mpq_cmp(tmp1,tmp2)!=0)
  549.                 return -1;
  550.         }
  551.         int r=eliminate_row(end_row-1,cid_var);
  552.         if(r==-1)return -1;
  553.         fr=1;
  554.         if(end_row>cur_row+1){
  555.             remove_empty_rows();
  556.         }
  557.     }
  558. #ifdef OUTPUT
  559.     printf("After reduce var\n");
  560.     output();
  561. #endif
  562.     return fr;
  563. }

  564. int ssolver::reduce_inorder()
  565. {
  566.     int i;
  567.     int max_c=-1,max_index=-1;
  568.     for(i=0;i<_n;i++){
  569.         ctmp[i]=0;
  570.     }
  571.     for(i=0;i<lc;i++){
  572.         int cid=left_column[i];
  573.         if(column_info[cid][0]==column_info[cid][1]){
  574.             ctmp[column_info[cid][0]]++;
  575.         }else{
  576.             ctmp[column_info[cid][0]]++;
  577.             ctmp[column_info[cid][1]]++;
  578.         }
  579.     }
  580.     for(i=0;i<_n;i++){
  581.         if(ctmp[i]>0){
  582.             int r=try_reduce_var(i);
  583.             if(r!=0)return r;
  584.         }
  585.     }
  586.     return 0;
  587. }

  588. int ssolver::reduce_iterator()
  589. {
  590.     int i;
  591.     int max_c=-1,max_index=-1;
  592.     for(i=0;i<_n;i++){
  593.         ctmp[i]=0;
  594.     }
  595.     for(i=0;i<lc;i++){
  596.         int cid=left_column[i];
  597.         if(column_info[cid][0]==column_info[cid][1]){
  598.             ctmp[column_info[cid][0]]++;
  599.         }else{
  600.             ctmp[column_info[cid][0]]++;
  601.             ctmp[column_info[cid][1]]++;
  602.         }
  603.     }
  604.     for(i=0;i<_n;i++){
  605.         if(ctmp[i]>max_c){
  606.             max_c=ctmp[i];
  607.             max_index=i;
  608.         }
  609.     }
  610.     return try_reduce_var(max_index);
  611. }

  612. ssolver *solver;
  613. void add_item_x(int x_n, int fx[], int x[], bool sub)
  614. {
  615.     if(fx[x_n]==UNSET){
  616.         mpq_t q;mpq_init(q);mpq_set_ui(q,1,1);
  617.         if(sub)mpq_neg(q,q);
  618.         solver->insert_item(curr_line_num, 2*x_n+1,0,q);
  619.         mpq_clear(q);
  620.     }else if(fx[x_n]==SET_CONST){
  621.         mpq_t q;mpq_init(q);mpq_set_ui(q,x[x_n],1);
  622.         if(sub)mpq_neg(q,q);
  623.         solver->insert_item(curr_line_num, 0,0, q);
  624.         mpq_clear(q);
  625.     }else{
  626.         fprintf(stderr,"invaid\n");
  627.     }
  628. }

  629. void add_item_y(int y_n, int fy[], int y[], bool sub)
  630. {
  631.     if(fy[y_n]==UNSET){
  632.         mpq_t q;mpq_init(q);mpq_set_ui(q,1,1);
  633.         if(sub)mpq_neg(q,q);
  634.         solver->insert_item(curr_line_num, 2*y_n+2, 0, q);
  635.         mpq_clear(q);
  636.     }else if(fy[y_n]==SET_CONST){
  637.         mpq_t q;mpq_init(q);mpq_set_ui(q,y[y_n],1);
  638.         if(sub)mpq_neg(q,q);
  639.         solver->insert_item(curr_line_num, 0, 0, q);
  640.         mpq_clear(q);
  641.     }else{
  642.         fprintf(stderr,"invaid\n");
  643.     }
  644. }

  645. void add_an_item(int x_n, int y_n, int fx[], int x[], int fy[], int y[] , bool sub)
  646. {
  647.     if(fx[x_n]==UNSET&&fy[y_n]==UNSET){
  648.         mpq_t q;
  649.         mpq_init(q);mpq_set_ui(q,1,1);
  650.         if(sub)mpq_neg(q,q);
  651.         solver->insert_item(curr_line_num, 2*x_n+1, 2*y_n+2,q);
  652.         mpq_clear(q);
  653.     }else if(fx[x_n]==UNSET&&fy[y_n]==SET_CONST){
  654.         mpq_t q;mpq_init(q);mpq_set_ui(q,y[y_n],1);
  655.         if(sub)mpq_neg(q,q);
  656.         solver->insert_item(curr_line_num, 2*x_n+1,0,q);
  657.         mpq_clear(q);
  658.     }else if(fx[x_n]==SET_CONST&&fy[y_n]==UNSET){
  659.         mpq_t q;mpq_init(q);mpq_set_ui(q,x[x_n],1);
  660.         if(sub)mpq_neg(q,q);
  661.         solver->insert_item(curr_line_num, 2*y_n+2,0,q);
  662.         mpq_clear(q);
  663.     }else if(fx[x_n]==SET_CONST&&fy[y_n]==SET_CONST){
  664.         mpq_t q;mpq_init(q);mpq_set_ui(q,x[x_n]*y[y_n],1);
  665.         if(sub)mpq_neg(q,q);
  666.         solver->insert_item(curr_line_num, 0,0, q);
  667.         mpq_clear(q);
  668.     }else{
  669.         fprintf(stderr,"Invalid \n");
  670.         exit(-1);
  671.     }
  672. }

  673. #define ADD_AN_ITEM(xn,yn) add_an_item(xn,yn,fx,x,fy,y,false)
  674. #define SUB_AN_ITEM(xn,yn) add_an_item(xn,yn,fx,x,fy,y,true)
  675. #define ADD_X(xn)          add_item_x(xn,fx,x,false)
  676. #define SUB_X(xn)          add_item_x(xn,fx,x,true)
  677. #define ADD_Y(yn)          add_item_y(yn,fy,y,false)
  678. #define SUB_Y(yn)          add_item_y(yn,fy,y,true)

  679. void output_line(char a,char b,char c, int fx[],int fy[],int x[],int y[]){
  680.     if(fx[c]!=SET_INFTY){///Limit case
  681.         ADD_AN_ITEM(b,a);
  682.         ADD_AN_ITEM(c,b);
  683.         ADD_AN_ITEM(a,c);
  684.         SUB_AN_ITEM(b,c);
  685.         SUB_AN_ITEM(c,a);
  686.         SUB_AN_ITEM(a,b);
  687.     }else{
  688.         if(fy[c]==SET_INFTY){///parallel to x or y coord
  689.             if(x[c]==1&&y[c]==0){///y=const
  690.                 ADD_Y(a);
  691.                 SUB_Y(b);
  692.             }else if(x[c]==0&&y[c]==1){
  693.                 ADD_X(a);
  694.                 SUB_X(b);
  695.             }else{
  696.                 fprintf(stderr,"invalid data");
  697.                 exit(-1);
  698.             }
  699.         }else{///The ratio
  700.             ADD_Y(b);
  701.             SUB_Y(a);
  702.             SUB_AN_ITEM(b,c);
  703.             ADD_AN_ITEM(a,c);
  704.         }
  705.     }
  706.     curr_line_num++;
  707. }

  708. void ssolver::simplify()
  709. {
  710.     init_left_columns();
  711. #ifdef OUTPUT
  712.     printf("Before remove empty rows\n");
  713.     output();
  714. #endif
  715.     remove_empty_rows();
  716. #ifdef OUTPUT
  717.     printf("After init\n");
  718.     output();
  719. #endif
  720.     do{
  721.         int r=reduce_iterator();
  722.         if(r==-1){
  723.             _valid=false;
  724.             return;
  725.         }
  726.         if(r==1)continue;
  727.         r=reduce_inorder();
  728.         if(r==-1){
  729.             _valid=false;
  730.             return;
  731.         }
  732.         if(r==0)break;
  733.     }while(1);
  734.     if(_valid){
  735.         simplify_result();
  736.     }
  737. }

  738. void process_one_line(char *input)
  739. {
  740.     int i,j,k;
  741.     init();
  742.     for(i=0;;i++){
  743.         char c=input[i*4];
  744.         if(c>='A'&&c<='Z'){
  745.             setv(input[i*4]-'A',input[i*4+1]-'A',input[i*4+2]-'A',input[i*4+3]-'A');
  746.         }else{
  747.             break;
  748.         }
  749.     }

  750.     int max_degree=0;
  751.     char e_to_n[MAX_TOTAL_EDGES][MAX_TOTAL_EDGES];
  752.     char n_to_e[NUM_NODES][NUM_NODES];
  753.     for(i=0;i<MAX_TOTAL_EDGES;i++)for(j=0;j<MAX_TOTAL_EDGES;j++){
  754.         e_to_n[i][j]=-1;
  755.     }
  756.     for(i=0;i<NUM_NODES;i++)for(j=0;j<NUM_NODES;j++){
  757.         n_to_e[i][j]=-1;
  758.     }
  759.     for(i=0;i<line_count;i++){
  760.         for(j=0;j<NODES_PER_EDGE;j++){
  761.             for(k=j+1;k<NODES_PER_EDGE;k++){
  762.                 n_to_e[line_buf[i][j]][line_buf[i][k]]=
  763.                     n_to_e[line_buf[i][k]][line_buf[i][j]]=i;
  764.             }
  765.         }
  766.     }
  767.     for(i=0;i<NUM_NODES;i++){
  768.         for(j=0;j<NUM_NODES;j++){
  769.             if(n_to_e[i][j]==-1)continue;
  770.             for(k=j+1;k<NUM_NODES;k++){
  771.                 if(n_to_e[i][k]==-1)continue;
  772.                 if(n_to_e[i][j]==n_to_e[i][k])continue;
  773.                 e_to_n[n_to_e[i][j]][n_to_e[i][k]]=
  774.                     e_to_n[n_to_e[i][k]][n_to_e[i][j]]=i;
  775.             }
  776.         }
  777.     }

  778.     int max_sum=0;
  779.     int best_i,best_j,best_k;
  780.     int a,b,c;

  781.     for(i=0;i<line_count;i++){
  782.         for(j=i+1;j<line_count;j++){
  783.             if(e_to_n[i][j]==-1)continue;
  784.             for(k=j+1;k<line_count;k++){
  785.                 if(e_to_n[i][k]==-1||e_to_n[j][k]==-1)continue;
  786.                 if(e_to_n[i][j]==e_to_n[i][k])continue;
  787.                 int a=e_to_n[j][k];
  788.                 int b=e_to_n[i][k];
  789.                 int c=e_to_n[i][j];
  790.                 ///Try edge i
  791.                 int u;
  792.                 int lsum=used[a];
  793.                 for(u=0;u<NODES_PER_EDGE;u++){
  794.                     lsum+=used[line_buf[i][u]];
  795.                 }
  796.                 if(lsum>max_sum){
  797.                     max_sum=lsum;
  798.                     best_i=i;best_j=j;best_k=k;
  799.                 }
  800.                 lsum=used[b];
  801.                 for(u=0;u<NODES_PER_EDGE;u++){
  802.                     lsum+=used[line_buf[j][u]];
  803.                 }
  804.                 if(lsum>max_sum){
  805.                     max_sum=lsum;
  806.                     best_i=j;best_j=k;best_k=i;
  807.                 }
  808.                 lsum=used[c];
  809.                 for(u=0;u<NODES_PER_EDGE;u++){
  810.                     lsum+=used[line_buf[k][u]];
  811.                 }
  812.                 if(lsum>max_sum){
  813.                     max_sum=lsum;
  814.                     best_i=k;best_j=i;best_k=j;
  815.                 }
  816.             }
  817.         }
  818.     }

  819.     if(max_sum==0){
  820.         printf("%s\nerror: No triangle found\n",input);
  821.         return;
  822.     }

  823.     solver =new ssolver(2*NUM_NODES+1, 2*line_count);
  824.     a=e_to_n[best_j][best_k];///(0,0,1)
  825.     b=e_to_n[best_i][best_k];///(1,0,0)
  826.     c=e_to_n[best_i][best_j];///(0,1,0)
  827.     int x[NUM_NODES],y[NUM_NODES];
  828.     int fx[NUM_NODES],fy[NUM_NODES];
  829.     for(i=0;i<NUM_NODES;i++){
  830.         fx[i]=fy[i]=UNSET;///value unset
  831.     }
  832.     fx[a]=fy[a]=SET_CONST;x[a]=y[a]=0;
  833.     fx[b]=fy[b]=SET_INFTY;x[b]=1;y[b]=0;
  834.     fx[c]=fy[c]=SET_INFTY;x[c]=0;y[c]=1;
  835.     for(i=0;i<NODES_PER_EDGE;i++){///in best_k, y=0
  836.         if(line_buf[best_k][i]!=a&&line_buf[best_k][i]!=b){
  837.             int n=line_buf[best_k][i];
  838.             fx[n]=fy[n]=SET_CONST;
  839.             x[n]=1;y[n]=0;
  840.             break;
  841.         }
  842.     }
  843.     for(i++;i<NODES_PER_EDGE;i++){
  844.         if(line_buf[best_k][i]!=a&&line_buf[best_k][i]!=b){
  845.             int n=line_buf[best_k][i];
  846.             fy[n]=SET_CONST;
  847.             y[n]=0;
  848.             break;
  849.         }
  850.     }
  851.     for(i=0;i<NODES_PER_EDGE;i++){///in best_j, x=0
  852.         if(line_buf[best_j][i]!=a&&line_buf[best_j][i]!=c){
  853.             int n=line_buf[best_j][i];
  854.             fx[n]=fy[n]=SET_CONST;
  855.             x[n]=0;y[n]=1;
  856.             break;
  857.         }
  858.     }
  859.     for(i++;i<NODES_PER_EDGE;i++){
  860.         if(line_buf[best_j][i]!=a&&line_buf[best_j][i]!=c){
  861.             int n=line_buf[best_j][i];
  862.             fx[n]=SET_CONST;
  863.             x[n]=0;
  864.             break;
  865.         }
  866.     }
  867.     for(i=0;i<NODES_PER_EDGE;i++){///in best_i, INFTY LINE
  868.         if(line_buf[best_i][i]!=b&&line_buf[best_i][i]!=c){
  869.             int n=line_buf[best_i][i];
  870.             fx[n]=SET_INFTY;
  871.             fy[n]=UNSET;
  872.             x[n]=1;
  873.         }
  874.     }

  875.     for(i=0;i<line_count;i++){
  876.         if(i==best_i||i==best_j||i==best_k)
  877.             continue;
  878.         int s,t,z,w;
  879.         sort_by_feature(line_buf[i],fx,fy);
  880.         s=line_buf[i][0],t=line_buf[i][1],z=line_buf[i][2],w=line_buf[i][3];
  881.         if(fx[t]==SET_INFTY||fx[z]==SET_INFTY||fx[s]==SET_INFTY){
  882.             printf("%s\nInvalid lines data\n",input);
  883.             delete solver;
  884.             return;
  885.         }
  886.         if(fx[w]==SET_INFTY){
  887.             output_line(s,t,w,fx,fy,x,y);
  888.             output_line(s,z,w,fx,fy,x,y);
  889.         }else{
  890.             output_line(s,t,z,fx,fy,x,y);
  891.             output_line(s,t,w,fx,fy,x,y);
  892.         }
  893.     }
  894.     last_comb_id = curr_comb_id;
  895.     last_line_num = curr_line_num;

  896.     solver->simplify();
  897.     if(solver->isValid()){
  898.         printf("%s\n",input);
  899.         solver->output();
  900.         for(i=0;i<NUM_NODES;i++){
  901.             if(fx[i]==SET_INFTY&&fy[i]==SET_INFTY){
  902.                 printf("%c=(%d,%d,0) ",i+'A',x[i],y[i]);
  903.             }else if(fx[i]==SET_INFTY){
  904.                 printf("%c=(1,%c_y,0) ",i+'A',i+'A');
  905.             }else{
  906.                 if(fx[i]==SET_CONST){
  907.                     printf("%c_x=%d ",i+'A',x[i]);
  908.                 }
  909.                 if(fy[i]==SET_CONST){
  910.                     printf("%c_y=%d ",i+'A',y[i]);
  911.                 }
  912.             }
  913.         }
  914.         printf("\n");
  915.     }

  916.     delete solver;
  917. }

  918. #define LINE_BUF_SIZE (MAX_TOTAL_EDGES*(NODES_PER_EDGE+1)+20)
  919. void process_file(char *filename)
  920. {
  921.     char line[LINE_BUF_SIZE];
  922.     FILE *pRead;
  923.     pRead=fopen(filename,"r");
  924.     if(pRead==NULL){
  925.         fprintf(stderr,"Cannot read input file %s\n",filename);
  926.         exit(-1);
  927.     }
  928.     while(fgets(line,LINE_BUF_SIZE,pRead)){
  929.         process_one_line(line);
  930.     }
  931.     fclose(pRead);
  932. }

  933. int main(char argc, char *argv[])
  934. {
  935.     init_mem();
  936.     process_file(argv[1]);
  937.     return 0;
  938. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-21 10:37:59 | 显示全部楼层
mathe可以发表论文了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-21 10:48:50 | 显示全部楼层
为什么不允许游客访问呢,禁止他们回复和发帖还不行么
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 10:52:02 | 显示全部楼层
原帖由 0→∞ 于 2008-8-21 10:48 发表
为什么不允许游客访问呢,禁止他们回复和发帖还不行么

游客,如果您要查看本帖隐藏内容请回复

发表论文我兴趣不大,比较花时间,网络上发表结果就可以了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 11:16:39 | 显示全部楼层
不过现在都只是证明了一些人家找出来的结果已经是最优结果,没有找出更好的结果。如果能够对n=17找出16条直线或者n=20找出24条直线的,那就更加好了。
另外zgg和没一一问题有没有试一试用我那个解方程的程序过滤一下你们关于问题二找出来的一些候选解?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-21 12:00:38 | 显示全部楼层
关于问题2,能否算出在20点24线时共有多少种不同类的解?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 12:49:58 | 显示全部楼层
连存在都不能证明
不可能给出20点4点共线的24直线解的数量的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 13:29:20 | 显示全部楼层
他说的是问题2的数量。这个关于17点不少于17条边情况的求解在我的计算机上产生几十G数据以后好像让我的Linux机器崩溃了,现在我不能远程登录了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-11-28 22:28 , Processed in 0.450132 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表