How to detect fingers?

Its always such a fun, to think at the beginning of some code-work, things like, "Yeah I'm going to write a blog on this, when I'm done....", but at the end, we're so overwhelmed with what we have achieved, (and thus what we potentially could), the task of writing about it, seems pretty absurd...
For people who don't write much, (like me), this seems like one of the most time-consuming processes on Earth!
But then, I've getting quite a few requests for code, and I didn't feel like to end up with mailing code to every one of them personally, or explain in details.
And since it happens to be one of the earliest days I've woken up one (8 AM fellas!), I've made up my mind on writing!

Objective: Detecting (separating) the fingers which are up, in a open palm. (And getting it done by your Computer!)

Prerequisites:

• MATLAB (I used Matlab 13a)
• Familiarity with Matlab. (I'm not explaining Matlab in this blog.)
• A Webcam

Here's how it looks like..

Disclaimer: Yes, this one's a Matlab one. The project is rather demonstrative, and by itself is of little use. You're free to use the article or the code. But mind the recognition of original work ;) But I hope you'll build up something stellar, and when you do so,  don't forget to share with everyone else :)

Confession: 

The code is rather slow. I was new to Matlab then, and I haven't optimized it since. Also, it uses plain skin detection in YUV color range. So, things get messed up quick when there are skin like elements in background. Also, lightning should be uniform. 

Also, the work here is based upon work of others. Some reference codes from here and there, and a few research papers. Yes, I got a lot of help from freely available knowledge all over the Internet!

Basic Idea:

1. First skin is detected from image using filtering in YUV color space and largest blob is retained. This is new image [1].
2.  Then image is cleared using Morphological Operations. 
3.  Finally:

• Find the nearest point from centroid of extracted blob (which we might safely assume to be palm)
• The distance from the point can safely be assumed to approximate palm radius.
• With a disc element of a nearly this distance, erode the image.
• Subtract the resultant image[2] from image[1]
• Do a few more morphological operations, to make fingers significant in appearance.

That's all!

This gives countable number of connected components, giving the number of fingers. The Video shows the Regions of Interest, i.e. the palm with fingers (which are up) only. Counting fingers, need some extra code (Which is being left as an exercise :p).

Screenshots:

   







Code:

1. bwFingers.m


%%
%Finger Tracking
%Author: Arindam Sarkar
%Copyright?
%You can use this code for whatever you want! I'm not responsible for
%whatever it brings upon you, your system or your pet!
%Try to attribute the effort when you use part of this code in your own
%projects ;)
%Happy Coding!
%(c)2014 & beyond
%%
%boundary of hand
%background substraction with skin marking
close all;
clc;
clear all;
vid=imaq.VideoDevice('winvideo',1,'RGB24_640x480');
%set(vid,'ReturnedColorSpace','grayscale');
%preview(vid);
while 1
dntshw=false;
pause(.001);
%acquireimage from webcam
%capture frame
frame = step(vid);
%Read the image, and capture the dimensions
img=uint8(255*frame);
out=skinDetect2Func(img);
stats=regionprops(out,'Centroid');
if length(stats)
    cx=stats.Centroid(1);
    cy=stats.Centroid(2);
    %find the nearest countour point
    boundary=bwboundaries(out);
    minDist=2*640*640;
    mx=cx;
    my=cy;
    bImg=uint8(zeros(480,640));
    for i=1:length(boundary)
        cell=boundary{i,1};
        for j=1:length(cell)
            y=cell(j,1);
            x=cell(j,2);
            sqrDist=(cx-x)*(cx-x)+(cy-y)*(cy-y);
            bImg(x,y)=255;
            if(sqrDist<minDist)
                minDist=sqrDist;
                mx=x;
                my=y;
            end
        end   
    end
   
    sed=strel('disk',round(sqrt(minDist)/2));
    final=imerode(out,sed);
    final=imdilate(final,sed);
    final=out-final;
   
    final=bwareaopen(final,200);
    final=imerode(final,strel('disk',10));
    final=bwareaopen(final,400);
   
    [L,num]=bwlabel(final,8);
    final=imclearborder(final,8);

    imshow(final);
   
else
    imshow(out)
end
% imshow(bImg);
end


2. skinDetect2Func.m


%skin detect return pixels
function out=skinDetect2func(img)
imshow(img);
sz=size(img);
r=1;g=2;b=3;y=1;u=2;v=3;
yuv=img;
region=yuv;
for i=1:sz(1)
    for j=1:sz(2)
        yuv(i,j,y)=(img(i,j,r)+2*img(i,j,g)+img(i,j,b))/4;
        yuv(i,j,u)=img(i,j,r)-img(i,j,g);
        yuv(i,j,v)=img(i,j,b)-img(i,j,g);
    end
end
for i=1:sz(1)
    for j=1:sz(2)
        if yuv(i,j,u)>20 && yuv(i,j,u)<74
            region(i,j,r)=255;
            region(i,j,g)=255;
            region(i,j,b)=255;
     
        else
            region(i,j,r)=0;
            region(i,j,g)=0;
            region(i,j,b)=0;
        end
    end
end
out=region;
%filtering
out=im2bw(out);
out=bwareaopen(out,100);
out=imdilate(out,strel('diamond',4));
%retain largest only
res=out;
cc=bwconncomp(res);
arr=(cellfun('length',cc.PixelIdxList));
newLabel=res;
if ~isempty(round(arr))
    msz=0;
    for i=1:length(arr)
        if msz<arr(i:i)
            msz=arr(i:i);
            index=i;
        end
    end
    labels=labelmatrix(cc);
    newLabel=(labels==index);
    out=newLabel;
end
out=imfill(out,'holes');
end

Full code: detectFinger.zip

Happy Coding! Share knowledge. Make the planet wiser, everyday!

Feedback expected & Welcome :)

Edit 1:
When you post a comment regarding problem while running the code, include sufficient details.
Lets say you're getting an error "some random error!", then instead of just writing
"some random error!", writing -
I'm getting "some random error! *Complete Error String* " *Matlab version, OS * *Personal Note :D* 
is much more useful ;)

