Saturday, June 12, 2004

Re: N-queens solution

I still haven't read Dinesh's 'Optimum' solution completely and am assuming i understood what i read. But another idea came to my mind. I don't know how much performance gain can be achieved if any at all. You be the judge.

The idea is to use Reflection.

Reflection allows Classes to be thought of as objects and it is possible to create instances of classes and use those to invoke methods etc of the Class. (just a intro for completeness). As mohn put it,(i think) Reflection is using meta-data of the Classes.

I am not sure if Reflection is possible in C++.

In Dinesh's 'Optimum' solution,
File ChessBoard.cpp, method void Search(int xpos), iteration is done at each step by these lines

ChessBoard* chess = new ChessBoard ( currSol,order);

I guess creating 'new' instances for every row each time, is very costly. Hey.. Reflection is definitely costlier than 'new'. But could be used here.

If N instances of ChessBoard are created and stored in a List, these can be used for the solutions.

A new method, say flush(), to clear the state of the ChessBoard could be created.

Now instead of multiple 'new', the instances are created only once. Then Method objects can be created and invoked(). For each row, the Method of the element of the List can be called and after a search, all the List elements are 'flush()'ed for a new search...

No comments: