Last visit was: It is currently Thu Mar 28, 2024 10:29 am


All times are UTC-05:00




Post new topic Reply to topic  [64 posts ] 
Author Message
 Post subject:
PostPosted:Mon Aug 13, 2007 9:17 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
Thanks that did it.

Edit:P.S. for anyone else that is C++ handicapped I was getting those errors because I had #include "stdafx.h" as the third line. It has to be the first.

FrenchFrog, I optimized the code in your program, I'd be interested to see how your compiled (assuming you have lowlevel optimizations) works against mine.


Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 8:54 am 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
Ok, reference time (the code posted above):
Quote:
0 # of solutions for 2 x 2 = 0
0 # of solutions for 3 x 3 = 0
0 # of solutions for 4 x 4 = 2
0 # of solutions for 5 x 5 = 10
0 # of solutions for 6 x 6 = 4
0 # of solutions for 7 x 7 = 40
0 # of solutions for 8 x 8 = 92
0 # of solutions for 9 x 9 = 352
16 # of solutions for 10 x 10 = 724
31 # of solutions for 11 x 11 = 2680
172 # of solutions for 12 x 12 = 14200
1047 # of solutions for 13 x 13 = 73712
6828 # of solutions for 14 x 14 = 365596
46750 # of solutions for 15 x 15 = 2279184
My improved code:
Quote:
0 # of solutions for 2 x 2 = 0
0 # of solutions for 3 x 3 = 0
0 # of solutions for 4 x 4 = 2
0 # of solutions for 5 x 5 = 10
0 # of solutions for 6 x 6 = 4
0 # of solutions for 7 x 7 = 40
0 # of solutions for 8 x 8 = 92
0 # of solutions for 9 x 9 = 352
0 # of solutions for 10 x 10 = 724
0 # of solutions for 11 x 11 = 2680
31 # of solutions for 12 x 12 = 14200
172 # of solutions for 13 x 13 = 73712
938 # of solutions for 14 x 14 = 365596
6515 # of solutions for 15 x 15 = 2279184
Code:
10 16 0 0.00% 11 31 0 0.00% 12 172 31 18.02% 13 1047 172 16.43% 14 6828 938 13.74% 15 46750 6515 13.94%
EDIT: Just for fun, how does it stack up against the very optimized programs you posted earlier?


Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 11:50 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
Quote:
Here's the results for my optimized version of your code.

0 # of solutions for 2 x 2 = 0
0 # of solutions for 3 x 3 = 0
0 # of solutions for 4 x 4 = 2
0 # of solutions for 5 x 5 = 10
0 # of solutions for 6 x 6 = 4
0 # of solutions for 7 x 7 = 40
0 # of solutions for 8 x 8 = 92
0 # of solutions for 9 x 9 = 352
0 # of solutions for 10 x 10 = 724
62 # of solutions for 11 x 11 = 2680
328 # of solutions for 12 x 12 = 14200
2031 # of solutions for 13 x 13 = 73712
13125 # of solutions for 14 x 14 = 365596
Just for fun what kind of machine are you running? Also the optimized thing I posted earlier was garbage.


Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 12:39 pm 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
Quote:
Just for fun what kind of machine are you running?
I think the best way to get meaningful result is to run on your computer the original code I posted and than compare it to your optimized build.

Then produce small table with the results:
Code:
10 16 0 0.00% 11 31 0 0.00% 12 172 31 18.02% 13 1047 172 16.43% 14 6828 938 13.74% 15 46750 6515 13.94%


Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 2:56 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
How do I do the small table?

But here is your unoptimized code.
Quote:
0 # of solutions for 2 x 2 = 0
0 # of solutions for 3 x 3 = 0
0 # of solutions for 4 x 4 = 2
0 # of solutions for 5 x 5 = 10
0 # of solutions for 6 x 6 = 4
0 # of solutions for 7 x 7 = 40
0 # of solutions for 8 x 8 = 92
15 # of solutions for 9 x 9 = 352
63 # of solutions for 10 x 10 = 724
359 # of solutions for 11 x 11 = 2680
2109 # of solutions for 12 x 12 = 14200
14313 # of solutions for 13 x 13 = 73712
82281 # of solutions for 14 x 14 = 365596
This is my optimization of your code.
Quote:
0 # of solutions for 2 x 2 = 0
0 # of solutions for 3 x 3 = 0
0 # of solutions for 4 x 4 = 2
0 # of solutions for 5 x 5 = 10
0 # of solutions for 6 x 6 = 4
0 # of solutions for 7 x 7 = 40
0 # of solutions for 8 x 8 = 92
0 # of solutions for 9 x 9 = 352
15 # of solutions for 10 x 10 = 724
63 # of solutions for 11 x 11 = 2680
328 # of solutions for 12 x 12 = 14200
2078 # of solutions for 13 x 13 = 73712
17359 # of solutions for 14 x 14 = 365596