Edit 2:
Try the code against a constant plain background, possibly white, and in uniform white light illumination, when in doubt if the code works. This code is pretty basic, and has limitations.

Edit 3:
Make two separate files, for each piece of code, with the given names ;)

Below are some links you could find useful.


 


Edit: 12/7/2016

The code above might seem a bit slow. One of the readers had complained. It can be speeded up by as much as 10x by a simple improvement.

In code below, I've used vectorization to speed up the earlier code. This might speed up the code by upto 10x.

skinDetect2Func.m
 %skin detect return pixels
function out=skinDetect2func(img)
imshow(img);
sz=size(img);
r=1;g=2;b=3;y=1;u=2;v=3;
yuv=img;
region=yuv;

yuv(:,:,y) = (img(:,:,r)+2.*img(:,:,g)+img(:,:,b))/4;
yuv(:,:,u) = img(:,:,r)-img(:,:,g);
yuv(:,:,v)=img(:,:,b)-img(:,:,g);

region = (yuv(:,:,u)>20 & yuv(:,:,v)<74) .* 255;

toc

out=region;
%filtering
out=im2bw(out);
out=bwareaopen(out,100);
out=imdilate(out,strel('diamond',4));
%retain largest only
res=out;
cc=bwconncomp(res);
arr=(cellfun('length',cc.PixelIdxList));
newLabel=res;
if ~isempty(round(arr))
    msz=0;
    for i=1:length(arr)
        if msz<arr(i:i)
            msz=arr(i:i);
            index=i;
        end
    end
    labels=labelmatrix(cc);
    newLabel=(labels==index);
    out=newLabel;
end
out=imfill(out,'holes');
end

Now this doesn't improve accuracy any way, but speeds up the code! 

ACM ICPC KGP Online Round Rank Analysis

The ACM ICPC KGP online round was held on 2nd November 2013. Today is 14th November, and I was getting desperate about the results, which weren't out till now. Our team got a slot for Amritapuri Onsite round at Kerala, too far from Kolkata! (sigh...)

So, the best we could hope for was to get selected for Onsite round at Kharagpur. But our rank was 200, dropped from 139, after the KGP online goof-up from organizers!

Selection Procedure:

1.There are 60 seats available for the on-site contest.

2. All teams will be divided into groups where each group consists of all teams of the same Institute or School.

3. All teams of the same group will be ranked with respect to their performances.

4. To get a seat by a group for the on-site contest, a team of that group has to submit at least one correct program. 

5. An attempt will be made to provide a seat for the on-site contest to the best ranked team of that group.

6. In case it is found that the number of selected teams in this process is less than the available seats, best ranked  teams among the non-selected teams will be considered to fill the remaining seats.

7.In case it is found that the number of selected teams is more than the available seats, worst ranked teams among the selected teams will not be given the seats for the on-site contest.

So, partly out of curiousity, and partly out of boredom, I extracted the institute names from codechef.com ranklist using a small PHP script, and here are the analysis results (Ranks against the Institute Names):

Total Participant Institutes: 105

Top Rankers from Each College:

# 1:: Rank->1 -> International Institute of Information Technology, Hyderabad

# 2:: Rank->3 -> Indian Institute of Technology Delhi

# 3:: Rank->4 -> Indian Institute of Technology Madras

# 4:: Rank->5 -> Netaji Subhas Institute of Technology, New Delhi

# 5:: Rank->7 -> Indian Institute of Technology Kharagpur

# 6:: Rank->8 -> Amirkabir University of Technology

# 7:: Rank->9 -> Delhi Technological University

# 8:: Rank->10 -> Indian Institute of Technology Bombay

# 9:: Rank->11 -> Indian Institute of Information Technology, Allahabad

# 10:: Rank->12 -> Birla Institute of Technology Mesra

# 11:: Rank->13 -> National Institute of Technology Warangal

# 12:: Rank->21 -> Anil Neerukonda Institute of Technology and Sciences

# 13:: Rank->22 -> Indian Institute of Technology Roorkee

# 14:: Rank->24 -> National Institute of Technology Karnataka

# 15:: Rank->26 -> Jaypee Institute of Information Technology

# 16:: Rank->27 -> Guru Kashi University, Talwandi Sabo

# 17:: Rank->29 -> Indian Institute of Technology, Varanasi

# 18:: Rank->32 -> Veermata Jijabai Technological Institute, Mumbai

# 19:: Rank->33 -> Indraprastha Institute of Information Technology, Delhi

# 20:: Rank->36 -> Indian Institute of Technology Guwahati

# 21:: Rank->42 -> Amrita University

# 22:: Rank->46 -> Indian Institute of Technology Indore

# 23:: Rank->49 -> Maulana Azad National Institute of Technology, Bhopal

# 24:: Rank->61 -> Birla Institute of Technology & Science Pilani, Hyderabad Campus

# 25:: Rank->62 -> Indian Institute of Technology, Jodhpur

# 26:: Rank->63 -> Jaypee University of Engineering and Technology, Guna

# 27:: Rank->66 -> College of Engineering, Guindy

# 28:: Rank->68 -> Pune Institute of Computer Technology

# 29:: Rank->70 -> National Institute of Technology, Durgapur

# 30:: Rank->72 -> International Institute of Information Technology, Bangalore

# 31:: Rank->75 -> National Institute of Technology Tiruchirappalli

# 32:: Rank->87 -> National Institute of Technology Raipur

# 33:: Rank->90 -> Birla Institute of Technology & Science Pilani, Pilani Campus

# 34:: Rank->91 -> Indian Institute of Information Technology, Design and Manufacturing, Jabalpur

# 35:: Rank->97 -> Motilal Nehru National Institute of Technology Allahabad

# 36:: Rank->103 -> National Institute of Technology Patna

# 37:: Rank->105 -> Jadavpur University

# 38:: Rank->109 -> National Institute of Technology, Jamshedpur

# 39:: Rank->119 -> Visvesvaraya National Institute of Technology, Nagpur

