I have a haunch that number puzzles in general, and the sudoku in particular, are more popular in countries like Japan , China, and the Arabic middle-east because the written forms of their languages do not easily lend themselves to crossword arrangement. By the name sudoku, it is reasonable to assume that the puzzle originated in Japan. However, a quick check in wikipedia would reveal that the first puzzles were published by Dell in the US, and eventually found their way to Japan where they become very popular and given the name by which they are currently known. A google search would reveal hundreds of sites dedicated to this mind game underscoring its popularity.
Anyway, I was introduced to sudoku by my boss (A Syrian doctor of Engineering) in my first company here in Dubai, who is an enthusiast of the game. You could tell the level of his addiction by the way he would summon me by phone to his office - which is just next door to mine - and, behind closed doors, would show me his latest sudoku slay. At first, I could only give him a stupefied smile and a feigned nod of appreciation while he gave me that I'm-smarter-than-you grin. A lecture on how he arrived at his elegant solution would usually follow - if I could not find my excuse to get out of his room in time. He would encourage me to take up the game as a means to fight stress and to ward off alzheimer's - plus a number of other benefits which is more than I really wanted to know. Later, whenever there is an opportune time, he would call me to his desk, and over coffee, he would ask me to work out the solution with him for particularly challenging pieces. He would do that almost every afternoon for the entire eight months that we worked together although I have the funny feeling that I was the only one working while he kept busy with his game. Even at restaurant tables or park benches during company outings, we would talk about sudoku. I guess it is safe to say that our social interaction revolves only around that single subject. Of course, I have to play along with my boss and besides, I'm starting to genuinely appreciate the game myself. In fairness to him, he is very good at it, needing me only to confirm his mastery of the game. I am not bad at deductive reasoning myself but I am not so keen about spending my time at such a juvenile task.
And soon, I just got fed up. I decided to show my computer programming side so that with one master stroke, we could set aside his puzzle book for good. I wrote a computer program for him.
But writing such a program is easier said than done. A manually-arrived solution is a product of tedious exercise in pure deductive reasoning or by a tenacious cut-and-try approach, or a combination of both techniques. Each sudoku puzzle is unique but a human analyst could usually make out a pattern which could be taken advantage of in order to find the shortest route to the solution. Unfortunately, such nuances and subtle nudges of the puzzle, which comes very clear and useful to the puzzle enthusiast, could not be recognized by the computer. In writing a general computer program that could solve every sudoku puzzle, it is possible to use a logical deductions approach (or any of the "human-like" methods of solving sudoku) but it would mean writing an impossibly complicated maze of if-then-else conditional branches and a formidable amount of bookkeeping to keep track of all the twists and turns. I therefore decided against using such methods and instead planned to write a sudoku program employing a sweeping, brute-force approach. For all of sudoko's complexity, the program is rather simple and short. This is how it works:
- The program marks and "remembers" the cells containing the given clues or knowns as well as the blank cells or unknowns.
- The unknowns are then numbered consecutively starting from the upper-left-most blank cell, proceeding to the right, and going down one row at a time. Each of the blank cell is given an initial value of zero.
- Starting with blank cell number one, the program considers one blank cell at a time in the order by which they were numbered.
- The current value of the blank cell under consideration is incremented by one to obtain a new trial value.
- The trial value is checked against the existence of its duplicate along the row, along the column, and within the 3x3 sub-grid to which the blank cell belongs.
- If a duplicate is detected, the program goes back to step 4 and will proceed to succeeding steps as usual;
- Else, if no duplicate is found, the trial number is provisionally adopted as the current value for that blank cell and the focus of consideration is shifted to the next blank cell. The program goes back to step 4 and from there, the process proceeds to the next steps as usual.
- In the process of assuming progressively higher trial numbers on an unknown cell, all the possibilities (1 to 9) may be exhausted without satisfying the non-duplicate condition. This would only mean that a current value on a previously solved cell is inconsistent. Thus, the program will reset the current value of the blank cell under consideration to zero, will backtrack to shift its focus of consideration to the previous blank cell and will go back to perform steps Nos. 4. to 7.
- The process is continued throughout until all the blank cells are filled out correctly without inconsistencies.
Now, this outlined procedure appears to be painstakingly laborious and exhaustingly repetitive. And indeed, it is a slow and plodding process - if it is to be done by hand. But computers thrive in drudgery and were devised to make mince meat of particularly boring tasks.
In short, I succeeded in writing a general sudoko program in a single sitting using the procedure outlined above. The following day, I presented it as a gift to my boss. He loaded it on his Presario and fiddled with the program for a while, testing randomly and reveling on its speed and accuracy. And then in his halting Arabic accent, gave me a gentle rebuke, "This is good, sonny. I like to keep it for checking my solutions. But you don't understand. I solve the puzzles because I like confronting and conquering mental challenges. Please don't take that thrill away." He was right of course, and I feel like some kind of a jerk. But I recovered in time and in an apologetic way, I told him, "I'm sorry, Ahmed, but that is not my intention. Actually, I like confronting mental challenges myself. And I consider writing a general program more challenging and thrilling, in a wholesale kind of way, than filling out those squares, one cell at a time". We both laughed and I knew he understood.
We still call each other- Dr. Ahmed and me, from time to time, even if I moved on to another company. We still talk about sudoku and lately he is again excited about another numbers puzzle – Kakuro! But that's for another article!
For those who are interested in sudoku and who would want to verify their solution against the computer, I have attached a compiled version which could be run directly on any PC. You could encode the givens from your morning paper, and then let the computer do the rest. Press the solve button and dig in for the long wait – all of seven hundred million nanoseconds on my intel centrino duo powered HP notebook. You could also use it to make and solve your own puzzles to impress unwary friends. It is so powerful that it could churn out a solution even without a single clue!
Just one reminder. Don't attempt to solve a puzzle with an innate error. For example, you cannot have, for a clue, two 7's in a single row.
For those who are interested in writing their own sudoku computer program (for the hundreds of talented young programmers from Asingan who are eager for a challenge), I have attached the VB text code for your reference. Comments have also been provided at each crucial point on the code to describe the functions and routines for better comprehension. I have kept features to a minimum, not wanting to dilute the essence of the game with unnecessary distractions. If you want to enhance, modifyor translate the program, please feel free to do so. If possible, e-mail me a note describing the changes you made and attach a copy of your version. Better still, you can post it here.
Happy computing, everybody!
No comments:
Post a Comment