Last edited by Gwanky on Tue Aug 14, 2007 3:18 pm, edited 1 time in total.

Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 3:17 pm 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
Quote:
How do I do the small table?
Excel?

+
Code:
int main() { FILE *out = fopen( "out.txt", "w" ); const int n = 15; for ( int i = 2; i <= n; i++ ) { clock_t init = clock(); unsigned long nbSol = nQueens( i ); clock_t final = clock(); printf( "%10u # of solutions for %d x %d = %u\n", (unsigned int)( (final - init) * 1000 / CLOCKS_PER_SEC ), i, i, nbSol ); fprintf( out, "%d\t%u\n", i, (unsigned int)( (final - init) * 1000 / CLOCKS_PER_SEC ) ); } fclose( out ); printf( "\nPress a key\n" ); getchar(); return 0; }
But I guess you can easily do it by hand with only the 3 biggest N ...

EDIT: I quick look at your number reveal that our code is pretty much the same speed


Last edited by frenchfrog on Tue Aug 14, 2007 3:25 pm, edited 1 time in total.

Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 3:25 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
I kind of suck at coding :( , I keep getting errors whenever I try to implant the Excel code you gave me.


Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 3:26 pm 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
I mean, you open the out.txt generated file in your favorite text editor and copy/paste it in Excel.

But like I said earlier just do it by hand.


EDIT: Your numbers, they are good :)
Code:
11 359 63 17.55% 12 2109 328 15.55% 13 14313 2078 14.52% 14 82281 17359 21.10%


Last edited by frenchfrog on Tue Aug 14, 2007 3:30 pm, edited 2 times in total.

Top
Offline  
 Post subject:
PostPosted:Tue Aug 14, 2007 3:29 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
I mean, you open the out.txt generated file in your favorite text editor and copy/paste it in Excel.

But like I said earlier just do it by hand.
On Windows, I just use the 'mark' feature in the command prompt to select a column of floating point values (representing seconds) and then drop them into excel. It converts them to numbers when I paste, so long as they have no non-numeric characters in them, like 's' representing the unit type, etc.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Wed Aug 15, 2007 9:14 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
Quick tip to everyone that's using Microsoft Visual Studio 2005 (or 2003 or 6.0), download the Intel C++ compiler, it will automatically optimize code for you, and it integrates fine into Visual Studio 6.0 and higher.


Top
Offline  
 Post subject:
PostPosted:Wed Aug 15, 2007 5:41 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
Quick tip to everyone that's using Microsoft Visual Studio 2005 (or 2003 or 6.0), download the Intel C++ compiler, it will automatically optimize code for you, and it integrates fine into Visual Studio 6.0 and higher.
You're making a common programmer error. Assuming that the compiler can optimize well enough that the programmer doesn't have to. Intel's compiler is fantastic, indeed, but it's still depending on the programmer to write a good algorithm. Also, the SSE2 build of Onlink was built with Intel's C++ Compiler v10.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Thu Aug 16, 2007 1:00 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
I never suggested it in lue of good programing but it certainly is a helpful tool.

Tycho just an idea, maybe you should have the next challenge be more free form, and less math oriented. Like you have a specific task that has to be accomplished and we can approach it anyway we want.


Top
Offline  
 Post subject:
