| July 2008 |
|
September 2008 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
template < class T>
T maximum (T value1, T value2, T value3) {
T max = value1;
if( value2 > max ) max = value2;
if( value3 > max ) max = value3;
return max;
}
F_n = F_{n-1} + F_{n-2} with F_0 = 0, F_1 = 1.
The "golden ratio"
F_n/F_{n-1}
converges to the continued fraction 1 + 1/ [1 + 1/{1/1+ ..}]
= [1 + sqrt{5}] / 2 = 1.6180339887.
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1)+fib(n-2);
}
#include <iostream>
#include <cmath>
int main() {
int k, counter = 0, candidate;
for (int i = 1; i <= 500; i++) {
for (int j = i; j <= 500; j++) {
candidate = i*i+j*j;
k = floor(sqrt(candidate));
if(k > 500) continue;
if ( k*k == candidate) {
std::cout << i << " , " << j << " -> " << k << std::endl;
counter++;
}
}
}
std::cout << "Total " << counter << " triples found." << std::endl;
return 0;
}
The output is
3 , 4 -> 5 5 , 12 -> 13 6 , 8 -> 10 7 , 24 -> 25 8 , 15 -> 17 9 , 12 -> 15 9 , 40 -> 41 10 , 24 -> 26 11 , 60 -> 61 12 , 16 -> 20 12 , 35 -> 37 13 , 84 -> 85 14 , 48 -> 50 15 , 20 -> 25 15 , 36 -> 39 15 , 112 -> 113 16 , 30 -> 34 16 , 63 -> 65 17 , 144 -> 145 18 , 24 -> 30 18 , 80 -> 82 19 , 180 -> 181 20 , 21 -> 29 20 , 48 -> 52 20 , 99 -> 101 21 , 28 -> 35 21 , 72 -> 75 21 , 220 -> 221 22 , 120 -> 122 23 , 264 -> 265 24 , 32 -> 40 24 , 45 -> 51 24 , 70 -> 74 24 , 143 -> 145 25 , 60 -> 65 25 , 312 -> 313 26 , 168 -> 170 27 , 36 -> 45 27 , 120 -> 123 27 , 364 -> 365 28 , 45 -> 53 28 , 96 -> 100 28 , 195 -> 197 29 , 420 -> 421 30 , 40 -> 50 30 , 72 -> 78 30 , 224 -> 226 31 , 480 -> 481 32 , 60 -> 68 32 , 126 -> 130 32 , 255 -> 257 33 , 44 -> 55 33 , 56 -> 65 33 , 180 -> 183 34 , 288 -> 290 35 , 84 -> 91 35 , 120 -> 125 36 , 48 -> 60 36 , 77 -> 85 36 , 105 -> 111 36 , 160 -> 164 36 , 323 -> 325 38 , 360 -> 362 39 , 52 -> 65 39 , 80 -> 89 39 , 252 -> 255 40 , 42 -> 58 40 , 75 -> 85 40 , 96 -> 104 40 , 198 -> 202 40 , 399 -> 401 42 , 56 -> 70 42 , 144 -> 150 42 , 440 -> 442 44 , 117 -> 125 44 , 240 -> 244 44 , 483 -> 485 45 , 60 -> 75 45 , 108 -> 117 45 , 200 -> 205 45 , 336 -> 339 48 , 55 -> 73 48 , 64 -> 80 48 , 90 -> 102 48 , 140 -> 148 48 , 189 -> 195 48 , 286 -> 290 49 , 168 -> 175 50 , 120 -> 130 51 , 68 -> 85 51 , 140 -> 149 51 , 432 -> 435 52 , 165 -> 173 52 , 336 -> 340 54 , 72 -> 90 54 , 240 -> 246 55 , 132 -> 143 55 , 300 -> 305 56 , 90 -> 106 56 , 105 -> 119 56 , 192 -> 200 56 , 390 -> 394 57 , 76 -> 95 57 , 176 -> 185 60 , 63 -> 87 60 , 80 -> 100 60 , 91 -> 109 60 , 144 -> 156 60 , 175 -> 185 60 , 221 -> 229 60 , 297 -> 303 60 , 448 -> 452 63 , 84 -> 105 63 , 216 -> 225 63 , 280 -> 287 64 , 120 -> 136 64 , 252 -> 260 65 , 72 -> 97 65 , 156 -> 169 65 , 420 -> 425 66 , 88 -> 110 66 , 112 -> 130 66 , 360 -> 366 68 , 285 -> 293 69 , 92 -> 115 69 , 260 -> 269 70 , 168 -> 182 70 , 240 -> 250 72 , 96 -> 120 72 , 135 -> 153 72 , 154 -> 170 72 , 210 -> 222 72 , 320 -> 328 72 , 429 -> 435 75 , 100 -> 125 75 , 180 -> 195 75 , 308 -> 317 76 , 357 -> 365 77 , 264 -> 275 77 , 420 -> 427 78 , 104 -> 130 78 , 160 -> 178 80 , 84 -> 116 80 , 150 -> 170 80 , 192 -> 208 80 , 315 -> 325 80 , 396 -> 404 81 , 108 -> 135 81 , 360 -> 369 84 , 112 -> 140 84 , 135 -> 159 84 , 187 -> 205 84 , 245 -> 259 84 , 288 -> 300 84 , 437 -> 445 85 , 132 -> 157 85 , 204 -> 221 87 , 116 -> 145 87 , 416 -> 425 88 , 105 -> 137 88 , 165 -> 187 88 , 234 -> 250 88 , 480 -> 488 90 , 120 -> 150 90 , 216 -> 234 90 , 400 -> 410 91 , 312 -> 325 93 , 124 -> 155 93 , 476 -> 485 95 , 168 -> 193 95 , 228 -> 247 96 , 110 -> 146 96 , 128 -> 160 96 , 180 -> 204 96 , 247 -> 265 96 , 280 -> 296 96 , 378 -> 390 98 , 336 -> 350 99 , 132 -> 165 99 , 168 -> 195 99 , 440 -> 451 100 , 105 -> 145 100 , 240 -> 260 102 , 136 -> 170 102 , 280 -> 298 104 , 153 -> 185 104 , 195 -> 221 104 , 330 -> 346 105 , 140 -> 175 105 , 208 -> 233 105 , 252 -> 273 105 , 360 -> 375 108 , 144 -> 180 108 , 231 -> 255 108 , 315 -> 333 108 , 480 -> 492 110 , 264 -> 286 111 , 148 -> 185 112 , 180 -> 212 112 , 210 -> 238 112 , 384 -> 400 112 , 441 -> 455 114 , 152 -> 190 114 , 352 -> 370 115 , 252 -> 277 115 , 276 -> 299 117 , 156 -> 195 117 , 240 -> 267 119 , 120 -> 169 119 , 408 -> 425 120 , 126 -> 174 120 , 160 -> 200 120 , 182 -> 218 120 , 209 -> 241 120 , 225 -> 255 120 , 288 -> 312 120 , 350 -> 370 120 , 391 -> 409 120 , 442 -> 458 123 , 164 -> 205 125 , 300 -> 325 126 , 168 -> 210 126 , 432 -> 450 128 , 240 -> 272 129 , 172 -> 215 130 , 144 -> 194 130 , 312 -> 338 132 , 176 -> 220 132 , 224 -> 260 132 , 351 -> 375 132 , 385 -> 407 132 , 475 -> 493 133 , 156 -> 205 133 , 456 -> 475 135 , 180 -> 225 135 , 324 -> 351 135 , 352 -> 377 136 , 255 -> 289 136 , 273 -> 305 138 , 184 -> 230 140 , 147 -> 203 140 , 171 -> 221 140 , 225 -> 265 140 , 336 -> 364 140 , 480 -> 500 141 , 188 -> 235 144 , 165 -> 219 144 , 192 -> 240 144 , 270 -> 306 144 , 308 -> 340 144 , 420 -> 444 145 , 348 -> 377 145 , 408 -> 433 147 , 196 -> 245 150 , 200 -> 250 150 , 360 -> 390 152 , 285 -> 323 152 , 345 -> 377 153 , 204 -> 255 153 , 420 -> 447 155 , 372 -> 403 155 , 468 -> 493 156 , 208 -> 260 156 , 320 -> 356 156 , 455 -> 481 159 , 212 -> 265 160 , 168 -> 232 160 , 231 -> 281 160 , 300 -> 340 160 , 384 -> 416 161 , 240 -> 289 162 , 216 -> 270 165 , 220 -> 275 165 , 280 -> 325 165 , 396 -> 429 168 , 224 -> 280 168 , 270 -> 318 168 , 315 -> 357 168 , 374 -> 410 168 , 425 -> 457 170 , 264 -> 314 170 , 408 -> 442 171 , 228 -> 285 174 , 232 -> 290 175 , 288 -> 337 175 , 420 -> 455 176 , 210 -> 274 176 , 330 -> 374 176 , 468 -> 500 177 , 236 -> 295 180 , 189 -> 261 180 , 240 -> 300 180 , 273 -> 327 180 , 299 -> 349 180 , 385 -> 425 180 , 432 -> 468 183 , 244 -> 305 184 , 345 -> 391 185 , 444 -> 481 186 , 248 -> 310 189 , 252 -> 315 189 , 340 -> 389 190 , 336 -> 386 190 , 456 -> 494 192 , 220 -> 292 192 , 256 -> 320 192 , 360 -> 408 195 , 216 -> 291 195 , 260 -> 325 195 , 400 -> 445 196 , 315 -> 371 198 , 264 -> 330 198 , 336 -> 390 200 , 210 -> 290 200 , 375 -> 425 201 , 268 -> 335 203 , 396 -> 445 204 , 253 -> 325 204 , 272 -> 340 207 , 224 -> 305 207 , 276 -> 345 208 , 306 -> 370 208 , 390 -> 442 210 , 280 -> 350 210 , 416 -> 466 213 , 284 -> 355 216 , 288 -> 360 216 , 405 -> 459 219 , 292 -> 365 220 , 231 -> 319 222 , 296 -> 370 224 , 360 -> 424 224 , 420 -> 476 225 , 272 -> 353 225 , 300 -> 375 228 , 304 -> 380 228 , 325 -> 397 231 , 308 -> 385 231 , 392 -> 455 232 , 435 -> 493 234 , 312 -> 390 237 , 316 -> 395 238 , 240 -> 338 240 , 252 -> 348 240 , 275 -> 365 240 , 320 -> 400 240 , 364 -> 436 240 , 418 -> 482 243 , 324 -> 405 246 , 328 -> 410 249 , 332 -> 415 252 , 275 -> 373 252 , 336 -> 420 252 , 405 -> 477 255 , 340 -> 425 255 , 396 -> 471 258 , 344 -> 430 260 , 273 -> 377 260 , 288 -> 388 261 , 348 -> 435 261 , 380 -> 461 264 , 315 -> 411 264 , 352 -> 440 266 , 312 -> 410 267 , 356 -> 445 270 , 360 -> 450 273 , 364 -> 455 276 , 368 -> 460 279 , 372 -> 465 280 , 294 -> 406 280 , 342 -> 442 280 , 351 -> 449 282 , 376 -> 470 285 , 380 -> 475 288 , 330 -> 438 288 , 384 -> 480 291 , 388 -> 485 294 , 392 -> 490 297 , 304 -> 425 297 , 396 -> 495 300 , 315 -> 435 300 , 400 -> 500 319 , 360 -> 481 320 , 336 -> 464 325 , 360 -> 485 340 , 357 -> 493 Total 386 triples found.
// Peter Minuit Problem:
// calculating compound interest with several interest rates.
#include <iostream>
#include <iomanip>
using namespace std;
#include <cmath> // standard C++ math library
using std::pow; // enables program to use function pow
int main()
{
double amount; // amount on deposit at end of each year
double principal = 24.0; // initial amount before interest
double rate; // interest rate
// set floating-point number format
cout << fixed << setprecision( 2 );
// loop through interest rates 5% to 10%
for ( float rate = 0.05; rate <= 0.10; rate += 0.01 )
{
// display headers
cout << "\nInterest rate: " << rate * 100 << "%\n"
<< "Year" << setw( 30 ) << "Amount on deposit" << endl;
// calculate amount on deposit for each of ten years
for ( int year = 1626; year <= 2020; year++ )
{
// calculate new amount for specified year
amount = principal * pow( 1.0 + rate, year - 1626 );
// display the year and the amount
if ( year == 1626 || year == 2008 || year == 2010 ||
year == 2020 || year % 50 == 0 )
{
cout << setw( 4 ) << year << setw( 30 ) << amount << endl;
}
} // end inner for
} // end outer for
return 0; // indicate successful termination
} // end main
The output is
Interest rate: 5.00% Year Amount on deposit 1626 24.00 1650 77.40 1700 887.60 1750 10178.51 1800 116721.09 1850 1338487.45 1900 15348971.20 1950 176012795.34 2000 2018409163.17 2008 2982109622.84 2010 3287775863.85 2020 5355440476.68 Interest rate: 6.00% Year Amount on deposit 1626 24.00 1650 97.17 1700 1789.97 1750 32971.50 1800 607340.12 1850 11187299.88 1900 206071812.96 1950 3795875013.34 2000 69920611217.71 2008 111442833564.66 2010 125217168356.54 2020 224244882562.71 Interest rate: 7.00% Year Amount on deposit 1626 24.00 1650 121.74 1700 3586.00 1750 105633.02 1800 3111634.51 1850 91659497.14 1900 2700016142.09 1950 79534444275.77 2000 2342848151035.92 2008 4025449323524.23 2010 4608736933070.20 2020 9066083138531.02 Interest rate: 8.00% Year Amount on deposit 1626 24.00 1650 152.19 1700 7137.88 1750 334777.94 1800 15701623.93 1850 736431420.39 1900 34539818262.21 1950 1619973038303.35 2000 75979341434494.00 2008 140632456555682.95 2010 164033696783372.47 2020 354136442517305.00 Interest rate: 9.00% Year Amount on deposit 1626 24.00 1650 189.87 1700 14117.96 1750 1049776.38 1800 78058754.02 1850 5804254337.95 1900 431589881756.75 1950 32091947593857.64 2000 2386277213392541.00 2008 4754806692918464.00 2010 5649185791697433.00 2020 13373676758931714.00 Interest rate: 10.00% Year Amount on deposit 1626 24.00 1650 236.39 1700 27750.43 1750 3257646.15 1800 382417756.90 1850 44892334475.78 1900 5269948004084.08 1950 618643523221839.25 2000 72623071143725136.00 2008 155673995903236960.00 2010 188365533001560224.00 2020 488571654491750208.00Historically (actually until 1980's) the interest rate has been at the level of 10% or higher. So, Peter Minuit's heirs could have made in excess of 100,000 trillion dollars if he had decided to keep the money in bank. The Manhattan Island is certainly not worth more than a few trillion dollars today. So, from this calculation alone, it seems that Peter Minuit's investment wasn't that good. However, no existing commercial bank from 1626 has survived to this day and there was no FDIC until the great depression of 1933, so investing in real state or gold was perhaps the least risky investment. From that perspective we cannot fault Peter Minuit's decision.
#include <iostream>
const char
*PRESENTS[] = {
"\t\tA Partridge in a Pear Tree\n", "\t\tTwo Turtle Doves\n",
"\t\tThree French Hens\n", "\t\tFour Calling Birds \n",
"\t\tFive Golden Rings\n", "\t\tSix Geese a Laying\n",
"\t\tSeven Swans a Swimming\n", "\t\tEight Maids a Milking\n",
"\t\tNine Ladies Dancing\n", "\t\tTen Lords a Leaping\n",
"\t\tEleven Pipers Piping\n", "\t\tTwelve Drummers Drumming\n"},
*DAYS[] = {
"1st", "2nd", "3rd", "4th", "5th", "6th",
"7th", "8th", "9th", "10th", "11th", "12th"};
void PrintTwelveDaysSong()
{
for (int i = 0; i < 12; ++i) {
printf("\n\tOn the %s day of Christmas my true love sent to me\n", DAYS[i]);
for (int j = i; j > 0; --j) std::cout << PRESENTS[j];
if (i > 0) std::cout << "\t\tand\n";
std::cout<< PRESENTS[0];
}
}
/* Main function */
int main()
{
PrintTwelveDaysSong();
return 0;
}
And the output is
On the 1st day of Christmas my true love sent to me A Partridge in a Pear Tree On the 2nd day of Christmas my true love sent to me Two Turtle Doves and A Partridge in a Pear Tree On the 3rd day of Christmas my true love sent to me Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 4th day of Christmas my true love sent to me Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 5th day of Christmas my true love sent to me Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 6th day of Christmas my true love sent to me Six Geese a Laying Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 7th day of Christmas my true love sent to me Seven Swans a Swimming Six Geese a Laying Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 8th day of Christmas my true love sent to me Eight Maids a Milking Seven Swans a Swimming Six Geese a Laying Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 9th day of Christmas my true love sent to me Nine Ladies Dancing Eight Maids a Milking Seven Swans a Swimming Six Geese a Laying Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 10th day of Christmas my true love sent to me Ten Lords a Leaping Nine Ladies Dancing Eight Maids a Milking Seven Swans a Swimming Six Geese a Laying Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 11th day of Christmas my true love sent to me Eleven Pipers Piping Ten Lords a Leaping Nine Ladies Dancing Eight Maids a Milking Seven Swans a Swimming Six Geese a Laying Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree On the 12th day of Christmas my true love sent to me Twelve Drummers Drumming Eleven Pipers Piping Ten Lords a Leaping Nine Ladies Dancing Eight Maids a Milking Seven Swans a Swimming Six Geese a Laying Five Golden Rings Four Calling Birds Three French Hens Two Turtle Doves and A Partridge in a Pear Tree
#include < iostream>
void hanoi( int from, int to, int temp, int count)
{
if(count>1) {
// Move all disks smaller than this one over to the spare.
// So if disk size is 5, we move 4 disks to the spare.
// This leaves us with 1 disk on the source peg.
// Note the placement of the params.
// We are now using the destination peg as the spare peg.
// This causes each recursion to ping-pong the spare and dest pegs.
hanoi(from, temp, to, count-1);
// Move the remaining disk to the destination peg.
std::cout << "Move disk " << count << " from peg "
<< from << " to peg " << to << std::endl;
// Move the disks we just moved to the spare back over to the destination peg
hanoi(temp, to, from, count-1);
}
else
{
// This is our standard termination case.
// We get to here when we are operating on the smallest possible disk.
std::cout << "Move disk " << count << " from peg "
<< from << " to peg " << to << std::endl;
}
}
int main()
{
// Move 5 disks from peg 0 to peg 1 using peg 2 as a temporary.
int count = 5;
int source = 0;
int dest = 1;
int spare = 2;
std::cout << "source peg = " << source
<< ", destination peg = " << dest
<< ", spare peg = " << spare
<< ", #disks = " << count << std::endl;
hanoi( source, dest, spare, count);
return 0;
}
#include < iostream>
#include < iomanip>
#include < stdlib>
void GenerateDieRoll( int trials ) {
int seed = 909999;
srand( seed);
for (int i=0; i< trials; i++) {
std::cout << std::setw(10) << 1 + rand() %6;
if( i%5 ==0 ) std::cout << std::endl;
}
}
int Factorial( int n) {
int fact = 1;
for (int i = n; i >1; i--) fact *= i;
return fact;
}
Alternatively,
int Factorial2( int n) {
if( n<= 1) return 1; // base case
else return n * Factorial2( n-1); // recursive case
}
int gcd (int x, int y) {
if( y == 0) return x; // base case
return gcd( y, x % y); // recursive case
}
#include< iostream>
#include< ctime>
int coin()
{
int flip;
flip = rand() % 2; // assign random numbers
if (flip == 1) std::cout << "The flip was heads." << std::endl;
else cout << "The flip was tails." << endl;
return (flip);
}
void CoinFlip ()
{
int NUM_FLIPS = 100;
int heads = 0, tails = 0;
// initialize the random number generator
time_t rawtime;
srand(rawtime);
// generate and count the number of heads and tails
for (int count=1; count <= NUM_FLIPS; count++) {
int face = coin();
if (face == 1) heads++;
else tails++;
}
std::cout << "The number flips: " << NUM_FLIPS << std::endl;
std::cout << "The number of heads: " << heads << std::endl;
std::cout << "The number of tails: " << tails << std::endl;
}
#include <iostream>
void menu (char );
int encrypt ( int );
int decrypt ( int );
int main ()
{
char a; // identified a character to execute the menu func.
std::cout << "**************************************\n"
<< "* Integer Encryption/Decryption Tool *\n"
<< "**************************************\n" << std::endl;
std::cout << "(E/e) Encryption" << std::endl;
std::cout << "(D/d) Decryption" << std::endl;
std::cout << "(Q/q) Quit" << std::endl;
menu (a); // menu func starts here.
return 0;
}
void menu ( char x )
{
int a;
char code; // code is the character that user will input
std::cout << "Enter operation code: ";
std::cin >> code;
if ( code == 'e' || code == 'E') encrypt(a);
else if ( code == 'd' || code == 'D' ) decrypt(code);
else if ( code == 'q' || code == 'Q' ) std::cout << "Bye!" << std::endl;
else std::cout << "You entered an invalid operation code!" << std::endl;
}
int encrypt (int a)
{
std::cout << "**********************\n"
<< "* Encryption Process *\n"
<< "**********************\n\n"
<< "Enter the 4-digit integer to be encrypted : ";
int digit,b;
char cont;
std::cin >> digit;
int bas1,bas2,bas3,bas4;
if ( 999 < digit && digit < 10000 ) {
bas1=digit/1000;
bas2=digit/100 - 10*bas1;
bas4= digit%10;
bas3= (digit%100 -bas4)/10;
std::cout << "Encrypted integer is "
<< (bas1+7)%10
<< (bas2+7)%10
<< (bas3+7)%10
<< (bas4+7)%10
<< "." << std::endl;
return 0;
}
else {
std::cout << "You entered an invalid integer!" << std::endl;
return 1;
}
}
int decrypt ( int a)
{
std::cout << "**********************\n"
<< "* Decryption Process *\n"
<< "**********************\n\n"
<< "Enter the 4-digit integer to be decrypted : ";
int digit,c;
std::cin >> digit;
int bas1,bas2,bas3,bas4;
if ( 999 < digit && digit < 10000 ) {
bas1=digit/1000;
bas2=digit/100 - 10*bas1;
bas4= digit%10;
bas3= (digit%100 -bas4)/10;
std::cout << "Decrypted integer is " << (bas1+3)%10
<< (bas2+3)%10
<< (bas3+3)%10
<< (bas4+3)%10
<< std::endl;
return 0;
}
else {
std::cout << "You entered an invalid integer!" << std::endl;
return 1;
}
}
Here is the output
./EncryptionDecryption ************************************** * Integer Encryption/Decryption Tool * ************************************** (E/e) Encryption (D/d) Decryption (Q/q) Quit Enter operation code: e ********************** * Encryption Process * ********************** Enter the 4-digit integer to be encrypted : 4617 Encrypted integer is 1384. Enter operation code: d ********************** * Decryption Process * ********************** Enter the 4-digit integer to be decrypted : 1384 Decrypted integer is 4617
#include < string>
#include < vector>
#include < iostream>
using namespace std;
int main()
{
string input; // our input string
vector s_words; // to contain our words
string new_word; // for building the words
int count;
cout << "Enter a sentance: ";
getline (cin, input); // get our input
for (int i = 0; i < input.size(); i++) // for each char in input
{
if (input.at(i) == ' ') // if char equal to space
{
if (new_word.size() > 0) // if we have something in new_word
{
s_words.push_back(new_word); // add it to our array
new_word = ""; // clear new_word
count++;
}
continue; // go to next iteration of loop
}
new_word += input.at(i); // add char to new_word
}
s_words.push_back(new_word);
cout << "Reversed sentance: " << endl;
for (int i = count; i >= 0; i--) // for each word in reverse
cout << s_words.at(i) << " "; // cout the word
cout << endl; // and finally an endline
return 0;
}
stdout from running the above code
Enter a sentance: where the hell i am Reversed sentance: am i hell the where
#include <iostream>
#include <cmath>
int main()
{
int t1=-1, t2=-1, t3=-1, t4=-1, N=200000;
double pi=0.0;
for(int i=0; i< N; i++) {
double term = pow(-1, i%2) * 4.0 / (2*i+1);
pi += term;
if(i<10) std::cout << i << "\t" << pi << std::endl;
if( fabs(pi-3.14) < 0.01 && t1==-1) t1 = i;
if( fabs(pi-3.141) < 0.001 && t2==-1) t2 = i;
if( fabs(pi-3.1415) < 0.0001 && t3==-1) t3 = i;
if( fabs(pi-3.14159) < 0.00001 && t4==-1) t4 = i;
if( fabs(pi-3.14159265359) < 0.00000000001) break;
}
std::cout << "First term with 3.14 is i = " << t1 << std::endl;
std::cout << "First term with 3.141 is i = " << t2 << std::endl;
std::cout << "First term with 3.1415 is i = " << t3 << std::endl;
std::cout << "First term with 3.14159 is i = " << t4 << std::endl;
return 0;
}
The output is
0 4 1 2.66667 2 3.46667 3 2.89524 4 3.33968 5 2.97605 6 3.28374 7 3.01707 8 3.25237 9 3.04184 First term with 3.14 is i = 87 First term with 3.141 is i = 627 First term with 3.1415 is i = 5191 First term with 3.14159 is i = 79029
#include <iostream>
#include <ctime>
int main()
{
std::srand(time(0));
int frequency[6]={0};
for(int i=0; i<6000; i++) frequency[rand()%6]++;
for(int i=0;i<6;i++)
std::cout << i+1 << " was rolled " << frequency[i]
<< " times." << std::endl;
return 0;
}
The output is
1 was rolled 1019 times. 2 was rolled 946 times. 3 was rolled 1017 times. 4 was rolled 1014 times. 5 was rolled 993 times. 6 was rolled 1011 times.
#include <iostream>
#include <ctime>
enum Status {CONTINUE, WON, LOST };
int rollDice();
Status checkStatus(int roll);
int main()
{
//create player
std::srand(time(0));
int points = rollDice(); // first roll of the dice
Status gameStatus = checkStatus(points);
int sum;
while (gameStatus == CONTINUE) {
sum = rollDice(); // subsequent roll
if(sum == points) gameStatus = WON; // win by making point
else if(sum == 7) gameStatus = LOST; // lose by rolling 7
}
if(gameStatus == WON) std::cout << "Player wins" << std::endl;
else std::cout << "Player looses" << std::endl;
return 0;
}
int rollDice()
{
int die1 = 1 + rand() %6;
int die2 = 1 + rand() %6;
int sum = die1 + die2;
std::cout << "Player rolled " << die1 << " + " << die2
<< " = " << sum << std::endl;
return sum;
}
Status checkStatus(int roll)
{
if( roll == 2 || roll == 3 || roll == 12) return LOST;
else if(roll == 7 || roll == 11 ) return WON;
else return CONTINUE;
}
Here are the outputs from successive trials
~>./craps Player rolled 2 + 1 = 3 Player looses ~>./craps Player rolled 2 + 4 = 6 Player rolled 3 + 6 = 9 Player rolled 3 + 2 = 5 Player rolled 4 + 3 = 7 Player looses ~>./craps Player rolled 2 + 5 = 7 Player wins ~>./craps Player rolled 3 + 4 = 7 Player wins ~>./craps Player rolled 2 + 6 = 8 Player rolled 2 + 4 = 6 Player rolled 4 + 2 = 6 Player rolled 2 + 6 = 8 Player wins
#include < iostream>
#include < algorithm>
#include < string>
int main() {
std::string input; // our input string
std::cout << "Enter a number: ";
getline (std::cin, input); // get our input
std::reverse (input.begin(), input.end()); // reverse the input
std::cout << "Reversed number: " << std::atoi( input.c_str() ) << std::endl;
return 0;
}
#include< iostream>
#include< string>
#include < algorithm>
int main() {
std::string s;
std::cout<<"enter a string: ";
getline(std::cin,s);
std::transform(s.begin(), s.end(), s.begin(), toupper);
std::cout << s.c_str() << std::endl;
return 0;
}
Bucket sort:
Set up buckets for each possible element, and just
toss elements into their corresponding buckets. Then empty the buckets
in order, and the result is a sorted list.
To implement this algorithm, we can use an array to represent
buckets, where the value at each array index is the number
of elements in the corresponding bucket. We then step through the unsorted array,
reading the value of each element, going to the corresponding index in
the buckets array, and incrementing the value there.
The time complexity is O(n), however there are two
big drawbacks: we must know the maximum value of the elements
in the unsorted array and must be able to
create enough buckets in memory for every element.
Thus, bucket sort places a much higher demand on system memory than the other
sorting algorithms.
Example: Given a[10] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}
Steps:
Create a bucket b[10][10].
Put 2 in the bucket b[0][2]
6 in the bucket b[0][6]
4 in the bucket b[0][4]
8 in the bucket b[0][8]
10 in the bucket b[1][0]
12 in the bucket b[1][2]
89 in the bucket b[8][9]
68 in the bucket b[6][8]
45 in the bucket b[4][5]
37 in the bucket b[3][7]
Then enpty the buckets in order.
Merge sort:
is a divide and conquer algorithm that works in two steps.
The first step is to divide the unsorted list into n sublists, each
containing 1 element. In the second step, repeatedly merge sublists to
produce new sorted sublists until there
is only 1 sublist remaining.
The average and worst-case performance are both O(n log n).
It is more efficient than quicksort if the unsorted data can only be
accessed sequentially.
Example: Given {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}
Split: {2, 6, 4, 8, 10} {12, 89, 68, 45, 37} → {2, 6} {4, 8, 10} {12, 89} {68, 45, 37} → 2, 6, 4, {8, 10} 12, 89, 68, {45, 37} → 2, 6, 4, 8, 10, 12, 89, 68, 45, 37
Merge: {2, 6} {4, 8} {10, 12} {68, 89} {37, 45} →
{2, 4, 6, 8} {10, 12} {37, 45, 68, 89} →
{2, 4, 6, 8, 10, 12} {37, 45, 68, 89} →
{2, 4, 6, 8, 10, 12, 37, 45, 68, 89}
Quick sort:
is also a divide and conquer algorithm. It first divides a
large list into two smaller sub-lists: the low elements and the high
elements (with respect to a randomly chosen pivot). Quicksort can then
recursively sort each sub-lists.
Average time complexity is O(n log n)
and the worst-case performance is O(n2). Like merge sort, quicksort
can also be parallelized due to its divide-and-conquer nature.
An effective way to choose the pivot is a technique
called median of three: consider the first, the middle,
and the last elements in the list and take their median as pivot.
Example: Given {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}
Step 1: Using the median of three technique, let's pick 12 as the
first pivot value: {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}
Step 2: Move right from the pivot until we find a value larger than pivot,
move left from the end until we find a value smaller than pivot.
If we found both and haven't crossed the path yet then swap the elements.
When we cross path, we have found the split point.
In this particular case, the split point is 12 itself. So, we need to sort two
sublists: {2, 6, 4, 8, 10, 12} and {89, 68, 45, 37}.
Step 3: Starting with the left sub-list.
Pick 8 as pivot: {2, 6, 4, 8, 10, 12}. Repeat step 2.
Split point is 8: {2, 6, 4} and {8, 10, 12}. Continuing the recursion
process we get left sorted sub-list: {2, 4, 6, 8, 10, 12}.
Step 4: Now need to sort the right sub-list: {89, 68, 45, 37}.
Let's pick 45 as pivot and split: {89, 68}, {45, 37}. Sorting them further we
get the right sorted sub-list {37, 45, 68, 89}.
Step 5: Putting the two sorted sub-lists together we find the fully sorted output:
{2, 4, 6, 8, 10, 12, 37, 45, 68, 89}.
Q: Given an array a[10] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}, write
a program to sort this array in ascending order using bubble sort,
bucket sort, merge sort, and quick sort algorithms.
Here is the code:
#include <iostream>
void printArray(int array[], int size);
void bubble_sort(int array[], int arraySize);
void bucket_sort(int array[], int size) ;
void merge(int a[], int low, int mid, int high);
void merge_sort(int array[], int low, int high);
void quick_sort(int array[], int low, int high);
int main()
{
const int arraySize = 10;
int a[arraySize] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37};
int b[arraySize], c[arraySize], d[arraySize];
std::copy(a, a + arraySize, b);
std::copy(a, a + arraySize, c);
std::copy(a, a + arraySize, d);
// -------- print the original array ----------
std::cout << "Original array:";
printArray(a, arraySize);
// -------- perform bubble sort and print array -----
bubble_sort(a, arraySize);
std::cout << "Sorted array (Bubble sort):";
printArray(a, arraySize);
// -------- perform bucket sort and print array -----
bubble_sort(b, arraySize);
std::cout << "Sorted array (Bucket sort):";
printArray(b, arraySize);
// -------- perform merge sort and print array -----
merge_sort(c, 0, arraySize-1);
std::cout << "Sorted array (Merge sort): ";
printArray(c, arraySize);
// -------- perform quick sort and print array -----
quick_sort( d, 0, arraySize-1);
std::cout << "Sorted array (Quick sort): ";
printArray(d, arraySize);
}
void printArray(int array[], int size)
{
for( int i=0; i< size; i++) std::cout << " " << array[i];
std::cout << std::endl;
}
void bubble_sort(int array[], int size)
{
for(int i=0; i < size-1; i++) {
for(int j=0; j < size-1; j++) {
if(array[j] > array[j+1]) std::swap( array[j], array[j+1] );
}
}
}
void merge(int a[], int low, int mid, int high)
{
int h = low, i = low, j = mid+1, b[high+1];
while( (h <= mid) && (j <= high) ) {
if( a[h] <= a[j] ) { b[i] = a[h]; h++; }
else { b[i] = a[j]; j++; }
i++;
}
int start = h, end = mid;
if(h > mid) { start = j; end = high; }
for(int k=start; k <= end; k++) {
b[i] = a[k];
i++;
}
for(int k=low; k <= high; k++) a[k] = b[k];
}
void merge_sort(int array[], int low, int high)
{
int mid;
if(low < high) {
mid = (low + high) / 2;
merge_sort(array, low, mid);
merge_sort(array, mid+1, high);
merge(array, low, mid, high);
}
}
void quick_sort(int array[], int low, int high)
{
if( abs(high - low) < 2) return; //only sort if there is more than 1 element
// Initially find a random pivot
int pivotIndex = rand() % high;
int pivot = array[pivotIndex];
// Pointer to begining of array and one to the end
int* begin = &array[0];
int* end = &array[high];
// While begin < end
while( begin < end ) {
// Find the lowest bound number to swap
while( *begin < pivot ) begin++;
// Find the highest bound number to swap
while( *end > pivot ) end--;
// Do the swap
std::swap(*begin, *end);
}
quick_sort(array, 0, pivotIndex - 1); //sort elements to the left of pivot
quick_sort(array, pivotIndex + 1, high); //sort elements to the right of pivot
}
void bucket_sort(int array[], int size)
{
// use bucket[x][size] to hold the current count
int bucket[10][size+1];
// init bucket counters
for(int x = 0; x < 10; x++) bucket[x][size] = 0;
// main loop for each digit position
for(int digit = 1; digit <= 1000000000; digit *= 10) {
// array to bucket
for(int i = 0; i < size; i++) {
// get the digit 0-9
int dig = (array[i] / digit) % 10;
// add to bucket and increment count
bucket[dig][bucket[dig][size]++] = array[i];
}
// bucket to array
int idx = 0;
for(int x = 0; x < 10; x++) {
for(int y = 0; y < bucket[x][size]; y++) {
array[idx++] = bucket[x][y];
}
// reset the internal bucket counters
bucket[x][size] = 0;
}
} // end of main loop
}
The output is
~>./array_sort Original array: 2 6 4 8 10 12 89 68 45 37 Sorted array (Bubble sort): 2 4 6 8 10 12 37 45 68 89 Sorted array (Bucket sort): 2 4 6 8 10 12 37 45 68 89 Sorted array (Merge sort): 2 4 6 8 10 12 37 45 68 89 Sorted array (Quick sort): 2 4 6 8 10 12 37 45 68 89
#includeusing namespace std; struct TreeNode { int data; TreeNode *left; TreeNode *right; }; class BinaryTree { private: TreeNode *root; public: BinaryTree() { root = NULL; }; ~BinaryTree() { ClearTree(root); }; TreeNode* NewNode(int data); TreeNode* NewNode(TreeNode* x); bool isEmpty() {return (root == NULL); }; TreeNode *SearchTree(int data); int Insert(TreeNode *node); int Insert(int data); int Delete(int data); void PrintNode(TreeNode *T) { std::cout << T->data << std::endl; }; void PrintTree(TreeNode *T); int numNodes(TreeNode *T); void inorder(TreeNode *T); private: void ClearTree(TreeNode *T); }; // Helper function that allocates a new node with the // given data and NULL left and right pointers. TreeNode* BinaryTree::NewNode(int data) { TreeNode* node = new TreeNode; node->data = data; node->left = NULL; node->right = NULL; return(node); } TreeNode* BinaryTree::NewNode(TreeNode* x) { TreeNode* node = new TreeNode; node->data = x->data; node->left = x->left; node->right = x->right; return(node); } void BinaryTree::ClearTree(TreeNode *T) { if(T==NULL) return; // Nothing to clear if(T->left != NULL) ClearTree(T->left); // Clear left sub-tree if(T->right != NULL) ClearTree(T->right); // Clear right sub-tree delete T; // Destroy this node } TreeNode* BinaryTree::SearchTree(int data) { TreeNode *temp = root; while((temp != NULL) && (temp->data != data)) data < temp->data ? temp = temp->left : temp = temp->right; if(temp == NULL) return temp; // Search key not found else return(NewNode(temp)); // Found it so return a duplicate } int BinaryTree::Insert(TreeNode *node) { TreeNode *temp = root; TreeNode *back = NULL; while((temp != NULL) ) { // Loop till temp falls out of the tree back = temp; node->data < temp->data ? temp = temp->left : temp = temp->right; } // Now attach the new node to the node that back points to if(back == NULL) // Attach as root node in a new tree root = node; else node->data < back->data ? back->left = node : back->right = node; return(1); } int BinaryTree::Insert(int data) { TreeNode *newNode = NewNode(data); // Call other Insert() to do the actual insertion return(Insert(newNode)); } //////// Note: Deleting data from BST is a complicated business :( //////// int BinaryTree::Delete(int data) { TreeNode *temp = root;// Temporary node for iteration TreeNode *parent; // Parent of node to delete TreeNode *delNode; // Node to delete TreeNode *back; // Spare node for backup while((temp != NULL) && (temp->data != data)) { back = temp; data < temp->data ? temp = temp->left : temp = temp->right; } if(temp == NULL) { // Didn't find the one to delete std::cout << "Data not found. Nothing deleted.\n"; return false; } else if(temp == root) { // Deleting the root delNode = root; parent = NULL; } else { delNode = temp; parent = back; } // Start deleting // Case 1: Deleting node with no children or one child if(delNode->right == NULL) { if(parent == NULL) { // If deleting the root root = delNode->left; delete delNode; return true; } else { if(parent->left == delNode) parent->left = delNode->left; else parent->right = delNode->left; delete delNode; return true; } } else // There is at least one child { if(delNode->left == NULL) // Only 1 child and it is on the right { if(parent == NULL) { // If deleting the root root = delNode->right; delete delNode; return true; } else { if(parent->left == delNode) parent->left = delNode->right; else parent->right = delNode->right; delete delNode; return true; } } else // Case 2: Deleting node with two children { // Find the replacement value. Locate the node // containing the largest value smaller than the // key of the node being deleted. temp = delNode->left; back = delNode; while(temp->right != NULL) { back = temp; temp = temp->right; } // Copy the replacement value into the node to be deleted delNode->data = temp->data; // Remove the replacement node from the tree if(back == delNode) back->left = temp->left; else back->right = temp->left; delete temp; return true; } } } void BinaryTree::PrintTree(TreeNode *T) { if(T != NULL) { PrintTree(T->left); PrintNode(T); PrintTree(T->right); } } int BinaryTree::numNodes(TreeNode *T) { if(T == NULL) return 0; int size = 1; TreeNode *left = T->left; TreeNode *right = T->right; if (left != NULL) size += numNodes(left); if (right != NULL) size += numNodes(right); return size; } void BinaryTree::inorder(TreeNode *T) { if(T != NULL) { inorder (T->left); std::cout << T->data << std::endl; inorder (T->right); } }
class MySingleton
{
public:
static MySingleton& getInstance() {
static MySingleton instance;
return instance;
}
// other non-static member function
private:
// Private constructor
MySingleton() {};
// Prevent copy-construction
MySingleton (MySingleton const& copy); // not implemented
// Prevent assignment
MySingleton& operator = (MySingleton const& copy); // not implemented
};
#include <iostream>
#include <ctime>
const int N = 8;
/* This array represents the chess board.
We'll record the move number that takes us to a given box.*/
int visited[N][N];
/* xMove[] and yMove[] define next move of Knight. */
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
/* A utility function to check if i,j are valid indexes for N*N chessboard */
bool isSafe(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && visited[x][y] == -1;
}
/* A utility function to print solution matrix sol[N][N] */
void printSolution() {
std::cout << "-----------------------------------------------------------------" << std::endl;
for (int x = 0; x < N; x++) {
std::cout << "|";
for (int y = 0; y < N; y++)
std::cout << " " << visited[x][y] << "\t| ";
std::cout << std::endl;
}
std::cout << "-----------------------------------------------------------------" << std::endl;
}
/* A recursive utility function to solve Knight Tour problem */
bool knightsTourRecursive(int x, int y, int movei) {
int nextX, nextY;
if (movei == N*N) return true;
/* Try all next moves from the current coordinate x, y */
for (int k = 0; k < 8; k++) {
nextX = x + xMove[k];
nextY = y + yMove[k];
if (isSafe(nextX, nextY)) {
visited[nextX][nextY] = movei;
if (knightsTourRecursive(nextX, nextY, movei+1)) // recursion
return true;
else
visited[nextX][nextY] = -1; // backtracking
}
}
return false;
}
/* Run Knight's Tour program starting with a given initial position */
bool knightsTour(int initX, int initY) {
/* Initialization of solution matrix */
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
visited[x][y] = -1;
std::cout << "Starting at " << initX << " " << initY << std::endl;
// Since the Knight is initially at the origin
visited[initX][initY] = 0;
/* explore all tours using recursion */
if(!knightsTourRecursive(initX, initY, 1) ) {
std::cout << "Solution does not exist" << std::endl;
return false;
}
else
printSolution();
return true;
}
int main() {
srand( (unsigned) time(0));
int initX = rand() % N;
int initY = rand() % N;
// Good starting points: (0,0), (0,3), (0,7), (2,6), (3,2),
// (4,0), (4,2), (4,5), (7,0), (7,3), (7,4)
knightsTour(initX, initY);
return 0;
}
Some solutions:
Starting at 0 0 ----------------------------------------------------------------- | 0 | 59 | 38 | 33 | 30 | 17 | 8 | 63 | | 37 | 34 | 31 | 60 | 9 | 62 | 29 | 16 | | 58 | 1 | 36 | 39 | 32 | 27 | 18 | 7 | | 35 | 48 | 41 | 26 | 61 | 10 | 15 | 28 | | 42 | 57 | 2 | 49 | 40 | 23 | 6 | 19 | | 47 | 50 | 45 | 54 | 25 | 20 | 11 | 14 | | 56 | 43 | 52 | 3 | 22 | 13 | 24 | 5 | | 51 | 46 | 55 | 44 | 53 | 4 | 21 | 12 | ----------------------------------------------------------------- Starting at 0 3 ----------------------------------------------------------------- | 55 | 60 | 27 | 0 | 15 | 62 | 25 | 6 | | 48 | 31 | 56 | 61 | 26 | 7 | 14 | 63 | | 59 | 54 | 49 | 28 | 1 | 16 | 5 | 24 | | 32 | 47 | 30 | 57 | 50 | 23 | 8 | 13 | | 53 | 58 | 51 | 22 | 29 | 2 | 17 | 4 | | 46 | 33 | 40 | 37 | 42 | 19 | 12 | 9 | | 39 | 52 | 35 | 44 | 21 | 10 | 3 | 18 | | 34 | 45 | 38 | 41 | 36 | 43 | 20 | 11 | ----------------------------------------------------------------- Starting at 0 7 ----------------------------------------------------------------- | 59 | 44 | 25 | 38 | 61 | 8 | 23 | 0 | | 26 | 37 | 60 | 43 | 24 | 1 | 62 | 9 | | 45 | 58 | 41 | 20 | 39 | 10 | 7 | 22 | | 36 | 27 | 46 | 57 | 42 | 21 | 2 | 63 | | 47 | 56 | 35 | 40 | 19 | 4 | 11 | 6 | | 34 | 53 | 28 | 49 | 30 | 13 | 16 | 3 | | 55 | 48 | 51 | 32 | 15 | 18 | 5 | 12 | | 52 | 33 | 54 | 29 | 50 | 31 | 14 | 17 | ----------------------------------------------------------------- Starting at 2 6 ----------------------------------------------------------------- | 32 | 37 | 24 | 61 | 30 | 9 | 22 | 63 | | 39 | 60 | 31 | 10 | 23 | 62 | 29 | 8 | | 36 | 33 | 38 | 25 | 42 | 27 | 0 | 21 | | 59 | 40 | 43 | 34 | 11 | 2 | 7 | 28 | | 44 | 35 | 58 | 41 | 26 | 15 | 20 | 1 | | 57 | 54 | 47 | 50 | 17 | 12 | 3 | 6 | | 48 | 45 | 52 | 55 | 14 | 5 | 16 | 19 | | 53 | 56 | 49 | 46 | 51 | 18 | 13 | 4 | ----------------------------------------------------------------- Starting at 3 2 ----------------------------------------------------------------- | 37 | 52 | 29 | 56 | 13 | 62 | 27 | 6 | | 30 | 57 | 38 | 61 | 28 | 7 | 12 | 63 | | 51 | 36 | 53 | 24 | 55 | 14 | 5 | 26 | | 58 | 31 | 0 | 39 | 60 | 25 | 8 | 11 | | 35 | 50 | 59 | 54 | 23 | 10 | 15 | 4 | | 44 | 47 | 32 | 1 | 40 | 17 | 20 | 9 | | 49 | 34 | 45 | 42 | 19 | 22 | 3 | 16 | | 46 | 43 | 48 | 33 | 2 | 41 | 18 | 21 | ----------------------------------------------------------------- Starting at 4 0 ----------------------------------------------------------------- | 44 | 59 | 24 | 33 | 8 | 17 | 22 | 63 | | 51 | 34 | 45 | 60 | 23 | 62 | 7 | 16 | | 58 | 43 | 52 | 25 | 32 | 9 | 18 | 21 | | 35 | 50 | 27 | 46 | 61 | 20 | 15 | 6 | | 0 | 57 | 42 | 53 | 26 | 31 | 10 | 19 | | 49 | 36 | 47 | 28 | 39 | 12 | 5 | 14 | | 56 | 1 | 38 | 41 | 54 | 3 | 30 | 11 | | 37 | 48 | 55 | 2 | 29 | 40 | 13 | 4 | ----------------------------------------------------------------- Starting at 4 2 ----------------------------------------------------------------- | 30 | 33 | 58 | 45 | 28 | 15 | 6 | 63 | | 59 | 44 | 29 | 32 | 7 | 62 | 27 | 14 | | 34 | 31 | 60 | 57 | 46 | 25 | 16 | 5 | | 43 | 48 | 55 | 24 | 61 | 8 | 13 | 26 | | 54 | 35 | 0 | 47 | 56 | 21 | 4 | 17 | | 49 | 42 | 51 | 38 | 23 | 18 | 9 | 12 | | 36 | 53 | 40 | 1 | 20 | 11 | 22 | 3 | | 41 | 50 | 37 | 52 | 39 | 2 | 19 | 10 | ----------------------------------------------------------------- Starting at 4 5 ----------------------------------------------------------------- | 53 | 48 | 25 | 60 | 13 | 62 | 23 | 4 | | 44 | 59 | 52 | 47 | 24 | 5 | 12 | 63 | | 49 | 54 | 45 | 26 | 61 | 14 | 3 | 22 | | 58 | 43 | 28 | 51 | 46 | 21 | 6 | 11 | | 55 | 50 | 57 | 20 | 27 | 0 | 15 | 2 | | 42 | 33 | 36 | 29 | 38 | 17 | 10 | 7 | | 35 | 56 | 31 | 40 | 19 | 8 | 1 | 16 | | 32 | 41 | 34 | 37 | 30 | 39 | 18 | 9 | ----------------------------------------------------------------- Starting at 7 0 ----------------------------------------------------------------- | 49 | 42 | 29 | 60 | 13 | 62 | 27 | 6 | | 30 | 59 | 50 | 41 | 28 | 7 | 12 | 63 | | 43 | 48 | 57 | 24 | 61 | 14 | 5 | 26 | | 58 | 31 | 44 | 51 | 40 | 25 | 8 | 11 | | 47 | 52 | 39 | 56 | 23 | 10 | 15 | 4 | | 38 | 55 | 32 | 45 | 34 | 17 | 20 | 9 | | 53 | 46 | 1 | 36 | 19 | 22 | 3 | 16 | | 0 | 37 | 54 | 33 | 2 | 35 | 18 | 21 | ----------------------------------------------------------------- Starting at 7 3 ----------------------------------------------------------------- | 56 | 59 | 22 | 31 | 6 | 15 | 20 | 63 | | 47 | 32 | 57 | 60 | 21 | 62 | 5 | 14 | | 58 | 55 | 48 | 23 | 30 | 7 | 16 | 19 | | 33 | 46 | 25 | 54 | 61 | 18 | 13 | 4 | | 42 | 53 | 40 | 49 | 24 | 29 | 8 | 17 | | 45 | 34 | 43 | 26 | 37 | 10 | 3 | 12 | | 52 | 41 | 36 | 39 | 50 | 1 | 28 | 9 | | 35 | 44 | 51 | 0 | 27 | 38 | 11 | 2 | ----------------------------------------------------------------- Starting at 7 4 ----------------------------------------------------------------- | 45 | 60 | 27 | 50 | 11 | 62 | 25 | 4 | | 28 | 49 | 44 | 61 | 26 | 5 | 10 | 63 | | 59 | 46 | 53 | 22 | 51 | 12 | 3 | 24 | | 48 | 29 | 58 | 43 | 54 | 23 | 6 | 9 | | 57 | 42 | 47 | 52 | 21 | 8 | 13 | 2 | | 36 | 39 | 30 | 55 | 32 | 15 | 18 | 7 | | 41 | 56 | 37 | 34 | 17 | 20 | 1 | 14 | | 38 | 35 | 40 | 31 | 0 | 33 | 16 | 19 | -----------------------------------------------------------------One obvious improvement to the above program would be to use an accessibility heuristic to determine the next move of the knight instead of the brute force. We can classify each of the chess boxes according to how accessible they are, and then always moving the knight to the box (within the knight's L-shaped move, of course) that is most inaccessible. On a blank chessboard, each box in the center is rated as 8, each corner box is rated as 2, and the other boxes have accessibility numbers 3, 4, or 6 as follows:
Starting at 0 0 ----------------------------------------------------------------- | 0 | 33 | 2 | 17 | 48 | 31 | 12 | 15 | | 3 | 18 | 55 | 32 | 13 | 16 | 49 | 30 | | 56 | 1 | 34 | 47 | 54 | 51 | 14 | 11 | | 19 | 4 | 59 | 52 | 35 | 46 | 29 | 50 | | 40 | 57 | 36 | 45 | 60 | 53 | 10 | 25 | | 5 | 20 | 41 | 58 | 37 | 26 | 63 | 28 | | 42 | 39 | 22 | 7 | 44 | 61 | 24 | 9 | | 21 | 6 | 43 | 38 | 23 | 8 | 27 | 62 | ----------------------------------------------------------------- Starting at 0 1 ----------------------------------------------------------------- | 13 | 0 | 43 | 28 | 15 | 10 | 19 | 22 | | 44 | 29 | 14 | 11 | 42 | 21 | 16 | 9 | | 1 | 12 | 39 | 46 | 27 | 18 | 23 | 20 | | 30 | 45 | 56 | 63 | 38 | 41 | 8 | 17 | | 59 | 2 | 47 | 40 | 55 | 26 | 37 | 24 | | 48 | 31 | 60 | 57 | 62 | 35 | 52 | 7 | | 3 | 58 | 33 | 50 | 5 | 54 | 25 | 36 | | 32 | 49 | 4 | 61 | 34 | 51 | 6 | 53 | ----------------------------------------------------------------- Starting at 0 2 ----------------------------------------------------------------- | 40 | 31 | 0 | 15 | 52 | 29 | 10 | 13 | | 1 | 16 | 41 | 30 | 11 | 14 | 51 | 28 | | 42 | 39 | 32 | 59 | 56 | 53 | 12 | 9 | | 17 | 2 | 57 | 54 | 33 | 60 | 27 | 50 | | 38 | 43 | 34 | 61 | 58 | 55 | 8 | 23 | | 3 | 18 | 63 | 46 | 35 | 24 | 49 | 26 | | 44 | 37 | 20 | 5 | 62 | 47 | 22 | 7 | | 19 | 4 | 45 | 36 | 21 | 6 | 25 | 48 | ----------------------------------------------------------------- Starting at 0 3 ----------------------------------------------------------------- | 39 | 18 | 15 | 0 | 37 | 28 | 13 | 10 | | 16 | 1 | 38 | 29 | 14 | 11 | 36 | 27 | | 19 | 40 | 17 | 58 | 43 | 34 | 9 | 12 | | 2 | 63 | 50 | 41 | 30 | 45 | 26 | 35 | | 51 | 20 | 59 | 44 | 57 | 42 | 33 | 8 | | 60 | 3 | 62 | 49 | 54 | 31 | 46 | 25 | | 21 | 52 | 5 | 56 | 23 | 48 | 7 | 32 | | 4 | 61 | 22 | 53 | 6 | 55 | 24 | 47 | ----------------------------------------------------------------- Starting at 0 4 ----------------------------------------------------------------- | 46 | 13 | 60 | 31 | 0 | 15 | 18 | 33 | | 63 | 30 | 45 | 14 | 59 | 32 | 1 | 16 | | 12 | 47 | 56 | 61 | 44 | 17 | 34 | 19 | | 29 | 62 | 41 | 52 | 55 | 58 | 39 | 2 | | 48 | 11 | 54 | 57 | 40 | 43 | 20 | 35 | | 25 | 28 | 51 | 42 | 53 | 38 | 3 | 6 | | 10 | 49 | 26 | 23 | 8 | 5 | 36 | 21 | | 27 | 24 | 9 | 50 | 37 | 22 | 7 | 4 | ----------------------------------------------------------------- Starting at 0 5 ----------------------------------------------------------------- | 13 | 10 | 43 | 28 | 15 | 0 | 19 | 22 | | 44 | 29 | 14 | 11 | 42 | 21 | 16 | 1 | | 9 | 12 | 39 | 46 | 27 | 18 | 23 | 20 | | 30 | 45 | 56 | 63 | 38 | 41 | 2 | 17 | | 59 | 8 | 47 | 40 | 55 | 26 | 37 | 24 | | 48 | 31 | 60 | 57 | 62 | 35 | 52 | 3 | | 7 | 58 | 33 | 50 | 5 | 54 | 25 | 36 | | 32 | 49 | 6 | 61 | 34 | 51 | 4 | 53 | ----------------------------------------------------------------- Starting at 0 6 ----------------------------------------------------------------- | 62 | 15 | 30 | 33 | 50 | 17 | 0 | 3 | | 29 | 34 | 61 | 16 | 31 | 2 | 47 | 18 | | 14 | 63 | 32 | 49 | 58 | 51 | 4 | 1 | | 35 | 28 | 53 | 60 | 37 | 48 | 19 | 46 | | 54 | 13 | 36 | 57 | 52 | 59 | 38 | 5 | | 27 | 10 | 55 | 42 | 39 | 22 | 45 | 20 | | 12 | 41 | 8 | 25 | 56 | 43 | 6 | 23 | | 9 | 26 | 11 | 40 | 7 | 24 | 21 | 44 | ----------------------------------------------------------------- Starting at 0 7 ----------------------------------------------------------------- | 43 | 50 | 5 | 56 | 19 | 22 | 3 | 0 | | 6 | 57 | 42 | 49 | 4 | 1 | 18 | 21 | | 51 | 44 | 59 | 26 | 55 | 20 | 23 | 2 | | 58 | 7 | 54 | 41 | 48 | 25 | 28 | 17 | | 45 | 52 | 47 | 60 | 27 | 34 | 13 | 24 | | 8 | 61 | 38 | 53 | 40 | 31 | 16 | 29 | | 37 | 46 | 63 | 10 | 35 | 14 | 33 | 12 | | 62 | 9 | 36 | 39 | 32 | 11 | 30 | 15 | ----------------------------------------------------------------- Starting at 1 0 ----------------------------------------------------------------- | 39 | 18 | 1 | 20 | 41 | 36 | 3 | 6 | | 0 | 21 | 40 | 37 | 2 | 5 | 44 | 35 | | 17 | 38 | 19 | 50 | 45 | 42 | 7 | 4 | | 22 | 51 | 58 | 47 | 30 | 49 | 34 | 43 | | 63 | 16 | 23 | 52 | 57 | 46 | 29 | 8 | | 24 | 13 | 62 | 59 | 48 | 31 | 54 | 33 | | 15 | 60 | 11 | 26 | 53 | 56 | 9 | 28 | | 12 | 25 | 14 | 61 | 10 | 27 | 32 | 55 | ----------------------------------------------------------------- Starting at 1 1 ----------------------------------------------------------------- | 54 | 13 | 40 | 1 | 46 | 23 | 38 | 3 | | 41 | 0 | 53 | 24 | 39 | 2 | 47 | 22 | | 14 | 55 | 12 | 45 | 52 | 49 | 4 | 37 | | 11 | 42 | 63 | 50 | 25 | 44 | 21 | 48 | | 56 | 15 | 32 | 43 | 58 | 51 | 36 | 5 | | 31 | 10 | 57 | 62 | 35 | 26 | 59 | 20 | | 16 | 33 | 8 | 29 | 18 | 61 | 6 | 27 | | 9 | 30 | 17 | 34 | 7 | 28 | 19 | 60 | ----------------------------------------------------------------- Starting at 1 2 ----------------------------------------------------------------- | 1 | 34 | 3 | 18 | 43 | 32 | 13 | 16 | | 4 | 19 | 0 | 33 | 14 | 17 | 46 | 31 | | 35 | 2 | 37 | 44 | 49 | 42 | 15 | 12 | | 20 | 5 | 56 | 41 | 38 | 45 | 30 | 47 | | 63 | 36 | 39 | 50 | 55 | 48 | 11 | 26 | | 6 | 21 | 60 | 57 | 40 | 27 | 52 | 29 | | 59 | 62 | 23 | 8 | 51 | 54 | 25 | 10 | | 22 | 7 | 58 | 61 | 24 | 9 | 28 | 53 | ----------------------------------------------------------------- Starting at 1 3 ----------------------------------------------------------------- | 62 | 1 | 18 | 21 | 52 | 11 | 16 | 13 | | 19 | 22 | 61 | 0 | 17 | 14 | 47 | 10 | | 2 | 63 | 20 | 53 | 48 | 51 | 12 | 15 | | 23 | 36 | 49 | 60 | 43 | 38 | 9 | 46 | | 58 | 3 | 54 | 37 | 50 | 45 | 42 | 29 | | 35 | 24 | 59 | 44 | 55 | 30 | 39 | 8 | | 4 | 57 | 26 | 33 | 6 | 41 | 28 | 31 | | 25 | 34 | 5 | 56 | 27 | 32 | 7 | 40 | ----------------------------------------------------------------- Starting at 1 4 ----------------------------------------------------------------- | 41 | 16 | 43 | 18 | 39 | 34 | 1 | 4 | | 44 | 19 | 40 | 35 | 0 | 3 | 38 | 33 | | 15 | 42 | 17 | 46 | 49 | 36 | 5 | 2 | | 20 | 45 | 62 | 51 | 28 | 47 | 32 | 37 | | 63 | 14 | 21 | 48 | 61 | 50 | 27 | 6 | | 22 | 11 | 60 | 55 | 52 | 29 | 58 | 31 | | 13 | 54 | 9 | 24 | 59 | 56 | 7 | 26 | | 10 | 23 | 12 | 53 | 8 | 25 | 30 | 57 | ----------------------------------------------------------------- Starting at 1 5 ----------------------------------------------------------------- | 62 | 13 | 28 | 35 | 50 | 15 | 30 | 1 | | 27 | 36 | 61 | 14 | 29 | 0 | 47 | 16 | | 12 | 63 | 34 | 49 | 58 | 51 | 2 | 31 | | 37 | 26 | 53 | 60 | 33 | 48 | 17 | 46 | | 54 | 11 | 38 | 57 | 52 | 59 | 32 | 3 | | 25 | 8 | 55 | 42 | 39 | 20 | 45 | 18 | | 10 | 41 | 6 | 23 | 56 | 43 | 4 | 21 | | 7 | 24 | 9 | 40 | 5 | 22 | 19 | 44 | ----------------------------------------------------------------- Starting at 1 6 ----------------------------------------------------------------- | 63 | 12 | 57 | 24 | 59 | 14 | 49 | 18 | | 40 | 25 | 60 | 13 | 56 | 17 | 0 | 15 | | 11 | 62 | 41 | 58 | 23 | 48 | 19 | 50 | | 26 | 39 | 32 | 61 | 52 | 55 | 16 | 1 | | 33 | 10 | 53 | 42 | 47 | 22 | 51 | 20 | | 38 | 27 | 36 | 31 | 54 | 43 | 2 | 5 | | 9 | 34 | 29 | 46 | 7 | 4 | 21 | 44 | | 28 | 37 | 8 | 35 | 30 | 45 | 6 | 3 | ----------------------------------------------------------------- Starting at 1 7 ----------------------------------------------------------------- | 22 | 25 | 8 | 47 | 20 | 1 | 6 | 3 | | 9 | 46 | 21 | 24 | 7 | 4 | 19 | 0 | | 26 | 23 | 62 | 45 | 48 | 17 | 2 | 5 | | 61 | 10 | 49 | 54 | 59 | 36 | 43 | 18 | | 50 | 27 | 60 | 63 | 44 | 57 | 16 | 35 | | 11 | 30 | 55 | 58 | 53 | 42 | 37 | 40 | | 28 | 51 | 32 | 13 | 56 | 39 | 34 | 15 | | 31 | 12 | 29 | 52 | 33 | 14 | 41 | 38 | ----------------------------------------------------------------- Starting at 2 0 ----------------------------------------------------------------- | 62 | 1 | 34 | 17 | 54 | 3 | 36 | 19 | | 33 | 16 | 61 | 2 | 35 | 18 | 49 | 4 | | 0 | 63 | 32 | 53 | 48 | 55 | 20 | 37 | | 15 | 52 | 57 | 60 | 31 | 50 | 5 | 46 | | 58 | 11 | 30 | 51 | 56 | 47 | 38 | 21 | | 29 | 14 | 59 | 42 | 39 | 24 | 45 | 6 | | 10 | 41 | 12 | 27 | 8 | 43 | 22 | 25 | | 13 | 28 | 9 | 40 | 23 | 26 | 7 | 44 | ----------------------------------------------------------------- Starting at 2 1 ----------------------------------------------------------------- | 1 | 16 | 59 | 34 | 3 | 18 | 21 | 38 | | 60 | 33 | 2 | 17 | 58 | 37 | 4 | 19 | | 15 | 0 | 63 | 56 | 35 | 20 | 39 | 22 | | 32 | 61 | 50 | 45 | 54 | 57 | 36 | 5 | | 51 | 14 | 55 | 62 | 49 | 44 | 23 | 40 | | 28 | 31 | 48 | 53 | 46 | 41 | 6 | 9 | | 13 | 52 | 29 | 26 | 11 | 8 | 43 | 24 | | 30 | 27 | 12 | 47 | 42 | 25 | 10 | 7 | ----------------------------------------------------------------- Starting at 2 2 ----------------------------------------------------------------- | 14 | 1 | 56 | 29 | 16 | 11 | 20 | 23 | | 55 | 30 | 15 | 12 | 51 | 22 | 17 | 10 | | 2 | 13 | 0 | 57 | 28 | 19 | 24 | 21 | | 31 | 54 | 41 | 50 | 39 | 52 | 9 | 18 | | 42 | 3 | 62 | 53 | 58 | 27 | 38 | 25 | | 63 | 32 | 59 | 40 | 49 | 36 | 47 | 8 | | 4 | 43 | 34 | 61 | 6 | 45 | 26 | 37 | | 33 | 60 | 5 | 44 | 35 | 48 | 7 | 46 | ----------------------------------------------------------------- Starting at 2 3 ----------------------------------------------------------------- | 45 | 14 | 39 | 32 | 1 | 16 | 19 | 34 | | 40 | 31 | 44 | 15 | 38 | 33 | 2 | 17 | | 13 | 46 | 41 | 0 | 51 | 18 | 35 | 20 | | 30 | 43 | 56 | 59 | 48 | 37 | 50 | 3 | | 63 | 12 | 47 | 42 | 57 | 52 | 21 | 36 | | 26 | 29 | 58 | 55 | 60 | 49 | 4 | 7 | | 11 | 62 | 27 | 24 | 9 | 6 | 53 | 22 | | 28 | 25 | 10 | 61 | 54 | 23 | 8 | 5 | ----------------------------------------------------------------- Starting at 2 4 Solution does not exist Starting at 2 5 ----------------------------------------------------------------- | 39 | 4 | 29 | 54 | 37 | 2 | 27 | 14 | | 30 | 55 | 38 | 3 | 28 | 13 | 36 | 1 | | 5 | 40 | 31 | 44 | 53 | 0 | 15 | 26 | | 56 | 59 | 52 | 41 | 32 | 43 | 12 | 35 | | 51 | 6 | 57 | 60 | 45 | 34 | 25 | 16 | | 58 | 61 | 48 | 33 | 42 | 19 | 22 | 11 | | 7 | 50 | 63 | 46 | 9 | 24 | 17 | 20 | | 62 | 47 | 8 | 49 | 18 | 21 | 10 | 23 | ----------------------------------------------------------------- Starting at 2 6 ----------------------------------------------------------------- | 26 | 23 | 6 | 43 | 36 | 21 | 4 | 1 | | 7 | 42 | 25 | 22 | 5 | 2 | 35 | 20 | | 24 | 27 | 44 | 39 | 60 | 37 | 0 | 3 | | 41 | 8 | 63 | 48 | 15 | 50 | 19 | 34 | | 28 | 45 | 40 | 59 | 38 | 61 | 14 | 51 | | 9 | 56 | 47 | 62 | 49 | 16 | 33 | 18 | | 46 | 29 | 54 | 11 | 58 | 31 | 52 | 13 | | 55 | 10 | 57 | 30 | 53 | 12 | 17 | 32 | ----------------------------------------------------------------- Starting at 2 7 ----------------------------------------------------------------- | 43 | 52 | 3 | 24 | 17 | 20 | 1 | 22 | | 4 | 25 | 44 | 51 | 2 | 23 | 16 | 19 | | 63 | 42 | 53 | 26 | 45 | 18 | 21 | 0 | | 54 | 5 | 62 | 57 | 50 | 33 | 28 | 15 | | 41 | 58 | 55 | 34 | 27 | 46 | 11 | 32 | | 6 | 61 | 38 | 49 | 56 | 31 | 14 | 29 | | 37 | 40 | 59 | 8 | 35 | 12 | 47 | 10 | | 60 | 7 | 36 | 39 | 48 | 9 | 30 | 13 | ----------------------------------------------------------------- Starting at 3 0 ----------------------------------------------------------------- | 51 | 16 | 19 | 2 | 55 | 46 | 21 | 4 | | 18 | 1 | 52 | 47 | 20 | 3 | 24 | 45 | | 15 | 50 | 17 | 56 | 43 | 54 | 5 | 22 | | 0 | 59 | 48 | 53 | 40 | 23 | 44 | 25 | | 49 | 14 | 63 | 42 | 57 | 32 | 39 | 6 | | 60 | 11 | 58 | 33 | 36 | 41 | 26 | 29 | | 13 | 34 | 9 | 62 | 31 | 28 | 7 | 38 | | 10 | 61 | 12 | 35 | 8 | 37 | 30 | 27 | ----------------------------------------------------------------- Starting at 3 1 ----------------------------------------------------------------- | 40 | 19 | 2 | 21 | 42 | 37 | 4 | 7 | | 1 | 22 | 41 | 38 | 3 | 6 | 45 | 36 | | 18 | 39 | 20 | 43 | 56 | 47 | 8 | 5 | | 23 | 0 | 59 | 48 | 31 | 44 | 35 | 46 | | 52 | 17 | 24 | 55 | 60 | 57 | 30 | 9 | | 25 | 14 | 53 | 58 | 49 | 32 | 63 | 34 | | 16 | 51 | 12 | 27 | 54 | 61 | 10 | 29 | | 13 | 26 | 15 | 50 | 11 | 28 | 33 | 62 | ----------------------------------------------------------------- Starting at 3 2 ----------------------------------------------------------------- | 23 | 14 | 41 | 2 | 25 | 46 | 59 | 4 | | 40 | 1 | 24 | 55 | 60 | 3 | 26 | 45 | | 15 | 22 | 13 | 42 | 47 | 56 | 5 | 58 | | 12 | 39 | 0 | 63 | 54 | 61 | 44 | 27 | | 21 | 16 | 53 | 48 | 43 | 28 | 57 | 6 | | 38 | 11 | 36 | 19 | 62 | 49 | 32 | 29 | | 17 | 20 | 9 | 52 | 31 | 34 | 7 | 50 | | 10 | 37 | 18 | 35 | 8 | 51 | 30 | 33 | ----------------------------------------------------------------- Starting at 3 3 ----------------------------------------------------------------- | 50 | 17 | 52 | 19 | 40 | 43 | 2 | 5 | | 53 | 20 | 49 | 44 | 1 | 4 | 39 | 42 | | 16 | 51 | 18 | 57 | 48 | 41 | 6 | 3 | | 21 | 54 | 63 | 0 | 45 | 56 | 47 | 38 | | 32 | 15 | 22 | 55 | 58 | 37 | 28 | 7 | | 23 | 12 | 33 | 62 | 29 | 46 | 59 | 36 | | 14 | 31 | 10 | 25 | 34 | 61 | 8 | 27 | | 11 | 24 | 13 | 30 | 9 | 26 | 35 | 60 | ----------------------------------------------------------------- Starting at 3 4 ----------------------------------------------------------------- | 41 | 14 | 35 | 38 | 29 | 16 | 31 | 20 | | 36 | 53 | 40 | 15 | 34 | 19 | 28 | 17 | | 13 | 42 | 37 | 52 | 39 | 30 | 21 | 32 | | 54 | 59 | 48 | 43 | 0 | 33 | 18 | 27 | | 49 | 12 | 55 | 60 | 51 | 26 | 1 | 22 | | 58 | 61 | 50 | 47 | 44 | 23 | 4 | 7 | | 11 | 46 | 63 | 56 | 9 | 6 | 25 | 2 | | 62 | 57 | 10 | 45 | 24 | 3 | 8 | 5 | ----------------------------------------------------------------- Starting at 3 5 ----------------------------------------------------------------- | 62 | 11 | 26 | 47 | 42 | 13 | 28 | 31 | | 25 | 46 | 61 | 12 | 27 | 30 | 41 | 14 | | 10 | 63 | 48 | 45 | 58 | 43 | 32 | 29 | | 49 | 24 | 53 | 60 | 33 | 0 | 15 | 40 | | 54 | 9 | 50 | 57 | 44 | 59 | 34 | 1 | | 23 | 6 | 55 | 52 | 35 | 18 | 39 | 16 | | 8 | 51 | 4 | 21 | 56 | 37 | 2 | 19 | | 5 | 22 | 7 | 36 | 3 | 20 | 17 | 38 | ----------------------------------------------------------------- Starting at 3 6 ----------------------------------------------------------------- | 23 | 26 | 9 | 52 | 21 | 2 | 7 | 4 | | 10 | 61 | 22 | 25 | 8 | 5 | 20 | 1 | | 27 | 24 | 53 | 60 | 51 | 18 | 3 | 6 | | 62 | 11 | 58 | 41 | 54 | 43 | 0 | 19 | | 57 | 28 | 63 | 50 | 59 | 40 | 17 | 36 | | 12 | 31 | 48 | 55 | 42 | 37 | 44 | 39 | | 29 | 56 | 33 | 14 | 49 | 46 | 35 | 16 | | 32 | 13 | 30 | 47 | 34 | 15 | 38 | 45 | ----------------------------------------------------------------- Starting at 3 7 ----------------------------------------------------------------- | 4 | 33 | 6 | 45 | 2 | 37 | 16 | 39 | | 7 | 44 | 3 | 34 | 17 | 40 | 1 | 36 | | 32 | 5 | 62 | 43 | 46 | 35 | 38 | 15 | | 57 | 8 | 31 | 48 | 55 | 18 | 41 | 0 | | 30 | 63 | 56 | 61 | 42 | 47 | 14 | 51 | | 9 | 58 | 27 | 54 | 49 | 52 | 19 | 22 | | 26 | 29 | 60 | 11 | 24 | 21 | 50 | 13 | | 59 | 10 | 25 | 28 | 53 | 12 | 23 | 20 | ----------------------------------------------------------------- Starting at 4 0 ----------------------------------------------------------------- | 10 | 27 | 12 | 43 | 8 | 25 | 48 | 41 | | 13 | 34 | 9 | 26 | 55 | 42 | 7 | 24 | | 28 | 11 | 56 | 63 | 44 | 47 | 40 | 49 | | 33 | 14 | 35 | 46 | 59 | 54 | 23 | 6 | | 0 | 29 | 60 | 57 | 62 | 45 | 50 | 39 | | 15 | 32 | 17 | 36 | 53 | 58 | 5 | 22 | | 18 | 1 | 30 | 61 | 20 | 3 | 38 | 51 | | 31 | 16 | 19 | 2 | 37 | 52 | 21 | 4 | ----------------------------------------------------------------- Starting at 4 1 ----------------------------------------------------------------- | 25 | 28 | 15 | 32 | 37 | 8 | 13 | 10 | | 16 | 33 | 26 | 29 | 14 | 11 | 38 | 7 | | 27 | 24 | 31 | 36 | 43 | 40 | 9 | 12 | | 34 | 17 | 44 | 41 | 30 | 49 | 6 | 39 | | 23 | 0 | 35 | 62 | 53 | 42 | 57 | 48 | | 18 | 61 | 20 | 45 | 58 | 63 | 50 | 5 | | 1 | 22 | 59 | 54 | 3 | 52 | 47 | 56 | | 60 | 19 | 2 | 21 | 46 | 55 | 4 | 51 | ----------------------------------------------------------------- Starting at 4 2 ----------------------------------------------------------------- | 52 | 17 | 20 | 3 | 56 | 47 | 22 | 5 | | 19 | 2 | 53 | 48 | 21 | 4 | 25 | 46 | | 16 | 51 | 18 | 57 | 44 | 55 | 6 | 23 | | 1 | 62 | 49 | 54 | 41 | 24 | 45 | 26 | | 50 | 15 | 0 | 43 | 58 | 33 | 40 | 7 | | 63 | 12 | 61 | 34 | 37 | 42 | 27 | 30 | | 14 | 35 | 10 | 59 | 32 | 29 | 8 | 39 | | 11 | 60 | 13 | 36 | 9 | 38 | 31 | 28 | ----------------------------------------------------------------- Starting at 4 3 ----------------------------------------------------------------- | 35 | 60 | 13 | 42 | 37 | 6 | 11 | 8 | | 14 | 43 | 36 | 61 | 12 | 9 | 38 | 5 | | 63 | 34 | 59 | 46 | 41 | 52 | 7 | 10 | | 44 | 15 | 62 | 55 | 58 | 47 | 4 | 39 | | 33 | 56 | 45 | 0 | 51 | 40 | 53 | 22 | | 16 | 27 | 30 | 57 | 54 | 21 | 48 | 3 | | 29 | 32 | 25 | 18 | 1 | 50 | 23 | 20 | | 26 | 17 | 28 | 31 | 24 | 19 | 2 | 49 | ----------------------------------------------------------------- Starting at 4 4 ----------------------------------------------------------------- | 14 | 11 | 16 | 35 | 6 | 9 | 26 | 31 | | 17 | 34 | 13 | 10 | 27 | 32 | 5 | 8 | | 12 | 15 | 42 | 33 | 36 | 7 | 30 | 25 | | 43 | 18 | 59 | 56 | 41 | 28 | 37 | 4 | | 60 | 57 | 44 | 53 | 0 | 55 | 24 | 29 | | 19 | 52 | 61 | 58 | 47 | 40 | 3 | 38 | | 62 | 45 | 50 | 21 | 54 | 1 | 48 | 23 | | 51 | 20 | 63 | 46 | 49 | 22 | 39 | 2 | ----------------------------------------------------------------- Starting at 4 5 ----------------------------------------------------------------- | 29 | 26 | 9 | 48 | 39 | 24 | 7 | 4 | | 10 | 47 | 28 | 25 | 8 | 5 | 38 | 23 | | 27 | 30 | 55 | 44 | 49 | 40 | 3 | 6 | | 46 | 11 | 50 | 41 | 18 | 43 | 22 | 37 | | 31 | 56 | 45 | 54 | 51 | 0 | 17 | 2 | | 12 | 63 | 52 | 59 | 42 | 19 | 36 | 21 | | 57 | 32 | 61 | 14 | 53 | 34 | 1 | 16 | | 62 | 13 | 58 | 33 | 60 | 15 | 20 | 35 | ----------------------------------------------------------------- Starting at 4 6 ----------------------------------------------------------------- | 42 | 13 | 36 | 39 | 30 | 15 | 32 | 19 | | 37 | 54 | 41 | 14 | 35 | 18 | 29 | 16 | | 12 | 43 | 38 | 55 | 40 | 31 | 20 | 33 | | 59 | 56 | 53 | 44 | 25 | 34 | 17 | 28 | | 48 | 11 | 60 | 57 | 52 | 27 | 0 | 21 | | 61 | 58 | 49 | 26 | 45 | 24 | 3 | 6 | | 10 | 47 | 62 | 51 | 8 | 5 | 22 | 1 | | 63 | 50 | 9 | 46 | 23 | 2 | 7 | 4 | ----------------------------------------------------------------- Starting at 4 7 ----------------------------------------------------------------- | 27 | 10 | 25 | 52 | 29 | 12 | 33 | 50 | | 24 | 61 | 28 | 11 | 38 | 51 | 30 | 13 | | 9 | 26 | 53 | 60 | 47 | 32 | 49 | 34 | | 62 | 23 | 58 | 37 | 54 | 39 | 14 | 31 | | 57 | 8 | 63 | 46 | 59 | 48 | 35 | 0 | | 22 | 5 | 44 | 55 | 36 | 17 | 40 | 15 | | 7 | 56 | 3 | 20 | 45 | 42 | 1 | 18 | | 4 | 21 | 6 | 43 | 2 | 19 | 16 | 41 | ----------------------------------------------------------------- Starting at 5 0 ----------------------------------------------------------------- | 13 | 28 | 9 | 62 | 23 | 26 | 7 | 60 | | 10 | 47 | 12 | 27 | 8 | 61 | 22 | 25 | | 29 | 14 | 63 | 44 | 55 | 24 | 59 | 6 | | 46 | 11 | 48 | 39 | 58 | 43 | 36 | 21 | | 15 | 30 | 45 | 54 | 37 | 56 | 5 | 42 | | 0 | 49 | 38 | 57 | 40 | 53 | 20 | 35 | | 31 | 16 | 51 | 2 | 33 | 18 | 41 | 4 | | 50 | 1 | 32 | 17 | 52 | 3 | 34 | 19 | ----------------------------------------------------------------- Starting at 5 1 ----------------------------------------------------------------- | 62 | 55 | 12 | 49 | 60 | 41 | 10 | 7 | | 13 | 50 | 61 | 54 | 11 | 8 | 35 | 40 | | 56 | 63 | 48 | 51 | 42 | 59 | 6 | 9 | | 47 | 14 | 53 | 58 | 45 | 36 | 39 | 34 | | 24 | 57 | 46 | 37 | 52 | 43 | 20 | 5 | | 15 | 0 | 25 | 44 | 21 | 38 | 33 | 30 | | 26 | 23 | 2 | 17 | 28 | 31 | 4 | 19 | | 1 | 16 | 27 | 22 | 3 | 18 | 29 | 32 | ----------------------------------------------------------------- Starting at 5 2 ----------------------------------------------------------------- | 59 | 48 | 15 | 40 | 29 | 8 | 13 | 10 | | 16 | 41 | 60 | 49 | 14 | 11 | 28 | 7 | | 63 | 58 | 47 | 32 | 39 | 30 | 9 | 12 | | 42 | 17 | 56 | 61 | 50 | 33 | 6 | 27 | | 57 | 62 | 51 | 46 | 31 | 38 | 23 | 34 | | 18 | 43 | 0 | 55 | 52 | 35 | 26 | 5 | | 1 | 54 | 45 | 20 | 3 | 24 | 37 | 22 | | 44 | 19 | 2 | 53 | 36 | 21 | 4 | 25 | ----------------------------------------------------------------- Starting at 5 3 ----------------------------------------------------------------- | 40 | 27 | 10 | 61 | 36 | 25 | 8 | 5 | | 11 | 60 | 39 | 26 | 9 | 6 | 35 | 24 | | 28 | 41 | 62 | 51 | 58 | 37 | 4 | 7 | | 63 | 12 | 59 | 38 | 19 | 50 | 23 | 34 | | 42 | 29 | 52 | 57 | 46 | 33 | 18 | 3 | | 13 | 56 | 45 | 0 | 53 | 20 | 49 | 22 | | 30 | 43 | 54 | 15 | 32 | 47 | 2 | 17 | | 55 | 14 | 31 | 44 | 1 | 16 | 21 | 48 | ----------------------------------------------------------------- Starting at 5 4 ----------------------------------------------------------------- | 33 | 30 | 7 | 16 | 47 | 44 | 5 | 18 | | 8 | 15 | 32 | 43 | 6 | 17 | 54 | 45 | | 31 | 34 | 29 | 48 | 63 | 46 | 19 | 4 | | 14 | 9 | 40 | 35 | 42 | 55 | 60 | 53 | | 39 | 28 | 13 | 56 | 49 | 62 | 3 | 20 | | 10 | 25 | 36 | 41 | 0 | 59 | 52 | 61 | | 27 | 38 | 23 | 12 | 57 | 50 | 21 | 2 | | 24 | 11 | 26 | 37 | 22 | 1 | 58 | 51 | ----------------------------------------------------------------- Starting at 5 5 ----------------------------------------------------------------- | 26 | 23 | 12 | 43 | 36 | 5 | 10 | 7 | | 13 | 42 | 25 | 22 | 11 | 8 | 35 | 4 | | 24 | 27 | 44 | 39 | 60 | 37 | 6 | 9 | | 41 | 14 | 63 | 48 | 21 | 50 | 3 | 34 | | 28 | 45 | 40 | 59 | 38 | 61 | 20 | 51 | | 15 | 56 | 47 | 62 | 49 | 0 | 33 | 2 | | 46 | 29 | 54 | 17 | 58 | 31 | 52 | 19 | | 55 | 16 | 57 | 30 | 53 | 18 | 1 | 32 | ----------------------------------------------------------------- Starting at 5 6 ----------------------------------------------------------------- | 55 | 10 | 35 | 32 | 45 | 12 | 37 | 16 | | 34 | 31 | 54 | 11 | 36 | 15 | 44 | 13 | | 9 | 56 | 33 | 52 | 49 | 46 | 17 | 38 | | 30 | 53 | 48 | 59 | 40 | 51 | 14 | 43 | | 63 | 8 | 57 | 50 | 47 | 42 | 39 | 18 | | 26 | 29 | 60 | 41 | 58 | 21 | 0 | 3 | | 7 | 62 | 27 | 24 | 5 | 2 | 19 | 22 | | 28 | 25 | 6 | 61 | 20 | 23 | 4 | 1 | ----------------------------------------------------------------- Starting at 5 7 ----------------------------------------------------------------- | 40 | 7 | 52 | 37 | 30 | 9 | 32 | 13 | | 53 | 44 | 39 | 8 | 51 | 12 | 29 | 10 | | 6 | 41 | 36 | 55 | 38 | 31 | 14 | 33 | | 45 | 54 | 43 | 58 | 35 | 50 | 11 | 28 | | 42 | 5 | 60 | 49 | 56 | 27 | 34 | 15 | | 63 | 46 | 57 | 26 | 59 | 18 | 21 | 0 | | 4 | 25 | 48 | 61 | 2 | 23 | 16 | 19 | | 47 | 62 | 3 | 24 | 17 | 20 | 1 | 22 | ----------------------------------------------------------------- Starting at 6 0 ----------------------------------------------------------------- | 24 | 31 | 14 | 63 | 26 | 7 | 12 | 9 | | 15 | 54 | 25 | 30 | 13 | 10 | 27 | 6 | | 32 | 23 | 60 | 51 | 62 | 29 | 8 | 11 | | 53 | 16 | 55 | 34 | 59 | 38 | 5 | 28 | | 22 | 33 | 52 | 61 | 50 | 35 | 42 | 37 | | 17 | 48 | 19 | 56 | 45 | 58 | 39 | 4 | | 0 | 21 | 46 | 49 | 2 | 41 | 36 | 43 | | 47 | 18 | 1 | 20 | 57 | 44 | 3 | 40 | ----------------------------------------------------------------- Starting at 6 1 ----------------------------------------------------------------- | 9 | 22 | 49 | 42 | 7 | 20 | 33 | 30 | | 50 | 43 | 8 | 21 | 48 | 31 | 6 | 19 | | 23 | 10 | 59 | 46 | 41 | 34 | 29 | 32 | | 58 | 51 | 44 | 39 | 56 | 47 | 18 | 5 | | 11 | 24 | 57 | 60 | 45 | 40 | 35 | 28 | | 52 | 61 | 12 | 25 | 38 | 55 | 4 | 17 | | 13 | 0 | 63 | 54 | 15 | 2 | 27 | 36 | | 62 | 53 | 14 | 1 | 26 | 37 | 16 | 3 | ----------------------------------------------------------------- Starting at 6 2 ----------------------------------------------------------------- | 28 | 7 | 26 | 57 | 30 | 9 | 34 | 55 | | 25 | 58 | 29 | 8 | 53 | 56 | 31 | 10 | | 6 | 27 | 62 | 59 | 48 | 33 | 54 | 35 | | 63 | 24 | 41 | 50 | 61 | 52 | 11 | 32 | | 20 | 5 | 60 | 47 | 40 | 49 | 36 | 45 | | 23 | 2 | 21 | 42 | 51 | 46 | 15 | 12 | | 4 | 19 | 0 | 39 | 14 | 17 | 44 | 37 | | 1 | 22 | 3 | 18 | 43 | 38 | 13 | 16 | ----------------------------------------------------------------- Starting at 6 3 ----------------------------------------------------------------- | 43 | 10 | 59 | 48 | 41 | 12 | 37 | 54 | | 60 | 49 | 42 | 11 | 58 | 55 | 40 | 13 | | 9 | 44 | 63 | 56 | 47 | 38 | 53 | 36 | | 50 | 61 | 26 | 45 | 52 | 57 | 14 | 39 | | 23 | 8 | 51 | 62 | 25 | 46 | 35 | 30 | | 2 | 5 | 24 | 27 | 34 | 31 | 18 | 15 | | 7 | 22 | 3 | 0 | 17 | 20 | 29 | 32 | | 4 | 1 | 6 | 21 | 28 | 33 | 16 | 19 | ----------------------------------------------------------------- Starting at 6 4 ----------------------------------------------------------------- | 62 | 45 | 12 | 37 | 26 | 5 | 10 | 7 | | 13 | 38 | 61 | 46 | 11 | 8 | 25 | 4 | | 58 | 63 | 44 | 29 | 36 | 27 | 6 | 9 | | 39 | 14 | 57 | 60 | 47 | 30 | 3 | 24 | | 56 | 59 | 48 | 43 | 28 | 35 | 20 | 31 | | 15 | 40 | 55 | 52 | 49 | 32 | 23 | 2 | | 54 | 51 | 42 | 17 | 0 | 21 | 34 | 19 | | 41 | 16 | 53 | 50 | 33 | 18 | 1 | 22 | ----------------------------------------------------------------- Starting at 6 5 ----------------------------------------------------------------- | 7 | 60 | 9 | 34 | 5 | 30 | 19 | 32 | | 10 | 51 | 6 | 59 | 20 | 33 | 4 | 29 | | 63 | 8 | 61 | 50 | 35 | 48 | 31 | 18 | | 52 | 11 | 56 | 47 | 58 | 21 | 28 | 3 | | 55 | 62 | 53 | 38 | 49 | 36 | 17 | 22 | | 12 | 41 | 44 | 57 | 46 | 25 | 2 | 27 | | 43 | 54 | 39 | 14 | 37 | 0 | 23 | 16 | | 40 | 13 | 42 | 45 | 24 | 15 | 26 | 1 | ----------------------------------------------------------------- Starting at 6 6 ----------------------------------------------------------------- | 28 | 25 | 8 | 47 | 38 | 23 | 6 | 3 | | 9 | 46 | 27 | 24 | 7 | 4 | 37 | 22 | | 26 | 29 | 48 | 41 | 50 | 39 | 2 | 5 | | 45 | 10 | 51 | 58 | 17 | 42 | 21 | 36 | | 30 | 59 | 44 | 49 | 40 | 57 | 16 | 1 | | 11 | 52 | 63 | 56 | 43 | 18 | 35 | 20 | | 60 | 31 | 54 | 13 | 62 | 33 | 0 | 15 | | 53 | 12 | 61 | 32 | 55 | 14 | 19 | 34 | ----------------------------------------------------------------- Starting at 6 7 ----------------------------------------------------------------- | 63 | 12 | 29 | 32 | 43 | 14 | 27 | 18 | | 30 | 33 | 62 | 13 | 28 | 17 | 40 | 15 | | 11 | 60 | 31 | 44 | 57 | 42 | 19 | 26 | | 34 | 49 | 58 | 61 | 24 | 39 | 16 | 41 | | 59 | 10 | 53 | 38 | 45 | 56 | 25 | 20 | | 48 | 35 | 50 | 55 | 52 | 23 | 2 | 5 | | 9 | 54 | 37 | 46 | 7 | 4 | 21 | 0 | | 36 | 47 | 8 | 51 | 22 | 1 | 6 | 3 | ----------------------------------------------------------------- Starting at 7 0 ----------------------------------------------------------------- | 31 | 36 | 11 | 38 | 41 | 50 | 9 | 6 | | 12 | 39 | 32 | 49 | 10 | 7 | 42 | 51 | | 35 | 30 | 37 | 40 | 63 | 52 | 5 | 8 | | 28 | 13 | 60 | 33 | 48 | 43 | 58 | 53 | | 23 | 34 | 29 | 44 | 59 | 62 | 19 | 4 | | 14 | 27 | 24 | 61 | 20 | 47 | 54 | 57 | | 25 | 22 | 1 | 16 | 45 | 56 | 3 | 18 | | 0 | 15 | 26 | 21 | 2 | 17 | 46 | 55 | ----------------------------------------------------------------- Starting at 7 1 ----------------------------------------------------------------- | 62 | 9 | 36 | 53 | 58 | 11 | 34 | 31 | | 37 | 50 | 61 | 10 | 35 | 32 | 57 | 12 | | 8 | 63 | 52 | 49 | 54 | 59 | 30 | 33 | | 51 | 38 | 25 | 60 | 45 | 48 | 13 | 56 | | 22 | 7 | 44 | 39 | 24 | 55 | 46 | 29 | | 1 | 4 | 23 | 26 | 47 | 40 | 17 | 14 | | 6 | 21 | 2 | 43 | 16 | 19 | 28 | 41 | | 3 | 0 | 5 | 20 | 27 | 42 | 15 | 18 | ----------------------------------------------------------------- Starting at 7 2 ----------------------------------------------------------------- | 41 | 4 | 53 | 34 | 39 | 6 | 45 | 32 | | 54 | 25 | 40 | 5 | 52 | 33 | 38 | 7 | | 3 | 42 | 57 | 62 | 35 | 44 | 31 | 46 | | 24 | 55 | 26 | 43 | 58 | 51 | 8 | 37 | | 17 | 2 | 63 | 56 | 61 | 36 | 47 | 30 | | 20 | 23 | 18 | 27 | 50 | 59 | 12 | 9 | | 1 | 16 | 21 | 60 | 11 | 14 | 29 | 48 | | 22 | 19 | 0 | 15 | 28 | 49 | 10 | 13 | ----------------------------------------------------------------- Starting at 7 3 ----------------------------------------------------------------- | 4 | 49 | 22 | 25 | 6 | 33 | 38 | 27 | | 21 | 24 | 5 | 48 | 41 | 26 | 7 | 34 | | 50 | 3 | 62 | 23 | 32 | 37 | 28 | 39 | | 57 | 20 | 51 | 42 | 47 | 40 | 35 | 8 | | 2 | 63 | 56 | 61 | 36 | 31 | 46 | 29 | | 19 | 58 | 17 | 52 | 43 | 54 | 9 | 12 | | 16 | 1 | 60 | 55 | 14 | 11 | 30 | 45 | | 59 | 18 | 15 | 0 | 53 | 44 | 13 | 10 | ----------------------------------------------------------------- Starting at 7 4 ----------------------------------------------------------------- | 29 | 26 | 9 | 48 | 39 | 24 | 7 | 4 | | 10 | 47 | 28 | 25 | 8 | 5 | 38 | 23 | | 27 | 30 | 49 | 42 | 51 | 40 | 3 | 6 | | 46 | 11 | 52 | 59 | 18 | 43 | 22 | 37 | | 31 | 56 | 45 | 50 | 41 | 58 | 17 | 2 | | 12 | 53 | 60 | 57 | 44 | 19 | 36 | 21 | | 63 | 32 | 55 | 14 | 61 | 34 | 1 | 16 | | 54 | 13 | 62 | 33 | 0 | 15 | 20 | 35 | ----------------------------------------------------------------- Starting at 7 5 ----------------------------------------------------------------- | 62 | 25 | 6 | 21 | 52 | 35 | 4 | 19 | | 7 | 22 | 61 | 36 | 5 | 20 | 47 | 34 | | 26 | 63 | 24 | 53 | 48 | 51 | 18 | 3 | | 23 | 8 | 49 | 60 | 37 | 40 | 33 | 46 | | 58 | 27 | 54 | 39 | 50 | 45 | 2 | 17 | | 9 | 12 | 59 | 44 | 55 | 38 | 41 | 32 | | 28 | 57 | 14 | 11 | 30 | 43 | 16 | 1 | | 13 | 10 | 29 | 56 | 15 | 0 | 31 | 42 | ----------------------------------------------------------------- Starting at 7 6 ----------------------------------------------------------------- | 43 | 50 | 11 | 56 | 25 | 4 | 9 | 6 | | 12 | 57 | 42 | 49 | 10 | 7 | 24 | 3 | | 51 | 44 | 59 | 28 | 55 | 26 | 5 | 8 | | 58 | 13 | 54 | 41 | 48 | 29 | 2 | 23 | | 45 | 52 | 47 | 60 | 27 | 34 | 19 | 30 | | 14 | 61 | 38 | 53 | 40 | 31 | 22 | 1 | | 37 | 46 | 63 | 16 | 35 | 20 | 33 | 18 | | 62 | 15 | 36 | 39 | 32 | 17 | 0 | 21 | ----------------------------------------------------------------- Starting at 7 7 ----------------------------------------------------------------- | 6 | 57 | 8 | 51 | 4 | 43 | 18 | 45 | | 9 | 50 | 5 | 56 | 19 | 46 | 3 | 42 | | 58 | 7 | 52 | 49 | 38 | 41 | 44 | 17 | | 53 | 10 | 61 | 40 | 55 | 20 | 47 | 2 | | 62 | 59 | 54 | 37 | 48 | 39 | 16 | 21 | | 11 | 32 | 35 | 60 | 29 | 24 | 1 | 26 | | 34 | 63 | 30 | 13 | 36 | 27 | 22 | 15 | | 31 | 12 | 33 | 28 | 23 | 14 | 25 | 0 | -----------------------------------------------------------------
#include <iostream>
const int N = 8;
int position[N];
// Check if a position is safe.
// The column position is same as the queen_number, i.e., we place
// the first queen in column 1, the second queen in column 2, etc.
bool isSafe(int queen_number, int row_position)
{
// Check each queen before this one
for (int i = 0; i < queen_number; i++) {
// Get another queen's row_position
int other_row_pos = position[i];
// Now check if they're in the same row or diagonals
if (other_row_pos == row_position || // Same row
other_row_pos == row_position - (queen_number - i) || // Same diagonal
other_row_pos == row_position + (queen_number - i)) // Same diagonal
return false;
}
return true;
}
// Place N-k queens starting with queen #k
void solveNQueens(int k)
{
if (k == N) { // We placed N-1 queens (0 included), problem solved!
// Solution found!
std::cout << "Solution: [ ";
for (int i = 0; i < N; i++)
std::cout << "(" << i+1 << "," << position[i]+1 << ") ";
std::cout << "]" << std::endl;
}
else {
for (int i = 0; i < N; i++) { // Generate ALL combinations
// Before putting the k-th queen into a row, test if it is safe
if (isSafe(k, i)) {
position[k] = i;
// Place another queen
solveNQueens(k + 1);
}
}
}
}
int main()
{
std::cout << "All possible Solutions ...\n"
<< "The coordinates of the 8-queens are given as (Row,Col).\n";
std::cout << "Note that the Rows and Colums are numbered 1--8.\n";
solveNQueens(0);
return 0;
}
There are 92 solutions for the 8 queens problem:
All possible solutions of the 8-queens problem ... The coordinates of the 8-queens are given as (Row,Col). Note that the Rows and Colums are numbered 1--8. Solution: [ (1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4) ] Solution: [ (1,1) (2,6) (3,8) (4,3) (5,7) (6,4) (7,2) (8,5) ] Solution: [ (1,1) (2,7) (3,4) (4,6) (5,8) (6,2) (7,5) (8,3) ] Solution: [ (1,1) (2,7) (3,5) (4,8) (5,2) (6,4) (7,6) (8,3) ] Solution: [ (1,2) (2,4) (3,6) (4,8) (5,3) (6,1) (7,7) (8,5) ] Solution: [ (1,2) (2,5) (3,7) (4,1) (5,3) (6,8) (7,6) (8,4) ] Solution: [ (1,2) (2,5) (3,7) (4,4) (5,1) (6,8) (7,6) (8,3) ] Solution: [ (1,2) (2,6) (3,1) (4,7) (5,4) (6,8) (7,3) (8,5) ] Solution: [ (1,2) (2,6) (3,8) (4,3) (5,1) (6,4) (7,7) (8,5) ] Solution: [ (1,2) (2,7) (3,3) (4,6) (5,8) (6,5) (7,1) (8,4) ] Solution: [ (1,2) (2,7) (3,5) (4,8) (5,1) (6,4) (7,6) (8,3) ] Solution: [ (1,2) (2,8) (3,6) (4,1) (5,3) (6,5) (7,7) (8,4) ] Solution: [ (1,3) (2,1) (3,7) (4,5) (5,8) (6,2) (7,4) (8,6) ] Solution: [ (1,3) (2,5) (3,2) (4,8) (5,1) (6,7) (7,4) (8,6) ] Solution: [ (1,3) (2,5) (3,2) (4,8) (5,6) (6,4) (7,7) (8,1) ] Solution: [ (1,3) (2,5) (3,7) (4,1) (5,4) (6,2) (7,8) (8,6) ] Solution: [ (1,3) (2,5) (3,8) (4,4) (5,1) (6,7) (7,2) (8,6) ] Solution: [ (1,3) (2,6) (3,2) (4,5) (5,8) (6,1) (7,7) (8,4) ] Solution: [ (1,3) (2,6) (3,2) (4,7) (5,1) (6,4) (7,8) (8,5) ] Solution: [ (1,3) (2,6) (3,2) (4,7) (5,5) (6,1) (7,8) (8,4) ] Solution: [ (1,3) (2,6) (3,4) (4,1) (5,8) (6,5) (7,7) (8,2) ] Solution: [ (1,3) (2,6) (3,4) (4,2) (5,8) (6,5) (7,7) (8,1) ] Solution: [ (1,3) (2,6) (3,8) (4,1) (5,4) (6,7) (7,5) (8,2) ] Solution: [ (1,3) (2,6) (3,8) (4,1) (5,5) (6,7) (7,2) (8,4) ] Solution: [ (1,3) (2,6) (3,8) (4,2) (5,4) (6,1) (7,7) (8,5) ] Solution: [ (1,3) (2,7) (3,2) (4,8) (5,5) (6,1) (7,4) (8,6) ] Solution: [ (1,3) (2,7) (3,2) (4,8) (5,6) (6,4) (7,1) (8,5) ] Solution: [ (1,3) (2,8) (3,4) (4,7) (5,1) (6,6) (7,2) (8,5) ] Solution: [ (1,4) (2,1) (3,5) (4,8) (5,2) (6,7) (7,3) (8,6) ] Solution: [ (1,4) (2,1) (3,5) (4,8) (5,6) (6,3) (7,7) (8,2) ] Solution: [ (1,4) (2,2) (3,5) (4,8) (5,6) (6,1) (7,3) (8,7) ] Solution: [ (1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,1) (8,5) ] Solution: [ (1,4) (2,2) (3,7) (4,3) (5,6) (6,8) (7,5) (8,1) ] Solution: [ (1,4) (2,2) (3,7) (4,5) (5,1) (6,8) (7,6) (8,3) ] Solution: [ (1,4) (2,2) (3,8) (4,5) (5,7) (6,1) (7,3) (8,6) ] Solution: [ (1,4) (2,2) (3,8) (4,6) (5,1) (6,3) (7,5) (8,7) ] Solution: [ (1,4) (2,6) (3,1) (4,5) (5,2) (6,8) (7,3) (8,7) ] Solution: [ (1,4) (2,6) (3,8) (4,2) (5,7) (6,1) (7,3) (8,5) ] Solution: [ (1,4) (2,6) (3,8) (4,3) (5,1) (6,7) (7,5) (8,2) ] Solution: [ (1,4) (2,7) (3,1) (4,8) (5,5) (6,2) (7,6) (8,3) ] Solution: [ (1,4) (2,7) (3,3) (4,8) (5,2) (6,5) (7,1) (8,6) ] Solution: [ (1,4) (2,7) (3,5) (4,2) (5,6) (6,1) (7,3) (8,8) ] Solution: [ (1,4) (2,7) (3,5) (4,3) (5,1) (6,6) (7,8) (8,2) ] Solution: [ (1,4) (2,8) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5) ] Solution: [ (1,4) (2,8) (3,1) (4,5) (5,7) (6,2) (7,6) (8,3) ] Solution: [ (1,4) (2,8) (3,5) (4,3) (5,1) (6,7) (7,2) (8,6) ] Solution: [ (1,5) (2,1) (3,4) (4,6) (5,8) (6,2) (7,7) (8,3) ] Solution: [ (1,5) (2,1) (3,8) (4,4) (5,2) (6,7) (7,3) (8,6) ] Solution: [ (1,5) (2,1) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4) ] Solution: [ (1,5) (2,2) (3,4) (4,6) (5,8) (6,3) (7,1) (8,7) ] Solution: [ (1,5) (2,2) (3,4) (4,7) (5,3) (6,8) (7,6) (8,1) ] Solution: [ (1,5) (2,2) (3,6) (4,1) (5,7) (6,4) (7,8) (8,3) ] Solution: [ (1,5) (2,2) (3,8) (4,1) (5,4) (6,7) (7,3) (8,6) ] Solution: [ (1,5) (2,3) (3,1) (4,6) (5,8) (6,2) (7,4) (8,7) ] Solution: [ (1,5) (2,3) (3,1) (4,7) (5,2) (6,8) (7,6) (8,4) ] Solution: [ (1,5) (2,3) (3,8) (4,4) (5,7) (6,1) (7,6) (8,2) ] Solution: [ (1,5) (2,7) (3,1) (4,3) (5,8) (6,6) (7,4) (8,2) ] Solution: [ (1,5) (2,7) (3,1) (4,4) (5,2) (6,8) (7,6) (8,3) ] Solution: [ (1,5) (2,7) (3,2) (4,4) (5,8) (6,1) (7,3) (8,6) ] Solution: [ (1,5) (2,7) (3,2) (4,6) (5,3) (6,1) (7,4) (8,8) ] Solution: [ (1,5) (2,7) (3,2) (4,6) (5,3) (6,1) (7,8) (8,4) ] Solution: [ (1,5) (2,7) (3,4) (4,1) (5,3) (6,8) (7,6) (8,2) ] Solution: [ (1,5) (2,8) (3,4) (4,1) (5,3) (6,6) (7,2) (8,7) ] Solution: [ (1,5) (2,8) (3,4) (4,1) (5,7) (6,2) (7,6) (8,3) ] Solution: [ (1,6) (2,1) (3,5) (4,2) (5,8) (6,3) (7,7) (8,4) ] Solution: [ (1,6) (2,2) (3,7) (4,1) (5,3) (6,5) (7,8) (8,4) ] Solution: [ (1,6) (2,2) (3,7) (4,1) (5,4) (6,8) (7,5) (8,3) ] Solution: [ (1,6) (2,3) (3,1) (4,7) (5,5) (6,8) (7,2) (8,4) ] Solution: [ (1,6) (2,3) (3,1) (4,8) (5,4) (6,2) (7,7) (8,5) ] Solution: [ (1,6) (2,3) (3,1) (4,8) (5,5) (6,2) (7,4) (8,7) ] Solution: [ (1,6) (2,3) (3,5) (4,7) (5,1) (6,4) (7,2) (8,8) ] Solution: [ (1,6) (2,3) (3,5) (4,8) (5,1) (6,4) (7,2) (8,7) ] Solution: [ (1,6) (2,3) (3,7) (4,2) (5,4) (6,8) (7,1) (8,5) ] Solution: [ (1,6) (2,3) (3,7) (4,2) (5,8) (6,5) (7,1) (8,4) ] Solution: [ (1,6) (2,3) (3,7) (4,4) (5,1) (6,8) (7,2) (8,5) ] Solution: [ (1,6) (2,4) (3,1) (4,5) (5,8) (6,2) (7,7) (8,3) ] Solution: [ (1,6) (2,4) (3,2) (4,8) (5,5) (6,7) (7,1) (8,3) ] Solution: [ (1,6) (2,4) (3,7) (4,1) (5,3) (6,5) (7,2) (8,8) ] Solution: [ (1,6) (2,4) (3,7) (4,1) (5,8) (6,2) (7,5) (8,3) ] Solution: [ (1,6) (2,8) (3,2) (4,4) (5,1) (6,7) (7,5) (8,3) ] Solution: [ (1,7) (2,1) (3,3) (4,8) (5,6) (6,4) (7,2) (8,5) ] Solution: [ (1,7) (2,2) (3,4) (4,1) (5,8) (6,5) (7,3) (8,6) ] Solution: [ (1,7) (2,2) (3,6) (4,3) (5,1) (6,4) (7,8) (8,5) ] Solution: [ (1,7) (2,3) (3,1) (4,6) (5,8) (6,5) (7,2) (8,4) ] Solution: [ (1,7) (2,3) (3,8) (4,2) (5,5) (6,1) (7,6) (8,4) ] Solution: [ (1,7) (2,4) (3,2) (4,5) (5,8) (6,1) (7,3) (8,6) ] Solution: [ (1,7) (2,4) (3,2) (4,8) (5,6) (6,1) (7,3) (8,5) ] Solution: [ (1,7) (2,5) (3,3) (4,1) (5,6) (6,8) (7,2) (8,4) ] Solution: [ (1,8) (2,2) (3,4) (4,1) (5,7) (6,5) (7,3) (8,6) ] Solution: [ (1,8) (2,2) (3,5) (4,3) (5,1) (6,7) (7,4) (8,6) ] Solution: [ (1,8) (2,3) (3,1) (4,6) (5,2) (6,5) (7,7) (8,4) ] Solution: [ (1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5) ]