It's a 2D table tennis simulation game. The player controls a paddle that moves vertically up and down on the side of the screen and can compete against AI or a second player, who controls the second paddle on the opposite side. The aim of the game is to hit the ball back and forth and reach 11 points before the opponent (although, I didn't build a scoring system for my implementation as I felt it wasn't necessary).
History
Pong is one of the most popular and commercially successful arcade game built by Atari, Inc in 1972. It was the company's first game and was created by Allan Alcorn, who got it as a warm-up exercise from the founder of the company, Nolan Bushnell.
Game mechanics
There are two important mechanics that made it challenging to build this game:
While I was building Pong, I thought of making it a 2 player game but later I decided to build a simple AI to make things interesting. Building the AI logic for this was simple, "When the player paddle hits the ball, the AI should try it's best to position itself by tracking the ball's destination to hit the it's center".
Code snippet of the AI object:
varai={x:null,y:null,width:10,height:100,//Update the AI paddle position based on the ball's directionupdate:function(){vardest_y=ball.y-(this.height-ball.side)*0.5;this.y+=(dest_y-this.y)*0.1;this.y=Math.max(Math.min(this.y,height-this.height),0);},draw:function(){ctx.fillRect(this.x,this.y,this.width,this.height);}};
Ball Collision
In this game, the collision works a little different than Breakout's version. I came across an algorithm called Axis Aligned Bounding Box, which is one of the simpler forms of detecting a collision between a set of objects that are axis aligned that means no rotation. This algorithm also inspired me to use it in my next game, Tetris.
Code snippet of the Axis Aligned Bounding Boxes collision:
//AABB Collision functionvarAABBCollision=function(px,py,pw,ph,bx,by,bw,bh){returnpx<bx+bw&&py<by+bh&&bx<px+pw&&by<py+ph;}//if the ball has -ve velocity, it's hit by AI paddle and it's the player's turn//if the ball has +ve velocity, it's hit by player paddle and it's the AI's turnvarpaddle=this.velocity.x<0?player:ai;if(AABBCollision(paddle.x,paddle.y,paddle.width,paddle.height,this.x,this.y,this.side,this.side)){this.x=(paddle==player?player.x+player.width:ai.x-this.side);varn=(this.y+this.side-paddle.y)/(paddle.height+this.side);varphi=0.25*pi*(2*n-1);vardir=(paddle==player?1:-1);varimpact=Math.abs(phi)>0.2*pi?1.5:1;this.velocity.x=impact*dir*this.speed*Math.cos(phi);this.velocity.y=impact*this.speed*Math.sin(phi);}
The game was built using HTML5 Canvas and Javascript, so please feel free to read the source code to understand the logic of the game.
What's next?
Building this game was fun as I built a simple AI and implemented a better collision detection algorithm. In my first post of this series, I had mentioned that I was working on Tetris and honestly, I finished building that game today as I didn't find the time to work on it. Now that it's ready, hence, my next post will be about Tetris.
This is the second post of this month's personal challenge. I'll be talking about Breakout, it's history and game mechanics, in short.
Before you read more about this article, play with the above game. You can control the paddle using the mouse or left-right arrow keys. Press P to pause the game. Press S to resume and R to restart the game.
This is part of the Arcade Challenge series. In the previous post, I built a snake game, click here if you've not read the article.
Background
Breakout is a single player game where you have to break a layer of bricks with a ball that travels across the screen (in this case, it's a canvas) that bounces off the walls of the screen. When the ball hits a brick, the ball bounces back and of course, the brick gets destroyed or disappears. If the ball touches the bottom of the screen, the game is over. In order to prevent this from happening, the player is given a movable paddle to bounce the ball upwards, which ensures the game continues.
History
Breakout was one of the most popular arcade games developed by Atari, Inc. Inspired by the 1972's Pong, the game was developed and designed by Nolan Bushnell, Steve Wozniak, Steve Bristow using the hardware built for Pong against it's competitors who built clones of Pong.
Atari's Video Pinball console system
Most notably, the late Steve Jobs was also involved with the development of Breakout as he was approached by Nolan Bushnell to design a prototype that required 150 to 170 computer chips. Jobs brought in Wozniak to work with along with him on building the prototype, who built a version of Pong using 30 computer chips and they both had spent days and nights working on it and finally built the prototype that had 44 computer chips.
However, Wozniak's design wasn't approved by Atari, Inc as they found the design to be complicated and infeasible to manufacture, so they ended up making their own version of the hardware which contained around 100 computer chips.
Game mechanics
Unlike the previous post, the game mechanics of this game are quite simple to understand and it makes use of 2D Mathematics.
Using 2D Mathematics, I was able to program the ball-brick collision, movement and bounciness of the ball and the movement of the paddle (which can only move on the x-axis).
Collision Detection
To check for ball collision, the program must check if the ball has touched / collided with the wall, if so, then the ball's direction will be changed accordingly. The ball can only bounce off from the top, left and right side of the walls and the paddle, if it touches the bottom of the canvas, it's game over.
Ball Movement and Collision Detection:
If the distance between the ball radius and the wall's edge is the same, it will change the ball direction. This would allow a proper ball collision to bounce off the walls.
Code for Ball Movement and Collision Detection:
$(document).ready(function(){//Canvas stuffvarcanvas=document.getElementById("ball_collision_canvas");varheight=canvas.height;varwidth=canvas.width;varctx=canvas.getContext("2d");//coordinates of the ballvarx=canvas.width/2;vary=canvas.height-30;vardir_x=2;vardir_y=4;varball_r=10;//Draw a circlefunctioncircle(x,y,r){ctx.fillStyle="#FF6D6D";ctx.beginPath();ctx.arc(x,y,r,0,Math.PI*2,true);ctx.closePath();ctx.fill();}//Draw canvasfunctiondraw(){ctx.clearRect(0,0,width,height);circle(x,y,ball_r);/* If the distance between the ball radius and the wall's edge is the same, it will change the ball direction. This would allow a proper ball collision to bounce off the walls. */if(x+dir_x>width-ball_r||x+dir_x<ball_r){dir_x=-dir_x;}if(y+dir_y>height-ball_r||y+dir_y<ball_r){dir_y=-dir_y;}x+=dir_x;y+=dir_y;}setInterval(draw,10);});
The game was built using HTML5 Canvas and Javascript, so please feel free to read the source code to understand the logic of the game.
What's next?
In my next post, I'll be talking about the third game that I built in this challenge, Pong. Well, that's it for today, hope you guys have found this post interesting and yes, have fun playing the game!
This is the first post of this month's personal challenge. I'll be talking about Snake Game, it's history and game mechanics, in short.
Before you read more about this article, play with the above game. You can control the snake using WASD or the ←↑↓→ keys. Orange block is for food, it'll increase your score. Yellow block is for poison, if eaten, it'll reduce your score. Press Space to pause the game. Press P to resume and R to restart the game. Oh and avoid hitting the white walls!
Background
Snake is a game of simple concept where the player manuevers the snake in all 4 straight directions (reverse movement is not possible i.e. UP, DOWN, LEFT, RIGHT only) to eat the fruit and as a result, the length of the snake increases, making the game difficult for the player. The player will have to prevent the snake to hit the walls or from eating the poison, which will decrease the snake's length, and also prevent it from hitting itself.
History
I remember playing this game, for the first time, on my father's monochrome Nokia 3310 mobile phone (which can still break walls, I guess!) and every 90's kid I knew played this game a lot.
Nokia 3310 (in case, if you've never heard about it!)
The game was published by Nokia and it was programmed by a Nokia Design Engineer named Taneli Armanto in 1997 for Nokia 6110. The original concept of this game was derived from an arcade game called Blockade, which was published in 1976 by Gremlin Industries. Ever since, there have been so many variations and clones of this game, in fact, there are over 300+ variations of this game for iOS devices alone.
Game mechanics
The game makes use of Linked Lists, which is a simple and dynamic data structure used to store and control the movement of the snake. Below is the pseudocode for each of the game's behaviour:
Movement of the Snake:
for node in the list (always starts from the end of the list):
if node is not equal to head node:
shift the snake's position to node+1 (by making it closer to the snake)
set head node to new position
endfor
Length of the Snake:
nx: current x coordinate of the snake head
ny: current y coordinate of the snake head
fx: x coordinate of the food
fy: y coordinate of the food
px: x coordinate of the poison
py: y coordinate of the poison
if [nx] matches with [fx] and if [ny] matches with [fy]:
push the new cell to the snake's tail node
shift the new cell from tail node to the head node
increment score + 1
if [nx] matches with [px] and if [ny] matches with [py]:
pop the cell from the tail node
shift cell from tail node to head node
decrement life - 1
Collision of the Snake:
nx: current x coordinate of the snake head
ny: current y coordinate of the snake head
sx: x coordinate of the snake cell
sy: y coordinate of the snake cell
wx: x coordinate of the wall cell
wy: y coordinate of the wall cell
for cell in the wall array:
if [nx] matches with [wx] and if [ny] matches with [wy]:
display "game over" message
for cell in the snake list:
if [nx] matches with [sx] and if [ny] matches with [sy]:
display "game over" message
Oh yeah, please feel free to study the source code of this game in order to understand how this game was implemented on Javascript.
What's next?
In my next post, I'll be talking about, the second game that I built in this challenge, Breakout. I hope you've found this article interactive and interesting and yes, have fun playing this game!
I challenged myself to build four arcade games during this month. Hope you'll enjoy reading this article.
Alas! It has been a long time since my last blog post.
Last month was the Holy Month of Ramadan, so I kept myself busy with my religious duties and it also kind of ruined my sleeping pattern, thus I was tired to post anything. Since I was pretty exhausted after that, I decided to take a week off from work to spend some time with my family and also thought of working on my side projects and then I realized that I need to set a personal challenge to get myself motivated for the month.
What's the challenge?
When I was building this blog, I had the intention of remaking arcade games and posting them over here for the visitors to come and play them! So since I had a week off from work, I challenged myself to build four arcade games this month and create a separate blog post for each game, where I would be talking about how it was built, it's history and it's game mechanics.
These are the list of games that I had planned to build/already built during this month:
Snake
Breakout
Pong
Tetris
How did the challenge feel?
Honestly, it was really refreshing and felt like a mini-hackathon. I was able to learn new things about Game Programming and 2D Mathematics and as a result, I have upgraded my knowledge on Javascript as well. Although I told myself that I would build all of these games in a month, during my time off, I was able to build everything except Tetris as I'm still working on it.
What's next?
I know this is a short post but I'm working on the content for each blog post, so that it doesn't feel rushed! Once I have posted all of them, I'd like to know your views on each of them and it would be also nice if you could suggest any arcade games that I could remake!
A blog post on how to become a productive, efficient and competent programmer.
Have you ever felt unproductive, bored, burnt out or stuck in a block? Yes, I've gone through that during my earlier days of programming and sometimes, even now, especially when working on large projects (side projects or work related).
How did I overcome it?
As time passed by, one day, I asked myself: "How do I become productive?" and "How do I overcome this negative barrier and become much more competent and efficient at solving problems?". If you've ever questioned yourself about this, then this blog post is for you.
I have developed and learnt some strategies and techniques to overcome this negative barrier such as:
During my earlier days of programming, I would give very less thought to the design or the structure of the project and dive straight into coding it. Thus, I produced a lot of errors, dirty code and a buggy mess. It would be okay for a small project but what if you are asked to build a software that is used in the Wall Street Stock Exchange to monitor real-time trading which involves 99.9% of accuracy and correctness and handles millions of transactions per second? Yeah, that's not going to turn out really well for you and your client.
Suggestions:
Gather your requirements and analyze them
Design it using a pen and paper and brainstorm different strategies on how to solve the problem
Build a prototype
Try to make your program fail earlier as it is much easier to fix than later
Document your work
Repeat
It's like building a house, if there's no requirement analysis and design before building the project, you're more likely going to end up with a overly coupled and high cohesion software that also means your code will be harder to debug, harder to write and add new features and put it on production and very unlikely, it wouldn't perform really well.
Write clean code and refactor it
We have all been there, when we are trying to figure out:
"What does this method do?"
Why you wrote a huge class with methods that contain 100+ lines of code and that is hard to debug or understand it's original logic?
That variable name that doesn't make any sense at all.
Suggestions:
Write clean and short blocks of code
Write meaningful variable names, methods and classes
Follow a Singleton Pattern
Try to write methods that are less than 100 lines of code
These suggestions should help you as our minds can't really handle a lot of complex logic especially if you have a piece of code that's unneccessary long and complex which could be harder to debug. Good luck on that!
DRY i.e. Don't Repeat Yourself
Whenever you have tasks that are too mundane, repetitive or time consuming, consider automating that process which could save your time and help you focus your energy on solving the actual problem.
Examples:
You could build a Code Generator to speed up your process of building classes, objects, variables, methods and so on.
You could write a script to create your project file structure with all the necessary folders and boilerplate code using Powershell (Windows) or Bash (Linux).
You could build a dynamic webpage to display different content instead of building hundreds of static pages which might have the same way of displaying content as a dynamic one.
You could write an automated test to look out for bugs and errors in your code and fix them quickly.
There are so many ways to automate your work and all you have to do is look for a specific pattern, especially if it's repetitive, in the problem that you are trying to solve..
Prioritize your tasks
We all need to prioritze our tasks in order to feel more productive every day.
Suggestions:
Keep a checklist and keep track of your tasks for the day.
Solve problems that you feel is the most important as majority of the time is usually spent on solving the wrong problems.
Try to refrain from multitasking as it could be inefficient.
Step away from the keyboard and take a break every few minutes.
But please use these tips at work, don't ever take work to home, unless it's really urgent, as it could be a sign of bad management skills and which means you might need to restrategize the way you work in order to be more efficient.
Use the right tools for your project
Today, due to the proliferation of various technologies, there are so many tools out there but it can get confusing to choose the right one, so choose the tools that you feel most comfortable with and master it. I know that there are a bunch of programmers who'd debate VIM over Emacs, Microsoft Visual Studio over NetBeans, MySQL over NoSQL or C++ over Javascript but does this mean that one of them is better than the other?
No, it doesn't even matter because each of them has it's own pros and cons and is used for specific purposes or tasks but it is you who has to choose the kind of tools that you would like to have at your disposal.
Read other people's code
Seriously, it's one of the best ways to learn. As you read code, you might encounter:
Different programming patterns
New libraries or APIs
New programming syntax or techniques
Some of those encounters might be new or even unheard of, research about them using Google and try to implement it in one of your projects (not on your work-related projects).
Reading code written by other programmers is very important as it will be helpful with code reviews, debugging and working on any open source project(s).
Work on side projects
To some extent, the projects you work on during office hours might not keep you too busy or challenge you enough, so instead, you'll have to spend some time working on side projects.
Now, for some people, they would enjoy their weekend and stay away from code after a long week of programming until next Sunday, I totally agree and yes it's fine to take a break as most of us might not have the luxury of free time but for those who do, by working on side projects, it doesn't necessarily mean that you should spend a lot of time on it, you can work on them for about 2-3 hours a week.
Suggestions:
You could learn how to use that new tool, library, API
Build a small game
Implement an existing algorithm
Solve a math equation (for those who love math)
Study on how to use Regular Expressions (very useful)
Learn and experiment a new programming language or technique
By working on side projects, you'll be adding new skills to your existing skillset and that could help improve your career.
Read more books
Yes, you can find a lot of learning material in the form of tutorials, YouTube videos and online courses but nothing beats reading a book that is written by a good yet experienced developer as the author would tend to go deep and give a lot of insights as to why he/she chose to solve a problem in a specific/particular manner.
Also, it talks about the journey of the developer as to how they succeeded, made mistakes and learnt from it during their career.
What's next?
Hopefully, these tips and suggestions should have given you an idea on how to make yourself feel more productive, efficient and competent at programming.
An article about monoalphabetic substitution ciphers, it's applications and variations.
This is the first post in the "Let's Cipher This!" series and in this post, I'll be talking about the various versions of Monoalphabetic Substitution Ciphers such as:
This post will be a bit longer than my previous ones as I had been occupied with a lot of work and other commitments. But I do feel the need to post something atleast once a month with good content, as it keeps me productive (especially during weekends), so hope you'll find this information useful!
What's a Monoalphabetic Substitution Cipher?
It's a type of substitution cipher that is used to replace each letter of a plaintext with another letter using a fixed number or replacement structure, which makes up the ciphertext. There are many variations of these, but today, I have decided to talk about a few that I have mentioned, in the beginning.
Atbash Cipher
Atbash Cipher is a monoalphabetic substitution cipher which is used, originally, to encode Hebrew Alphabets but when modified, it can also be used with any alphabets.
Algorithm
The algorithm is pretty straight-forward, if you have a plaintext of "ABCDEFGHIJKLMNOPQRSTUVWXYZ", then the ciphertext would be the exact reverse of the plaintext: "ZYXWVUTSRQPONMLKJIHGFEDCBA".
Encrypting the message is very simple, you just have to replace every letter of the plaintext with the ciphertext, for example, 'A' would become 'Z' and 'T' would become 'G' and the whole message would be encrypted in this manner.
Decrypting the Atbash Cipher is the opposite of it's encryption process, for example, 'Z' would become 'A' and 'G' would become 'T' and the whole message would be decrypted in this manner.
As you might have understood, this is not a secure cipher and in fact, can be broken very easily, assuming, that the ciphertext has been enciphered using Substitution Cipher or by determining the key by trying out each and every letter i.e. using hill-climbing technique.
However, it can be a bit secure if you add some numbers and punctuation to the plaintext alphabets:
Caesar Cipher is one of the most widely known and simplest substitution ciphers (you probably heard about it or were introduced to it in one of your earlier computer science classes by your ingenious professor!), in which each letter from the plaintext is replaced with another letter that is determined by a fixed number of positions or "shifts". This is named after Julius Caesar, who used it to send private messages that are related to military intelligence with a shift of 3. This is also used in modern ROT-13 system with a shift of 13.
Algorithm
The ciphertext is made by aligning two alphabets, so in this case, I will be using a shift of 15 i.e. letter 'A' would be letter 'P' and letter 'B' would be letter 'Q' and so on.
The encryption process is represented using Modular Artihmetic by transforming the letters into it's positions and the mathematical formula is:
E(x) = (x + n) mod 26
By using this formula, we can encrypt our plaintext with a shift of 15:
shifts(n): 15
plaintext: H E L L O W O R L D
integers(x): 7 4 11 11 14 22 14 17 11 3
E(x) = (x + 15) % 26: 22 19 0 0 3 11 3 6 0 18
ciphertext: W T A A D L D G A S
Decryption
The decryption, again, is done is reverse with a shift of 15 using Modular Arithmetic i.e. letter 'P' would be letter 'A' and letter 'Q' would be letter 'B' and so on. The mathematical formula for deciphering the text is:
D(x) = (x - n) mod 26
We can use this formula to decrypt the ciphertext:
shifts(n): 15
ciphertext: W T A A D L D G A S
integers(x): 22 19 0 0 3 11 3 6 0 18
D(x) = (x - 15) % 26: 7 4 11 11 14 22 14 17 11 3
plaintext: H E L L O W O R L D
Cryptanalysis
Caesar Cipher is insecure and can be easily broken in two scenarios:
If the cryptanalyst deduces that it's a Caesar Cipher but doesn't know the shift key.
If the cryptanalyst figures out that some sort of substitution cipher is used but doesn't know that it's Caesar Cipher.
In the first scenario, it's more straightforward as there are only a limited number of possible shifts (e.g. 26 in English) and can use a Brute Force atack to crack the ciphertext. For the second one, it can be broken using techniques like Frequency analysis or looking for patterns.
Affine Cipher
Affine Cipher is a type of monoalphabetic substitution cipher but it's different compared to Atbash Cipher but similar to Caesar Cipher, where each alphabet is mapped to it's numerical equivalent and then it is encrypted using a simple mathematical function.
Algorithm
The letters are first mapped to the integers in the range of 0, 1, ..., m-1(m = the length of the alphabets used), which then uses a Modular Arithmetic method to convert the integers to it's corresponding letter.
alphabets: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
integers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Encryption
The mathematical formula for encrytion is:
E(x) = (ax + b) mod m
In this formula, a and b are the keys of the cipher and m is the size of the alphabet. The key a must be chosen in such a way that a and m are coprime i.e. "a should not have any common factors with m."
Decryption
Unlike the encryption formula, the decryption process of the ciphertext is performed inversely to retrieve the plaintext:
D(x) = c(y - b) mod m
In this formula, c is the Modular Multiplicative Inverse of a. In order to find the multiplicative inverse of a, you need to find a number x in such a way that it satisfies the following equation:
ax = 1 (mod m)
Explanation
Let's say you want to encrypt a plaintext that says "HELLOWORLD" with a = 5 and b = 8. The reason I chose "5" for a is because it has to be relatively prime with 26.
plaintext: H E L L O W O R L D
integers(x): 7 4 11 11 14 22 14 17 11 3
Now, you have to take each value of x and convert it to a different letter using the encryption formula mentioned above:
key a = 5
key b = 8
plaintext: H E L L O W O R L D
integers(x): 7 4 11 11 14 22 14 17 11 3
E(x) = 5(x) + 8 % 26: 17 2 11 11 0 14 0 15 11 23
ciphertext: R C L L A O A P L X
Okay, let's decrypt the ciphertext that says "RCLLAOAPLX" to "HELLOWORLD" using the same keys (a = 5, b = 8):
ciphertext: R C L L A O A P L X
integers(y): 17 2 11 11 0 14 0 15 11 23
Before we proceed, we need to find the modular inverse of a, in this case, it would be 21. You can find the modular inverse using the Extended Euclidean algorithm, which uses Greatest Common Divisor(GCD) of both a and m. If a has a modular inverse modulo m, then the GCD must be 1.
Once you find a, we can start decrypting the ciphertext:
key a = 5
key b = 8
ciphertext: R C L L A O A P L X
integers(y): 17 2 11 11 0 14 0 15 11 23
D(y) = a(y - 8) % 26: 7 4 11 11 14 22 14 17 11 3
plaintext: H E L L O W O R L D
Cryptanalysis
Affine Cipher is known to be a very insecure cipher as it's just another version of Caesar Cipher, which is due to it being a monoalphabetic substitution cipher. If a cryptanalyst is able to discover 2 or more common characters using techniques like Brute Force, Frequency Analysis or maybe even guessing, the key can then be obtained via solving a Simultaneous Equation, since a and m are coprime, it can discard any wrong keys easily in an automated program.
What's next?
So I hope you have understood what's a monoalphabetic substitution cipher and it's applications and variations. You can play around with the encryption tools above or experiment with your own messages to see how it works and prank your friends with it!
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!
I built a sudoku solver using Javascript by implementing the Exhaustive Recursion and Backtracking algorithms.
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 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 functionsolveSudoku(grid,row,col){varcell=findUnassignedLocation(grid,row,col);row=cell[0];col=cell[1];// base case: if there's no empty cell if(row==-1){returntrue;}for(varnum=1;num<=9;num++){if(noConflicts(grid,row,col,num)){grid[row][col]=num;if(solveSudoku(grid,row,col)){returntrue;}// mark cell as empty (with 0) grid[row][col]=0;}}// trigger back trackingreturnfalse;}//Find an empty cellfunctionfindUnassignedLocation(grid,row,col){vardone=false;varres=[-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;}}}}returnres;}//Check if there are any conflicts in row, column or 3x3 subgridfunctionnoConflicts(grid,row,col,num){returnisRowOk(grid,row,num)&&isColOk(grid,col,num)&&isBoxOk(grid,row,col,num);}//Check if this number is valid in this rowfunctionisRowOk(grid,row,num){for(varcol=0;col<9;col++)if(grid[row][col]==num)returnfalse;returntrue;}//Check if this number is valid in this columnfunctionisColOk(grid,col,num){for(varrow=0;row<9;row++)if(grid[row][col]==num)returnfalse;returntrue;}//check if this number is valid in 3x3 subgridfunctionisBoxOk(grid,row,col,num){row=Math.floor(row/3)*3;col=Math.floor(col/3)*3;for(varr=0;r<3;r++)for(varc=0;c<3;c++)if(grid[row+r][col+c]==num)returnfalse;returntrue;}
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!