PostPosted:Thu Aug 16, 2007 9:01 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
You said it would "automatically optimize code for you", which implied to me that since it does so, you don't have to. If that wasn't your intent, I apologize, but other people may read it as I did.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Mon Aug 27, 2007 8:43 am 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
bah, here the untouched umipressive code I posted benchmark above with (since the end of the challenge is very near):
Code:
#include <stdio.h> #include <stdlib.h> #include <time.h> unsigned long nQueens2Small( int n, int x0 ) { int row[sizeof(unsigned long) * 8 / 2]; unsigned long rowMask[sizeof(unsigned long) * 8 / 2]; unsigned long nbSol = 0; int y = 2; int xstart = 0; row[0] = x0; unsigned long maskCol = 1 << x0; rowMask[1] = 1L << ( x0 - 1 ); rowMask[1] |= 1L << ( x0 + 1 ); rowMask[1] |= 1 << x0; while ( y >= 2 ) { for ( int x = xstart; x < n; x++ ) { if ( !( rowMask[y - 1] & ( 1L << ( row[y - 1] = x ) ) ) ) { if ( y < n ) { y++; maskCol |= 1 << x; unsigned long masky = 0; for ( int i = 1; i < y; i++ ) { int rowVal = row[y - i - 1]; masky |= 1L << ( rowVal - i ); masky |= 1L << ( rowVal + i ); } rowMask[y - 1] = masky | maskCol; x = -1; // to start the next for at 0 } else { nbSol++; break; } } } y--; xstart = row[y - 1] + 1; maskCol ^= 1L << row[y - 1]; } return nbSol; } unsigned long nQueens2Medium( int n, int x0 ) { int row[sizeof(unsigned long) * 8]; unsigned long rowMask[sizeof(unsigned long) * 8]; unsigned long nbSol = 0; int y = 2; int xstart = 0; row[0] = x0; unsigned long maskCol = 1 << x0; rowMask[1] = 1 << x0; if ( x0 - 1 >= 0 ) rowMask[1] |= 1L << ( x0 - 1 ); if ( x0 + 1 < n ) rowMask[1] |= 1L << ( x0 + 1 ); while ( y >= 2 ) { for ( int x = xstart; x < n; x++ ) { if ( !( rowMask[y - 1] & ( 1L << ( row[y - 1] = x ) ) ) ) { if ( y < n ) { y++; maskCol |= 1 << x; unsigned long masky = 0; for ( int i = 1; i < y; i++ ) { int rowVal = row[y - i - 1]; if ( rowVal - i >= 0 ) masky |= 1L << ( rowVal - i ); if ( rowVal + i < n ) masky |= 1L << ( rowVal + i ); } rowMask[y - 1] = masky | maskCol; x = -1; // to start the next for at 0 } else { nbSol++; break; } } } y--; xstart = row[y - 1] + 1; maskCol ^= 1L << row[y - 1]; } return nbSol; } inline bool nQueens2LargeSafe( int *row, int x, int y ) { for ( int i = 1; i <= y; i++ ) { int rowVal = row[y - i]; if ( rowVal == x || rowVal == x - i || rowVal == x + i ) return false; } return true; } unsigned long nQueens2Large( int n, int x0 ) { int *row = new int[n]; unsigned long nbSol = 0; int y = 2; int xstart = 0; row[0] = x0; while ( y >= 2 ) { for ( int x = xstart; x < n; x++ ) { if ( nQueens2LargeSafe( row, row[y - 1] = x, y - 1 ) ) { if ( y < n ) { y++; x = -1; // to start the next for at 0 } else { nbSol++; break; } } } y--; xstart = row[y - 1] + 1; } delete [] row; return nbSol; } unsigned long nQueens( int n ) { if ( n == 1 ) return 1; unsigned long nbSolLeft = 0, nbSolMid = 0; int limit = ( n - 1 ) >> 1; for ( int x = 0; x <= limit; x++ ) { unsigned long nbSolTemp; if ( sizeof(unsigned long) * 8 / 2 >= n ) nbSolTemp = nQueens2Small( n, x ); else if ( sizeof(unsigned long) * 8 >= n ) nbSolTemp = nQueens2Medium( n, x ); else nbSolTemp = nQueens2Large( n, x ); if ( x == limit && ( n & 1 ) ) nbSolMid += nbSolTemp; else nbSolLeft += nbSolTemp; } return ( nbSolLeft << 1 ) + nbSolMid; } int main() { //FILE *out = fopen( "out.txt", "w" ); const int n = 15; for ( int i = 2; i <= n; i++ ) { clock_t init = clock(); unsigned long nbSol = nQueens( i ); clock_t final = clock(); printf( "%10u # of solutions for %d x %d = %u\n", (unsigned int)( (final - init) * 1000 / CLOCKS_PER_SEC ), i, i, nbSol ); //fprintf( out, "%d\t%u\n", i, (unsigned int)( (final - init) * 1000 / CLOCKS_PER_SEC ) ); } //fclose( out ); printf( "\nPress a key\n" ); getchar(); return 0; }


Top
Offline  
 Post subject:
