The Sudoko Challenge

by Sonny Espejo

.

Sudoku is a number arrangement game which is currently very popular here in Dubai and possibly in other places (the entire world, if I may believe the hype carried in the puzzle caption of the morning paper). Sudoku is to numbers as Crossword Puzzle is to words. The puzzle is played on a grid of nine by nine squares further grouped into 9 sub-grids of three by three squares. The object of the game is to fill-out the squares exclusively with the digits 1 to 9 so that any given digit will appear once and only once in a row, only once in a column, and only once in a 3 by 3 sub-grid. An unsolved sudoku puzzle is sprinkled with about 25 pre-filled squares of seemingly random distribution but are actually cleverly placed clues to ensure a unique solution.

.

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 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 cared to know.

.

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.

.

How it works

1. The program marks and "remembers" the cells containing the given clues or knowns as well as the blank cells or unknowns.

2. 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.

3. Starting with blank cell number one, the program considers one blank cell at a time in the order by which they were numbered.

4.The current value of the blank cell under consideration is incremented by one to obtain a new trial value.

5.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.

6. If a duplicate is detected, the program goes back to step 4 and will proceed to succeeding steps as usual;

7. Else, if no duplicate is found, the trial number is provisionally adopted as the current value for that blank cell and the focus of attention 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.

8. 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.

9. The process is continued throughout until all the blank cells are filled out correctly without inconsistencies.

.

Now, the above 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.

.

Finally, I succeeded in writing a general sudoko program in one 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, Isah (which is how he calls me). 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.

.

.

For those who are interested in sudoku and who would want to verify their solution against the computer, I could send you a compiled version for free which you could run directly on any PC. (Just e-mail me at sonny.espejo @ gmail.com).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 SLC who are eager for a challenge), I have attached the VB text code which you could cut and paste 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, modify or 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, everyone!

.

I invite and would welcome any comment or discussion, even ideas for another approach or algorithm.

.
-ise
.
The Sudoko Program in VB

‘******************
‘Sudoko
‘by engr. sonny espejo
‘aka icarus
‘******************
'
‘**************************************************************
'The sub-routine Cruncher is the meat of the program.
‘All the other routines are either for data entry, data display
‘or file handling. Cruncher was written based on the outlined
'procedure above
‘**************************************************************

Dim Trial(81) As Integer
Dim RowNo(81) As Integer
Dim ColNo(81) As Integer
Dim C(9, 9)

Private Sub Form_Load()
Show
Line (cell(1).Left - 60, cell(1).Top - 60)-(cell(81).Left + cell(81).Width + 50, cell(81).Top + cell(81).Height + 50), vbBlue, BF
cell(1).SetFocus
End Sub

Private Sub cell_KeyDown(Index As Integer, KeyCode As Integer, Shift As Integer)
If KeyCode = vbKeyLeft Then
Index = Index - 1
If Index < index =" 81" keycode =" vbKeyRight" index =" Index"> 81 Then Index = 1
End If

If KeyCode = vbKeyReturn Then
Index = Index + 1
If Index > 81 Then Index = 1
End If

If KeyCode = vbKeyUp Then
Index = Index - 9
If Index < index =" Index" keycode =" vbKeyDown" index =" Index"> 81 Then Index = Index - 9
End If

SelStart = Len(cell(Index).Text) + 1
cell(Index).SetFocus
End Sub

Private Sub cell_Change(Index As Integer)
If Val(cell(Index).Text) < text = ""> 9 Then
cell(Index).Text = ""
Else
cell(Index).Text = Val(cell(Index).Text)
End If
End Sub

Private Sub FileNewMenu_Click()
For i = 1 To 81
cell(i).Text = ""
Next i
End Sub

Private Sub FileOpenMenu_Click()
RetrieveData
End Sub

Private Sub FileSaveMenu_Click()
SaveData
End Sub

Private Sub FileExitMenu_Click()
End
End Sub

Private Sub HelpGettingStartedMenu_Click()
Frame1.Visible = True
End Sub

Private Sub SolveMenu_Click()
Cruncher
End Sub

Private Sub AboutHelp_Click()
Frame2.Visible = True
End Sub

Private Sub Command1_Click()
Frame1.Visible = False
End Sub

Private Sub Command2_Click()
Frame2.Visible = False
End Sub

Sub SaveData()
CommonDialog1.ShowSave
Q$ = CommonDialog1.FileTitle
Open Q$ For Output As #1
ctr = 0
For i = 1 To 9
For j = 1 To 9
ctr = ctr + 1
Write #1, cell(ctr).Text
Next j
Next i
Close #1
End Sub

Sub RetrieveData()
CommonDialog1.ShowOpen
Q$ = CommonDialog1.FileTitle
Open Q$ For Input As #1
ctr = 0
For i = 1 To 9
For j = 1 To 9
ctr = ctr + 1
Input #1, xyz
cell(ctr).Text = xyz
Next j
Next i
Close #1
End Sub

Sub Cruncher()

'transfer the cell contents to 2D array for more efficient handling
ctr = 0
For i = 1 To 9
For j = 1 To 9
ctr = ctr + 1
C(i, j) = Val(cell(ctr).Text)
Next j
Next i

'The blank cells are counted and numbered consecutively
ctr = 0
For i = 1 To 9
For j = 1 To 9
If C(i, j) = 0 Then
ctr = ctr + 1
RowNo(ctr) = i
ColNo(ctr) = j
End If
Next j
Next i

NoCell = ctr

'The trial values for the blank cells are initialized to zero
For i = 1 To NoCell
Trial(i) = 0
Next i

'Starting with the first blank cell
simula = 1

bb:
For k = simula To NoCell

aa:
'increment the current value by 1 to have new trial value
Trial(k) = Trial(k) + 1

'check row-wise for any duplicate
For j = 1 To 9
If Trial(k) = C(RowNo(k), j) Then GoTo aa
'if a duplicate is found, we go back to aa and the next higher trial value is used
Next j

'check column-wise for any duplicate
For i = 1 To 9
If Trial(k) = C(i, ColNo(k)) Then GoTo aa
'if a duplicate is found, we go back to aa and the next higher trial value is used
Next i

'check 3 x 3 sub-grid for any duplicate
ix = 3 * Int((RowNo(k) - 1) / 3) + 1
jy = 3 * Int((ColNo(k) - 1) / 3) + 1

For i = ix To ix + 2
For j = jy To jy + 2
If Trial(k) = C(i, j) Then GoTo aa
'if a duplicate is found, we go back to aa and the next higher trial value is used
Next j
Next i

'If no duplicate is detected and the trial value is within
'the range of possible values (1 to 9) then we adopt
'the trial value as a provisional value for the cell

If Trial(k) <= 9 Then C(RowNo(k), ColNo(k)) = Trial(k)

'if all possible values have been tried without success 'then something is wrong with the values adopted in the previous 'cell, so we set the value of the current cell to zero 'and go back to the previous cell.

ElseIf Trial(k) > 9 Then
Trial(k) = 0
C(RowNo(k), ColNo(k)) = 0
simula = k - 1
GoTo bb
End If

Next k

'once this stage is reached, inconsistencies would have been totally eliminated
'and we may now finalize the solution and fill-up the grid with the final values

FillUpGrid

End Sub

Sub FillUpGrid()
ctr = 0
For i = 1 To 9
For j = 1 To 9
ctr = ctr + 1
cell(ctr).Text = C(i, j)
Next j
Next i
End Sub

.