# 40:: Rank->127 -> ABV - Indian Institute of Information Technology and Management Gwalior

# 41:: Rank->128 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai

# 42:: Rank->129 -> Madras Institute of Technology, Anna University

# 43:: Rank->134 -> Indian Institute of Technology Kanpur

# 44:: Rank->136 -> Indira Gandhi Institute of Technology

# 45:: Rank->138 -> SR Engineering College, Hasanparthy

# 46:: Rank->157 -> Techno India NJR Institute of technology

# 47:: Rank->159 -> Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar

# 48:: Rank->165 -> National Institute of Technology, Rourkela

# 49:: Rank->171 -> Birla Institute of Technology & Science Pilani, Goa Campus

# 50:: Rank->185 -> Amrita School of Engineering, Coimbatore

# 51:: Rank->190 -> Institute of Engineering and Management, Kolkata

# 52:: Rank->192 -> Indian Institute of Technology, Hyderabad

# 53:: Rank->196 -> Sardar Vallabhbhai National Institute of Technology, Surat

# 54:: Rank->198 -> Lalbhai Dalpatram College of Engineering, Ahmedabad

# 55:: Rank->199 -> Vellore Institute of Technology, Vellore

# 56:: Rank->200 -> Netaji Subhash Engineering College

# 57:: Rank->203 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley

# 58:: Rank->212 -> Neotia Institute of Technology Management and Science

# 59:: Rank->222 -> YMCA University of Science and Technology, Faridabad

# 60:: Rank->232 -> Amrita School of Engineering, Amritapuri

# 61:: Rank->234 -> Institute of Engineering and Technology, Devi Ahilya Vishwavidyalaya

# 62:: Rank->243 -> Institute of Technical Education & Research, Bhubaneswar

# 63:: Rank->245 -> Malaviya National Institute of Technology, Jaipur

# 64:: Rank->255 -> National Institute of Technology, Calicut

# 65:: Rank->263 -> The LNM Institute of Information Technology

# 66:: Rank->266 -> Birsa Institute of Technology, Sindri

# 67:: Rank->274 -> PSG College of Technology, Coimbatore

# 68:: Rank->278 -> Rashtreeya Vidyalaya College of Engineering, Bangalore

# 69:: Rank->292 -> Indian School of Mines, Dhanbad

# 70:: Rank->294 -> Veer Surendra Sai University of Technology, Orissa

# 71:: Rank->302 -> Chennai Mathematical Institute

# 72:: Rank->321 -> University Institute of Engineering and Technology, Punjab University

# 73:: Rank->329 -> Vishwakarma Institute of Technology, Pune

# 74:: Rank->336 -> JSS Academy of Technical Education, Noida

# 75:: Rank->340 -> MIT College of Engineering Pune

# 76:: Rank->342 -> Rustamji Institute of Technology

# 77:: Rank->343 -> Thapar University

# 78:: Rank->348 -> Sri Sivasubramaniya Nadar College of Engineering, Chennai

# 79:: Rank->356 -> Raj Kumar Goel Institute of Technology

# 80:: Rank->358 -> Jawaharlal Nehru Technological University, Vizianagaram

# 81:: Rank->359 -> Acropolis Institute of Technology & Research, Indore

# 82:: Rank->385 -> Indian Institute of Technology Mandi

# 83:: Rank->387 -> Shri Ramswaroop Memorial College of Engineering and Management

# 84:: Rank->391 -> Bengal Engineering and Science University, Shibpur

# 85:: Rank->417 -> Lovely Professional University

# 86:: Rank->424 -> Vishwakarma Government Engineering College, Chandkheda

# 87:: Rank->427 -> University Visvesvaraya College of Engineering, Bangalore

# 88:: Rank->428 -> Institute of Technology, Nirma University

# 89:: Rank->429 -> Arya Institute of Engineering & Technology

# 90:: Rank->433 -> Heritage Institute of Technology, Kolkata

# 91:: Rank->436 -> Jamia Millia Islamia

# 92:: Rank->437 -> Indian Institute of Technology Patna

# 93:: Rank->450 -> St Vincent Pallotti College of Engineering & Technology, Nagpur

# 94:: Rank->451 -> Pimpri Chinchwad College of Engineering, Pune

# 95:: Rank->454 -> Chandigarh Group of Colleges, Landran

# 96:: Rank->479 -> SRM University

# 97:: Rank->486 -> Karpagam University

# 98:: Rank->488 -> University of Petroleum and Energy Studies, Dehradun

# 99:: Rank->491 -> SASTRA University

# 100:: Rank->493 -> Shahjalal University Of Science & Technology

# 101:: Rank->499 -> Shri Mata Vaishno Devi University

# 102:: Rank->501 -> Sree Vidyanikethan Engineering College

# 103:: Rank->507 -> Rajiv Gandhi College Of Engg And Research, Nagpur

# 104:: Rank->516 -> Jaypee University of Information Technology

# 105:: Rank->528 -> Charotar University of Science and Technology


-----------------------------------------------------------------------------------------------

All the Teams, sorted by Institute Names:

