Sudoku and TDD

For the last few months, I've been trying on and off to write a program to solve a Sudoku game. The "easy" ones are easy, you just use a rudimentary algorithm:


  • each cell has a list of possible values associated with it

  • start by associating all values 1-9 to each cell

  • repeat until solved:


    • for each cell, remove any values already present in the same line, column, or box




By this process of repeated elimination you can solve a lot of the "easy" tables. However, this algorithm is too limited and it will go into an infinite loop if you have a situation where, for example, two cells in the same row can accept values 1 and 5, but at this point you have no way of knowing which is which.

Now, of course the solution to that problem is simply a recursive backtracking algorithm:


  • save the current state

  • pick one value and try to solve the rest of the table; if it worked, all is good; if not, go back to the saved state and try the next value



The devil, however, is in the details. I would go into some weird state where suddenly I had a row with two cells having the same value... which of course ruined everything else. And debugging something which is five recursion levels deep and goes through 81 cells each time... I wasn't willing to spend all that effort for a stupid problem, especially with the number of programs already available solving it.

That was the case until one night when I was really bored and wanted to program something for fun :) But I had also just read yet another article on Test-Driven Design and decided to try it. It took me a few hours that night, and a few more hours the next morning, but I managed to make it work. Hehe. That's a cool feeling, especially since, while I have tried TDD before, this was the first time I actually felt it helped.

That's code I'd take to an interview :)

Comments

Post a Comment

Popular posts from this blog

Posting dynamic Master / Detail forms with Knockout

Image
I have the following dynamic form in my GitHub Inventory project : I created the form with KnockoutJS , using some ideas from this article . The detail view looks like this: <table id="acquisition_items" class="jtable"> <thead> <tr> <th>Product Name</th> <th>Quantity</th> <th>Price</th> <th>Value</th> <th><button data-bind="click: addItem">[+]</button></th> </tr> </thead> <tbody data-bind="foreach: items"> <tr> <td> <input data-bind="value: ProductName" type="text" value="" /> </td> <td> <input data-bind="value: Quantity" type="text" value="" /> </td> <td>
Read more

Comparing Excel files, take two

Image
I already wrote this project once, on GitHub , but I can't say that I like the result. I wrote that code without TDD, mostly to see if I can still work in the "normal" fashion. I can, but I had a bug that took me a while to even discover and then was difficult to write tests for. I also hate the temporal dependency in that design (if you don't call the SortBy method first, the ExcludeRecords method will return incorrect results). Anyway; here's attempt number two, writing that code using TDD. Structure I start by creating my usual structure for projects of this type - a library for the logic, a console application for the main program and a test project for tests. I also use the Enable NuGet Package Restore option (right-click on the solution node) to add the three NuGet files that will allow someone to automatically download all the packages I'm referencing without wasting space in the source code repository. (Right now I've only added the Moq pa
Read more

EF Code First: seeding with foreign keys

This is just a quick tip, more for future reference for myself than anything else. When using Entity Framework Code First, one of the things you might want to do while developing the application is to seed your database with some test data. This can be something as easy as: protected override void Seed(InventoryDB context) { context.Products.AddOrUpdate( p => p.Name, new Product { Name = "Hammer", SalePrice = 11.99m, }, new Product { Name = "Nail Pack x100", SalePrice = 0.05m, }, new Product { Name = "Saw", SalePrice = 19.99m, }, new Product { Name = "Toolkit", SalePrice = 39.99m, } ); //... } (I am using the AddOrUpdate method so the code detects whether those products already exist and doesn't add them again if they do.) The Product class is quite simple and – most importantly – doesn't depend on any other: public class Product { public int Id { g
Read more