Posts

Developing a Sudoku solver

Image
I've never been great at solving Sudoku because I find it boring to sit down for an hour staring at boxes some filled and others to be filled with numbers. But I think it's an interesting game. I've always thought of developing an algorithm to solve any given Sudoku puzzle. I've had this in my mind from the very first year of my under graduation but I never gave it a serious thought. If you have seen my previous post, it's about backtracking which is a general algorithm used to solve many problems such as the classical N-Queens problem(I've solved it in that post). Yesterday I tried solving a question on the Hackerrank site which required me to use the backtracking algorithm and I was successful in devising an algorithm to solve it. I felt the question was very similar to solving a Sudoku puzzle so I thought of creating a sudoku solver and I've done it! It was simpler than what I thought it would be. All you need to know is how to use backtracking. If you …

Guide to Solving Maximal Subarray Problem using Kadane's Algorithm

Image
What is 'Maximal Subarray Problem'(MSP)?

Given an array having both positive and negative numbers, we need to find a continuous part of the array whose elements when added gives the largest possible sum.
Here are few examples to help you understand the MSP better:
1. consider the array [-1, 2, -1, 3]
    Now, here is a list of all the possible subarrays along with the sum of their elements:

ELEMENTSSUMstart indexend index-1-100-1, 2101-1, 2,-1002-1, 2,-1, 330322112,-11122,-1, 3413-1-122-1, 32233333
    From, the above table, its obvious that the answer is [ 2,-1, 3].
    All other subarrays sum up to a value that is less than 4.

2. consider the array [-1,-2]

    Here, the answer would be [-1]

3. consider the array [ 1, 2, 3]

    Here the answer would be [ 1, 2, 3]

I hope you got the idea of what is 'Maximal Subarray Problem' by now.


Given an array, how can we find the MSP?

One way to find the MSP for a given array is to check out all the possible subarrays and thus find …

Generic quicksort in C

Image
Recently I've learned how to use void pointers and function pointers in C and make functions generic as a part of MRND. So I've tried developing a generic quicksort function using it. I've implemented it in a header file so that it can be reused. Here's the gist for genericSort.h 



The four arguments being sent into the genericQSort function are:
void**arr:  It's an array of pointers which holds the addresses of each element of the array that is to be sorted.int lo: The start index from where the array needs to be sorted.int hi: The end index till where the array needs to be sorted.int (*compare)(void *, void *): A function pointer to the user's implementation of how to compare the sent array. It returns -1, 1 or 0. Here's a C program that makes use of the above function to sort an array of pairs. Here pair is a user-defined data-type which has two members x and y. The array is sorted based on the sum of x and y.

Here's a snap of execution of the program…

PvP Chain reaction game using Python

Image
At last, I've taken time and ventured a little deeper into the Python language! I used the Tkinterpackage to develop a rip-off of an android game called chain-reaction. It's a simple multiplayer board game in which the first person to occupy all the blocks on the board or of the opponent(s) wins. Try downloading and playing the game with your friends, it's FUN!

Here's a video of the game I've developed(I've set the number of players to 4 and board dimensions are 6*8):



Coming to the coding, I actually enjoyed the process of writing code much more in Python compared to any other previous languages that I've used. Maybe it is due to the fact that it's the first high-level language that I got my hands on. I'd never worked with Tkinter package before. It was quite easy to understand and I was able to build the game in roughly in four hours. I think that just a little effort is enough for anyone to understand how to use the tkinter package.

Talking about…

Creating own header files for statistics

Image
I was always interested in the subject of 'Probability & Statistics'. So I went ahead and created a header file to help me solve the questions present in the text book I was studying.

I've developed two header files:
measures.h: It has all the functions to measure the various measures used in statistics like mean, median, variance, deviation etc.data.h: This contains the definitions of two data-types 'univariateData' and 'bivariateData'. These are helpful in processing data right on input and giving out details about the given data. They are immutable(can't be edited).*Note: Don't include measures.h if data.h is already included because data.h has measures.h declared in it.
The cool part is that just 2 lines of code and user input are now enough to analyze any univariate data or bivariate data and display the info!
Here's an example: (source: http://www.seattlecentral.edu/qelp/sets/018/018.html)
About the data: The given data is about the use …

Beginner's guide to Solving the N-Queens problem using backtracking method

Image
This post serves as a good introduction to the backtracking method which is used widely in various types of problems to find a possible solution. Here we'll be seeing how to solve the classical N-Queens problem using backtracking method.

Backtracking:

The Wikipedia page for Backtracking defines it as "a general algorithm in which, we try to incrementally build candidates to the solutions, and discard a candidate as soon as we get to know that the candidate cannot possibly be completed to a valid solution". If that sounds complicated and confusing, don't worry! Let us understand it by running through a small example. Consider you are trapped in a haunted house with five rooms named A, B, C, D and E.Initially, you are in room A and you need to reach room E to exit the house.Below is an image of the rooms in the house. The arrows in the image indicate the directions in which you can move. For example, you can move to rooms B and C from A but, you cannot move back to room …

Developing Minesweeper using Java

Image
It's been a while since I've posted anything on my blog. The reason being that lately, I've been learning new languages like Python and Java. Well anyways, I've taken the time to develop Minesweeper game using Java applets. This game also got GUI which I've created using the components provided by Java. Here are a few pictures of the game.



Here's the video of my game:


There are two classes in my game:
Board class: This class provides the backend logic of building the board for the minesweeper game. This class has also got methods using which user can play the game on command prompt itself. I've commented out the methods required for running the game on cmd (the * beside a method listed below denotes that the method was commented). If you're interested in playing on cmd, fiddle around with invoking methods in the main method(create one!) and see if you can run it :). The various methods in Board class are:Board() *: Constructor to initialize the board si…