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

Binary heap based priority queue in Qt

Long time ago, I posted implementation of Priority Queue implemented using Qt's
 QQueue data structure. Here is old post.

That code was offering o(n) performance for enqueue operation and o(1) performance for dequeue operation. This might be acceptable for small data set. But for large data set you might want to use Priority queue based on Binary heap implementation.

I tried to implement my old priority queue using Binary heap, here is my implementation.

Following code implements BinaryHeap using QList. BinaryHeap class implements enqueue, dequeue and count method.

template <class T>
class BinaryHeap {
public:

    void enqueue(T item) {
        mList.append(item);
        int i = mList.count() - 1;
        int parent = (i-1)/2;
        while( parent >= 0 && mList[i] < mList[parent] ) {
            T temp = mList[parent];
            mList[parent] = mList[i];
            mList[i] = temp;
            i = parent;
            parent = (i-1)/2;
        }
    }

    T dequeue() {
        if( mList.isEmpty()) {
            return T();
        }

        T item = mList[0];
        int i = 0;
        mList[0] = mList[ count()-1];
        mList.removeLast();
        while( i < count() ) {
            int left = 2*i+1;
            int right = left + 1;

            if( right > count() - 1) {
                break;
            }

            int min = left;
            if( mList[right] < mList[left] ) {
                min = right;
            }

            if( mList[i] > mList[min] ) {
                T data = mList[min];
                mList[min] = mList[i];
                mList[i] = data;
                i = min;
            } else {
                break;
            }
        }
        return item;
    }

    int count() const {
        return mList.count();
    }

private:
    QList<T> mList;
};

And based on above BinaryHeap class, following is my PriorityQueue class.

enum Priority {
    Low = 2,
    Normal = 1,
    High = 0
};

template <class T>
class PriorityQueue
{
public:
    void enqueue( Priority priority, T data) {
        Item item(priority,data);
        mHeap.enqueue(item);
    }

    T dequeue() {
        Item item =  mHeap.dequeue();
        return item.mData;
    }

    int count() const {
        return mHeap.count();
    }

private:

    BinaryHeap<Item> mHeap;
};

And Item class looks like below.

    class Item{
    public:
        Item() {
        }

        Item(Priority priority, T data ):
            mPriority(priority),mData(data)
        {}

        bool operator<(const Item& other) {
            return mPriority < other.mPriority;
        }

        Priority mPriority;
        T mData;
    };

Saving custom structure in NSMutableDictionary/NSMutableArray with iPhone SDK

Recently while working on iPhone code, I required to store my custom structure in to NSMutableDictionary.

Well, NSMutableDictioary only store object derived from NSObject, so either we can make our structure, a class which is derived from NSObject and that's quite heavy and inefficient solution.

Better solution is to store custom structure in NSValue object and save NSValue to NSMutableDictionary.

As apple document suggest, The purpose of NSValue is to allow items of int, float, and char, pointers, structures and object ids data types to be added to collection objects such as instances of NSArray or NSSet, which require their elements to be objects.

Following is simple code that show how custom structure can be store in NSMutableDictionary.

Creating instance of NSMutableDictionary

NSMutableDictionary *map = [[NSMutableDictionary alloc] initWithCapacity:1];



Code to save structure in NSMutableDictionary.

MyStruct myStruct;
myStruct.someInt = 100; myStruct.someBool = NO;
NSValue* valueForStruct = [NSValue valueWithBytes:&myStruct objCType:@encode(MyStruct)];
[map setObject:valueForStruct forKey:@"MyStruct"];


Code to retrieve structure from NSMutableDictionary.

NSValue* valueForStruct = [map objectForKey:@"MyStruct"];
MyStruct myStruct;
[valueForStruct getValue:&myStruct];
NSLog(@"int val:%i, bool val:%i",myStruct.someInt, myStruct.someBool);


Though, it's not that difficult i thought to share this, hope it will help.

Simple priority queue with Qt

Recently in one of my Qt project I required to use priority queue and found that Qt framework dose not provide such container. Then I decided to write one my self.

Following is simple version of my actual implementation.

In code Queue class implement simple priority queue. Internally I am using QQueue as storage and created one helper structure which holds data and its priority. Actual work is done inside enqueue method, which check priority of item being inserted with other stored items and insert item at appropriate index.

#ifndef QUEUE_H
#define QUEUE_H

#include <QQueue>
#include <QDebug>

enum Priority {
    Normal = 0,
    High = 1
};

template<class T>
class Queue
{
public:

    Queue()
    {}

    void enqueue(Priority priority,T value)
    {
        Item<T> item(priority,value);
        for(int i = 0 ; i < _queue.count() ; ++i ) {
            const Item<T>& otherItem = _queue[i];
            if( priority > otherItem._priority )  {
                _queue.insert(i,item);
                return;
            }
        }
        _queue.append(item);
    }

    T dequeue()
    {
        const Item<T>& item = _queue.dequeue();
        return item._value;
    }

    int count()
    {
        return _queue.count();
    }

private:

    template<class C>
    struct Item
    {
        Priority _priority;
        C _value;

        Item(Priority priority, C value)
        {
            _priority = priority;
            _value = value;
        }
    };

    QQueue< Item<T > > _queue;

};

#endif // QUEUE_H

Some basic test code.

{
    //testing with int as value
    Queue<int> q;
    q.enqueue(High,1);
    q.enqueue(Normal,2);
    q.enqueue(High,3);
    q.enqueue(Normal,5);
    q.enqueue(Normal,6);
    q.enqueue(High,4);

    //output should be 1,3,4,2,5,6
    while( q.count() > 0 )
    {
        qDebug() << q.dequeue();
    }
}