Antimatroid, The

thoughts on computer science, electronics, mathematics

Posts Tagged ‘Sudoku

Sudoku Solver in Haskell

with 6 comments

This month will be a bit of short article since I haven’t had a whole lot of time on my hands lately. Haskell is a wonderful little language that has begun to pick up a bit of moment in the past year that I’ve been playing with on-and-off now for several years. Since I don’t post enough on Haskell, I figured I’d post my bare-bones Haskell Sudoku Solver.

import Data.List
import Data.Maybe

toRowColumn :: Int -> (Int, Int)
toRowColumn index = (r, c)
	where	r = div index 9
		c = mod index 9

toIndex :: (Int, Int) -> Int
toIndex (r, c) = r * 9 + c

toRegion :: (Int, Int) -> Int
toRegion (r, c) = (div r 3) * 3 + (div c 3)

columnIndicies :: Int -> [Int]
columnIndicies c = [c, c + 9..80]

regionIndicies :: Int -> [Int]
regionIndicies g = [toIndex(r + x, c + y) |
		x <- [0..2],
		y <- [0..2]
	]
	where	r = (div g 3) * 3
		c = (mod g 3) * 3

rowIndicies :: Int -> [Int]
rowIndicies r = [9 * r..9 * (r + 1) - 1]

values :: [Int] -> [Int] -> [Int]
values board indicies = filter (>0) (map (board!!) indicies)

possibleValues :: [Int] -> (Int, Int) -> [Int]
possibleValues board rowColumn = 
	foldl (\\) [1..9] (
		map (values board) (
			map (\f -> (fst f . snd f) rowColumn) (
				zip [rowIndicies, columnIndicies, regionIndicies]
					[fst, snd, toRegion]
			)
		)
	)

validBoard :: [Int] -> Bool
validBoard board = (length board == 81) && (and $ map (==0) l)
	where	l = map length s
		s = map (\\[1..9]) v
		v = [values board (xIndicies x) |
			x <- [0..8],
			xIndicies <- [rowIndicies, columnIndicies, regionIndicies]]

solvedBoard :: [Int] -> Bool
solvedBoard board = and $ map (>0) board

hasUnassigned :: [Int] -> Bool
hasUnassigned board = isJust $ elemIndex 0 board

assignFirstUnassigned :: [Int] -> Int -> [Int]
assignFirstUnassigned (b:bs) value
	| b == 0 = value : bs
	| otherwise = b : (assignFirstUnassigned bs value)

possibleBoards :: [Int] -> [Int] -> [[Int]]
possibleBoards board possibleAssignments = map (assignFirstUnassigned board)
	possibleAssignments

solve :: [Int] -> [[Int]]
solve board
	| not (validBoard board) = [[]]
	| solvedBoard board = [board]
	| not (hasUnassigned board) = [[]]
	| otherwise = concated
	where	concated = concat mapped
		mapped = map solve filtered
		filtered = filter (not . null) possibleSolved
		possibleSolved = possibleBoards board possibleAssignments
		possibleAssignments = possibleValues board unassignedRowColumn
		unassignedRowColumn = toRowColumn unassignedIndex
		unassignedIndex = fromJust $ elemIndex 0 board

demo :: [Int]
demo = [2,0,0,0,8,0,3,0,0,
	0,6,0,0,7,0,0,8,4,
	0,3,0,5,0,0,2,0,9,
	0,0,0,1,0,5,4,0,8,
	0,0,0,0,0,0,0,0,0,
	4,0,2,7,0,6,0,0,0,
	3,0,1,0,0,7,0,4,0,
	7,2,0,0,4,0,0,6,0,
	0,0,4,0,1,0,0,0,3]

Written by lewellen

2009-06-01 at 12:00 am

Posted in Algorithms

Tagged with ,

Sudoku Solver in C# using Lambda Expressions

leave a comment »

Seems that everywhere you look someone has a Sudoku Solver that they want to showcase, well, I’m no different so I figured I’d post my take on the subject. Microsoft has introduced/included/borrowed a number of functional programming features into the latest version of C# (3.0) that have made it easier for developers to write better, cleaner code. One of those features continues the trend of improving anonymous methods, which extend delegates which extend interfaces now known as Lambda expressions. E.g., the following are all the same for the expression \lambda x . x * x:

Func<int, int> square = (x) => x * x;
Func<int, int> square = new Func<int, int>(delegate(int x) { return x * x; });
public interface Func<T, R> {
    R Evaluate(T x);
}

public class Square : Func<int, int> {
    public int Evaluate(int x) {
        return x*x;
    }
}

...

Func<int,int> square = new Square();

Given that level of expressive power, I thought I would approach this implementation using as many lambda expressions as possible to see how concise and easy to follow an implementation I could create.

To start off, the solver will assume that the board will be passed in as a 81 character array containing digits 0-9. Zero shall represent an unassigned cell.