PostPosted:Tue Aug 28, 2007 1:31 am 
 

Joined:Thu Aug 09, 2007 9:09 am
Posts:26
I kept fussing around with this until the last minute, but it is still (in my time zone) the 27th.
Code:
#define NDEBUG 1 #include <algorithm> #include <bitset> #include <cassert> #include <climits> #include <cstdlib> #include <iostream> #include <iomanip> #include <vector> #include <math.h> using std::bitset; using std::clock; using std::cout; using std::endl; using std::ostream; using std::setw; using std::transform; using std::vector; /* This template contains a generic implementation of a N-queens algorithm. * The compiler should be able to optimize for speed (at the expense of code * size, which is far less important) based on the fact that N is a constant. * For efficiency, we can plug in hand-optimized implementations for any * value of N. * * The algorithm assumes that an unsigned long has at least N bits. Given * that it has at least 32 bits, and any computer capable of solving the * problem for N > 32 in any feasible amount of time will have at least a 64- * bit architecture, this seems safe. */ typedef unsigned long column_t; // A column_t is a bitfield with at most a single bit set, in the bit // position corresponding to the specified column. // This functor performs a bitwise AND on its two predicates. template <unsigned int N> struct bitwise_or { public: inline bitset<N> operator() ( const bitset<N> a, const bitset<N> b ); }; template <unsigned int N> inline bitset<N> bitwise_or<N>::operator() ( const bitset<N> a, const bitset<N> b ) { return bitset<N> ( a | b ); } template <unsigned int N> class board { /* This object represents a N * N chessboard. Internally, it maintains a * vector of bitfields, each of size N. A modern compiler should be able to * vectorize operations on these data. On most implementations, this should * fit each bitfield into the smallest appropriate integer type, permitting * a SIMD instruction such as POR. This is probably not the absolutely most * compact representation (e.g., the 5x5 board will probably need 5 bytes * instead of 4), but it should generate appropriately-aligned code for * speed. * * A 1 in the position representing any square means that a queen definitely * threatens that square. A 0 means that we do not know of any queen which * threatens that square. * * The bit positions are stored in row-major order, with the square on the * upper left represented by squares[0][0]. */ public: board (void); // We should not need to override the other implicit member functions. void clear (void); // Wipes all queens off the board; void place_queen( unsigned row, column_t column_bit ); // Place a queen, updating the board as to which squares it attacks. column_t first_safe_space( unsigned row ) const; // Returns the first column in the given row not under attack, or // (1 << N) if no such column exists. column_t next_safe_space ( unsigned row, column_t column_bit ) const; /* Returns either the first column to the right of the specified column * that is not under attack, or (1 << N) if no such column exists. */ static void initialize_attack_matrix(void); static void destroy_attack_matrix(void); private: static vector< vector< bitset<N> > > attack_matrix; vector< bitset<N> > squares; // Stores N * N bits representing the positions under attack on a N * N // chessboard. }; template <unsigned int N> vector< vector< bitset<N> > > board<N>::attack_matrix; /* Stores bitfields representing positions attacked by a queen in a given * square. The place_queen() member function fills the individual matrix * entries in as needed. * * A queen in row i, column j corresponds to the vector in * attack_matrix[ i*N + j ]. There are no entries for the last row, N-1, * because they should never be needed. Only the bitfields representing rows * i+1 through N-1 are stored. */ template <unsigned int N> board<N>::board (void) : squares( (size_t)N ) { return; } template <unsigned int N> void board<N>::clear( void ) // Wipes all queens off the board. { squares = vector< bitset<N> >( (size_t)N ); } template <unsigned int N> void board<N>::place_queen( unsigned row, column_t column_bit ) // Place a queen on the board, updating all rows below row to show which // squares are under attack. { /* One annoyance of representing column by a bitfield is that, to convert it * back to an index, we use floating-point math. This is still a constant- * time operation on modern computers. Furthermore, finding the next column * to search is also a constant-time operation. Therefore, this method * beats linear search for large N. * * We aren't using large N, so whether this is really faster is doubtful. */ const unsigned column = static_cast<unsigned> ( ilogb( static_cast<double> (column_bit) ) ); const ptrdiff_t i = N * row + column; static const bitwise_or<N> or_functor = bitwise_or<N>(); // If the test run passes all these sanity checks, it should be safe to // recompile with NDEBUG, and run without them. assert( row >= 0 ); assert( row < N - 1 ); assert( column >= 0 ); assert( column < N ); assert( squares.size() == N ); #ifndef NDEBUG { const bitset<sizeof(unsigned long) * CHAR_BIT> temp(column_bit); assert ( 1 == temp.count() ); } #endif const ptrdiff_t squares_to_fill = N - 1 - row; vector< bitset<N> > attacks; attacks.reserve( static_cast<size_t> (squares_to_fill) ); // If the requested square is already in the database, don't enter it again. if ( attack_matrix[i].empty() ) { // Find the highest square below us that is in the matrix, then fill upwards // from there. ptrdiff_t j; unsigned long shift = 0; for ( j = i + N; j < N * N - N; j += N ) if ( ! attack_matrix[j].empty() ) { attacks = attack_matrix[j]; shift = attacks.size(); break; } // If we fell through the loop, we are on the final row. If we didn't, we // are on the last filled square. In either case, we want to move one square // up. j -= N; { /* Starting with the second-to-last row, fill in the attack matrix for the * square in that row directly beneath the one we want. */ for ( ; j >= i; j -= N ) { ++shift; const bitset<N> bottom_row = column_bit | column_bit << shift | column_bit >> shift; attacks.push_back(bottom_row); attack_matrix[j] = attacks; } // end for } // end if assert ( attacks.size() == (size_t) squares_to_fill ); } // end if ( attack_matrix[i].empty() ) else attacks = attack_matrix[i]; // Now that we have the attack matrix, AND it with the board. transform ( squares.begin() + 1 + row, squares.end(), attacks.begin(), squares.begin() + 1 + row, or_functor ); } template <unsigned int N> column_t board<N>::first_safe_space( unsigned row ) const { const unsigned long to_return = squares[row].to_ulong(); return static_cast<column_t> ( ~to_return & (to_return + 1) ); } template <unsigned int N> column_t board<N>::next_safe_space( unsigned row, column_t column_bit ) const { unsigned long to_return = squares[row].to_ulong(); #ifndef NDEBUG { bitset<sizeof(column_t) * CHAR_BIT> temp(column_bit); assert ( 1 == temp.count() ); } #endif // Mask the columns up to column_bit. to_return |= column_bit; to_return |= column_bit - 1; return static_cast<column_t> ( ~to_return & (to_return + 1) ); } template <unsigned int N> void board<N>::initialize_attack_matrix (void) { attack_matrix.resize( (N - 1) * N ); } template <unsigned int N> void board<N>::destroy_attack_matrix (void) { attack_matrix.clear(); } #ifndef NDEBUG template <unsigned int N> void print_board ( const board<N> &x ) { for ( size_t i = 0; i < N; ++i ) { column_t t = x.first_safe_space(i); for ( column_t j = 1; j < 1 << N; j <<=1 ) { if ( t == j ) { cout << 'O'; t = x.next_safe_space(i, j); } else cout << 'X'; } cout << endl; } cout << endl; return ; } #endif template <unsigned int N> long solve_queens(void) { long solutions = 0; column_t j[N-1]; board<N> backtrack[N-1]; board<N>::initialize_attack_matrix(); /* Find the solutions where the queen on the first row is on the left half * of the board. For each such solution, there is a one-to-one corresp- * ondence with the solutions where that same queen is on the right half * of the board, and the solutions are reflections of each other. */ for ( j[0] = 1; j[0] < 1 << (N/2); j[0] <<= 1 ) { backtrack[0].clear(); backtrack[0].place_queen( 0, j[0] ); size_t current_row = 1; j[1] = backtrack[0].first_safe_space(1); while (true) { if ( 1 << N <= j[current_row] ) { // There are no (more) possible matches on this row. if ( 1 == current_row ) break; --current_row; j[current_row] = backtrack[current_row-1].next_safe_space( current_row, j[current_row] ); } else if ( N - 2 == current_row ) { // Descend to the final level. // // Any open spaces we find here (there should be one at most) is a // solution. Furthermore, it has a symmetric solution. backtrack[N-2] = backtrack[N-3]; backtrack[N-2].place_queen( N-2, j[N-2] ); if ( backtrack[N-2].first_safe_space(N-1) < 1 << N ) solutions += 2; j[N-2] = backtrack[N-3].next_safe_space( N-2, j[N-2] ); } else { // Descend. backtrack[current_row] = backtrack[current_row - 1]; backtrack[current_row].place_queen(current_row, j[current_row] ); ++current_row; j[current_row] = backtrack[current_row-1].first_safe_space(current_row); } // end if } // end while } // end for // If N is odd, we also need to check the middle column. The two halves of // the board on either side are symmetric, so we need only check one. if ( 1 == N % 2 ) { #ifndef NDEBUG j[0] = 1 << (N/2); #endif backtrack[0].clear(); backtrack[0].place_queen( 0, 1 << (N/2) ); // The second queen cannot be in the position diagonally below the first. for ( j[1] = 1; j[1] < 1 << (N/2 - 1); j[1] <<= 1 ) { backtrack[1] = backtrack[0]; backtrack[1].place_queen( 1, j[1] ); size_t current_row = 2; j[2] = backtrack[1].first_safe_space(2); while (true) { if ( 1 << N <= j[current_row] ) { // There are no (more) possible matches on this row. if ( 2 == current_row ) break; --current_row; j[current_row] = backtrack[current_row-1].next_safe_space( current_row, j[current_row] ); } else if ( N - 2 == current_row ) { // Descend to the final level. // // Any open spaces we find here (there should be one at most) is a // solution. Furthermore, it has a symmetric solution. backtrack[N-2] = backtrack[N-3]; backtrack[N-2].place_queen( N-2, j[N-2] ); if ( backtrack[N-2].first_safe_space(N-1) < 1 << N ) solutions += 2; j[N-2] = backtrack[N-3].next_safe_space( N-2, j[N-2] ); } else { // Descend. backtrack[current_row] = backtrack[current_row - 1]; backtrack[current_row].place_queen(current_row, j[current_row] ); ++current_row; j[current_row] = backtrack[current_row-1].first_safe_space(current_row); } // end if } // end while } // end for } // end if board<N>::destroy_attack_matrix(); return solutions; } // For the degenerate cases N < 4, we need trivial handlers: template <> long solve_queens<1> (void) { return 1; } template <> long solve_queens<2> (void) { return 0; } template <> long solve_queens<3> (void) { return 0; } long queens( unsigned n ) { switch (n) { case 1: return solve_queens<1> (); break; case 2: return solve_queens<2> (); break; case 3: return solve_queens<3> (); break; case 4: return solve_queens<4> (); break; case 5: return solve_queens<5> (); break; case 6: return solve_queens<6> (); break; case 7: return solve_queens<7> (); break; case 8: return solve_queens<8> (); break; case 9: return solve_queens<9> (); break; case 10: return solve_queens<10>(); break; case 11: return solve_queens<11>(); break; case 12: return solve_queens<12>(); break; case 13: return solve_queens<13>(); break; case 14: return solve_queens<14>(); break; default: return -1; // If you're getting -1, expand the switch block. } } int main(void) { static const unsigned start = 1; static const unsigned finish = 14; clock_t begin, end; clock_t total = 0; unsigned i; for ( i = start; i <= finish; ++i ) { long answer; begin = clock(); answer = queens(i); end = clock(); total += end - begin; cout << setw(9); cout << static_cast<double>( 1000 * (end - begin) ) / CLOCKS_PER_SEC; cout << "ms # of solutions for "; cout << setw(2) << i << " x "; cout << setw(2) << i << " = "; cout << answer << endl; } cout << "Total time: "; cout << static_cast<double>( 1000 * total ) / CLOCKS_PER_SEC; cout << "ms." << endl; return EXIT_SUCCESS; }
When I compiled with the -O3 option, I got the following output:
Code:
0ms # of solutions for 1 x 1 = 1 0ms # of solutions for 2 x 2 = 0 0ms # of solutions for 3 x 3 = 0 0ms # of solutions for 4 x 4 = 2 0ms # of solutions for 5 x 5 = 10 0ms # of solutions for 6 x 6 = 4 0ms # of solutions for 7 x 7 = 40 0ms # of solutions for 8 x 8 = 92 0ms # of solutions for 9 x 9 = 352 0ms # of solutions for 10 x 10 = 724 20ms # of solutions for 11 x 11 = 2680 80ms # of solutions for 12 x 12 = 14200 410ms # of solutions for 13 x 13 = 73712 2520ms # of solutions for 14 x 14 = 365596 Total time: 3030ms.
Your mileage may vary.


Top
Offline  
Display posts from previous: Sort by 
Post new topic Reply to topic

All times are UTC-05:00


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created by Miah with assistance from hyprnova