"Whenever you can, share. You never know who all will be able to see far away standing upon your shoulders!"
I write mainly on topics related to science and technology.
Sometimes, I create tools and animation.
If you haven't played chess ever or are not acquainted with it, this is how a knight can move on a chessboard - the crosses are the only locations a knight can go to starting from the shown location. This movement is sometimes called a two-and-a-half-box-move.
Coming back to the tour problem, while there are many solutions for a given starting position, there exist closed solutions as well, which means that the first position is reachable from the last position after the completion of the tour (for the knight).
This tool doesn't try to find closed solutions, which is a completely different ball game.
It's possible for a knight on a chessboard to traverse the complete board visiting every position once and only once.
Here I'm using backtracking to find such a tour starting with any position. Press '1' in any cell in the grid below and hit Submit.
Note that there exist many solutions and this tool finds just one out of those.
This page can also be used as a service that returns a JSON with the result having the solution in the form of a flattened 2D array. Pass a 64 character string having all '0's but one '1' at any position, e.g.:
/knight-solution/0000000000000000000000000000000000000000000000100000000000000000
The very next month after I started MCA (Master of Computer Applications) course in 2006, I saw this challenge posted on notice board:
My first thought was that these were going to be too difficult, something beyond me... so "don't even think about it".
But just as they say like a dancer cannot control his feet on hearing beats, perhaps a coder cannot control his fingers given a keyboard and a problem!
At that time, I didn't even know the rules of Sudoku, let alone trying solving one ever. By the next month, I started to think about the Sudoku challenge seriously. So I quickly acquainted myself with the rules, and hit the keyboard. Having had no previous training in solving such kind of problems through a computer program, the first obvious technique I tried was brute force (though at that time I didn't even know if there was such a thing called brute force algorithm).
Well after spending couple of days I realized that that was not going to work. But while still trying to tweak my brute force code, this clicked to me: "what if I start with just some random initial values, and go on filling the cells selecting random options out of the available ones. Then as soon as I am stuck, I'll go to the last cell and try the remaining options from that point onward. If I am stuck again, I'll go two steps back and try the remaining options".
I immediate knew that a recursive function would be needed. And some kind of memory construct to remember the options selected at any given point of time. It was around 6-7 pm in the evening when all this struck me. It was so exciting to realize this potential technique that there was no question of sleeping... well I didn't sleep the whole night and by morning the program was ready - in C. I remember the next day there was a farewell function for one of our teachers and somehow I was chosen to conduct the stage. I did it - barely managing to hide both my sleepiness and the excitement - excitement to go back to my room and maybe to run the program a few hundred times and observe its beauty! Only in the second year of my course did I come to know that this technique was called backtracking!
The next day or maybe in couple of days I wrote the program for knight's tour as well. These two C programs have seen all my journey as a coder and have incarnated into many languages - VB.Net, C#, J2ME and Python.
Fast forward two years. I was in third year when the idea of converting my C program into something that could be run on mobile phones occurred to me. It was the year 2008. Google immediately told me that J2ME would be the language if I wanted the program to run on my Nokia phone. I borrowed a J2ME book from my college library and after a fortnight I was filling the Sudokus in the newspapers in the college library everyday in two minutes (using my phone of course)! Don't worry, I stopped doing it after a week as I had already satisfied my programmer's itch and I didn't want to come in the way of habitual Sudoku solvers 🙂.
Find the link to the Sudoku solver below.
