During this week, I was thinking about writing a very long blog post about Cryptography but then it would be too long for the readers that it might get them to feel bored. So, for starters, I thought about making a series of short blog posts called "Let's Cipher This" that would focus on the areas of Cryptography.

What is it about?

Well, the aim of this series is that I want to talk about Codes (I meant secret "codes") and Ciphers, such as:

• How they both work
• How can they both be used to encrypt/decrypt messages
• How to use different methods/strategies to break intercepted code

What's next?

I know that there are a lot of simple and complex ciphers/crypto algorithmic techniques out there and I wanted to make each post as informative and interactive as possible i.e. by giving a detailed description about the cipher/technique, it's history, how it works and it's implementation, which can also be used as a tool for encrypting/decrypting your own messages.

The series is going to be a "Work in Progress", so there won't be an ending to it as the field of the Cryptography is quite vast, deep and complex. I will be updating this series as often as I can, so watch out for new posts that are related to it!

Before you read about this article, try playing the Sudoku Solver above. You can only insert numbers ranging from 1 to 9 in any empty cell. Press Random Level to generate a random sudoku puzzle. Made a mistake? Press Reset to clear the board. To test the algorithm, Press Solve to complete the entire puzzle.

As for the source code, you can view it in my GitHub repository or can be found near the end of this article.

What is Sudoku?

Sudoku stems from the two Japanese words: "Su" and "doku", when translated to English, it means "single numbers only". Although, many people feel that Sudoku was invented by the Japanese, it was actually invented by an American named Howard Garns in 1979 under the name "Number Place" but died in 1989 before a Japanese publisher named Nikoli made it popular, renamed it as "Sudoku" and which of course, became mainstream in 1986.

What is it about?

Sudoku is a logic-based, combinatorial, 9x9 number grid puzzle. The puzzles are usually a partially completed grid, thus allows the puzzle solver to come up with a single solution to the puzzle. The objective of this game is to fill the empty spaces in the partially completed 9x9 grid in such a way that each row, column and 3x3 subgrids (that compose the grid) contains all digits from 1 to 9.

Why did I build it?

Well, one day, I downloaded a Sudoku game on my iPhone and I got hooked to it instantly. I would play the game, usually, during metro rides to my university or any long trips to not make myself feel bored. So one day, I thought "What if I built a sudoku solver and see if it could solve all the puzzles from the game?", which made me even more curious to see how a computer would do it.

Implementation

Okay, I know this is the part that you must be waiting for: "How to implement this?". As I was doing my research on how to implement it, I came across two algorithmic techniques:

• Recursion
• Backtracking

Recursion

Recursion is an algorithmic technique used for breaking down larger problems into smaller instances of the same problem. This is also known as Divide-and-Conquer method. This is usually used in binary search, reversing a file, generating large Fibonacci numbers and the list could go on.

Backtracking

Backtracking is an algorithmic technique used for searching every possible combination in order to solve a problem in an optimized way. You could be familiar with this technique in popular problems like Chess, the 8 Queen Puzzle or Crossword solvers.

Explanation

Imagine, you're playing chess with a friend and you've made a silly move, which prompts you to ask your friend: "Hey, I made a mistake! Can I go back to my old move?", your friend (hopefully, a merciful one) would allow you to return back to your old move. So in this case, you'll return back to your old position and begin to restrategize your plans on how to take down the next pawn or maybe finally hatch your plot to trap your opponent's King (you evil person). If it fails, you can ask again but I don't think your friend would be dumb enough to give you another chance!

Here's a pseudocode on how this strategy would work:

Find [row,col] of an unassigned cell
If there is none, then return true

For digits from 1 to 9
    If there is no conflict for digit at [row,col]
        Assign digit to [row,col] and recursively try to fill in the rest of the grid
        If this recursion is successful, return true
        Otherwise, remove this digit and try another one
    If all digits have been tried for this cell and nothing worked out
        return false, trigger backtracking and try again

Javascript implementation:

//Sudoku solver 
function solveSudoku(grid, row, col) {
    var cell = findUnassignedLocation(grid, row, col);
    row = cell[0];
    col = cell[1];

    // base case: if there's no empty cell  
    if (row == -1) {
        return true;
    }

    for (var num = 1; num <= 9; num++) {

        if (noConflicts(grid, row, col, num)) {   
            grid[row][col] = num;

            if (solveSudoku(grid, row, col)) {                
                return true;
            }

            // mark cell as empty (with 0)    
            grid[row][col] = 0;
        }
    }

    // trigger back tracking
    return false;
}

//Find an empty cell
function findUnassignedLocation(grid, row, col) {
    var done = false;
    var res = [-1, -1];

    while (!done) {
        if (row == 9) {
            done = true;
        }
        else {
            if (grid[row][col] == 0) {
                res[0] = row;
                res[1] = col;
                done = true;
            }
            else {
                if (col < 8) {
                    col++;
                }
                else {
                    row++;
                    col = 0;
                }
            }
        }
    }

    return res;
}

//Check if there are any conflicts in row, column or 3x3 subgrid
function noConflicts(grid, row, col, num) {
    return isRowOk(grid, row, num) && isColOk(grid, col, num) && isBoxOk(grid, row, col, num);
}

//Check if this number is valid in this row
function isRowOk(grid, row, num) {
    for (var col = 0; col < 9; col++)
        if (grid[row][col] == num)
            return false;

    return true;
}

//Check if this number is valid in this column
function isColOk(grid, col, num) {
    for (var row = 0; row < 9; row++)
    if (grid[row][col] == num)
        return false;

    return true;    
}

//check if this number is valid in 3x3 subgrid
function isBoxOk(grid, row, col, num) {
    row = Math.floor(row / 3) * 3;
    col = Math.floor(col / 3) * 3;

    for (var r = 0; r < 3; r++)
        for (var c = 0; c < 3; c++)
            if (grid[row + r][col + c] == num)
                return false;

    return true;
}

What's next?

So now that you have understood the rough concept of how it works, combining and applying these two techniques in a Sudoku puzzle i.e. trying out every possible number to fill an empty square in the 9x9 grid would allow the computer to solve Sudoku puzzles more efficiently and quickly than using a plain Brute Force technique on puzzle that has around 4 x 1038 possibilities (which means, you'll probably require next-gen hardware to compute one puzzle that could take billions of years!)

Oh, you can play around with the Sudoku Solver above by trying out a Sudoku puzzle or generate a random one and solve it. Or best, if you'd like to challenge yourself, you could try to implement this solution on Project Euler's Problem 96 by solving all 50 sudoku puzzles in a row!

References

• Stanford's Exhaustive Recursion and Backtracking
• Solving Every Sudoku Puzzle

Hello World! This is my first blog post.

#include <iostream>
int main()
{
    cout << "Hello World" << endl;
    return 0;
}

I'm not a huge fan of open source CMS projects like Wordpress and Drupal, I decided to build my own custom blog engine for talking and discussing about my favorite topics.

For this blog, I aimed for a minimalistic look, hence I decided not to use any templates or CSS frameworks to make it look bloated or fancy.

On using this blogspace of mine, I intend to talk about technology, math, computer science, design, programming experience and a lot of positive stuff.

Hopefully, I will try my best to update this blog as frequently as possible.

Hope you guys will enjoy reading my future blog posts!