Killer Sudoku

A friend of mine pointed out this variation on a favorite past-time of mine. It's called 'Killer Sudoku', which is like regular sudoku for all intents and purposes, but has additional rules (wiki Killer Sudoku).

As with normal sudoku, Killer Sudoku implements another dimension to the sudoku challenge; with the addition of 'cages', a group of cells must add up to the total of the cage, which in a sense limits which values can be placed onto the board. Often, but not always, will you find simply cages instead of hard values as starts to your board game.

Awhile ago, I had made a sudoku solver, which, given a solvable sudoku board, popped out all available solutions. The solver worked both logistically (solving a board assuming no guessing or trial-and-error) and with a brute force attempt (iteration over the sequence of possible values).

To be honest, I hadn't thought of a good way to program a solver for Killer Sudoku logistically, but I wanted to at least try a brute force attempt at it.

Here is what I came up with:

#/usr/bin/python
import math
board = [[0 for col in range(9)] for row in range(9)]
def rowCheck(testx, testy, board):
    test=board[testx][testy]
    possible=[]
    for each in range(0,9):
        possible.append(board[testx][each])
    if possible.count(test) ==1:
        return 1
    else:
        return 0
def columnCheck(testx, testy, board):
    test=board[testx][testy]
    possible=[]
    for each in range(0,9):
        possible.append(board[each][testy])
    if possible.count(test) ==1:
        return 1
    else:
        return 0
def nonetCheck(testx,testy,board):
    test=board[testx][testy]
    rootx=int(math.floor(testx/3))*3
    rooty=int(math.floor(testy/3))*3
    possible=[]
    possible.append(board[rootx][rooty])
    possible.append(board[rootx][rooty+1])
    possible.append(board[rootx][rooty+2])
    possible.append(board[rootx+1][rooty])
    possible.append(board[rootx+1][rooty+1])
    possible.append(board[rootx+1][rooty+2])
    possible.append(board[rootx+2][rooty])
    possible.append(board[rootx+2][rooty+1])
    possible.append(board[rootx+2][rooty+2])
    if possible.count(test) == 1:
        return 1
    else:
        return 0
def cellCheck(testx,testy,board):
    test=board[testx][testy]
    if test==10:
        return 0
    else:
        return 1
def cageValidate(cages):
    for cage in cages:
        if len(cage) != 2:
            print "Each cage must contain exactly 2 elements!", cage
            return -1
        if type(cage[0]) is not int:
            print "The first element of each cage must be an integer!",cage
            return -1
        if type(cage[1]) is not list:
            print "The second element of each cage must be a list!",cage
            return -1
        cagevals=cage[1]
        if len(cagevals)==0:
            print "Every cage must have at least one cell!"
            return -1
        for set in cagevals:
            if len(set) != 2:
                print "Every cell coordinate set must have two coordinates!",set
                return -1
            if type(set[0]) is not int or type(set[1]) is not int:
                print "Every cell coordinate must be an integer!",set
                return -1
def solve(board,cages):
    ioerow=0
    ioecol=0
    while ioerow != 9:
        board[ioerow][ioecol]=board[ioerow][ioecol]+1
        if cellCheck(ioerow,ioecol,board) == 0:
            board[ioerow][ioecol]=0
            ioecol=ioecol-1
            if ioecol == -1:
                ioecol=8
                ioerow=ioerow-1
                if ioerow == -1:
                    print "Solve failed"
                    return 0
            continue
        if rowCheck(ioerow,ioecol,board) == 0:
            continue
        if columnCheck(ioerow,ioecol,board) == 0:
            continue
        if nonetCheck(ioerow,ioecol,board) == 0:
            continue
        currcell = [ioerow, ioecol]
        cagefail=0
        for cage in cages:
            if currcell not in cage[1]:
                continue
            index=cage[1].index(currcell)
            cagesum=0
            coords=cage[1]
            for x in range(0,index+1):
                temp=coords[x]
                cagesum=cagesum+board[coords[x][0]][coords[x][1]]
            if index == len(coords)-1 and cagesum == cage[0]:
                continue
            if index == len(coords)-1 and cagesum != cage[0]:
                cagefail=1
                break
            if index != len(coords)-1 and cagesum >= cage[0]:
                cagefail =1
                break
        if cagefail == 0:
            ioecol = ioecol +1
        if ioecol == 9:
            ioecol = 0
            ioerow = ioerow +1
cages=[[11,[[0,0],[1,0]]],
       [8,  [[0, 1],[1, 1]]],
       [31, [[0,2],[0,3],[0,4],[0,5],[0,6],[1,4]]],
       [8,  [[0,7],[1,7]]],
       [13, [[0,8],[1,8]]],
       [14, [[1,2],[1,3],[2,2]]],
       [16, [[1,5],[1,6],[2,6]]],
       [11, [[2,0],[3,0]]],
       [5,  [[2,1],[3,1]]],
       [29, [[2,3],[2,4],[2,5],[3,4]]],
       [8,  [[2,7],[3,7]]],
       [9,  [[2,8],[3,8]]],
       [25, [[3,2],[3,3],[4,0],[4,1],[4,2]]],
       [20, [[3,5],[3,6],[4,6],[4,7],[4,8]]],
       [21, [[4,3],[5,0],[5,1],[5,2],[5,3],[6,0]]],
       [22, [[4,4],[5,4],[6,4]]],
       [33, [[4,5],[5,5],[5,6],[5,7],[5,8],[6,8]]],
       [14, [[6,1],[6,2],[6,3]]],
       [17, [[6,5],[6,6],[6,7]]],
       [28, [[7,0],[7,1],[7,2],[7,3],[8,0]]],
       [5,  [[7,4],[8,4]]],
       [28, [[7,5],[7,6],[7,7],[7,8],[8,8]]],
       [22, [[8,1],[8,2],[8,3]]],
       [7,  [[8,5],[8,6],[8,7]]]]
solve(board,cages)
cageValidate(cages)
for row in board:
    for col in row:
        print col,
    print ""

Essentially, brute forcing a killer sudoku board is pretty easy; in addition to the simple row, column and nonet checks, Killer Sudoku must have a cage check. This is handled by the above cageValidate function.

I believe this must have been one of my first pieces of code written in python; had I written this today, I would have written some optimization within the cageValidate function (there is no point in validating all cages after every iteration, for example), and I would have encapsulated all of these definitions into a single class.

An Introduction

I began learning python nearly 3 years ago, almost on whim. I can't recall what it was that originally drew me to it, but ever since then I've been unable to put it down. Before then, I knew about python but never bothered learning about it, as C and C++ were my go-to languages of choice whenever a particular problem needed solving.

Since then, my python skill-set has improved dramatically. I might find it difficult to imagine that I was the original author of some of the original code I had written, and I hope that in another few years I will be able to look back at my current code and think of ways that I could have written my code more elegantly or more efficiently.

Elegance in python is important. It should be easy for most python programmers to look at your code and know exactly what it does, as it should be written in a concise fashion. Still, there are stylistic differences from programmer to programmer. Chances are, the way I write my code will look different from the way you might write your own.

Efficiency is important, but not as important as elegance. My code will likely not be extremely efficient, but for the purposes that I write it, it will be "good enough". If I wanted to write code to handle operations extremely efficiently, I'd write it in C.

This blog will serve as a chronicle of projects that I've interest in. I'm going to make mistakes, and there are going to be some pretty glaringly obvious improvements that could be made. If you're feeling so inclined, you can leave comments about possible improvements, but ultimately it is not the purpose of the project.

That's all-- enjoy the show. Hopefully someone can learn something from these projects that serve as self-teaching tools.