Sudoku solutions in Python and Ruby

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.

1. The data structure (named 's' for sudoku) is a 9x9 array (s = [][]).
   
2. 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)
   
3. 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(',')).
   
4. 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.