127 -> ABV - Indian Institute of Information Technology and Management Gwalior
262 -> ABV - Indian Institute of Information Technology and Management Gwalior
406 -> ABV - Indian Institute of Information Technology and Management Gwalior
359 -> Acropolis Institute of Technology & Research, Indore
375 -> Acropolis Institute of Technology & Research, Indore
8 -> Amirkabir University of Technology
232 -> Amrita School of Engineering, Amritapuri
331 -> Amrita School of Engineering, Amritapuri
425 -> Amrita School of Engineering, Amritapuri
500 -> Amrita School of Engineering, Amritapuri
185 -> Amrita School of Engineering, Coimbatore
384 -> Amrita School of Engineering, Coimbatore
403 -> Amrita School of Engineering, Coimbatore
473 -> Amrita School of Engineering, Coimbatore
477 -> Amrita School of Engineering, Coimbatore
533 -> Amrita School of Engineering, Coimbatore
42 -> Amrita University
21 -> Anil Neerukonda Institute of Technology and Sciences
316 -> Anil Neerukonda Institute of Technology and Sciences
429 -> Arya Institute of Engineering & Technology
391 -> Bengal Engineering and Science University, Shibpur
465 -> Bengal Engineering and Science University, Shibpur
481 -> Bengal Engineering and Science University, Shibpur
538 -> Bengal Engineering and Science University, Shibpur
171 -> Birla Institute of Technology & Science Pilani, Goa Campus
306 -> Birla Institute of Technology & Science Pilani, Goa Campus
376 -> Birla Institute of Technology & Science Pilani, Goa Campus
448 -> Birla Institute of Technology & Science Pilani, Goa Campus
61 -> Birla Institute of Technology & Science Pilani, Hyderabad Campus
489 -> Birla Institute of Technology & Science Pilani, Hyderabad Campus
90 -> Birla Institute of Technology & Science Pilani, Pilani Campus
155 -> Birla Institute of Technology & Science Pilani, Pilani Campus
161 -> Birla Institute of Technology & Science Pilani, Pilani Campus
163 -> Birla Institute of Technology & Science Pilani, Pilani Campus
187 -> Birla Institute of Technology & Science Pilani, Pilani Campus
239 -> Birla Institute of Technology & Science Pilani, Pilani Campus
330 -> Birla Institute of Technology & Science Pilani, Pilani Campus
413 -> Birla Institute of Technology & Science Pilani, Pilani Campus
453 -> Birla Institute of Technology & Science Pilani, Pilani Campus
523 -> Birla Institute of Technology & Science Pilani, Pilani Campus
525 -> Birla Institute of Technology & Science Pilani, Pilani Campus
12 -> Birla Institute of Technology Mesra
19 -> Birla Institute of Technology Mesra
23 -> Birla Institute of Technology Mesra
35 -> Birla Institute of Technology Mesra
38 -> Birla Institute of Technology Mesra
45 -> Birla Institute of Technology Mesra
50 -> Birla Institute of Technology Mesra
59 -> Birla Institute of Technology Mesra
65 -> Birla Institute of Technology Mesra
76 -> Birla Institute of Technology Mesra
89 -> Birla Institute of Technology Mesra
114 -> Birla Institute of Technology Mesra
168 -> Birla Institute of Technology Mesra
169 -> Birla Institute of Technology Mesra
174 -> Birla Institute of Technology Mesra
183 -> Birla Institute of Technology Mesra
191 -> Birla Institute of Technology Mesra
216 -> Birla Institute of Technology Mesra
223 -> Birla Institute of Technology Mesra
224 -> Birla Institute of Technology Mesra
226 -> Birla Institute of Technology Mesra
260 -> Birla Institute of Technology Mesra
265 -> Birla Institute of Technology Mesra
276 -> Birla Institute of Technology Mesra
286 -> Birla Institute of Technology Mesra
290 -> Birla Institute of Technology Mesra
301 -> Birla Institute of Technology Mesra
310 -> Birla Institute of Technology Mesra
349 -> Birla Institute of Technology Mesra
353 -> Birla Institute of Technology Mesra
364 -> Birla Institute of Technology Mesra
407 -> Birla Institute of Technology Mesra
439 -> Birla Institute of Technology Mesra
446 -> Birla Institute of Technology Mesra
463 -> Birla Institute of Technology Mesra
470 -> Birla Institute of Technology Mesra
476 -> Birla Institute of Technology Mesra
480 -> Birla Institute of Technology Mesra
266 -> Birsa Institute of Technology, Sindri
475 -> Birsa Institute of Technology, Sindri
454 -> Chandigarh Group of Colleges, Landran
528 -> Charotar University of Science and Technology
302 -> Chennai Mathematical Institute
352 -> Chennai Mathematical Institute
66 -> College of Engineering, Guindy
110 -> College of Engineering, Guindy
219 -> College of Engineering, Guindy
275 -> College of Engineering, Guindy
341 -> College of Engineering, Guindy
392 -> College of Engineering, Guindy
397 -> College of Engineering, Guindy
485 -> College of Engineering, Guindy
519 -> College of Engineering, Guindy
539 -> College of Engineering, Guindy
9 -> Delhi Technological University
20 -> Delhi Technological University
56 -> Delhi Technological University
58 -> Delhi Technological University
71 -> Delhi Technological University
96 -> Delhi Technological University
125 -> Delhi Technological University
137 -> Delhi Technological University
150 -> Delhi Technological University
189 -> Delhi Technological University
209 -> Delhi Technological University
287 -> Delhi Technological University
298 -> Delhi Technological University
339 -> Delhi Technological University
383 -> Delhi Technological University
414 -> Delhi Technological University
490 -> Delhi Technological University
494 -> Delhi Technological University
527 -> Delhi Technological University
531 -> Delhi Technological University
159 -> Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar
242 -> Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar
244 -> Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar
128 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai
312 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai
422 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai
423 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai
431 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai
443 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai
482 -> Dwarkadas Jivanlal Sanghvi College of Engineering, Vile Parle, Mumbai
27 -> Guru Kashi University, Talwandi Sabo
433 -> Heritage Institute of Technology, Kolkata
469 -> Heritage Institute of Technology, Kolkata
11 -> Indian Institute of Information Technology, Allahabad
18 -> Indian Institute of Information Technology, Allahabad
28 -> Indian Institute of Information Technology, Allahabad
31 -> Indian Institute of Information Technology, Allahabad
77 -> Indian Institute of Information Technology, Allahabad
85 -> Indian Institute of Information Technology, Allahabad
88 -> Indian Institute of Information Technology, Allahabad
98 -> Indian Institute of Information Technology, Allahabad
107 -> Indian Institute of Information Technology, Allahabad
108 -> Indian Institute of Information Technology, Allahabad
144 -> Indian Institute of Information Technology, Allahabad
172 -> Indian Institute of Information Technology, Allahabad
179 -> Indian Institute of Information Technology, Allahabad
195 -> Indian Institute of Information Technology, Allahabad
197 -> Indian Institute of Information Technology, Allahabad
268 -> Indian Institute of Information Technology, Allahabad
271 -> Indian Institute of Information Technology, Allahabad
91 -> Indian Institute of Information Technology, Design and Manufacturing, Jabalpur
122 -> Indian Institute of Information Technology, Design and Manufacturing, Jabalpur
230 -> Indian Institute of Information Technology, Design and Manufacturing, Jabalpur
261 -> Indian Institute of Information Technology, Design and Manufacturing, Jabalpur
313 -> Indian Institute of Information Technology, Design and Manufacturing, Jabalpur
317 -> Indian Institute of Information Technology, Design and Manufacturing, Jabalpur
10 -> Indian Institute of Technology Bombay
17 -> Indian Institute of Technology Bombay
117 -> Indian Institute of Technology Bombay
133 -> Indian Institute of Technology Bombay
148 -> Indian Institute of Technology Bombay
158 -> Indian Institute of Technology Bombay
160 -> Indian Institute of Technology Bombay
162 -> Indian Institute of Technology Bombay
248 -> Indian Institute of Technology Bombay
252 -> Indian Institute of Technology Bombay
438 -> Indian Institute of Technology Bombay
496 -> Indian Institute of Technology Bombay
3 -> Indian Institute of Technology Delhi
145 -> Indian Institute of Technology Delhi
182 -> Indian Institute of Technology Delhi
362 -> Indian Institute of Technology Delhi
36 -> Indian Institute of Technology Guwahati
47 -> Indian Institute of Technology Guwahati
92 -> Indian Institute of Technology Guwahati
95 -> Indian Institute of Technology Guwahati
106 -> Indian Institute of Technology Guwahati
111 -> Indian Institute of Technology Guwahati
131 -> Indian Institute of Technology Guwahati
139 -> Indian Institute of Technology Guwahati
149 -> Indian Institute of Technology Guwahati
170 -> Indian Institute of Technology Guwahati
221 -> Indian Institute of Technology Guwahati
249 -> Indian Institute of Technology Guwahati
253 -> Indian Institute of Technology Guwahati
254 -> Indian Institute of Technology Guwahati
257 -> Indian Institute of Technology Guwahati
259 -> Indian Institute of Technology Guwahati
280 -> Indian Institute of Technology Guwahati
285 -> Indian Institute of Technology Guwahati
311 -> Indian Institute of Technology Guwahati
344 -> Indian Institute of Technology Guwahati
369 -> Indian Institute of Technology Guwahati
371 -> Indian Institute of Technology Guwahati
372 -> Indian Institute of Technology Guwahati
430 -> Indian Institute of Technology Guwahati
462 -> Indian Institute of Technology Guwahati
466 -> Indian Institute of Technology Guwahati
467 -> Indian Institute of Technology Guwahati
474 -> Indian Institute of Technology Guwahati
506 -> Indian Institute of Technology Guwahati
514 -> Indian Institute of Technology Guwahati
517 -> Indian Institute of Technology Guwahati
529 -> Indian Institute of Technology Guwahati
46 -> Indian Institute of Technology Indore
282 -> Indian Institute of Technology Indore
300 -> Indian Institute of Technology Indore
325 -> Indian Institute of Technology Indore
134 -> Indian Institute of Technology Kanpur
180 -> Indian Institute of Technology Kanpur
207 -> Indian Institute of Technology Kanpur
411 -> Indian Institute of Technology Kanpur
502 -> Indian Institute of Technology Kanpur
7 -> Indian Institute of Technology Kharagpur
15 -> Indian Institute of Technology Kharagpur
104 -> Indian Institute of Technology Kharagpur
113 -> Indian Institute of Technology Kharagpur
120 -> Indian Institute of Technology Kharagpur
141 -> Indian Institute of Technology Kharagpur
146 -> Indian Institute of Technology Kharagpur
184 -> Indian Institute of Technology Kharagpur
186 -> Indian Institute of Technology Kharagpur
193 -> Indian Institute of Technology Kharagpur
213 -> Indian Institute of Technology Kharagpur
236 -> Indian Institute of Technology Kharagpur
288 -> Indian Institute of Technology Kharagpur
299 -> Indian Institute of Technology Kharagpur
334 -> Indian Institute of Technology Kharagpur
366 -> Indian Institute of Technology Kharagpur
367 -> Indian Institute of Technology Kharagpur
374 -> Indian Institute of Technology Kharagpur
379 -> Indian Institute of Technology Kharagpur
388 -> Indian Institute of Technology Kharagpur
389 -> Indian Institute of Technology Kharagpur
405 -> Indian Institute of Technology Kharagpur
432 -> Indian Institute of Technology Kharagpur
4 -> Indian Institute of Technology Madras
217 -> Indian Institute of Technology Madras
231 -> Indian Institute of Technology Madras
241 -> Indian Institute of Technology Madras
284 -> Indian Institute of Technology Madras
318 -> Indian Institute of Technology Madras
320 -> Indian Institute of Technology Madras
360 -> Indian Institute of Technology Madras
370 -> Indian Institute of Technology Madras
408 -> Indian Institute of Technology Madras
435 -> Indian Institute of Technology Madras
461 -> Indian Institute of Technology Madras
468 -> Indian Institute of Technology Madras
484 -> Indian Institute of Technology Madras
511 -> Indian Institute of Technology Madras
385 -> Indian Institute of Technology Mandi
402 -> Indian Institute of Technology Mandi
437 -> Indian Institute of Technology Patna
22 -> Indian Institute of Technology Roorkee
37 -> Indian Institute of Technology Roorkee
51 -> Indian Institute of Technology Roorkee
64 -> Indian Institute of Technology Roorkee
94 -> Indian Institute of Technology Roorkee
140 -> Indian Institute of Technology Roorkee
178 -> Indian Institute of Technology Roorkee
240 -> Indian Institute of Technology Roorkee
283 -> Indian Institute of Technology Roorkee
323 -> Indian Institute of Technology Roorkee
346 -> Indian Institute of Technology Roorkee
192 -> Indian Institute of Technology, Hyderabad
373 -> Indian Institute of Technology, Hyderabad
62 -> Indian Institute of Technology, Jodhpur
93 -> Indian Institute of Technology, Jodhpur
441 -> Indian Institute of Technology, Jodhpur
483 -> Indian Institute of Technology, Jodhpur
29 -> Indian Institute of Technology, Varanasi
82 -> Indian Institute of Technology, Varanasi
188 -> Indian Institute of Technology, Varanasi
237 -> Indian Institute of Technology, Varanasi
381 -> Indian Institute of Technology, Varanasi
444 -> Indian Institute of Technology, Varanasi
292 -> Indian School of Mines, Dhanbad
136 -> Indira Gandhi Institute of Technology
33 -> Indraprastha Institute of Information Technology, Delhi
34 -> Indraprastha Institute of Information Technology, Delhi
39 -> Indraprastha Institute of Information Technology, Delhi
142 -> Indraprastha Institute of Information Technology, Delhi
143 -> Indraprastha Institute of Information Technology, Delhi
365 -> Indraprastha Institute of Information Technology, Delhi
386 -> Indraprastha Institute of Information Technology, Delhi
190 -> Institute of Engineering and Management, Kolkata
338 -> Institute of Engineering and Management, Kolkata
234 -> Institute of Engineering and Technology, Devi Ahilya Vishwavidyalaya
410 -> Institute of Engineering and Technology, Devi Ahilya Vishwavidyalaya
243 -> Institute of Technical Education & Research, Bhubaneswar
428 -> Institute of Technology, Nirma University
72 -> International Institute of Information Technology, Bangalore
121 -> International Institute of Information Technology, Bangalore
382 -> International Institute of Information Technology, Bangalore
390 -> International Institute of Information Technology, Bangalore
1 -> International Institute of Information Technology, Hyderabad
2 -> International Institute of Information Technology, Hyderabad
6 -> International Institute of Information Technology, Hyderabad
14 -> International Institute of Information Technology, Hyderabad
16 -> International Institute of Information Technology, Hyderabad
25 -> International Institute of Information Technology, Hyderabad
40 -> International Institute of Information Technology, Hyderabad
41 -> International Institute of Information Technology, Hyderabad
43 -> International Institute of Information Technology, Hyderabad
44 -> International Institute of Information Technology, Hyderabad
48 -> International Institute of Information Technology, Hyderabad
52 -> International Institute of Information Technology, Hyderabad
53 -> International Institute of Information Technology, Hyderabad
54 -> International Institute of Information Technology, Hyderabad
55 -> International Institute of Information Technology, Hyderabad
60 -> International Institute of Information Technology, Hyderabad
73 -> International Institute of Information Technology, Hyderabad
74 -> International Institute of Information Technology, Hyderabad
80 -> International Institute of Information Technology, Hyderabad
81 -> International Institute of Information Technology, Hyderabad
83 -> International Institute of Information Technology, Hyderabad
84 -> International Institute of Information Technology, Hyderabad
86 -> International Institute of Information Technology, Hyderabad
102 -> International Institute of Information Technology, Hyderabad
123 -> International Institute of Information Technology, Hyderabad
124 -> International Institute of Information Technology, Hyderabad
132 -> International Institute of Information Technology, Hyderabad
152 -> International Institute of Information Technology, Hyderabad
153 -> International Institute of Information Technology, Hyderabad
167 -> International Institute of Information Technology, Hyderabad
173 -> International Institute of Information Technology, Hyderabad
175 -> International Institute of Information Technology, Hyderabad
176 -> International Institute of Information Technology, Hyderabad
181 -> International Institute of Information Technology, Hyderabad
201 -> International Institute of Information Technology, Hyderabad
215 -> International Institute of Information Technology, Hyderabad
225 -> International Institute of Information Technology, Hyderabad
227 -> International Institute of Information Technology, Hyderabad
228 -> International Institute of Information Technology, Hyderabad
229 -> International Institute of Information Technology, Hyderabad
235 -> International Institute of Information Technology, Hyderabad
238 -> International Institute of Information Technology, Hyderabad
258 -> International Institute of Information Technology, Hyderabad
277 -> International Institute of Information Technology, Hyderabad
289 -> International Institute of Information Technology, Hyderabad
314 -> International Institute of Information Technology, Hyderabad
324 -> International Institute of Information Technology, Hyderabad
333 -> International Institute of Information Technology, Hyderabad
335 -> International Institute of Information Technology, Hyderabad
337 -> International Institute of Information Technology, Hyderabad
350 -> International Institute of Information Technology, Hyderabad
351 -> International Institute of Information Technology, Hyderabad
355 -> International Institute of Information Technology, Hyderabad
357 -> International Institute of Information Technology, Hyderabad
363 -> International Institute of Information Technology, Hyderabad
368 -> International Institute of Information Technology, Hyderabad
394 -> International Institute of Information Technology, Hyderabad
418 -> International Institute of Information Technology, Hyderabad
442 -> International Institute of Information Technology, Hyderabad
445 -> International Institute of Information Technology, Hyderabad
457 -> International Institute of Information Technology, Hyderabad
458 -> International Institute of Information Technology, Hyderabad
460 -> International Institute of Information Technology, Hyderabad
495 -> International Institute of Information Technology, Hyderabad
336 -> JSS Academy of Technical Education, Noida
105 -> Jadavpur University
112 -> Jadavpur University
326 -> Jadavpur University
436 -> Jamia Millia Islamia
509 -> Jamia Millia Islamia
513 -> Jamia Millia Islamia
358 -> Jawaharlal Nehru Technological University, Vizianagaram
26 -> Jaypee Institute of Information Technology
67 -> Jaypee Institute of Information Technology
154 -> Jaypee Institute of Information Technology
279 -> Jaypee Institute of Information Technology
395 -> Jaypee Institute of Information Technology
63 -> Jaypee University of Engineering and Technology, Guna
319 -> Jaypee University of Engineering and Technology, Guna
526 -> Jaypee University of Engineering and Technology, Guna
516 -> Jaypee University of Information Technology
486 -> Karpagam University
198 -> Lalbhai Dalpatram College of Engineering, Ahmedabad
417 -> Lovely Professional University
340 -> MIT College of Engineering Pune
129 -> Madras Institute of Technology, Anna University
135 -> Madras Institute of Technology, Anna University
220 -> Madras Institute of Technology, Anna University
269 -> Madras Institute of Technology, Anna University
401 -> Madras Institute of Technology, Anna University
534 -> Madras Institute of Technology, Anna University
245 -> Malaviya National Institute of Technology, Jaipur
512 -> Malaviya National Institute of Technology, Jaipur
49 -> Maulana Azad National Institute of Technology, Bhopal
78 -> Maulana Azad National Institute of Technology, Bhopal
211 -> Maulana Azad National Institute of Technology, Bhopal
97 -> Motilal Nehru National Institute of Technology Allahabad
101 -> Motilal Nehru National Institute of Technology Allahabad
126 -> Motilal Nehru National Institute of Technology Allahabad
214 -> Motilal Nehru National Institute of Technology Allahabad
218 -> Motilal Nehru National Institute of Technology Allahabad
246 -> Motilal Nehru National Institute of Technology Allahabad
264 -> Motilal Nehru National Institute of Technology Allahabad
532 -> Motilal Nehru National Institute of Technology Allahabad
24 -> National Institute of Technology Karnataka
164 -> National Institute of Technology Karnataka
204 -> National Institute of Technology Karnataka
247 -> National Institute of Technology Karnataka
272 -> National Institute of Technology Karnataka
297 -> National Institute of Technology Karnataka
305 -> National Institute of Technology Karnataka
103 -> National Institute of Technology Patna
508 -> National Institute of Technology Patna
515 -> National Institute of Technology Patna
87 -> National Institute of Technology Raipur
99 -> National Institute of Technology Raipur
100 -> National Institute of Technology Raipur
205 -> National Institute of Technology Raipur
210 -> National Institute of Technology Raipur
281 -> National Institute of Technology Raipur
75 -> National Institute of Technology Tiruchirappalli
116 -> National Institute of Technology Tiruchirappalli
118 -> National Institute of Technology Tiruchirappalli
206 -> National Institute of Technology Tiruchirappalli
233 -> National Institute of Technology Tiruchirappalli
303 -> National Institute of Technology Tiruchirappalli
415 -> National Institute of Technology Tiruchirappalli
524 -> National Institute of Technology Tiruchirappalli
13 -> National Institute of Technology Warangal
396 -> National Institute of Technology Warangal
472 -> National Institute of Technology Warangal
255 -> National Institute of Technology, Calicut
293 -> National Institute of Technology, Calicut
322 -> National Institute of Technology, Calicut
361 -> National Institute of Technology, Calicut
70 -> National Institute of Technology, Durgapur
115 -> National Institute of Technology, Durgapur
130 -> National Institute of Technology, Durgapur
151 -> National Institute of Technology, Durgapur
208 -> National Institute of Technology, Durgapur
291 -> National Institute of Technology, Durgapur
347 -> National Institute of Technology, Durgapur
109 -> National Institute of Technology, Jamshedpur
250 -> National Institute of Technology, Jamshedpur
273 -> National Institute of Technology, Jamshedpur
309 -> National Institute of Technology, Jamshedpur
354 -> National Institute of Technology, Jamshedpur
398 -> National Institute of Technology, Jamshedpur
409 -> National Institute of Technology, Jamshedpur
421 -> National Institute of Technology, Jamshedpur
459 -> National Institute of Technology, Jamshedpur
535 -> National Institute of Technology, Jamshedpur
165 -> National Institute of Technology, Rourkela
296 -> National Institute of Technology, Rourkela
307 -> National Institute of Technology, Rourkela
412 -> National Institute of Technology, Rourkela
212 -> Neotia Institute of Technology Management and Science
5 -> Netaji Subhas Institute of Technology, New Delhi
30 -> Netaji Subhas Institute of Technology, New Delhi
57 -> Netaji Subhas Institute of Technology, New Delhi
69 -> Netaji Subhas Institute of Technology, New Delhi
79 -> Netaji Subhas Institute of Technology, New Delhi
147 -> Netaji Subhas Institute of Technology, New Delhi
156 -> Netaji Subhas Institute of Technology, New Delhi
166 -> Netaji Subhas Institute of Technology, New Delhi
177 -> Netaji Subhas Institute of Technology, New Delhi
267 -> Netaji Subhas Institute of Technology, New Delhi
315 -> Netaji Subhas Institute of Technology, New Delhi
327 -> Netaji Subhas Institute of Technology, New Delhi
399 -> Netaji Subhas Institute of Technology, New Delhi
400 -> Netaji Subhas Institute of Technology, New Delhi
404 -> Netaji Subhas Institute of Technology, New Delhi
426 -> Netaji Subhas Institute of Technology, New Delhi
471 -> Netaji Subhas Institute of Technology, New Delhi
520 -> Netaji Subhas Institute of Technology, New Delhi
200 -> Netaji Subhash Engineering College
274 -> PSG College of Technology, Coimbatore
451 -> Pimpri Chinchwad College of Engineering, Pune
68 -> Pune Institute of Computer Technology
251 -> Pune Institute of Computer Technology
356 -> Raj Kumar Goel Institute of Technology
434 -> Raj Kumar Goel Institute of Technology
507 -> Rajiv Gandhi College Of Engg And Research, Nagpur
203 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley
419 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley
456 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley
510 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley
518 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley
522 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley
536 -> Rajiv Gandhi University of Knowledge Technologies, RK Valley
278 -> Rashtreeya Vidyalaya College of Engineering, Bangalore
342 -> Rustamji Institute of Technology
491 -> SASTRA University
521 -> SASTRA University
138 -> SR Engineering College, Hasanparthy
479 -> SRM University
196 -> Sardar Vallabhbhai National Institute of Technology, Surat
202 -> Sardar Vallabhbhai National Institute of Technology, Surat
332 -> Sardar Vallabhbhai National Institute of Technology, Surat
345 -> Sardar Vallabhbhai National Institute of Technology, Surat
377 -> Sardar Vallabhbhai National Institute of Technology, Surat
393 -> Sardar Vallabhbhai National Institute of Technology, Surat
449 -> Sardar Vallabhbhai National Institute of Technology, Surat
455 -> Sardar Vallabhbhai National Institute of Technology, Surat
487 -> Sardar Vallabhbhai National Institute of Technology, Surat
497 -> Sardar Vallabhbhai National Institute of Technology, Surat
503 -> Sardar Vallabhbhai National Institute of Technology, Surat
537 -> Sardar Vallabhbhai National Institute of Technology, Surat
540 -> Sardar Vallabhbhai National Institute of Technology, Surat
493 -> Shahjalal University Of Science & Technology
499 -> Shri Mata Vaishno Devi University
387 -> Shri Ramswaroop Memorial College of Engineering and Management
501 -> Sree Vidyanikethan Engineering College
505 -> Sree Vidyanikethan Engineering College
348 -> Sri Sivasubramaniya Nadar College of Engineering, Chennai
450 -> St Vincent Pallotti College of Engineering & Technology, Nagpur
157 -> Techno India NJR Institute of technology
343 -> Thapar University
416 -> Thapar University
263 -> The LNM Institute of Information Technology
308 -> The LNM Institute of Information Technology
440 -> The LNM Institute of Information Technology
478 -> The LNM Institute of Information Technology
492 -> The LNM Institute of Information Technology
321 -> University Institute of Engineering and Technology, Punjab University
427 -> University Visvesvaraya College of Engineering, Bangalore
488 -> University of Petroleum and Energy Studies, Dehradun
294 -> Veer Surendra Sai University of Technology, Orissa
32 -> Veermata Jijabai Technological Institute, Mumbai
194 -> Veermata Jijabai Technological Institute, Mumbai
270 -> Veermata Jijabai Technological Institute, Mumbai
447 -> Veermata Jijabai Technological Institute, Mumbai
498 -> Veermata Jijabai Technological Institute, Mumbai
199 -> Vellore Institute of Technology, Vellore
378 -> Vellore Institute of Technology, Vellore
541 -> Vellore Institute of Technology, Vellore
424 -> Vishwakarma Government Engineering College, Chandkheda
329 -> Vishwakarma Institute of Technology, Pune
119 -> Visvesvaraya National Institute of Technology, Nagpur
256 -> Visvesvaraya National Institute of Technology, Nagpur
295 -> Visvesvaraya National Institute of Technology, Nagpur
304 -> Visvesvaraya National Institute of Technology, Nagpur
328 -> Visvesvaraya National Institute of Technology, Nagpur
420 -> Visvesvaraya National Institute of Technology, Nagpur
452 -> Visvesvaraya National Institute of Technology, Nagpur
504 -> Visvesvaraya National Institute of Technology, Nagpur
530 -> Visvesvaraya National Institute of Technology, Nagpur
222 -> YMCA University of Science and Technology, Faridabad
380 -> YMCA University of Science and Technology, Faridabad

