Writing a simple Sudoku solver in F#

To continue learning about F# and to practice programming functionally, I have written a simple Sudoku solver. I use the word simple, because some simple Sudoku problems can be solved only by going over the board and removing entries without having to make “guesses” and backtracking.

This guessing and backtracking usually involves implementing a depth-first search when writing a Sudoku algorithm.

In the interest of time (there’s another project which I have been delaying for months and need to be starting) I have only implemented a solution to the easy type of Sudokus.

The first part is writing code that checks whether a board is correctly solved. This part can be done first and it’s better to do so since we will need it to check whether our Sudoku solver actually works.

The process is pretty easy, in Board.fs I implement the types I need to represent the board (Value) and it’s state (BoardSolved).

Checking the board implies collecting all it’s rows, columns and boxes (which are nine 3×3 regions on the board) and then checking them for duplicates.

To solve a board we go over all rows, columns and boxes and for each item in these collections we remove from the list of possible values those values which have already been selected in another item. I call this “locking” the values.

This operation is applied successively until the board is solved. The most complicated part came because I used a 2D array to represent the board but I needed to convert the rows, columns and boxes values to lists. Converting the lists generated from the boxes was the single most complicated and longest part of the whole program.

I guess it pays to just use lists for everything and skip on using arrays. The language and it’s libraries are pretty much made for working with lists and sequences so when you deviate from that you end up having to write additional code.

Here is the GitHub repo with the whole thing.

To make this solver capable of solving any Sudoku, we would need to change the

| BoardUnlocked -> failwith “Board not yet solved”

line with calling a depth-first search which would select the first unlocked value, try and select the first possible value for this item and then continue recursively trying to solve the board until either it succeeds or it fails. When/if it fails backtrack and continue it’s search using another value.

Genesis Procedural Content Generator

One of the things I have been working on is Genesis, a procedural content generator written in F#. It generates random names and terrain maps.

The project has almost nothing to do with what I had envisioned when I started it.

Here are some sample maps :

 

 

Mountains are in grey, grasslands/plains in pale green, forests in dark green, desert/arid climate in brown and water in blue.

It’s still lacking rivers and lakes and the output isn’t satisfactory. Sadly I think I would need to start over to get realistic terrain generation, which was one of my goal. The main problem is that I used midpoint displacement and noise functions which while good enough for video games don’t generate photo-realistic results alone.

To try and correct that, I devised my own solution using a crude simulation of water erosion rather than look into and implement standard algorithms.

It was a learning experience and a lot of fun but I would have had quicker and better results by copying some existing algorithm.

I don’t know what to do with the project right now as there are other things I want to spend my time on, but I would still like to work on it some more in the future. Maybe take a whole different approach and generate fantasy maps with brushes and icons which are much less detailed.

How to create an F# project under Linux

There isn’t a ton of info about starting out a new F# project under Linux so I’ve decided to document how I do it.

Install Mono

Following the instructions on the official F# site, install Mono and F#:

sudo apt-get install mono-complete fsharp

You can test that F# is installed by typing

fsharpc

to bring up the F# compiler.

Install Visual Studio Code

You could use any editor, I chose Visual Studio Code because it offers superb F# integration when combined with the Ionide plugin.

After installing VS Code press Ctr-Shift-X to open the Extension window and search for “Ionide” and install the following extensions:

  • Ionide-fsharp
  • Ionide-Paket
  • Ionide-FAKE

Start a new project

Using Ctr-P bring up the command window and type:

>f#:new project

Follow the instruction and select a class library project.

This will create the base project scaffolding including some files and folders. Now might be a good time to do a git init.

Paket

To build your project you must use the build.sh script. If you try this now, the command will fail because it won’t be able to find the Paket bootstrapper.

Paket is the package manager that downloads, installs and manages dependencies,  much like NuGet, Cargo or RubyGem on other platforms.

So head on over and download the latest Paket bootstrapper specifically paket.bootstrapper.exe and drop it in the .paket folder that was created by Ionide.

You can now run

./build.sh

And Paket will create a paket.dependencies and paket.lock.

Adding some code to the project

There should be a folder with the project name you specified to Ionide . Let’s add a new file to this project.

You have two choices here:

  1. Add it manually
  2. Use Ionide to automatically add the file to the project

Add it manually

To add the file manually you must create a new file with a .fs extension using the file system or VS Code.

Next you must add your file to the project by editing the .fsproj file.

Then open your .fsproj file and locate the ItemGroup section which includes the Compile Include tags. Similar to this:
<CompileInclude=”genesis2.fs”/>
<NoneInclude=”Script.fsx”/>
Add a new entry:
<CompileInclude=”NewFile.fs”/>
<CompileInclude=”genesis2.fs”/>
<NoneInclude=”Script.fsx”/>
Be careful, the order of the elements is important. If a file A is a dependency for file B, it must come before file B in this listing. In this example NewFile.fs can be a dependency for genesis2.fs but the reverse can’t be true.
The manual technique, even though it is tedious, is useful, particularly to debug your fsproj.

Use Ionide

The alternative is to use Ionide a to add a new file for you.

Create the new .fs file like before, but this time use Ctr-P, type in

>f#

And select, Add current file to project. Voila!

Adding a new dependency to our existing project

Let’s add a new dependency to our project, MathNet.Numerics, a library that provides methods and algorithms for numerical computations.

Again let’s see how to add it both manually and using the Ionide plugin.

Before installing any packages make sure that the .paket/paket.exe file that was previously downloaded by the bootstrapper  is executable. To do so, change the permissions via the command line or the GUI.

Add it manually

First open the paket.dependencies file in your project root and add the following line:

nuget MathNet.Numerics
And then in your project folder (for each of the projects where you want to install the dependencies) locate the paket.references file and add this line:
MathNet.Numerics
Then run:
.paket/paket.exe install
To check that everything is working you can by adding the following in one of your source file:
open MathNet.Numerics.Distributions
And build your project again.

Use Ionide

Open the .fsproj file of the project you want to add the dependency to, type in Ctr-P and then:

> paket: Add NuGet to current project

Debugging the project

Twice I’ve had the project refusing to build because of the paket dependencies after a Mono upgrade. In this case your best bet is to delete the dependency info in the fsproj and add them again.