The core loop is pretty simple: Start with the initial board on a stack, in a loop take the first board off the stack and check if it is valid. A board is said to be valid if for every row, column and region each structure contains one and only one instance of the digits 1-9. If the board is not valid, no further work should be done.

Next we need to check if the board is solved. If it is not, then we need to explore the possible boards that can be derived from that board. To do so, we will need to find the first possible cell that is unassigned and push on to the the stack a derived board using the possible values that can be assigned to the identified cell.

Once the loop finally exits, print out the solved board.

using System;
using System.Collections.Generic;

namespace Sudoku {
    public class Program {
        static public void Main(string[] args) {
            string input = "200080300060070084030500209000105408000000000402706000301007040720040060004010003";
            Board inputBoard = null;
            try {
                inputBoard = new Board(input);
            } catch (InvalidInputException iie) {
                Console.WriteLine(iie.InvalidInput);
                return;
            }

            Stack boards = new Stack();
            boards.Push(inputBoard);
            Board board = null;
            do {
                board = boards.Pop();
                if (!board.Valid)
                    continue;
                if (!board.Solved)
                    board.FirstAvailable((r, c) => 
                        board.PossibleValuesAt(r, c, (v) => 
                            boards.Push(board.DeriveUsing(r, c, v))
                        )
                    );
            } while (boards.Count > 0 && !board.Solved);
            Console.WriteLine(board);
        }
    }
}

I’m going to start with the private member methods since they form the basic grammar that I will use to implement the public member methods and properties.

The first thing you’ll notice is the private class Structure; it is a simple pair class that contains two member properties for accessing a function that iterates over all possible structures and a function that iterates over all the cells in a specific structure.

The private constructor instantiates a private member array containing the function pointers that enumerate over Rows, Column and Regions.

assertStructure method which iterates over every instance of a structure in the table, and verifies that one and only one instance of the digits 1-9 exist in that structure instance.

indexInStructure iterates over all of the indices of a structure- in this case, 0-8.

using System;
using System.Text;

namespace Sudoku {
    public partial class Board {
        private class Struct {
            public Action<Action<int>> In { get; set; }
            public Action<int, Action<int>> ForValues { get; set; }
            public Struct(Action<Action<int>> _in, Action<int, Action<int>> forValues) {
                In = _in; ForValues = forValues;
            }
        }

        private Struct[] structures;

        private Board(int[] board) {
            this.board = board;
            structures = new Struct[] {
                new Struct(Rows, ValuesInRow), new Struct(Columns, ValuesInColumn),
                new Struct(Regions, ValuesInRegion)
            };
        }

        private bool assertStructure(Action<Action<int>> structure, Action<int, Action<int>> 
            valuesInStructure) {
            bool asserted = true;
            structure((x) => {
                int[] used = new int[10];
                valuesInStructure(x, (y) => used[y]++);
                used[0] = 0;
                asserted &= forAllValues((v) => v < 2, used);
            });
            return asserted;
        }

        private void indexInStructure(Action<int> actOnIndex) {
            indexInStructure((n) => true, actOnIndex);
        }

        private void indexInStructure(Predicate<int> p, Action<int> actOnIndex) {
            indexFromToWhere(0, 9, p, actOnIndex, false);
        }

The forAllValues method is simply a way of writing the predicate (\forall x) Px applied to members of the universe of discourse (the array that was passed in).

indexFromToWhere is a simple wrapper around a common for loop with filtering and the option to break after the first object to pass through the filter is found.

        private bool forAllValues(Predicate f, T[] A) {
            bool held = true;
            for (int n = 0; n < A.Length && held; n++)
                held &= f(A[n]);
            return held;
        }

        private void indexFromToWhere(int min, int max, Predicate<int> p, Action<int> actOnIndex, 
            bool breakAfterFirst) {
            for (int n = min; n < max; n++)
                if (p(n)) {
                    actOnIndex(n);
                    if (breakAfterFirst)
                        break;
                }
        }

The following methods are all related to working with the board representation. I choose to implement the board as an integer array. The at method maps a logical row and column to a row order array value within board. Each of the different indexInBoard methods allows for iterating over the indices of the board.

        private int[] board;

        private int at(int row, int col) {
            return row * 9 + col;
        }

        private void indexInBoard(Action<int> actOnIndex) {
            indexInBoard((n) => true, actOnIndex);
        }

        private void indexInBoard(Predicate<int> p, Action<int> actOnIndex) {
            indexInBoard(p, actOnIndex, false);
        }

        private void indexInBoard(Predicate<int> p, Action<int> actOnIndex, bool breakAfterFirst) {
            indexFromToWhere(0, board.Length, p, actOnIndex, breakAfterFirst);
        }
    }
}

The first set of public member methods and properties we can look at are for managing the state of the board. The board is only Solved if each index is assigned. The board is only Valid if every structure in the board is asserted to be true. The constructor checks the input to make sure it is valid, delegates the some work to the private constructor and loads the input string in to the integer array.

