Recursive Sudoku solver

I got back to coding after a long absence cause mainly by the final exams. My first project was to implement a recursive Sudoku solver.

I had previously written an iterative Sudoku solver that makes use of the same techniques that people do by ruling out what numbers can fit in a cell untill there is only one possible number that can fir. However, this method fails on harder puzzles where a guess has to be made in order to solve the puzzle.

Brute force algorithms enter here. The Sudoku puzzle lends itself well to the classic recursive brute force algorithm,

The step by step algorithm:

  1. If puzzle is solved
    1. End
  2. If puzzle is not valid
    1. End
  3. Find first empty cell : cell that contains 0
  4. While the cell value is less than 10 and while the puzzle is unsolved
    1. Increment cell by 1
    2. Solve
  5. If the cell value is greater than 9
    1. Reset the cell value to 0 : This means that a previous guess was invalid so this ends and the previous cell value is incremented

Mapping the random function

As described over here, the rand() function in C++ is a pseudo random generator that returns a number between 0 and RAND_MAX. This number is generated by an algorithm that returns a sequence of apparently non-related numbers each time it is called. This algorithm uses a seed to generate the series, which should be initialized to some distinctive value using srand.

RAND_MAX is a constant defined in <cstdlib>

But just how random is the rand() function. Its easy to find out by calling the function and comparing how often different values are returned. I do this graphically using OpenGL code to render the graph.

Using fraps, I recorded the variation of outputs from the rand() function.

The graph tends towards a straight line indicating that the more often you call the rand() function, the more even its distribution.

A class based implementation of linked lists

A class based impelementation of linked lists. Learnt really basic C style lists at school, so I thought I’d go the whole hog and implement a class based interface. Taught myself templates while doing this! Now, I have to resist the urge to template nearly every damn function. Use this implementation by declaring an object of the list class. Add nodes using the push(data) and push_back(data) functions, and remove nodes using pop() and pop_back() functions.

// list.h
#include <iostream>

using namespace std;

template <class data_type>
class list
{
struct node
{
data_type data;
node *next;
node *prev;
};

node *top;
node *back;

int nNodes;
bool indexed;
public:
list();
list(data_type);
void push_back(data_type);
void push(data_type);
void pop();
void pop_back();
friend ostream& operator << (ostream &out, list &l)
{
node *iter= l.top;
while(iter != nullptr)
{
out << iter->data << " ";
iter = iter->next;
}

return out;
}
data_type operator[](int);
};

template <class data_type> list<data_type>::list()
{
top = nullptr;
back = nullptr;
nNodes = 0;
}

template <class data_type> void list<data_type>::push_back(data_type data) //push a new element onto the list (from behind)
{
node *new_node = new node;
new_node->next = nullptr;
new_node->prev = back;
new_node->data = data;

back->next = new_node;
back = back->next;
nNodes++;
}

template <class data_type> void list<data_type>::push(data_type data) //push an new element onto the list (from the top)
{
node *new_node = new node;
new_node->next = top;
new_node->prev = nullptr;
new_node->data = data;

top = new_node;

if(top->next == nullptr)
back = top;

nNodes++;
}

template <class data_type> void list<data_type>::pop() //pop off top element of the list
{
node* delete_node = top;
top = top->next;

delete delete_node;
nNodes--;
}

template <class data_type> void list<data_type>::pop_back() //pop off last element of the list
{
node* delete_node = back;
back = back->prev;
back->next = nullptr;

delete delete_node;
}

template <class data_type> data_type list<data_type>::operator[](int index)//displaye element[x] of the list
{
node *iter = top;
for(int i = 0; i < index && iter->next != nullptr; i++)
{
iter = iter->next;
}

return iter->data;
}

Stock Quotes

StockSearch is a nifty little application that retrieves Stock Market data using the Yahoo! Finance API. This is the first time I’ve used HTTP in an application.

HTTP requests are handled using the libcurl library.

The app maintains a list of all known stock ticker symbols from the NASDAQ and NYSE. It uses this list to find Companies matching the name or symbol that the user has entered. As of now, the list cannot be updated (The functionality exists in the code but has been commented out).

The app has been written in C++ (Visual C++), The GUI has been written for win32 and hence will not compile on other platforms.

Download the Source

Download the App 

Project Euler – Problem 11

Problem 11 of Project Euler is a bit annoying to solve!

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

So, if you’re attempting to do it the brute force way, you have to check every possible combination. Still it’s only a 20 x 20 grid, so it’s manageable.

To simplify input, the grid has been put into a text file.

Have a look at the gridfill() function, to see how to read text from it.

Solution in C++ 

Shoot ‘Em Up

Shoot ‘Em Up is a simple shooting game, where you have to survive for as long as possible. Enemies spawn at random locations and move towards you.

Kill them by firing bullets.

This particular game involved a bit of math, especially making the enemies re – orient themselves when the player moves.

It’s trigonometry time!

Here’s a short of explanation of the math behind that particular feature:

For this game, I’ve written a small 2D Vector class which uses Unit Vector Notation to represent vectors.

Both the player and the Enemies are objects of the particle class. The floating point co – ordinates, and the velocity of a particle are stored as vectors.

The acute angle between the line joining the two particles, and the  x – axis is given by:

Basically, the enemy must move along this line, if it is to reach the player. When this angle is calculated, the velocity of the enemy may be in some other direction. Our goal now, is to “point” the enemy in the direction of the player without changing his speed.

Speed is defined as:

The mod() function of the Vector class gives this result. To re-orient the velocity vector along the new θ, keeping it’s magnitude constant, we calculate the new x and y components as follows:

There is one problem. θ will always be between 0 and π/2. Hence cos θ and sin θ will always be positive. To get around this, we check the sign of Δy and Δx. If Δy is negative, multiply the y component by -1, and if Δx is negative, multiply the x component by -1.

Pointing bullets towards the mouse works in a similar fashion, where the position of the mouse replaces the position of the enemy. Also, the bullet is pointed towards the mouse only at the time of firing.

So there you have it. Application of high school maths and physics in programming. Hope this helped 🙂

Screenshot of the game:

 

Download the game

Download the source

View the help file

Brickbreaker Gameplay