Here are a few random program snippets, these may be handy for beginning programmer's.
Knight's tour implemented in Matlab
The board size is variable, this program uses the warnsdorff heuristic looking one move ahead. The knight's tour is a classic chess related problem. The problem is to move a knight to every single square on the board only once. Doing this randomly is nearly impossible, using something called the warnsdorff heuristic it becomes very easy. When I implemented this in C++ a run of 50000 tours gave a success rate 97.9%, on a standard 8 by 8 board. What the heuristic does is look at each square the knight can move to and from those squares count how many squares can be reached. The knight must then move to the square with the lowest score. This effectively gets the knight to get the hardest to reach squares first. The success rate can be improved by looking more than one square ahead, at the expense of more computation per move. The heuristic is not fool proof, as the above success rate shows, the heuristic can lead down down a blind alley. The heuristic also can fail more frequently for larger boards by cutting itself of and only getting to half the squares before being trapped. For someone trying to enumerate all possible routes of the knights tour this algorithm is not suitable. Since it is possible to complete a tour by making moves to squares that are easily accessible compared to other squares (in contradiction to the warnsdorff rules) this heuristic cannot create all possible tours. If the heuristic is modified so that all moves are made randomly unless a square must be moved to because another opportunity will not arise, then the algorithm would be capable of creating all possible tours.
The N-Queens problem is a generalization a the 8 queens problem. For an N by N board one must place N queens so that they don't attack each other. The parameter N is hard coded in this program. For the 8 by 8 case there are 92 solutions. The standard approach is to start a queen on the first row and column, then add queens and push them up each column to a safe spot, if a column is not safe the previous queen is moved up and so on. My algorithm and that of other programs I've seen has 4 vectors. One for y coordinates where the index is x, one of boolean values to indicate if a y value is already taken and two more for boolean values keeping track of which positive and negative diagonals are occupied. My program uses one byte for all these values, boolean or integer. I actually use char, since it is the only portable way to get a one byte int. However, my program uses inline assembly language to keep track of clock cycles used, this is obviously not portable. The boolean variables need not be one byte, one bit would suffice. I've written assembly code where I stuffed 4 one byte variables in a 4 byte register and accessed them separately by rotating the register. This saves potentially slow memory accesses. This could be done for this code, and would make it much faster, although much less readable.
Mode 13H Graphics in IA-32 Assembly Language
As part of a group project to develop a game for the PC in intel assembly language I wrote several basic graphics procedures (a couple thousand lines). The _DrawLine function uses the bresenham line drawing algorithm to draw lines between any two (x,y) coordinates. I made great efforts to use only integer math, and to use only registers, no memory access, for each procedure. Like all my other procedures all the variables were placed in registers. In the case of this algorithm I had to stuff several variables in one register and roll the register in order to access a given variable.
visitors since June 10th, 2005.
