Tiny Rule Engine, the Final Post (for now)

This should be the last post in the series about Tiny Rule Engine. I have most of the features down and the part that is left is to actually learn to use them. And what could be a better way than trying our new shiny Tiny Rule Engine than solving n-queens puzzle.

Eight queens (or n-queens) puzzle is popular puzzle as it’s simple enough that the logic is quickly seen. Because it’s combinatorial, amount of possible placements grows very quickly as the board grows.

Since each column can have only one queen and each column will have a queen, I’m using coding system where queen’s number directly tells on which column it resides.

There are two rules that tells when a queen can capture another one:

(rule tre (queen ?q1 is placed on row ?r)
    (rule tre (queen ?q2 is placed on row ?r)
          (unique ?q1 ?q2)
          (assert! tre (warning queen ?q1 can be taken))))

(rule tre (queen ?q1 is placed on row ?r1)
      (rule tre (queen ?q2 is placed on row ?r2)
            (unique ?q1 ?q2)
            (if (= (abs (- ?r2 ?r1))
                   (abs (- ?q2 ?q1)))
              (assert! tre (warning queen ?q1 can be taken)))))

First rule detects when two queens are placed on same row and asserts a warning in tre database. Second one performs a bit of arithmetic to detect when two queens are on same diagonal and again asserts a warning in the tre database.

Armed with this knowledge, we can start working out the actual search algorithm. I couldn’t figure out how to write this based only one rules and assertions and had to resort to some old fashioned lisp instead. I have a feeling that it might be possible to write the whole algorithm only with rules and assertions though. If you can figure out how, do let me know.

In any case, now we can try out the rules:

=> (setv tre (create-tre "queens"))
=> (assert! tre (queen 0 is placed on row 0))
=> (assert! tre (queen 3 is placed on row 3))
=> (run tre)
=> (show tre 'queen)
queen 0 is placed on row 0
queen 3 is placed on row 3
warning queen 0 can be taken
warning queen 3 can be taken

We’re using choice set based search algorithm to find solution for n-queens. This works by enumerating all possible choices for each queen and storing them as list of lists. Search routine can then try them out, one by one, until a valid choice is found and consideration for the next queen starts. Since we’re using Tiny Rule Engine, which expects assertions, the following code generates all those we need for us:

(defn build-choice-sets [n]
  "build choice sets for queens"
  (list-comp
   (list-comp `(queen ~queen is placed on row ~row) [row (range n)])
   [queen (range n)]))

Actual search is based on stack (available to use with use of push-tre and pop-tre). Given a tre and choice-sets algorithm checks that tre are no conflicts on the board and then starts processing choices of the first queen. Each choice is tried in turn, to see if it would cause a conflict. This is done with try-in-context that lets us to see what would happen if a given assertion was made. As soon as valid choice is found, the current status of tre is pushed into stack with push-tre and solve is called with rest of the queens in order to start placing the next queen. If there aren’t any queens left at this point, we have found a solution and can return.

If at any point we encounter a situation where none of the choices left for us work, a mistake has been made in placement of earlier queens. At this point there’s nothing else to do than to remove latest choice from stack and return False to the caller to indicate that they should try different choice of placement on the previous queen. Essentially, we’re doing a depth first search through choice sets in order to find a solution where rules in Tiny Rule Engine don’t detect any conflicts.

Sourcecode for solve is shown below.

(defn solve [tre choice-sets]
  "solve n queens problem"
  (setv solution False)
  (setv current-choices (copy (first choice-sets)))

  (while (and (not (fetch tre 'warning))
              (not solution)
              current-choices)
    (setv choice (.pop current-choices))
    (if (not (try-in-context tre choice
                             (fetch tre 'warning)))
      (do (push-tre tre "placing queen")
          (assert! tre choice)
          (run tre)
          (if (list (rest choice-sets))
            (if (solve tre (list (rest choice-sets)))
              (setv solution True)
              (pop-tre tre))
            (setv solution True)))))

  (when solution tre))

Final step is to ask tre to show all assertions containing symbol queen:

=> (show tre 'queen)
queen 0 is placed on row 7
queen 1 is placed on row 3
queen 2 is placed on row 0
queen 3 is placed on row 2
queen 4 is placed on row 5
queen 5 is placed on row 1
queen 6 is placed on row 6
queen 7 is placed on row 4

Which can be also turned into ascii-art:

+---+---+---+---+---+---+---+---+
|   |   | X |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | X |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | X |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   | X |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | X |
+---+---+---+---+---+---+---+---+
|   |   |   |   | X |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | X |   |
+---+---+---+---+---+---+---+---+
| X |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s