Clojure Connect Four - Part 1: Checking For A Winner

This post is part of the ongoing series about Connect four in Clojure:

• Clojure Connect Four - Part 1: Checking For A Winner

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:

• Reddit: r/coding
• HackerNews

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

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