Advertisement
Guest User

queens.cpp

a guest
Feb 26th, 2014
211
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. // % g++ --version | head -1
  2. // g++ (GCC) 4.4.7 20120313 (Red Hat 4.4.7-4)
  3. // % grep "model name" /proc/cpuinfo | uniq
  4. // model name   : Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz
  5. // % g++ -O3 -o queens queens.cpp
  6. // % time ./queens
  7. // ./queens  0.72s user 0.00s system 99% cpu 0.724 total
  8. // % perf stat ./queens
  9. //
  10. //  Performance counter stats for './queens':
  11. //
  12. //         731.375877 task-clock                #    0.998 CPUs utilized
  13. //                  2 context-switches          #    0.000 M/sec
  14. //                  0 CPU-migrations            #    0.000 M/sec
  15. //                229 page-faults               #    0.000 M/sec
  16. //      1,958,462,628 cycles                    #    2.678 GHz                     [83.33%]
  17. //        365,587,321 stalled-cycles-frontend   #   18.67% frontend cycles idle    [83.33%]
  18. //        243,090,347 stalled-cycles-backend    #   12.41% backend  cycles idle    [66.66%]
  19. //      4,704,710,704 instructions              #    2.40  insns per cycle
  20. //                                              #    0.08  stalled cycles per insn [83.33%]
  21. //        735,945,018 branches                  # 1006.247 M/sec                   [83.32%]
  22. //         19,752,991 branch-misses             #    2.68% of all branches         [83.36%]
  23. //
  24. //        0.733080675 seconds time elapsed
  25.  
  26. #include <algorithm>
  27. // #include <cstdio>
  28. using namespace std;
  29. int main( int argc, char **argv ) {
  30.     int sols = 0;
  31.     for ( int reps = 0; reps < 10000; ++reps ) {
  32.         int cols[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
  33.         int flags[ 30 ] = { 0 };
  34.         int *nw = flags, *ne = flags + 22;
  35.         sols = 0;
  36.         for ( int it = 1; ; ++it ) {
  37.             for ( int row = 0; row < 8; ++row ) {
  38.                 if ( nw[ row + cols[ row ] ] == it ||
  39.                      ne[ row - cols[ row ] ] == it ) {
  40.                     reverse( cols + row + 1, cols + 8 );
  41.                     goto fail;
  42.                 }
  43.                 nw[ row + cols[ row ] ] = it;
  44.                 ne[ row - cols[ row ] ] = it;
  45.             }
  46.             // for ( int row = 0; row < 8; ++row )
  47.             //     printf( "%s*%s\n", "......." + 7 - cols[ row ],
  48.             //                        "......." + cols[ row ] );
  49.             // printf( "\n" );
  50.             ++sols;
  51.           fail:
  52.             if ( !next_permutation( cols, cols + 8 ) )
  53.                 break;
  54.         }
  55.     }
  56.     return sols;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement