## Friday, October 12, 2012

### Eight queen puzzle and solution

In past sometime I was working on project for which I required to create algorithm based on backtracking. For learning purpose I thought to create first a sample program using backtracking to create skeleton code.

I created a program to solve 8 queen puzzle as sample. You can find more information about 8 queen puzzle here.

Following is my code and below is main function which invoke the algorithm.
```#include "board.h"

int main(int argc, char* argv[]) {

Board board;
board.print();
board.solve();
board.print();

return 0;
}

```
Following is Board class which implements algorithm to solve the puzzle. Code is quite self descriptive so not adding much details.

```#ifndef BOARD_H
#define BOARD_H

#include

const int EMPTY = -99;

class Board{
public:
Board() {
for( int i = 0 ; i < 8 ; ++i ) {
board[i] = EMPTY;
}
}

void setOccupied( int row, int col) {
board[row] = col;
}

void setEmpty( int row) {
board[row] = EMPTY;
}

bool canOccupy( int row, int column)
{
//check if row is occupied
if( board[row] != EMPTY ) {
return false;
}

//check diagonal and column
for( int i=0; i < 8; ++i){
int diff = column - board[i];
int diff1 = row -i;
if( qAbs(diff) == qAbs(diff1) || diff == 0 ){
return false;
}
}
return true;
}

void print() {
printf("###################### \n");
for( int row=0; row < 8 ; ++row) {
int cell = board[row];
for( int col=0; col < 8 ; ++col) {
if( col == cell) {
printf(" X");
} else {
printf(" -");
}
}
printf("\n");
}
printf("###################### \n");
}

void solve() {
solve(0);
}

private:

bool solve( int row ) {
if( row == 8 ){
print();
return true;
}

for( int col=0; col < 8 ; ++col) {
if( canOccupy(row,col) ){
setOccupied(row,col);
if( solve( row + 1) ) {
print();
return true;
} else {
setEmpty(row);
print();
}
}
}
return false;
}

//each row\array element contains, index of column where queen is placed
int board;
};

#endif // BOARD_H

```

## Tuesday, October 9, 2012

### Code for reversing the digits of a given integer

Recently while browsing and I found one interesting question to reverse the digit of given integer. I thought to solve the same.

Solution is quite simple then I initially thought. Following is my solution.
```
int origNum = 12304;
int reverseNum = 0;

while( origNum != 0) {
int lastDigit = origNum % 10;
origNum /= 10;
reverseNum = reverseNum * 10;
reverseNum = reverseNum + lastDigit;
}

printf("reverse number %d", reverseNum);
```