v 0. Pasted by ripatti as cpp at 2016-11-05 12:43:03 MSK and set expiration to never.

Paste will expire never.

  1. #pragma comment(linker,"/STACK:64000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <iostream>
  4. #include <vector>
  5. #include <set>
  6. #include <ctime>
  7. #include <memory.h>
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10.  
  11. using namespace std;
  12.  
  13. struct BAND
  14. {
  15.     int m[3][3][3]; // 3 blocks of 3x3 grids
  16.  
  17.     BAND()
  18.     {
  19.         for (int i=0; i<3; i++)
  20.             for (int j=0; j<3; j++)
  21.                 for (int k=0; k<3; k++)
  22.                     m[i][j][k] = 0;
  23.     }
  24.  
  25.     void print()
  26.     {
  27.         for (int i=0; i<3; i++)
  28.         {
  29.             for (int j=0; j<3; j++)
  30.             {
  31.                 for (int k=0; k<3; k++)
  32.                     printf( "%d", m[j][i][k] );
  33.                 printf( " " );
  34.             }
  35.             printf( "\n" );
  36.         }
  37.         printf( "\n" );
  38.     }
  39.  
  40.     bool is_valid( bool with_zeros )
  41.     {
  42.         for (int i=0; i<3; i++)
  43.             for (int j=0; j<3; j++)
  44.                 for (int k=0; k<3; k++)
  45.                 {
  46.                     if (!(0<=m[i][j][k] && m[i][j][k]<=9)) return false;
  47.                     if (!with_zeros && m[i][j][k]==0) return false;
  48.                 }
  49.  
  50.         bool F[10];
  51.         for (int i=0; i<3; i++) // check blocks
  52.         {
  53.             memset( F, 0, sizeof( F ) );
  54.             for (int j=0; j<3; j++)
  55.                 for (int k=0; k<3; k++)
  56.                 {
  57.                     if (F[m[i][j][k]]) return false;
  58.                     if (m[i][j][k]>0) F[m[i][j][k]] = true;
  59.                 }
  60.         }
  61.         for (int i=0; i<3; i++) // check rows
  62.         {
  63.             memset( F, 0, sizeof( F ) );
  64.             for (int j=0; j<3; j++)
  65.                 for (int k=0; k<3; k++)
  66.                 {
  67.                     if (F[m[j][i][k]]) return false;
  68.                     if (m[j][i][k]>0) F[m[j][i][k]] = true;
  69.                 }
  70.         }
  71.         return true;
  72.     }
  73.  
  74.     void normalize() // turn into standard form
  75.     {
  76.         // relabeling
  77.         int relabel[10];
  78.         int t = 1;
  79.         for (int i=0; i<3; i++)
  80.             for (int j=0; j<3; j++)
  81.                 relabel[m[0][i][j]] = t++;
  82.         for (int i=0; i<3; i++)
  83.             for (int j=0; j<3; j++)
  84.                 for (int k=0; k<3; k++)
  85.                     m[i][j][k] = relabel[m[i][j][k]];
  86.  
  87.         // lexicographic reduction
  88.         for (int i=1; i<3; i++)
  89.         {
  90.             if (m[i][0][0] > m[i][0][1])
  91.                 for (int j=0; j<3; j++)
  92.                     swap( m[i][j][0], m[i][j][1] );
  93.             if (m[i][0][1] > m[i][0][2])
  94.                 for (int j=0; j<3; j++)
  95.                     swap( m[i][j][1], m[i][j][2] );
  96.             if (m[i][0][0] > m[i][0][1])
  97.                 for (int j=0; j<3; j++)
  98.                     swap( m[i][j][0], m[i][j][1] );
  99.         }
  100.  
  101.         // swap B2 and B3
  102.         if (m[1][0][0] > m[2][0][0])
  103.             for (int i=0; i<3; i++)
  104.                 for (int j=0; j<3; j++)
  105.                     swap( m[1][i][j], m[2][i][j] );
  106.     }
  107.  
  108.     BAND get_copy()
  109.     {
  110.         BAND re;
  111.         for (int i=0; i<3; i++)
  112.             for (int j=0; j<3; j++)
  113.                 for (int k=0; k<3; k++)
  114.                     re.m[i][j][k] = m[i][j][k];
  115.         return re;
  116.     }
  117.  
  118.     BAND swap_blocks( int x, int y ) // swap blocks x and y
  119.     {
  120.         BAND re = get_copy();
  121.         for (int i=0; i<3; i++)
  122.             for (int j=0; j<3; j++)
  123.                 swap( re.m[x][i][j], re.m[y][i][j] );
  124.         re.normalize();
  125.         return re;
  126.     }
  127.  
  128.     BAND swap_rows( int x, int y ) // swap rows x and y
  129.     {
  130.         BAND re = get_copy();
  131.         for (int i=0; i<3; i++)
  132.             for (int j=0; j<3; j++)
  133.                 swap( re.m[i][x][j], re.m[i][y][j] );
  134.         re.normalize();
  135.         return re;
  136.     }
  137.  
  138.     BAND swap_columns( int b, int x, int y ) // swap columns x and y in block b
  139.     {
  140.         BAND re = get_copy();
  141.         for (int i=0; i<3; i++)
  142.             swap( re.m[b][i][x], re.m[b][i][y] );
  143.         re.normalize();
  144.         return re;
  145.     }
  146.  
  147.     BAND swap_cross( int b1, int b2, int r1, int r2, int c1, int c2 )
  148.     {
  149.         BAND re = get_copy();
  150.         // note: b1 must be together with c1 and b2 must be together with c2
  151.         if (re.m[b1][r1][c1] == re.m[b2][r2][c2] && re.m[b1][r2][c1] == re.m[b2][r1][c2])
  152.         {
  153.             swap( re.m[b1][r1][c1], re.m[b2][r1][c2] );
  154.             swap( re.m[b1][r2][c1], re.m[b2][r2][c2] );
  155.         }
  156.         re.normalize();
  157.         return re;
  158.     }
  159.  
  160.     BAND swap_3x2( int b1, int b2, int c1, int c2 )
  161.     {
  162.         BAND re = get_copy();
  163.         // note: b1 must be together with c1 and b2 must be together with c2
  164.         if ((   re.m[b1][0][c1] == re.m[b2][1][c2] &&
  165.                 re.m[b1][1][c1] == re.m[b2][2][c2] &&
  166.                 re.m[b1][2][c1] == re.m[b2][0][c2]) ||
  167.             (   re.m[b1][0][c1] == re.m[b2][2][c2] &&
  168.                 re.m[b1][1][c1] == re.m[b2][0][c2] &&
  169.                 re.m[b1][2][c1] == re.m[b2][1][c2]))
  170.         {
  171.             swap( re.m[b1][0][c1], re.m[b2][0][c2] );
  172.             swap( re.m[b1][1][c1], re.m[b2][1][c2] );
  173.             swap( re.m[b1][2][c1], re.m[b2][2][c2] );
  174.         }
  175.         re.normalize();
  176.         return re;
  177.     }
  178.  
  179.     BAND swap_mask( int r1, int r2, int mask )
  180.     {
  181.         BAND re = get_copy();
  182.         int num1=0, num2=0;
  183.         for (int i=0; i<3; i++) // block
  184.             for (int j=0; j<3; j++) // col
  185.                 if ((mask>>(i*3+j))&1)
  186.                 {
  187.                     num1 += (1<<re.m[i][r1][j]);
  188.                     num2 += (1<<re.m[i][r2][j]);
  189.                 }
  190.         if (num1 == num2)
  191.             for (int i=0; i<3; i++) // block
  192.                 for (int j=0; j<3; j++) // col
  193.                     if ((mask>>(i*3+j))&1)
  194.                         swap( re.m[i][r1][j], re.m[i][r2][j] );
  195.         re.normalize();
  196.         return re;
  197.     }
  198. };
  199.  
  200. bool operator< ( const BAND & A, const BAND & B )
  201. {
  202.     for (int i=0; i<3; i++)
  203.         for (int j=0; j<3; j++)
  204.             for (int k=0; k<3; k++)
  205.                 if (A.m[i][j][k] != B.m[i][j][k])
  206.                     return A.m[i][j][k] < B.m[i][j][k];
  207.     return false;
  208. }
  209.  
  210. bool operator== ( const BAND & A, const BAND & B )
  211. {
  212.     for (int i=0; i<3; i++)
  213.         for (int j=0; j<3; j++)
  214.             for (int k=0; k<3; k++)
  215.                 if (A.m[i][j][k] != B.m[i][j][k])
  216.                     return false;
  217.     return true;
  218. }
  219.  
  220. void gen_bands( BAND band, int block, int row, int col, vector< BAND > & res )
  221. {
  222.     col++; // move to the next empty cell
  223.     if (col==3) { col=0; row++; }
  224.     if (row==3) { row=1; block++; }
  225.     if (block==3) // no next empty cell
  226.     {
  227.         res.push_back( band );
  228.         return;
  229.     }
  230.  
  231.     for (int a=1; a<=9; a++)
  232.     {
  233.         band.m[block][row][col] = a;
  234.         if (band.is_valid( true ))
  235.             gen_bands( band, block, row, col, res );
  236.     }
  237. }
  238.  
  239. vector< BAND > gen_all_bands()
  240. {
  241.     BAND b0;
  242.     int t=1;
  243.     for (int i=0; i<3; i++)
  244.         for (int j=0; j<3; j++)
  245.             b0.m[0][i][j] = t++;
  246.     // b0 has standard block B1; B2 and B3 are empty
  247.  
  248.     vector< BAND > starting_bands;
  249.     for (int a=4; a<=4; a++)
  250.         for (int b=a+1; b<=9; b++)
  251.             for (int c=b+1; c<=9; c++)
  252.             {
  253.                 BAND b1 = b0;
  254.                 b1.m[1][0][0] = a;
  255.                 b1.m[1][0][1] = b;
  256.                 b1.m[1][0][2] = c;
  257.                 int ind = 0;
  258.                 for (int d=4; d<=9; d++)
  259.                     if (d!=a && d!=b && d!=c)
  260.                         b1.m[2][0][ind++] = d;
  261.                 //b1.print();
  262.                 starting_bands.push_back( b1 );
  263.             }
  264.     // we filled the first row by all possible ways
  265.     printf( "bands with filled the first row %d\n", (int)starting_bands.size() ); // 10 bands total
  266.  
  267.     vector< BAND > reduced_bands;
  268.     for (int i=0; i<(int)starting_bands.size(); i++)
  269.         gen_bands( starting_bands[i], 0, 2, 2, reduced_bands );
  270.     printf( "lexicographically reduced bands %d\n", (int)reduced_bands.size() ); // 36288 bands total
  271.  
  272.     return reduced_bands;
  273. }
  274.  
  275. set< BAND > used_bands;
  276. int comp_size;
  277.  
  278. void dfs( BAND b )
  279. {
  280.     if (used_bands.find( b ) != used_bands.end()) return;
  281.     comp_size++;
  282.     used_bands.insert( b );
  283.  
  284.     for (int i=0; i<3; i++)
  285.         for (int j=i+1; j<3; j++)
  286.         {
  287.             dfs( b.swap_blocks( i, j ) );
  288.             dfs( b.swap_rows( i, j ) );
  289.             for (int k=0; k<3; k++)
  290.                 dfs( b.swap_columns( k, i, j ) );
  291.         }
  292.  
  293.     for (int b1=0; b1<3; b1++)
  294.         for (int b2=b1+1; b2<3; b2++)
  295.             for (int r1=0; r1<3; r1++)
  296.                 for (int r2=r1+1; r2<3; r2++)
  297.                     for (int c1=0; c1<3; c1++)
  298.                         for (int c2=0; c2<3; c2++)
  299.                             dfs( b.swap_cross( b1, b2, r1, r2, c1, c2 ) );
  300.  
  301.     for (int b1=0; b1<3; b1++)
  302.         for (int b2=b1+1; b2<3; b2++)
  303.             for (int c1=0; c1<3; c1++)
  304.                 for (int c2=0; c2<3; c2++)
  305.                     dfs( b.swap_3x2( b1, b2, c1, c2 ) );
  306.  
  307.     for (int r1=0; r1<3; r1++)
  308.         for (int r2=r1+1; r2<3; r2++)
  309.             for (int mask=1; mask<(1<<9); mask++)
  310.                 dfs( b.swap_mask( r1, r2, mask ) );
  311. }
  312.  
  313. struct GRID
  314. {
  315.     int T[9][9];
  316.     bool R[9][10], C[9][10], B[9][10];
  317.  
  318.     void clear()
  319.     {
  320.         memset( T, 0, sizeof( T ) );
  321.         memset( R, 0, sizeof( R ) );
  322.         memset( C, 0, sizeof( C ) );
  323.         memset( B, 0, sizeof( B ) );
  324.     }
  325.  
  326.     void print()
  327.     {
  328.         for (int i=0; i<9; i++)
  329.         {
  330.             for (int j=0; j<9; j++)
  331.                 printf( "%d", T[i][j] );
  332.             printf( "\n" );
  333.         }
  334.         printf( "\n" );
  335.     }
  336.  
  337.     bool can_set( int num, int x, int y )
  338.     {
  339.         return !R[x][num] && !C[y][num] && !B[(x/3)*3+(y/3)][num];
  340.     }
  341.  
  342.     void set_num( int num, int x, int y )
  343.     {
  344.         T[x][y] = num;
  345.         R[x][num] = true;
  346.         C[y][num] = true;
  347.         B[(x/3)*3+(y/3)][num] = true;
  348.     }
  349.  
  350.     void unset_num( int num, int x, int y )
  351.     {
  352.         T[x][y] = 0;
  353.         R[x][num] = false;
  354.         C[y][num] = false;
  355.         B[(x/3)*3+(y/3)][num] = false;
  356.     }
  357. } G;
  358.  
  359. int grids_count;
  360.  
  361. void dfs2( int x, int y )
  362. {
  363.     x++; // find next empty cell
  364.     if (x==9) { x=3; y++; }
  365.     if (y==9) // no empty cells
  366.     {
  367.         grids_count++;
  368.         return;
  369.     }
  370.  
  371.     for (int a=1; a<=9; a++)
  372.         if (G.can_set( a, x, y ))
  373.         {
  374.             G.set_num( a, x, y );
  375.             dfs2( x, y );
  376.             G.unset_num( a, x, y );
  377.         }
  378. }
  379.  
  380. long long process_band( BAND band )
  381. {
  382.     int nums[] = { 2, 3, 5, 6, 8, 9 };
  383.     long long res = 0;
  384.  
  385.     for (int i=1; i<6; i++)
  386.         for (int j=i+1; j<6; j++)
  387.         {
  388.             G.clear();
  389.  
  390.             for (int a=0; a<3; a++)
  391.                 for (int b=0; b<3; b++)
  392.                     for (int c=0; c<3; c++)
  393.                         G.set_num( band.m[a][b][c], b, a*3+c );
  394.  
  395.             G.set_num( nums[0], 3, 0 );
  396.             G.set_num( nums[i], 4, 0 );
  397.             G.set_num( nums[j], 5, 0 );
  398.             int t = 6;
  399.             for (int k=1; k<6; k++)
  400.                 if (k!=i && k!=j)
  401.                     G.set_num( nums[k], t++, 0 );
  402.             // starting grid is complete
  403.             //G.print();
  404.  
  405.             grids_count = 0;
  406.             dfs2( 8, 0 );
  407.             res += grids_count;
  408.             fprintf( stderr, "." );
  409.         }
  410.  
  411.     return res;
  412. }
  413.  
  414. void solution()
  415. {
  416.     vector< BAND > bands = gen_all_bands();
  417.  
  418.     vector< int > comp_sizes;
  419.     vector< BAND > ident_bands;
  420.     for (int i=0; i<(int)bands.size(); i++)
  421.         if (used_bands.find( bands[i] ) == used_bands.end())
  422.         {
  423.             comp_size = 0;
  424.             dfs( bands[i] );
  425.             comp_sizes.push_back( comp_size );
  426.             ident_bands.push_back( bands[i] );
  427.         }
  428.  
  429.     printf( "number of connected components %d\n", (int)comp_sizes.size() ); // 416 components
  430.     //for (int i=0; i<(int)comp_sizes.size(); i++)
  431.     //  printf( "%d ", comp_sizes[i] );
  432.  
  433.     long long answer = 0;
  434.     for (int i=0; i<(int)comp_sizes.size(); i++)
  435.     {
  436.         fprintf( stderr, "process band %d/%d", i, (int)comp_sizes.size() );
  437.         long long tmp = process_band( ident_bands[i] );
  438.         answer += tmp*comp_sizes[i];
  439.         fprintf( stderr, "ok grids=%lld\n", tmp );
  440.         printf( "%2d/%2d %5d x %10lld\n", i, (int)comp_sizes.size(), comp_sizes[i], tmp );
  441.     }
  442.     printf( "total number of sudoku %lld*9!*72*72\n", answer );
  443.     printf( "total time %d sec\n", (int)(clock()/CLOCKS_PER_SEC) );
  444. }
  445.  
  446. int main()
  447. {
  448.     freopen("input.txt","r",stdin);
  449.     freopen("output.txt","w",stdout);
  450.  
  451.     solution();
  452.     return 0;
  453. }


Editing is locked.