Carl and Jane (my younger brother and his wife) gave me a sudoku book for Christmas. Yeah, I know - you wish that your family gave good gifts like mine. Puzzles are always great for holidays, and I've seen Japan's official national sport in the newspaper and most magazines and even in
Cedric's weblog for a while but I've never actually tried to do a sudoku. It was fun to do a few, so I thought I could either spend the rest of Christmas finishing the book, or I could write a program to solve them and then never have to worry about sudoku again in my life.
What I did:
Much to my wife's disgust, I pulled out my laptop and took about 2 hours to do a Python version of the solution with Python24.chm as my guiding companion. I've used Python a little bit for the last 2 years, so it was the first choice of language.
The data structure and algorithm that I devised is quite simple.
- The data structure (named 's' for sudoku) is a 9x9 array (s = [][]).
- The sudoku puzzle is read in from a text file (9 lines, each with 9 chars - either '1'-'9' or '.' - see below for an example)
- The puzzle is read in and each element of s is populated to either be a vector of size 1 containing the given value (e.g. v = ['3']), or is set to a vector containing chars '1' - '9' (v = '1,2,3,4,5,6,7,8,9'.split(',')).
- The solution is found by successively reducing all vectors down to a single value. The program iterates through all elements of 's'; if the given element is already solved (len(v) == 1), then remove that value (v[0]) from all elements in the same row, column, and 3x3 grid as that given element.
sudoku.txt:
..32.....
..6.7.982
..5.86...
29.8.3.75
1.8...4.9
53.4.1.26
...61.5..
649.3.2..
.....47..
sudoku.py:
#!/bin/python
import sys
f=file('sudoku.txt')
s=[]
def display(p=10, q=10):
for i in range(9):
if (i % 3 == 0): print('-' * 100)
for j in range(9):
if (j % 3 == 0): sys.stdout.write(' | ')
sys.stdout.write('%10s' % ''.join(s[i][j]))
if i==p and j==q: sys.stdout.write('_')
sys.stdout.write('\n')
sys.stdout.write('\n' * 3)
for l in f.readlines():
row = []
s.append(row)
for i in l.strip():
v = '1,2,3,4,5,6,7,8,9'.split(',')
if i in '123456789': v = [i]
row.append(v)
finished = False
while (not finished):
change = False
for i in range(9):
for j in range(9):
if len(s[i][j]) == 1:
# reduce rows and columns
for k in range(9):
if len(s[k][j]) > 1 and s[i][j][0] in s[k][j]:
s[k][j].remove(s[i][j][0])
change = True
for k in range(9):
if len(s[i][k]) > 1 and s[i][j][0] in s[i][k]:
s[i][k].remove(s[i][j][0])
change = True
#reduce small square
for p in range((i/3)*3, (i/3)*3+3):
for q in range((j/3)*3, (j/3)*3+3):
if len(s[p][q]) > 1 and s[i][j][0] in s[p][q]:
s[p][q].remove(s[i][j][0])
change = True
#randomly reduce any v if no change
p,q,v = 10,10,None
if not change:
for i in range(9):
for j in range(9):
if len(s[i][j]) > 1: p,q,v = i,j,[s[i][j][0]]
s[p][q] = v
finished = True
for i in range(9):
for j in range(9):
if len(s[i][j]) > 1:
finished = False
display()
That was kind of fun, but then a few days later I was watching the cricket and it was a bit dull and I thought that I really should try to learn Ruby a bit better so I can fit in with all the cool kids. I've written a few scripts in Ruby, but I don't know it as well as Python. So now with ProgrammingRuby.chm as my guide and the already completed sudoku.py, I wrote a Ruby program to solve sudoku.
sudoku.rb:
#!/bin/ruby
def display(s, p=10, q=10)
for i in 0..8
if (i % 3 == 0) then puts '-' * 100 end
for j in 0..8
if (j % 3 == 0) then print ' | ' end
printf('%10s', s[i][j].join(''))
if i==p and j==q then puts('_') end
end
print "\n"
end
print "\n" * 3
end
s = []
File.open('sudoku.txt').each do |line|
row = []
s.push(row)
line.strip().scan(/./).each do |c|
v = ('1'..'9').to_a
if v.include?(c) then v = [c] end
row.push(v)
end
end
finished = false
while (not finished)
change = false
for i in 0..8
for j in 0..8
if s[i][j].length == 1 then
# reduce rows and columns
for k in 0..8
if s[k][j].length > 1 and s[k][j].include?(s[i][j][0])
s[k][j].delete(s[i][j][0])
change = true
end
if s[i][k].length > 1 and s[i][k].include?(s[i][j][0])
s[i][k].delete(s[i][j][0])
change = true
end
end
#reduce small square
for p in ((i/3)*3)..((i/3)*3+2)
for q in ((j/3)*3)..((j/3)*3+2)
if s[p][q].length > 1 and s[p][q].include?(s[i][j][0])
s[p][q].delete(s[i][j][0])
change = true
end
end
end
end
end
end
#randomly reduce any v if no change
p,q,v = 10,10,nil
if not change
for i in 0..8
for j in 0..8
if s[i][j].length > 1 then p,q,v = i,j,[s[i][j][0]] end
end
end
s[p][q] = v
end
finished = true
for i in 0..8
for j in 0..8
if s[i][j].length > 1 then finished = false end
end
end
end
display(s)
What I learnt:
It didn't take much effort to change the Python solution to Ruby. For this program, I think both languages are an excellent fit. I'm very interested to hear from anyone who has ideas on a better solution algorithm, or a better way to implement the solution in Python or Ruby.
Some specific things that I learnt:
1. Python strings are immutable
I think I already knew this, but I learnt it again. I originally set my solution vector to
v = '123456789' since I knew that Python stores strings as an array, and it is less typing than
v = ['1', '2', '3', '4', '5', '6', '7', '8', '9']. I expected that I could do something like
'123456789'.remove('3'), but alas, I can't. I've seen that there is a MutableString type, but I used
v = '1,2,3,4,5,6,7,8,9'.split(',') to create my array instead. I first tried doing
'123456789'.split(''), but that didn't do what I wanted. Does anyone know a better way to create an array of chars from a string? Surely there has to be a simple way to do this.
2. Both Python and Ruby do everything they can to stop you using indexes in your loops, and that's a good thing
I never really noticed how annoying it is to use
for (int i = 0; i < a.length; i++) or even Java Iterators until I started using Python. Even the approach that I took of creating a Range object and doing
for i in range(9) or
for i in 0..8 feels wrong. I feel like I should be doing something like
for row in s: - I only used 'i' and 'j' because I couldn't think of a better way to associate the sudoku rows and columns without them.
3. Ruby's Range object is great!Every language should have one of these. I even like how Ruby's Range object is inclusive of each bound and I think especially for beginner programmers, it would be easier to learn and would help avoid the pesky off by 1 errors that are so common when indexing and iterating. I definitely noticed this as a difference between the two languages because when changing
for i in range(9) to
for i in 0..8, I wasn't just changing syntax, I was changing the actual value '9', to '8'. I considered creating my array in Ruby to be 10x10 and to index it from 1 to 9 as you would in Visual Basic, but some strong force in me would not allow it. Maybe it is the thought that I'm wasting slots in each array, or that Donald Knuth would get angry at me (maybe he wouldn't). I have actually taken the approach of indexing arrays 1-based before and I think it is a great approach in the right place. I guess in this case I wanted to keep the Python and Ruby programs as similar as possible. Going back to the previous point, Python and Ruby both do such a great job of iterating that it practically removes any 0-based or 1-based argument since you rarely need to use your 'i', 'j' or 'k' friends.
4. Python's list.remove(x) method raises a ValueError if x is not in the list.This is different to Ruby which returns nil if you try to remove an item from a list that doesn't exist (but doesn't throw any Exceptions). Initially this meant I had python code like
if len(s[k][j]) > 1 and s[i][j][0] in s[k][j]: s[k][j].remove(s[i][j][0]) and Ruby code that was slightly simpler like
if s[k][j].length > 1 then s[k][j].delete(s[i][j][0]) end, but I realised after trying my program with a
'difficult' level sudoku that sometimes the constraints in a sudoku puzzle allow for multiple solutions and my program needed to detect this case and arbitrarily reduce one of the solution vectors to force out a solution. To detect this case, I needed to do the check for inclusion, so the ruby code ended up semantically identical.
