SyntaxHighlighter

September 13, 2012

Clojure Connect Four - Part 1: Checking For A Winner

This post is part of the ongoing series about Connect four in Clojure:
GitHub: naeg/clj-connect-four

Checking For A Winner


Figure 1: Schema of sequences
In order to win a Connect four game, one player has to connect four of his pieces in sequence. A sequence is either a row (blue), a column (red) or a diagonal, which is either ascending (violet) or descending (green).

Before we start taking a closer look at the different algorithms, I'll explain the utility functions used to experiment and play with the different algorithms. If you have no idea what Clojure or functional programming is about, you might want to read this article about Conways Game of Life in Clojure first.
(def player [" ", "X", "O"])

(def empty-board
  "Empty board with 6 rows and 7 columns."
  (vec (repeat 6 (vec (repeat 7 (player 0))))))

(defn get-y
  "Determines y-coordinate for given x-coordinate."
  [board x]
  (first (filter #(= (get-in board [% x]) (player 0))
                 (range 5 -1 -1))))

(defn insert
  "Inserts symbol for given player (either 1 or 2) at specified x."
  [board x player-num]
  (let [y (get-y board x)]
    (assoc-in board [y x] (player player-num))))

(defn print-board
  [board]
  (println [1 2 3 4 5 6 7])
  (doseq [row board] (println row)))
Line 1: A vector containing strings which represent either an empty field (" ") or a piece of a player ("X" or "O")

Line 5: Generating a vector containing 6 vectors which contain 7 empty fields.

Line 10-11: filter out empty fields starting at the bottom (y = 5) of the board. This returns a lazy sequence of which we just take the first item.

Line 16-17: Creating a variable binding for the y-coordinate using let and then assoc-in the symbol of the given player-num at given x- and calculated y-coordinate.

Line 22: Iterate over the rows of the board an println them using doseq.

As you probably can tell by the code and by looking at Figure 1, I decided to use [y,x] coordinates with [0,0] being at the top left corner.

Now it's getting exciting. I tried three different algorithms to check for a winner: The first one pre-calculates all possible winning combinations and then pulls out those which are relevant to the current turn. The second one uses a bitboard representation for the board and a bit-fiddling function to check whether a player has won. The last one is a logical solution using Clojure's core.logic, which brings Prolog-like problem solving to Clojure.

Algorithm 1: Pre-calculated Winning Combinations


In total there are 69 possible winning combinations. On each row you have 4 possibilities of connecting four and there are 6 rows (24 combinations). On each column you have 3 possibilities and there are 7 columns (21 combinations). There are 12 ascending and 12 descending diagonals, resulting in a total number of 69 possibilites. Not that much, so we can store all of them in a simple vector.

After each turn, we filter out those winning combinations which are relevant to the current turn and see whether the player has connected four in one of these combinations. The highest number of combinations a certain cell can contribute to is 13 (for example the cell [2,3]). This number drops fast towards the corners and at the corners, there are only 3 possible combinations left in which the cell can contribute (e.g. the cell [5,0]).
(defn get-diags
  "Generates diagonals of given starting position using given step-fn."
  [step-fn start-pos]
  (for [pos start-pos]
    (take 4 (iterate step-fn pos))))

(def win-combos
  "All 69 possible winning combinations."
  (let [rows (for [y (range 6), j (range 4)]
               (for [i (range 4)]
                 [y (+ i j)]))
        columns (for [x (range 7), j (range 3)]
                  (for [i (range 4)]
                    [(+ i j) x]))
        diagonals (concat
                   ; descending diagonals \
                   (get-diags (partial mapv inc)
                              (for [y (range 3), x (range 4)]
                                [y x]))
                   ; ascending diagonals /
                   (get-diags (fn [[y x]] [(inc y) (dec x)])
                              (for [y (range 3), x (range 3 7)]
                                [y x])))]
    (concat rows columns diagonals)))