-----------------------------------------------------------------------------------------------
Waiting for the official results!

How I wrote a Sudoku Solver Program!

A few months ago, I wrote a Sudoku Solver program. It solves 9x9 Sudoku puzzles, instantly on any modern PC.

It was a long ordeal, I first started it just before my winter semesters, and the brute-force solver I came up with, would perhaps take hours to come to a solution in moderately hard sudoku puzzles. It was only after I took a Discrete Optimization course on Coursera (which I never completed :D), and more importantly, solved the Diabolic Sudoku puzzles myself  (for the first time :p ), with pencil-n-paper, that I came up with the idea of the fast solver, that actually worked.

Before I start with the programming part, I would like to write up a bit of background knowledge.

There are a lot of tricks to solve Sudoku with pencil-n-paper. We usually use deductive reasoning, i.e. we see the filled up boxes, mark the boxes with numbers that might fill up, and eliminate the impossible. If now there's a box with only one possibility, fill it up, and continue.

But often this basic strategy doesn't work too well with anything more than the cakewalk puzzles. Then we have to use other, bit more advanced tricks. Although I would love to enumerate those myself, but I don't think its mine to write, I learned those from these few websites:

1. http://www.paulspages.co.uk/sudoku/howtosolve/

2. http://www.sudokudragon.com/sudokustrategy.htm

