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[8];
};

#endif // BOARD_H


No comments:

Post a Comment