(defn check-board
  "Checks whether the newly inserted coin has won."
  [board coords]
  (let [win-combo
        (first (drop-while (fn [coll]
                             (apply not= (map #(get-in board %) coll)))
                    (filter #(some #{coords} %) win-combos)))]
    (if (empty? win-combo) nil [(get-in board coords) win-combo])))
Line 4-5: Going over each coordinate in start-pos using for and then take the values of 4 subsequent calls of the given step-fn function.

Line 9-14: Using list comprehensions to generate the 24 row and 21 column combinations and binding them to variables (rows and cols) using let.

Line 15-23: concatenate the result of applying our function get-diags on the starting positions of  the diagonals and giving each a special step-fn function:

Line 17: Mapping calls to inc on both variables in [y,x] and return a vector (therefore mapv). partial because we don't supply the collection, on which this mapping shall happen, yet.

Line 21: Creating a function which takes [y,x] coordinates and increments y and decrements x.

Line 24: concatenate all those vectors into one single vector.

Line 30-32: filter out all the winning combinations which contain the given coords (by using some). drop-while returns the first winning combination which is false for the condition function: apply not= on the value of the coordinates in the board (obtaining them with get-in). So if they all have the same value (e.g. "X"), this returns false and drop-while drops that combination.

Line 33: Return nil (instead of an empty lazy sequence) if win-combo is empty?. Otherwhise return the symbol of the winning player and the win-combo.

Algorithm 2: Bitboard


This is a Clojure implementation of the algorithm used in The Fhourstones Benchmark by John Tromp.

Figure 2: Bitboard representation
Since this solution implies adding a bitboard for each player, we have to change the utility functions and definitions to support this new representation. We'll use the vector board for game state and longs for the boards of the players.

If a player inserts a piece into a column, the first free bit of that column (see Figure 2; also note how the y/x axis swapped) inside the long will be set to 1 (all cells default to 0 of course). For example, if player one starts with inserting his first piece in the fourth column, the bit 21 on his bitboard is set to 1.

It's also important for the bit-shifting later on that the bits at 6, 13, 20, 27, 34, 41 and >=48 are always 0 (the board is therefore surrounded by 0s).
(def empty-board 
  "Create vector board of 6x7 for game state and
   empty bitboards for each player (just 0s)."
  [(vec (repeat 6 (vec (repeat 7 (player 0))))), 0, 0])

(defn bit-insert
  "Sets the bit of the given bitboard at position (y, x)."
  [bitboard y x]
  (bit-set bitboard (+ (* x 7) y)))

; Thanks to John for simplifying this one
(defn insert
  "Inserts symbol for given player (either 1 or 2) at specified x
  and sets according bit on his bitboard."
  [boards x player-num]
  (let [y (get-y (boards 0) x)
        vec-board (assoc-in (boards 0) [y x] (player player-num))
        bitboard1 (if (= player-num 1)
                    (bit-insert (boards 1) (- 5 y) x)
                    (boards 1))
        bitboard2 (if (= player-num 2)
                    (bit-insert (boards 2) (- 5 y) x)
                    (boards 2))]
        [vec-board bitboard1 bitboard2]))

(defn bit-print-board
  [bitboard sym]
  (println [1 2 3 4 5 6 7])
  (doseq [bit-row (for [y (range 5 -1 -1)]
                    (for [x (range 0 43 7)]
                      (+ x y)))]
    (println (mapv #(if (bit-test bitboard %) sym "-") bit-row))))

(defn print-boards
  "Print the vector and both bitboards."
  [boards]
  (println [1 2 3 4 5 6 7])
  (doseq [row board] (println row))       (println)
  (bit-print-board (boards 1) (player 1)) (println)
  (bit-print-board (boards 2) (player 2)) (println))
Line 9: Adjust given [y x] coordinates to the bitboard representation (Figure 2) and bit-set that bit on the bitboard.

Line 18-24: Check for each bitboard whether it has to be changed or simply returned unmodified. Change is achieved through our bit-insert. At the end just return all three boards in a vector.

Line 32: mapping a function which either printlns the given symbol or "-", depening on whether the bit is set (bit-test).

Line 29-31: List comprehension calculating all bit numbers of the bitboard (see Figure 2).

Now the actual checking, which is a bit more complex. Here is the code and the explanation is below it:
(defn bit-check
  [c x]
  (bit-and c (bit-shift-right c x)))

(defn check-board
  "Checks whether given bitboard has won."
  [bitboard]
  (let [positions [6 7 8 1]
        coords (mapv (partial bit-check bitboard) positions)]
    (apply bit-or (map bit-check coords (map #(* 2 %) positions)))))
I'll try to explain this algorithm by the aid of an example where a row is a winning combination. The bitboard looks like this:
[0 0 0 0 0 0 0]
[0 0 0 0 0 1 0]
[1 0 1 0 0 0 0]
[0 1 0 0 0 1 0]
[1 1 0 1 1 1 1]
[0 1 1 0 1 0 0]
The number representing this board is 9552816915338. Let's see what those bit-operations actually do.

First step:
(bit-and bitboard (bit-shift-right bitboard 7)
[0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]
[0 0 0 0 0 1 0]   [0 0 0 0 1 0 0]   [0 0 0 0 0 0 0]
[1 0 1 0 0 0 0] & [0 1 0 0 0 0 0] = [0 0 0 0 0 0 0]
[0 1 0 0 0 1 0]   [1 0 0 0 1 0 0]   [0 0 0 0 0 0 0]
[1 1 0 1 1 1 1]   [1 0 1 1 1 1 0]   [1 0 0 1 1 1 0]
[0 1 1 0 1 0 0]   [1 1 0 1 0 0 0]   [0 1 0 0 0 0 0]
Second step:
(bit-and bitboard (bit-shift-right bitboard (* 2 7)))
[0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]
[0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]
[0 0 0 0 0 0 0] & [0 0 0 0 0 0 0] = [0 0 0 0 0 0 0]
[0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]
[1 0 0 1 1 1 0]   [0 1 1 1 0 0 0]   [0 0 0 1 0 0 0]
[0 1 0 0 0 0 0]   [0 0 0 0 0 0 0]   [0 0 0 0 0 0 0]
As you can see the second row, which contains four connected pieces, results into [0 0 0 1 0 0 0] and is therefore the winning combination. All the other rows results into 0.

About the code:

Line 9: Doing the first step for diagonals, column and row.

Line 10: Joining together the result of the second step for diagonals, column and row with bit-or.

Algorithm 3: Logic


Figure 3: Board indices for logic solution
The idea here is to create indices for each cell that is owned by a player. The indices are in the form [y,x] => 10*y + x. Therefore: [2,3] => 23. By doing so, I can use core.logic to search for certain patterns within those numbers. There are four patterns which could lead to a victory: A sequence of four numbers where each number is higher by 1 than the number before (row), each number is higher by 10 (column), each number is higher by 11 (descending diagonal) or each number is higher by 9 (ascending diagonal).
(ns check-board-logic
  (:require [clojure.core.logic :as l]))

(defn diff-pattern
  "Declares that each lvar is higher by diff to the previous lvar."
  [lvars diff]
  (l/everyg (fn [[i j]] (l/+fd j diff i))
            (partition 2 1 lvars)))

(defn check-board
  "Checks whether player with the given symbol has won."
  [board sym]
  (let [indices (mapv (fn [[y x]] (+ (* y 10) x))
                      (filter #(= (get-in board %) sym)
                        (for [y (range 6), x (range 7)] [y x])))]
    (l/run 1 [a b c d diff]
      (l/infd a b c d (apply l/domain indices))
      (l/infd diff (l/domain 1 10 11 9))
      (diff-pattern [a b c d] diff))))
Line 1-2: Creating own namespace since we have to :require clojure.core.logic. Functions from within core.logic can then be accessed with l/function.

Line 7-8: everyg ensures that the given goal succeeds on all elements of the given collection. The goal is that each given pair of logic variables has a difference of diff between them. This is ensured by +fd stating that j equals to adding diff to i. The collection is the partition of the given lvars to be pairs of subsequent logic variables.

Line 13-15: filter the whole board for only those cells matching the given symbol. mapv the function which transforms the coordinates to indices (as described before) over all the cells owned by the player.

Line 16: run a core.logic solution search with 5 logic variables. At this point, the logic variables don't hold a value. Later on they can be everything or nothing - they just have to fit the goals we use.

Line 17: Rule describing that each logic variable (a, b, c and d) can only hold the value of one number inside indices. infd therefore assigns the given logic variables the domain containing the numbers of indices.

Line 18: Making sure that the logic variable diff holds the value of the difference for one possible pattern.

Line 19: Stating that the sequence of logic variables [a b c d] has the difference diff between each subsequent element.

core.logic now tries to give [a b c d] and diff values which satisfy all the goals. If there is a winner, it responds with the pattern inside of those numbers.

Performance


I'm not doing a lot of benchmarking in general, but I'll use those different algorithms on a few different boards so you get a vague feeling about their performance. We will create a function insert-pieces which takes a check-board function and a collection of [x, player-num] pairs.
(defn insert-pieces
  [check-board-fn xs-and-nums]
  (check-board-fn (reduce (fn [board [x player-num]]
                            (insert board x player-num))
                          empty-board xs-and-nums)))

; some [x player-num]s for testing:
(def test-row  [[0 1] [0 2] [1 1] [1 2] [2 1] [2 2] [3 1]])

(def test-col  [[1 1] [2 2] [1 1] [2 2] [1 1] [2 2] [1 1]])

(def test-desc [[4 1] [3 2] [3 1] [4 2] [2 1] [4 2] [3 1]
                [2 2] [2 1] [1 2] [1 1] [1 2] [1 1]])

(def test-asc  [[3 1] [4 2] [4 1] [5 2] [5 1] [6 2]
                [5 1] [6 2] [6 1] [0 2] [6 1]])
;;; usage:
; algorithm 1: win-combos
(insert-pieces #(time (check-board % [y x])) ; [y x] coordinates of newest piece
               test-*)

; algorithm 2: bitboard
(insert-pieces #(time (bit-check-board (% 1)))
               test-*)

; algorithm 3: logic
(insert-pieces #(time (check-board % "X"))
               test-*)
Execution times for test-row:
;;; test-row
; algorithm 1: win-combos
"Elapsed time: 0.084578 msecs"
[" " ([2 0] [2 1] [2 2] [2 3])]

; algorithm 2: bitboard
"Elapsed time: 0.045677 msecs"
1

; algorithm 3: logic
"Elapsed time: 0.651759 msecs"
([53 52 51 50 1])
Board for test-row:
[1 2 3 4 5 6 7]
[             ]
[             ]
[             ]
[             ]
[O O O        ]
[X X X X      ]
Execution times for test-col:
;;; test-col
; algorithm 1: win-combos
"Elapsed time: 0.122432 msecs"
["X" ([2 1] [3 1] [4 1] [5 1])]

; algorithm 2: bitboard
"Elapsed time: 0.051683 msecs"
128

; algorithm 3: logic
"Elapsed time: 0.948235 msecs"
([51 41 31 21 10])
Board for test-col:
[1 2 3 4 5 6 7]
[             ]
[             ]
[  X          ]
[  X O        ]
[  X O        ]
[  X O        ]
Execution times for test-desc:
;;; test-desc
; algorithm 1: win-combos
"Elapsed time: 0.188921 msecs"
["X" ([2 1] [3 2] [4 3] [5 4])]

; algorithm 2: bitboard
"Elapsed time: 0.051543 msecs"
1024

; algorithm 3: logic
"Elapsed time: 1.18807 msecs"
([54 43 32 21 11])
Board for test-desc:
[1 2 3 4 5 6 7]
[             ]
[             ]
[  X          ]
[  O X X O    ]
[  X O X O    ]
[  O X O X    ]
Execution times for test-asc:
;;; test-asc
; algorithm 1: win-combos
"Elapsed time: 0.174882 msecs"
["X" ([2 6] [3 5] [4 4] [5 3])]

; algorithm 2: bitboard
"Elapsed time: 0.050844 msecs"
2097152

; algorithm 3: logic
"Elapsed time: 1.028203 msecs"
([53 44 35 26 9])

Board for test-asc:
[1 2 3 4 5 6 7]
[             ]
[             ]
[            X]
[          X X]
[        X X O]
[O     X O O O]
As you can see, the bitboard solution is the fastest and has a rather constant time of about ~0.05 msecs, because it's always checking the whole board.

The win-combo algorithm is the second fastest and it mostly depends on the coordinates of the newly inserted piece, since this determines how many checks it has to do.

The slowest, but still fairly fast, logic solution depends on how many pieces have already been inserted into the board, because it searches over all those coordinates for a pattern.

Conclusion


First, I want to thank the guys in #clojure on Freenode who helped me quite a bit. Clojure has such a friendly and patient community.

In the next post I'll hopefully write about the different AI's I have implemented as opponents for this game, but this might take quite some time since I have to read a lot of stuff about AI first. That's also the reason why I'm not sure which algorithm I'll use for checking the board (I'd like to use the same for everything).

In the meantime, feel free to add me on Google+, write me an email (see G+ profile) if you have any questions, read my other posts and comment below or discuss this article here:

August 26, 2012

Adventures In Declarative Programming: Conway's Game Of Life

My first blog post about declarative programming explained how to write a Sudoku solver in the logic programming language Prolog. This time I'll show you how to implement Conway's Game of Life in the functional programming language Clojure.

But before that, let me explain a few general things. The first three paragraphs are for readers who are not familiar with certain concepts. People who already know what Clojure or Conway's Game of Life is, may feel free to skip those paragraphs. It starts getting serious at "Game of Life in Clojure".

Functional Programming


Functional Programming is a style of programming (a so called programming paradigm), that tries to avoid state and mutable data and emphasizes writing and using functions that have small or no side effects. This results in programs which are easier to test, maintain, understand and predict. One result of this rules is that functions are first-class, which means that they are treated like any other data. They can be created, passed around and modified just like a string.

Some languages, such as Lisp, are made for using this paradigma. Others may not be made for it, but they still can profit from this style.

Lisp


In order to understand the code below, I have to tell you a few things about how to write code in Lisp.
The code consists of s-expressions, which can be looked at as a list. This is the root of Lisp's syntax or , better say, lack of syntax. This is what allows Lisp to treat everything as data and manipulate it - even code itself. And that's the heart of the powerful macro system, which is as far as I know unique to Lisp. We will not care too much about the macro system now, but it's basically another level of abstraction which most other programming languages lack.

A s-expression can be as simple as:
(+ 1 1)
=> 2
which just adds 1 to 1. As you can see, s-expressions are written in prefix notation. Most other (imperative) languages use infix notation, but Lisp does everything for a reason. It's also strictly regular about its notation, unlike many other languages. A more complex s-expression could look like this:
(* (+ 1 (- 4 3)) (/ 6 (+ 2 1)))
=> 4
This notation might seem awkward at first, but as I said it has its cause. Since all those expressions are just simple lists, they can also be treated like that and hence manipulated by macros just like a normal list. This gives Lisp great metaprogramming and code generation capabilities.

Clojure


Clojure is a young Lisp dialect which can run in the Java Virtual Machine, the Common Language Runtime and JavaScript Engines. Since it's a Lisp, it's a functional programming language, but not purely functional such as Haskell, which means that certain functions can have side effects. It also has the beloved macro system known from other Lisp's, but we won't see that in action in this article.

One more thing rather special to Clojure as a Lisp dialect is the massive use of lazy sequences. Lazy sequences are only evaluated as far as they are needed, which avoids needless calculations and allows constructing potentially infinite data structures. We'll see them throughout the code.

Conway's Game of Life


This zero-player "game" basically consist of a cellular automaton following four rules which were devised by John Horton Conway. These rules together with the initial input determine the whole evolution of the cells in this game.

The world in which the evolution of those cells takes place is an infinite two-dimensional grid. Each cell is either dead or alive and has exactly eight neighbours.

The four rules are:
  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
The game starts by giving the world an initial state with certain cells being alive. Then those four rules are applied and by doing so, one of three things happen to each cell: Nothing, death or birth. After applying those rules the first time, we have the second generation of our world. The same procedure starts over and over again, until either we decide to stop it or all cells are dead.

There are some special patterns which are known to have certain behaviour. There are still lifes, oscillators, spaceships and so on. Some fancy graphics to visualize them:

Still lifes
Block
Boat
Oscillators
Blinker
Pulsar
Spaceships
Glider
Lightweight spaceship 

You can find some more patterns at Wikipedia.

Game of Life in Clojure


I'm currently learning Clojure with the book Clojure Programming and the authors decided to show how you can work with Clojure's collection by implementing Conway's Game of Life.
Let's go through a slightly modified version of the code in the book.

The first thing we need is a representation of the world, which is a two-dimensional grid. The most obvious and simple one is just a vector of vectors (or array of arrays in other languages). Inside these vectors dead cells are indicated by a whitespace (" ") and living cells by a "X" (just because it's nicer to print them later on). Let's start by writing a function that creates an the world, which optionally accepts a set of y/x coordinates to settle living cells.
(defn create-world
  "Creates rectangular world with the specified width and height.
  Optionally takes coordinates of living cells."
  [w h & living-cells]
  (vec (for [y (range w)]
         (vec (for [x (range h)]
                (if (contains? (first living-cells) [y x]) "X" " "))))))
Line 1: Use uf defn to define a function. The form is (defn name "optional doc-string" [arguments] body).

Line 4: Argument list consisting of two fixed arguments w and h. The & allows us to create the optional argument living-cells, which is then wrapped into a list, because there could be more variables than just living-cells. This is why we have to use first at line 7.

Line 5-6: vec creates a new vector from a given collection (in this case from a lazy sequence). for is a list comprehension with the form (for [bindings] body). We use both of them twice in order to create our nested vector of vectors.

Line 7: if has the form (if test then-form else-form). If the test statement evaluates to true, the then-form is executed and otherwhise the else-form. (contains? (first living-cells) [y x])checks whether the living-cells collection contains? the [y x] coordinates of our current position. If it does, we set that cell to "X" and otherwhise to " ".

We now can generate empty worlds and worlds with certain cells being alive:
(create-world 4 4)
=> [[" " " " " " " "] [" " " " " " " "] [" " " " " " " "] [" " " " " " " "]]

(create-world 4 4 #{[0 0], [1 1], [2 2], [3 3]})
=> [["X" " " " " " "] [" " "X" " " " "] [" " " " "X" " "] [" " " " " " "X"]]
The next two functions are the core of this implementation. In order to determine the next generation, we need a function that manipulates the cells according to the rules. Since the rules always depend on the neighbours of a given cell, we need a function to determine all neighbours of a cell. The neighbours function looks like this:
(defn neighbours
  "Determines all the neighbours of a given coordinate"
  [[x y]]
  (for [dx [-1 0 1] dy [-1 0 1] :when (not= 0 dx dy)]
    [(+ dx x) (+ dy y)]))
Line 4: Usage of for to create a lazy sequence using two variables, which iterate over -1, 0 and 1. :when both of those variables are not equal to 0, the body form is executed. The rightmost binding, dy, is iterated as the fastest one.

Line 5: Calculating new coordinates based on the offsets dx and dy given by the for bindings.

What are all the neighbours of the location (1/1)?
(neighbours [1 1])
=> ([0 0] [0 1] [0 2] [1 0] [1 2] [2 0] [2 1] [2 2])
Now, instead of writing a function which behaves exactly according to the rules of Conway's Game of Life, we could write a high-order function that takes three arguments: A function to determine the neighbours, a predicate which determines whether a cell shall be given life (e.g. #{3} for Conway's rules) and one predicate that determines whether a cell survives to the next generation (#{2 3}). It then returns a function which calculates the next generation according to the given rules.
(defn stepper
  "Returns a step function for Life-like cell automata.
   neighbours takes a location and return a sequential collection
   of locations. survive? and birth? are predicates on the number
   of living neighbours."
  [neighbours birth? survive?]
  (fn [cells]
    (set (for [[loc n] (frequencies (mapcat neighbours cells))
               :when (if (cells loc) (survive? n) (birth? n))]
           loc))))
Line 7: Use of fn to create and then return a new, unnamed function. The form is (fn [arguments] body).

Line 8: Creating a set from the return value of the list comprehension which iterates over the locations loc and the number of living neighbours n. mapcat returns the concatanated list of the result of calling neighbours on all coordinates in cells. frequencies then returns a hash table (map) of each distinct item returned by the mapcat and associates it with the number of occurence.

Line 9: :when makes sure only those coordinates loc are returned that pass the if test. If loc is in cells and the number of living neighbours n is high enough according to the predicate survive?, the loc is returned. If loc is not in cells, only those loc are returned that have enough living neighbours n according to the preidcate birth? to give that cell life.

Line 10: Just return those loc that apply to the rules described before.

Let's try to generate the second state of a blinker pattern. To do so, we give our stepper the coordinates of the livings cells for the vertical position of the blinker ( --- ):
((stepper neighbours #{3} #{2 3}) #{[1 0] [1 1] [1 2]})
=> #{[2 1] [1 1] [0 1]}
As we can see, we end up with the coordinates of the horizontal position of the blinker ( | ).

#{} is a set, which can be used as a predicate (#{3} and #{2 3}) to check whether the arguments given to it are in that set. For example: (#{2 3} 3) => 3 and (#{2 3} 1) => nil

Those two functions are quite straighforward in Clojure and actually everything you need to solve Conway's Game of Life. create-world is just for the representation of the world.
For the sake of a nicer interface, we will create some definitions.
(def glider #{[2 0] [2 1] [2 2] [1 2] [0 1]})
(def light-spaceship #{[2 0] [4 0] [1 1] [1 2] [1 3] [4 3] [1 4] [2 4] [3 4]})

(def conway-stepper (stepper neighbours #{3} #{2 3}))
Line 1: def has the form (def name body). name is then assigned the value of evaluating body. In this case a set of vectors containing two integers each, which are the coordinates of the living cells.

We now have two patterns, a glider and a lightweight spaceship, and one function that manipulates cells according to the rules of Conway. The last function, which we will write now, just helps us to determine the evolution according to Conway's Game of Life by giving it the size of the world, an initial pattern and the number of the generation we want to see.
(defn conway
  "Generates world of given size with initial pattern in specified generation"
  [[w h] pattern iterations]
   (->> (iterate conway-stepper pattern)
        (drop iterations)
        first
        (create-world w h)
        (map println)))
Line 4: ->> inserts the first form as the last item into the second form, then this new form as the last item into the third form and so on. iterate has the form (iterate function value) and returns the lazy sequence value, (function value), (function (function value)), etc.

Line 5: drop has the form (drop n collection) and returns a lazy sequence of all but the first n items of collection.

Line 6: first has the form (first collection) and returns only the first item of the collection.

Line 7: Usage of our self-defined function create-world to create the world with the living cells given by the 3 lines above.

Line 8: map calls println over all the rows in our world. println just prints out the row and then a newline.

So, let's see whether all those brackets can actually generate the evolution of some cells.
(conway [5 15] light-spaceship 0)
Output:
[                             ]
[  X X X X                    ]
[X       X                    ]
[        X                    ]
[X     X                      ]
(conway [5 15] light-spaceship 1)
Output:
[    X X                      ]
[  X X X X                    ]
[  X X   X X                  ]
[      X X                    ]
[                             ]
(conway [5 15] light-spaceship 2)
Output:
[  X     X                    ]
[          X                  ]
[  X       X                  ]
[    X X X X                  ]
[                             ]
(conway [5 15] light-spaceship 3)
Output:
[                             ]
[        X X                  ]
[    X X   X X                ]
[    X X X X                  ]
[      X X                    ]
(conway [5 15] light-spaceship 4)
Output:
[                             ]
[      X X X X                ]
[    X       X                ]
[            X                ]
[    X     X                  ]

And the glider:
(conway [4 4] glider 0)
Output:
[  X    ]
[    X  ]
[X X X  ]
[       ]
(conway [4 4] glider 1)
Output:
[       ]
[X   X  ]
[  X X  ]
[  X    ]
(conway [4 4] glider 2)
Output:
[       ]
[    X  ]
[X   X  ]
[  X X  ]
(conway [4 4] glider 3)
Output:
[       ]
[  X    ]
[    X X]
[  X X  ]
(conway [4 4] glider 4)
Output:
[       ]
[    X  ]
[      X]
[  X X X]
You can download the full source code here or copy it from here:
(ns conways-game-of-life.core)

(defn create-world
  "Creates rectangular world with the specified width and height.
  Optionally takes coordinates of living cells."
  [w h & living-cells]
  (vec (for [y (range w)]
         (vec (for [x (range w)]
                (if (contains? (first living-cells) [y x]) "X" " "))))))

(defn neighbours
  "Determines all the neighbours of a given coordinate"
  [[x y]]
  (for [dx [-1 0 1] dy [-1 0 1] :when (not= 0 dx dy)]
    [(+ dx x) (+ dy y)]))

(defn stepper
  "Returns a step function for Life-like cell automata.
   neighbours takes a location and return a sequential collection
   of locations. survive? and birth? are predicates on the number
   of living neighbours."
  [neighbours birth? survive?]
  (fn [cells]
    (set (for [[loc n] (frequencies (mapcat neighbours cells))
               :when (if (cells loc) (survive? n) (birth? n))]
           loc))))

; patterns
(def glider #{[2 0] [2 1] [2 2] [1 2] [0 1]})
(def light-spaceship #{[2 0] [4 0] [1 1] [1 2] [1 3] [4 3] [1 4] [2 4] [3 4]})

; steppers
(def conway-stepper (stepper neighbours #{3} #{2 3}))

(defn conway
  "Generates world of given size with initial pattern in specified generation"
  [[w h] pattern iterations]
   (->> (iterate conway-stepper pattern)
        (drop iterations)
        first
        (create-world w h)
        (map println)))

Game of Life in Functional Python


Since I'm coming from Python, I was curious whether this solution could be implemented in Python. Python does support functional programming to some extent. This might also help some people understanding the Clojure code above a bit better.

Note that this is NOT idiomatic Python code and probably no real-world Python developer would write code like this. I was just curious how far you can push functional programming in Python, which was actually not designed to be used this way.

The code is almost a transliteration of the Clojure code, so I don't have to explain all the functions again:
from collections import Counter
from itertools import chain

def mapcat(func, iter):
    "Maps func over iter and returns concanated list"
    return chain.from_iterable(func(*args) for args in iter)

def create_world(w, h, living_cells=()):
    """Creates a rectangular world with the specified width and height.
    Optionally takes coordinates of living cells. """
    return [["X" if (y, x) in living_cells else " " for x in range(h)] for y in range(w)]

def neighbours(y, x):
    "Determines all the neighbours of a given coordinate"
    return [(dy + y, dx + x) for dy in [-1, 0, 1] for dx in [-1, 0, 1]
            if not (dy == 0 and dx == 0)]

def stepper(neighbours, birth, survive):
    """Returns a step function for Life-like cell automata.
   neighbours takes a y/x-coordinates and returns a sequential collection
   of locations. survive and birth are constraints on the number
   of living neighbours."""
    return lambda cells: set(
        [loc for (loc, n) in Counter(mapcat(neighbours, cells)).items()
                   if (loc in cells and n == birth) or n == survive])

# pattern definitions
glider = set(((2, 0), (2, 1), (2, 2), (1, 2), (0, 1)))
light_spaceship = set(((2, 0), (4, 0), (1, 1), (1, 2), (1, 3), (4, 3), (1, 4), (2, 4), (3, 4)))

# steppers
conway_stepper = stepper(neighbours, 2, 3)

def conway(w, h, pattern, iterations):
    "Generates world of given size with initial pattern in specified generation"
    cells = pattern
    
    for unused in range(iterations):
        cells = conway_stepper(cells)
        
    for row in create_world(w, h, living_cells=cells):
        print(row)
Thanks to nedbat from #python for helping me with this.

None of the functions have side effects (beside conway(), which does printing), as emphasized by the functional programming style. Also, no function depends on some global state - hence they are all deterministic. This means that those functions always return the same output when called with a specific input. They are a mapping of input to output.

You can download the full Python source code here.

Conclusion


I hope I could make you interested in functional programming and Lisp, while giving you a vague idea what these things are about. The most widely used Lisp at the moment is probably Common Lisp and there is a good and free book out there called Practical Common Lisp.

Depending on what you want to do with Lisp, it might be a good idea to take a closer look at Clojure too. It has the potential to be more widely used in the "real world", since it's running in the JVM and is often used for things like web developing. Two good books on Clojure would be Clojure Programming and The Joy Of Clojure.



Discussion on Hacker News (thanks to samrat for submitting)
Discussion on Reddit: r/coding

August 6, 2012

Massive Open Online Classes With Udacity

One part of my first 30 day challenge was doing classes on Udacity. Now, after I finished CS101 and created a search engine, I decided to blog about Udacity and the experience I made.

About Udacity


Udacity is a kind of online university, where you can attend to classes and learn new things. The main topic is computer science, but they also offer some classes about math and physics (see here). According to Sebastian Thrun, it all started after he saw this TED Talk from the founder of Khan Academy.
Udacity evolved from the online AI class, which is/was basically the same class that the students at Stanford University took - just online, available when you want and for free.

Even though I'm not a teacher or professor, I can feel Sebastian's excitement too. Imagine you could educate and therefore help thousands or even millions of people around the world.
People, who do not have free higher education in their own country. People, who are running away from war. People, who want to make their own and the life of their families a better one.

How It Works


The classes are based on YouTube videos, which are mostly between 0.5 - 5 minutes long. After you learnt a new concept, you are asked to answer questions about what you've just learnt.

Many people might think that teaching in a real class room is much better, because there is an interaction between the students and the professor, which can't really happen in those YouTube videos. When you're one student in a class room of 200 students, do you really have an interaction with your professor? The professor can't pause or explain things over and over again to each student. But you can pause and rewind the video of a professor.

And you're not totally lost on your own. There is a community of students inside Udacity, in which you are encouraged to participate. This not only allows one to ask questions because he/she didn't fully understand a concept, but also let's the more experienced students help other students. The result is a deeper understanding for everyone.

My Experience


I'm really interested in education and I do like new and different approaches, but Udacity is definitely not for everyone. Here are some of the reasons why I enjoyed taking CS101:
  • Feeling of being tutored one-to-one (which leads to best results)
  • Python as the programming language (very simple to read, suitable for beginners)
  • Lots of quizzes (keeps you going)
  • Start, stop, pause, rewind and forward whenever you want
  • No deadlines - learn at your very own pace
Even though I didn't learn a lot of new technical things in this class, since I'm Python programmer who developed a few web crawlers already, I learnt a lot about myself and I want to encourage everybody to sign up at Udacity and give it a try.
You won't regret it.

July 22, 2012

Prolog Sudoku Solver Explained

Note: This is a follow-up blog post on Adventures In Declarative Programming: Sudoku Solver.

Prolog


The main language used in logic programming is Prolog, which name is derived from "PROgramming in LOGic". And that's exactly what it does: It allows you to program in terms of logic. The funny thing is that it doesn't actually solve problems really logical, as you'll see in this post.

Prolog was at first invented for computional linguists to do natural language processing, but its applications spreaded far over time. An extract from Wikipedia: "[...] theorem proving, expert systems, games, automated answering systems, ontologies and sophisticated control systems."

Therefore, Prolog can nowadays be seen as a high-level tool for solving logical problems (to what natural language understanding can be narrowed down too).

Knowledge Base


In Prolog you're describing your problem in terms of relations, which consist of facts and rules. Facts and rules together build up a knowledge base, which can be queried to get results to your problem.

That's how a simple knowledge base could look like:

human(socrates).         % facts about who is human
human(aristotle).
human(plato).

god(zeus).               % and who is a god
god(apollo).

mortal(X) :- human(X).   % a logical assertion (rule) that X is mortal if X is human
In this example we can see five facts and one rule. Some sample queries could look like this:
user@host> swipl -f kb.pro
% /path/to/kb.pro compiled 0.00 sec, 8 clauses
?- human(plato).      % is plato a human?
true.

?- god(X).            % who is a god?
X = zeus ;
X = apollo.

?- mortal(socrates).  % is socrates mortal?
true.

?- mortal(zeus).      % is zeus mortal?
false.

?- mortal(Y).         % who is mortal?
Y = socrates ;
Y = aristotle ;
Y = plato.
Prolog can answer our queries by using unification and proof search (including backtracking).

Unification


In the example above Prolog unified X with zeus and apollo and Y with socrates, aristotle and plato. But what exactly does this mean?

Prolog knows three types of terms:

  • Constants: Either atoms (plato) or numbers (42).
  • Variables: Always start with an uppercase letter (X, Head, A42, ...)
  • Complex terms: Have the form functor(term_1, ..., term_n).

plato and plato unfiy because they are the same atom; 42 and 42 unify because they are the same number; X and X unify because they are the same variable; human(plato) and human(plato) unify because they are the same complex term.

Constants and variables can unify if the variable has the same value as the atom or the number. god(zeus) and god(X) unify by assigning X the value zeus.

A precise definition of unification from the Learn Prolog Now tutorial:
  1. If term1 and term2 are constants, then term1 and term2 unify if and only if they are the same atom, or the same number.
  2. If term1 is a variable and term2 is any type of term, then term1 and term2 unify, and term1 is instantiated to term2 . Similarly, if term2 is a variable and term1 is any type of term, then term1 and term2 unify, and term2 is instantiated to term1 . (So if they are both variables, they’re both instantiated to each other, and we say that they share values.)
  3. If term1 and term2 are complex terms, then they unify if and only if:
    1. They have the same functor and arity (number of arguments a complex term takes), and
    2. all their corresponding arguments unify, and
    3. the variable instantiations are compatible. (For example, it is not possible to instantiate variable X to mia when unifying one pair of arguments, and to instantiate X to vincent when unifying another pair of arguments .)
  4. Two terms unify if and only if it follows from the previous three clauses that they unify.

Proof Search


If we remember our knowledge base about humans and gods again and especially the rule mortal(X) :- human(X). we can try to understand how Prolog solves this.

Prolog knows that in order to solve mortal(X) it only has to unify human(X) with something. It looks into the knowledge base and search from top to bottom for possible unifications. As it encounters human(socrates) it has found a possible solution by unifying human(X) with human(socrates). Therefore X = socrates and that's our first answer (actually it's Y = socrates in our sample queries, because Y is the same as the X inside the rule). If we ask for another solution by pressing ; Prolog goes on in the knowledge base and finds the other humans.


Everytime Prolog unifies a variable with a term while doing proof search, it remembers this as a choice point. If Prolog finds out it made a mistake, it reverts back to the last choice point and tries to unify the variable with some other term. This process is called backtracking and is fundamental for finding solutions in Prolog.

Sudoku Solver


In one of my previous blog posts I wrote about a Sudoku Solver written in 15 lines of code using SWI-Prolog and the CLPFD library. Let's recall the code:
:- use_module(library(clpfd)).

sudoku(Rows) :-  
  append(Rows, Vs), Vs ins 1..9,
  maplist(all_distinct, Rows),
  transpose(Rows, Columns),     
  maplist(all_distinct, Columns),     
  Rows = [A,B,C,D,E,F,G,H,I],     
  blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),     
  maplist(label, Rows).      

blocks([], [], []).       
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-     
  all_distinct([A,B,C,D,E,F,G,H,I]),      
  blocks(Bs1, Bs2, Bs3)
Now, as you understand the basic concepts of Prolog, I can explain the Sudoku solver in greater detail to you. But before I do so one short note about a notation used in the following lines. Whenever there is a predicate name mentioned, it's followed with a / and a number, indicating its arity (number of arguments it takes).

Line 1: "Include" the library CLPFD (Constraint Logic Programming over Finite Domains). This library basically allows us to make use of the domains coming up on Line 4.

Line 3: The solving predicate sudoku(Rows) takes a list of list as argument.

Line 4: Use of 'append/2' to insert Domains into our lists. A domain is like a variable without a concrete value, but with a range of possible values: In this case 1 to 9 as ensured by 'ins/2' from the CLPFD.

Line 5: With 'maplist/2' we call the predicate 'all_distinct/1' from the CLPFD library on all lists inside the list Rows. 'all_distinct/1' makes sure that every value in the list just occures once, as forced by the rules of Sudoku.

Line 6: The next step is to 'transpose/2' the Rows into Columns, which is again part of the CLPFD library.

Line 7: Then we use 'all_distinct/1' again to make sure all numbers just occur once in the Columns.

Lines 8-9: Convert Rows in 3x3 Blocks and checks whether they are 'all_distinct' using our self-defined predicate 'blocks/3' (see Lines 12-15).

Line 10: Again usage of 'maplist/2' to call the predicate 'label/1' on our Rows. 'label/1' makes sure all the domains have one concrete value - just in case there are more than one solutions to the Sudoku puzzle given.

Line 12: A simple fact expressing that our predicate is true when it gets three empty lists as input. This is the escape point for the recursion following now. (Note that it's very important that this is defined before and not after Line 13, because Prolog will always use this complex term for 'blocks/3' as the first one, since it's reading the knowledge base from top to bottom.)

Line 13: Prolog will use this rule if 'blocks/3' is supplied with non-empty lists. By the use of the pipe ( | ) we split up the given rows into their first three elements and the rest (so called tail) we want to use later.

Line 14: Now we're having a 3x3 block consisting of  three elements from each row originally given to 'blocks/3' in 'sudoku' at Line 9. And again we're making sure that every number just occurs once in this 3x3 block by using 'all_distinct/1'.

Line 15: Going into recursion with the rest of the list (until they are splitted up to empty lists).

Most of the backtracking is probably happening inside 'all_distinct/1'. This is where Prolog unifies the variables inside the Rows, Columns and 3x3 blocks with the numbers from 1 to 9. Sometimes it just has to backtrack a few variables, sometimes just a few rows and maybe it even has to start all over again from the very beginning, when it made a mistake unifying the first variable.

If you look at Prolog from a more procedural perspective, it might not be always the most efficient or performant way to get to the solution, but it makes solving easy logical problems easy and solving hard logical problems possible. It's all about simplicity and clearness, which is very important in my opinion.

There are of course a lot of interesting algorithms out there to solve Sudoku puzzles, some of them being much more efficient than this one, but this solution is interesting too - maybe not that much from a procedural perspective, but from a perspective focused on clearness and simplicity.

Why Should I Learn Prolog?


Even though this might be clear to most programmers, I want to point it out.

Learning new programming languages make you a better programmer. And it especially does if learning a new language includes a new way of thinking - such as the declarative programming in Prolog.

As Paul Graham explained in his essay Beating The Averages, you will start thinking about problems from a new perspective. The more perspectives you have, from which you can look at a problem and the more languages you have, in which you can think about a problem, the better your solution will be.

If you haven't read Beating The Averages yet, I highly recommened to do so now (or at least the paragraph about The Blub Paradox).

Sources


http://www.amzi.com/articles/prolog_under_the_hood.htm
http://www.learnprolognow.org/



Discussion on Reddit: r/coding

July 15, 2012

SWI-Prolog SyntaxHighlighter Brush

My last blog post about a Sudoku solver written in SWI-Prolog motivated me to create a custom brush for the JavaScript SyntaxHighlighter, which helps creating code blocks with syntax highlighting on any website (of course, Java Script has to be run though).

So it does for Blogger and here's how:

Install SyntaxHighlighter On Blogger


Go to www.blogger.com, login with your account and select the blog in which you want to use SyntaxHighlighter. Then click on Layout --> Add a Gadget --> HTML/JavaScript give it a title and paste in this Code into the Content:

<!-- Include required JS files -->
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js"></script>

<!--    At least one brush, here we choose JS. You need to include a brush for every language you want to highlight-->

<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushBash.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJScript.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCpp.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPython.js"></script>
<script type="text/javascript" src="http://dl.dropbox.com/u/84194941/SyntaxHighlighter/shBrushSWIProlog.js"></script>

<!-- Include *at least* the core style and default theme -->
<link href="http://alexgorbatchev.com/pub/sh/current/styles/shCore.css" rel="stylesheet" type="text/css" />
<link href="http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css" rel="stylesheet" type="text/css" />

<!-- Finally, to actually run the highlighter, you need to include this JS on your page -->
<script type="text/javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.defaults['tab-size'] = 4;
SyntaxHighlighter.all()

</script>

This is my current configuration which adds support for highlighing JavaScript, Bash, C++, Python and SWI-Prolog (for more brushes see here).

Highlight Code


There are two possitilies to highlight code now, as described here. I decided to use the <pre>-tag, so the HTML of my post looks like this:
<pre class="brush: swipl">:- use_module(library(clpfd)).

sudoku(Rows) :- 
  append(Rows, Vs), Vs ins 1..9,
  maplist(all_distinct, Rows),
  transpose(Rows, Columns),   
  maplist(all_distinct, Columns),   
  Rows = [A,B,C,D,E,F,G,H,I],   
  blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),   
  maplist(label, Rows).     

blocks([], [], []).     
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-   
  all_distinct([A,B,C,D,E,F,G,H,I]),     
  blocks(Bs1, Bs2, Bs3)

</pre>

The actual source code for this custom brush can be found here:
http://dl.dropbox.com/u/84194941/SyntaxHighlighter/shBrushSWIProlog.js

July 12, 2012

Adventures In Declarative Programming: Sudoku Solver

Declarative Programming


... in contrast to Imperative Programming (like C/C++, Python, Java, ...) doesn't care about the exact way of solving a problem. In Imperative Programming you define how a problem has to be solved. In Declarative Programming you simply describe what the problem is and 'the language' does the actual solving for you.
Since this is not that easy to understand if you never did it yourself before, I want to show you an example right away.

Solving Every Sudoku With 15 Lines Of Code


Of course lines of code is not a good measure to take, but it should just express that it's sometimes much easier to describe a problem than solving it step by step.
Before I'll show you the actual code I want to tell you a few things about the programming language used.

Prolog


Prolog is a logic programming language and basically consist of rules and facts. A Prolog program therefore is some kind of knowledge base, which you can query to get solutions to your problems.
So, in order to solve every Sudoku puzzle we just have to describe the rules of this game. Not that hard, eh? Great, let's do this.

Sudoku Solver In Prolog


:- use_module(library(clpfd)).

sudoku(Rows) :-  
  append(Rows, Vs), Vs ins 1..9,
  maplist(all_distinct, Rows),
  transpose(Rows, Columns),     
  maplist(all_distinct, Columns),     
  Rows = [A,B,C,D,E,F,G,H,I],     
  blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),     
  maplist(label, Rows).      

blocks([], [], []).       
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-     
  all_distinct([A,B,C,D,E,F,G,H,I]),      
  blocks(Bs1, Bs2, Bs3)

This program is actually that easy, that you can even find it in the SWI-Prolog manual. Note that this example only works with SWI-Prolog and not with other Prolog implementations, because it uses the SWI-Prolog CLPFD library (Constraint Logic Programming over Finite Domains).

This is already the whole solver. It's quite easy to see that an imperative solution to this problem would be far more complex. In this blog post I'm explaining how the Sudoku solver actually works: Prolog Sudoku Solver Explained

Solving A Sudoku Puzzle


In order to solve a Sudoku puzzle now we have to query our program. An example query looks like this:

 Puzzle = [  
   [8,_,_,_,_,_,_,_,_],  
   [_,_,3,6,_,_,_,_,_],  
   [_,7,_,_,9,_,2,_,_],  
   [_,5,_,_,_,7,_,_,_],  
   [_,_,_,_,4,5,7,_,_],  
   [_,_,_,1,_,_,_,3,_],  
   [_,_,1,_,_,_,_,6,8],  
   [_,_,8,5,_,_,_,1,_],  
   [_,9,_,_,_,_,4,_,_]  
   ],  
   Puzzle = [A,B,C,D,E,F,G,H,I],  
   sudoku([A,B,C,D,E,F,G,H,I]).  

The only reason I splitted the whole Puzzle up into single rows (A,B,C, ...) is to generate a nicer output. We can also wrap the call of the predicate 'sudoku' into 'time' so we can see how long the solving actually takes.

If you want to try it out yourself and play around with it, just install SWI-Prolog and copy the program into a file. Then launch the SWI-Prolog interpreter from a terminal with our program as the input file and type in our query:

 user@host> swipl -f sudoku.pro  
 % library(error) compiled into error 0.00 sec, 79 clauses  
 % library(lists) compiled into lists 0.00 sec, 178 clauses  
 % library(occurs) compiled into occurs 0.00 sec, 15 clauses  
 % library(assoc) compiled into assoc 0.00 sec, 98 clauses  
 % library(pairs) compiled into pairs 0.00 sec, 23 clauses  
 % library(clpfd) compiled into clpfd 0.08 sec, 2,724 clauses  
 % /path/to/sudoku.pro compiled 0.08 sec, 2,739 clauses  
 ?- Puzzle = [  
 |  [8,_,_,_,_,_,_,_,_],  
 |  [_,_,3,6,_,_,_,_,_],  
 |  [_,7,_,_,9,_,2,_,_],  
 |  [_,5,_,_,_,7,_,_,_],  
 |  [_,_,_,_,4,5,7,_,_],  
 |  [_,_,_,1,_,_,_,3,_],  
 |  [_,_,1,_,_,_,_,6,8],  
 |  [_,_,8,5,_,_,_,1,_],  
 |  [_,9,_,_,_,_,4,_,_]  
 |  ],  
 |  Puzzle = [A,B,C,D,E,F,G,H,I],  
 |  time(sudoku([A,B,C,D,E,F,G,H,I])).
% 934,447 inferences, 0.154 CPU in 0.155 seconds (100% CPU, 6051414 Lips)
 Puzzle = [[8, 1, 2, 7, 5, 3, 6, 4|...], [9, 4, 3, 6, 8, 2, 1|...], [6, 7, 5, 4, 9, 1|...], [1, 5, 4, 2, 3|...], [3, 6, 9, 8|...], [2, 8, 7|...], [5, 2|...], [4|...], [...|...]],  
 A = [8, 1, 2, 7, 5, 3, 6, 4, 9],  
 B = [9, 4, 3, 6, 8, 2, 1, 7, 5],  
 C = [6, 7, 5, 4, 9, 1, 2, 8, 3],  
 D = [1, 5, 4, 2, 3, 7, 8, 9, 6],  
 E = [3, 6, 9, 8, 4, 5, 7, 2, 1],  
 F = [2, 8, 7, 1, 6, 9, 5, 3, 4],  
 G = [5, 2, 1, 9, 7, 4, 3, 6, 8],  
 H = [4, 3, 8, 5, 2, 6, 9, 1, 7],  
 I = [7, 9, 6, 3, 1, 8, 4, 5, 2] .  
(Executed on an Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz and 4GB of RAM)

Solving this Sudoku puzzle takes 0.155 seconds on my laptop which is fast enough for most purposes (the first number 934,447 are the logical inferences during the solving and Lips are Logical Inferences Per Second).

Conclusion


I hope this article made you curious about new programming languages and Prolog specifically.

As a general tutorial on Prolog I can suggest Learn Prolog Now. There are lots of other good books and tutorials out there though. Happy coding!



Discussion on Reddit: r/coding