using System;
using System.Text;

namespace Sudoku {
    public partial class Board {
        public bool Solved {
            get { 
                return forAllValues((x) => x > 0, board);
            }
        }
        public bool Valid { 
            get { 
                return forAllValues((s) => assertStructure(s.In, s.ForValues), structures);
            }
        }
        
        public Board(string input) : this (new int[81]) {
            if (string.IsNullOrEmpty(input))
                throw new InvalidInputException(InvalidInput.Empty);
            if (input.Length != 81)
                throw new InvalidInputException(InvalidInput.Length);
            for (int n = 0; n  board[n] = input[n] - '0');
        }

        override public string ToString() {
            StringBuilder S = new StringBuilder(board.Length);
            indexInBoard((n) => S.Append((char)('0' + board[n])));
            return S.ToString();
        }

Next, we need a way to operate on each of the structures in the board. Each row from top to bottom, each column from left to right and each region from top left to bottom right (zig-zag) will be assigned an index from 0-8 respectively.

        public void Columns(Action<int> actOnColumn) {
            indexInStructure(actOnColumn);
        }

        public void Regions(Action<int> actOnRegion) {
            indexInStructure(actOnRegion);
        }

        public void Rows(Action<int> actOnRow) {
            indexInStructure(actOnRow);
        }

It is easy to then iterate the cells in a given structure. The values in a column are simply a trip down the Rows and we only want to act when the value is defined. The values in a row are just as easy by traveling across the Columns and acting when the value is defined. Iterating over the values in the region is a little more involved, but nonetheless just as easy to follow- map the region to the appropriate reference row and column and then iterate over the 3×3 grid and act only when the value is defined.

        public void ValuesInColumn(int column, Action<int> actOnValue) {
            Rows((r) => {
                int value = board[at(r, column)];
                if (value > 0)
                    actOnValue(value);
            });
        }

        public void ValuesInRegion(int region, Action<int> actOnValue) {
            int row = (region / 3) * 3;
            int column = (region % 3) * 3;
            int value = 0;
            for (int r = 0; r < 3; r++)
                for (int c = 0; c  0)
                        actOnValue(value);
                }
        }

        public void ValuesInRow(int row, Action<int> actOnValue) {
            Columns((c) => {
                int value = board[at(row, c)];
                if (value > 0)
                    actOnValue(value);
            });
        }

Finally, we have the interesting methods used in the main loop. DeriveUsing will copy the board into a cloned integer array and then assign the derived at row and column with the value supplied. The newly derived board is then returned.

FirstAvailable iterates over all the indices of the board until it finds an unassigned value and then it acts upon the reference row and column.

PossibleValuesAt goes and collects a list of possible values by first collecting the values used in the row, column and region that the reference row and column reside within, then each value not found is acted upon.

        public Board DeriveUsing(int row, int colum, int withValue) {
            int[] derived = new int[81];
            indexInBoard((n) => derived[n] = board[n]);
            derived[at(row, colum)] = withValue;
            return new Board(derived);
        }

        public void FirstAvailable(Action<int, int> actOnRowAndColumn) {
            indexInBoard((n) => 
                board[n] == 0, (n) => actOnRowAndColumn(n / 9, n % 9), true);
        }

        public void PossibleValuesAt(int row, int column, Action<int> actOnPossibleValue) {
            bool[] used = new bool[10];
            ValuesInRow(row, (x) => used[x] = true);
            ValuesInColumn(column, (x) => used[x] = true);
            ValuesInRegion((row / 3) * 3 + (column / 3), (x) => used[x] = true);
            indexFromToWhere(1, used.Length, (n) => !used[n], actOnPossibleValue, false);
        }
    }
}

Having approached this implementation as I did, I found some interesting bugs that I hadn’t come across before and I figure I’ll close with one that caught me off guard. I had spent an hour writing all my code and figured I’d run it to see what kind of output I got. To my surprise I got an immediate StackOverflowExeception. So I spent and an additional 10 minutes debugging and found the following offending code. Take a look at it and see if you can see what’s wrong with it before reading on.

public void act(Func<int,int> assign){ 
    act((n) => board[n] = assign(n));
}

public void act(Action<int> actOn) {
    for(int n = 0; n < board.Length; n++)
      actOn(n);
}

After a minute I had my ah-ha moment (as I’m sure have as well) and remembered that the assignment operator returns the value of the assignment so the compiler was turning (n) => board[n] = assign(n), into Func<int, int> instead of Action<int> as I had hoped. To fix the bug, I had to do the following to get the compiler to pick the statement up as Action<int>.

public void act(Func<int,int> assign) {
    for(int n = 0; n < board.Length; n++)
        act((n) => { board[n] = assign(n); });
}

Having made the change, I tested my input string and out printed the solution immediately. I decided against writing similar function overloading in the final implementation to prevent any unintended bugs.

Written by lewellen

2009-05-01 at 12:00 am

Posted in Algorithms

Tagged with ,