3. http://www.sudokuoftheday.com/pages/techniques-overview.php

Caution: Much of the material above is redundant :) That is a long list of techniques.

The Catch? You might need them to solve hardest Sudoku on paper, but your PC can use backtracking. We can sacrifice a few milliseconds of speed for a simpler program. So we can program only a few of them, and even the hardest puzzles will be solved in small fractions of a second.

So, this is what I did:

1. Fill in all the empty boxes, with options, i.e. numbers that may fill the boxes, given the already filled up boxes, and no constraints (rules of game) are violated.

2. Check for locked pairs. See what locked pairs mean? or here. Now remove options, as appropriate.

3. Now see if there's any box with only one option left. If yes, then fill it.

4. If no box was filled in last step, the program needs to make a guess.  Find the box with least possible options. This is in accordance to the fail-first principle. Lesser the options, lesser to backtrack!

5. If the program gets stuck, i.e. at some point, there is nothing program can do, and the puzzle isn't yet solved, go to the last state, that's the point from which the decision was made, and take another decision.

In any of these states, prune the search space, by steps 1-3.

6. At the end, the puzzle is guaranteed to be solved, if it was valid, which might be checked at the beginning of the puzzle itself.

Here's the code:
sudoku solver 1.0

 You can checkout my Sudoku Program (Windows version), its licensed under GPLv3, that means you can mess up with the code here (Qt Creator code. All in C++, but may be a bit strange for people who've never used Qt creator.