8-Queens Puzzle using Functional Programming

Following is the OCaml code I wrote yesterday to solve the 8-queen puzzle. I have presented a solution in Python in an earlier post for the same purpose. However, there's a key difference. This solution is purely functional programming. This means that we do a completely side-effect free computing here. Therefore, we don't have assignments, mutable types, and of course, no loops. Once I got the code in place, I re-implemented the whole thing using loops. For the benefit of those accustomed to a procedural way of programming (me included), I have included that code too here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

module EightQueen = struct let conflict a b diff = (a = b) || (abs (a - b) = diff) let emptyList = [];; let allValues = [ 0; 1; 2; 3; 4; 5; 6; 7 ];; let maxlength = List.length allValues;; let shuffle d = let nd = List.map (fun c -> (Random.bits (), c)) d in let sond = List.sort compare nd in List.map snd sond let rec checkConflict newList = let rec check i = let c = conflict (List.nth newList 0) (List.nth newList i) i in if c then false else if i = (List.length newList - 1) then true else check (i + 1) in if List.length newList < 2 then true else check 1 let rec solve pos = if checkConflict pos = false then emptyList else if List.length pos = maxlength then pos else let rec loop lst allowedValues = if allowedValues = emptyList then emptyList else let head = List.hd allowedValues and tail = List.tl allowedValues in let extendedList = head::pos in let answer = solve extendedList in if answer <> emptyList then answer else loop lst tail in loop pos (shuffle allValues) end;; let rec printList lst = match lst with [] -> () | e::l -> print_int e ; print_string " " ; printList l ;; let lst = EightQueen.solve EightQueen.emptyList in printList lst; print_string "\n";;

And here follows pretty much the same code using imperative style:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

let conflict a b diff = (a = b) || (abs (a - b) = diff) ;; let emptyList = [];; let allValues = [ 0; 1; 2; 3; 4; 5; 6; 7 ];; let maxlength = List.length allValues;; let rec print_list = function [] -> () | e::l -> print_int e ; print_string " " ; print_list l ;; let shuffle d = let nd = List.map (fun c -> (Random.bits (), c)) d in let sond = List.sort compare nd in List.map snd sond let rec checkConflict newList = let result = ref true in for i = 1 to ((List.length newList) - 1) do if !result = true then if conflict (List.nth newList 0) (List.nth newList i) i then result := false done; !result ;; let rec solve pos = if checkConflict pos = false then emptyList else if List.length pos = maxlength then pos else let result = ref emptyList in for i = 0 to ((List.length allValues) - 1) do if !result = emptyList then let value = (List.nth allValues i) in let extendedList = value::pos in let answer = solve extendedList in if answer <> emptyList then result := answer done; !result ;; let lst = solve emptyList in print_list lst; print_string "\n";;

An Automated Sudoku Generator

In a recent post, I presented an automated sudoku player. Given a sudoku puzzle, this little program gives you its solution in a matter of seconds (mostly fractions of a second).

Here's an addition to it: An automated Sudoku Generator.

In the earlier one, I had gone into gory details of the algorithm because the beauty lay in the depth first branch and bound design of the algorithm. Here, I don't go into any details, simply because there aren't any! And that's the beauty of the whole thing. It's ridiculously simple.

And it succeeds to completely build on the sudoku solver. Well, almost. I have modified the sudoku solver just slightly to make it randomised. That means that for the same input, two separate runs may (and most probably will) give out two distinct solutions. This was necessary to prevent our sudoku generator from throwing the same puzzle at us every time. Now, every 9 by 9 sudoku puzzle that can be has an equal probability of getting generated by our program!

The trick is simple: Give sudoku solver a completely empty sudoku puzzle and let it come back with a valid solved puzzle. Now, just mask away some of the cells in this grid with blanks. That's your new sudoku puzzle!
Here's the code:

#!/usr/bin/python
from sudoku import *

def mask(sudoku):
 def generateRandomList(num, lst):
  index = random.randint(0, len(lst) - 1)
  result = [lst.pop(index)]
  if(num > 1):
   result.extend(generateRandomList(num - 1, lst))
  return result

 for rowNum in range(9):
  row = sudoku[rowNum]
  offset = random.randint(0, 1)
  maskIndices = generateRandomList(5 + offset, range(9))
  for i in maskIndices:
   row[i] = 0
 return sudoku

In the above almost trivial piece of code, probably the function generateRandomList is the only part which merits a second glance. This function takes a list lst and returns a sublist of num randomly chosen elements of it. Again, don't you agree that implementing it recursively has made it simpler to read?

All the outer mask function does is to call generateRandomList for each of its rows.

If you wish to test the above, here's the main function:

if __name__ == '__main__':
 sudoku = [[0] * 9] * 9
 print 'solution:'
 solution = solve(sudoku)
 printSudoku(solution)
 print 'masked:'
 printSudoku(mask(solution))

That's all!

Follows the downloadable file:
sudoku_maker.py

Download it at the same place where you have placed your sudoku.py. And make sure to make the sudoku_maker.py an executable:
chmod +x sudoku_maker.py

Or run it as follows:

python sudoku_maker.py

Acknowledgement:

Thanks Prahlad for asking me to write the above (or something of this sort).

An Automated Sudoku Player

I never played Sudoku. And now, it's even more unlikely that I will ever play it again.

I built a cute little program, all of it probably less than 40 lines, that will solve any damn Sudoku puzzle for me (I think), however hard, while I pay attention to my morning tea and other less brain wracking articles in the newspaper.

The program isn't a trivial piece though. Let me also confess that the algorithm isn't mine. I saw it first in a Python course I sat through which Dr. Vinay was teaching. After teasing the students in his characteristic style for a couple of hours, he popped out his implementation of it. A 16 line Python code!

The one I present here is pretty much the same algorithm, albeit implemented by a mortal. :)

The algorithm...hm. Well, it's a brute force one, in the same way as the solution to the eight queen puzzle that I presented here. However, it's OK. Sudoku puzzles don't grow larger than 9 by 9. So, a decent implementation comes back with a solution (if it exists) within a second or so on an average. One way to look at it is to treat the puzzle instance as an array of 81 numbers. And you could use that decision cleverly to crunch your program into an ever smaller number of lines). But I am somewhat old fashioned. I have no taste for anything size zero. I decided to represent it in a way similar to how it appears to the eyes: a 9 by 9 matrix. That added some flab to my program. But I like it that way!

Again, a small bit of notation will help understand the algorithm.

satisfy(x, Env) =
    if permitted(x, Env) = {} then []
    else
        if x = end then let val be any value from permitted(x, Env) in
             Env U Env[x] = val

        else
            if there exists val in permitted(x, Env) such that
                satisfy(x + 1, Env U Env[x] = val) != [] then
                    satisfy(x + 1, Env U Env[x] = val)

            else  []

I know, I know. It hasn't remained that simple, this notation. But the attempt underneath to present the same thing in plain English will show you why people (like me) unwillingly resort to mathematical notations (I would agree with you that people who are eager to resort to mathematical notations for no good reason should be sent to the firing squad).

satisfy is recursive. It returns a partially filled sudoku grid (on success) or an empty grid (on failure). For any cell in the grid, if the grid is the last cell in the grid, then, if the set of permitted values for this cell under the given sudoku grid is empty, then it returns an empty grid. Otherwise, it picks any value from that permitted list, sticks that into the cell of the sudoku grid and returns that. In case the cell isn't the last one in the grid, if satisfy receives back a non-empty grid from the subsequent call, it returns the same. Else if it has any untried permitted value left, it uses the same to call satisfy on the next grid cell. If it gets back an empty grid for all permitted values, it returns an empty grid itself, indicating failure in finding a satisfying assignment for the sudoku grid that was passed to it.

Makes sense? No? To me neither! Let me not therefore belabour the point that math is sometimes not to be avoided for your own benefit.

One more point. Important one. The above mathematical expression is also a fairly loaded (programmers use the term generic) specification of a depth first backtracking state space search algorithm. The above structure will pop up in various places if your programming assignments ever take you in the neighbourhood of trees (as in, the data-structures). For example, our eight-queen solver algorithm could also be written very much in the same manner. Only the bells and whistles would be different. More on this sometime later.

OK. Now take a look back at the expression. Let's try to understand it bit by bit.
satisfy(x, Env) =
Here, we are defining a function satisfy that takes two arguments: x, the grid cell that we are considering currently and Env, which stands for the environment. Environment is again a jazzy word for a set of bindings to things which could be bound. In our case, all the cells in our sudoku grid can be bound to certain values (in the range [1..9]). Env contains one such set of valuations. In it some of the cells have been bound to some values, while some other mayn't yet have been bound to any value. The '=' in the end is the wall between the RHS and LHS. Note that the expression above is actually an equation. So, it's supposed to have an LHS and an RHS separated by an '='. Just to make things further clear, if you have been a lot into programming with C-like languages, the '=' isn't an assignment; it's an equality. Note that the function above is a declarative statement, not an imperative one. Therefore, you don't assign anything to anything; you just declare the condition of equality.

if permitted(x, Env) = {} then []

The above means that the set of permitted values for the cell x with the given (partially filled) sudoku grid is empty (i.e. we have no permitted values), then satisfy evaluates to an empty list. This means that with the given inputs this call to the satisfy has failed to come up with satisfying valuations to the empty cells of the sudoku grid.

But what is a permitted set? The universal set of numbers that can go into a cell is [1..9]. A cell can't have the numbers in this set which have already been taken by the cells with which it conflicts. And which are the cells with which a cell conflicts? The cells in the same row, and those in the same column and those in the same subgrid or region.

conflict(x, y) =
    row(x) = row(y) or column(x) = column(y) or region(x) = region(y)

unpermitted = set of values in all y such that conflict(x, y)
permitted = [1..9] \ unpermitted

One more question. How to determine the region of a cell? Here's how:
region(x) = (row(x) / 3, column(x) / 3)

That is, it's a pair obtained by dividing both the row and column of x by 3. And remember, this is an integer divide. So, the value computed as the quotient is also an integer, which is the floor of the actual quotient (possibly a rational number). I leave it up to you to convince yourself that this will give you the region indeed.

Phew! So much for a couple of lines! Are we going to have read a whole book to understand the complete expression? No. I think, we have dealt with most of the complicated stuff by now. Hereon, things ought to be straightforward.

    else
        if x = end then let val be any value from permitted(x, Env) in
             Env U Env[x] = val


So, we have dealt with the case when there are no permitted values. That corresponds to a failure, and the expression evaluates to an empty set {}. Now, if there are some permitted values, i.e. permitted is not {}, then we check if we are dealing with the last cell in the grid (x = end). If yes, then we have found a solution, and we return the grid as we received it. Else, we continue our journey to the next element in the grid:

        else
            if there exists val in permitted(x, Env) such that
                satisfy(x + 1, Env U Env[x] = val) != [] then
                    satisfy(x + 1, Env U Env[x] = val)

            else  []

which says that for a given value val in the permitted set, we must get a non-empty set from the call to satisfy on the next cell. If we get an empty set, this val is dud and we have to consider another one. If we aren't left with any before having found success in satisfying the next cell, the val being considered in the previous cell is a dud, and we need to tell it to the caller of this satisfy. How? Of course, by returning an empty set.

Also note that in computing the permitted set, we do another clever thing. If it turns out to be an empty set, we have no reason left to proceed further in the same direction, and we backtrack. This saves us from exploring potentially large portions of the state space where searching for a solution would be futile. This clever trick is called pruning. And the family of algorithms which use this technique are called branch and bound algorithms.

Understood? No! Well, I can't make any easier than this. Blame it on my bad writing skills. But as of now, if you haven't yet made it through the above explanation, and you are still keen to, the only way I can think of is to go through it again. Stare at it for a while. And you'll soon see light. It's not very difficult, I can tell you that!

And if understanding the above isn't your cup of tea, well, all is not lost. Here, below, I give out the whole code.

#!/usr/bin/python
def conflict((r1, c1), (r2, c2)):
 if(r1 == r2):         return True
 if(c1 == c2):         return True
 if(r1 / 3 == r2 / 3 and c1 / 3 == c2 / 3 and (not (r1 == r2 and c1 == c2))): return True
 return False

def setminus(lst1, lst2):
 return [x for x in lst1 if x not in lst2]

def nextcell((i, j)):
 if(j == 8):
  if(i == 8): return (0, 0)
  return (i + 1, 0)
 return (i, j + 1)

def solve(input):
 empty = [[0] * 9] * 9
 def satisfy(pos, sudoku):
  def getAllowedValues():
   conflicts = set([ (r, c) for r in range(9) for c in range(9) if((r, c) != pos and conflict(pos, (r, c)))])
   notallowed = set([sudoku[r][c] for (r, c) in conflicts if sudoku[r][c] != 0])
   return setminus(range(1, 10), notallowed)
  if(sudoku[pos[0]][pos[1]] != 0):
   if(pos != (8, 8)): return satisfy(nextcell(pos), sudoku)
   else:   return sudoku

  values = getAllowedValues()
  new = [r[:] for r in sudoku]
  for value in values:
   new[pos[0]][pos[1]] = value
   filled = satisfy(nextcell(pos), new)
   if(filled != empty): return filled
  return empty
 return satisfy((1, 0), input)

def printSudoku(sudoku):
 print '-------------------------'
 for i in range(9):
  for j in range(9):
   if(j == 8): print sudoku[i][j]
   elif(j%3 == 2): print str(sudoku[i][j]) + '|',
   else:  print str(sudoku[i][j]) + ' ',
  if(i%3 == 2):
   print '-------------------------'
 print

The downloadable algorithm is here:
sudoku.py

The driver is here:
sudoku driver

An couple of examples:
example input 1
example input 2

Just store the above files someplace (the same place) in your machine and run as follows:
sudoku_driver input_file

A Really Open Research Publication Process

Follows a fabricated discussion upon an idea of an alternative research publication system that could bring about several positive changes with respect to how it is done currently:

• It could drastically reduce the delay between a research and its reporting.
• It could significantly bring down the barrier to publication of research in the name of quality which is a very subjective and qualitative parameter as it is measured today.
• It will open up the possibility of significantly increasing the activity in authoring, reading, reviewing and ranking research work.

The below writeup as an approximate transcript of how I was trying to work out the idea in my own mind. So, another side intention of this is to present a new way of reporting research, in the form of dialogues, which doesn't merely presents an idea after it has already taken shape, but also hints towards how it evolved in the head of the researcher.

 

The Present System

How is research publication done today?

A researcher writes an article for a specific conference or a journal. The article is reviewed by a group of programme committee members, mostly anonymous, who give their votes, along with review comments, on whether the article should be considered for presentation and publication in conference proceedings (or journal). Depending on that, the fate of the article is decided.

What happens if the article gets published?

A research article getting published is a matter of prestige for a researcher. It is a documented proof of the fact that the researcher has made a contribution to the existing body of knowledge that human race has.

What happens if the article doesn't get published?

It's a matter of disappointment for the researcher. But it's not the end of the world. The article rejected from a conference or journal can be improved and resubmitted elsewhere for publication. The comments provided by the peer reviewers are supposed to provide valuable constructive inputs to the researcher to improve his paper.

What are the advantages of this method?

Many. As mentioned above, the very event of publication is a matter of prestige. The fact can be cited in the researcher's resume to assert the point that he has made contributions in the field of knowledge.

Is that all?

Of course not! Publication in a well-recognised journal or conference (together let's call the 'forum') brings it to the view of the entire world. The invention or discovery of the idea thus gets timestamped, and the inventor's (discoverer's) claim to it is also permanently etched in the human history. So, no one else would be able to come up later to stake claim on the same idea.

Then what happens?

So other researchers can't claim the work to be theirs anymore. But the reported work is read by other researchers and gives them more ideas. They can build upon your work to further the knowledge in that field.

You mentioned the word 'well-recognised' somewhere. What's that?

There are a large number of fora. Some are more famous -- well recognised -- than the others. That's because they have established a track record of having published research articles of high quality over time. Consequently, users of research ideas (for example, researchers and industries) are likely to refer to these fora more than others when they are looking for scholarly work useful for their purpose. Since the work published in these fora get seen by a large and/or high quality audience, researcher throng at their doorsteps to get their work published there. Competition rises. So does quality. The whole thing turns into a virtuous cycle. On the other hand, those fora who have chosen to let crappy stuff pass through their filters often lose credibility and audience. Eventually this helps weeding out waste stuff.

Disadvantages of the Present System

All this sounds so rosy! Then why are we here talking about an alternative model?

That'll be clear if allow to also talk about the negative aspects of the existing publishing model.

By all means, feel free.

OK. One negative thing is the delay between the inception of an idea and its publication. It could be anything between a few months to eternity. But almost never less than a few months.

Anything else?

Yes. And it may be a bit controversial. But all my fellows in research community must have seen this happening. These fora -- conferences and journals -- for obvious reasons tend to get more and more specialised as time passes. Usually papers are written on topics which are very niche. Mostly inaccessible to a large majority of scholars in the world. Often, even though there are millions of scholars in the world, there are almost equally numerous fields of study. Thus, it often happens that some subjects have just a handful of authorities in the entire world.

What's the consequence?

The consequence is that every time you submit a paper, it ends up with one of those handful. Even researchers are humans. And humans have their own biases, favourites, eyesores, rivals.

Are you pointing towards unethical conduct?

Not necessarily. But communities develop their own lingo. And the authority figures of any field often start defining what's acceptable as a valid contribution to that area, how it ought to be presented etc.

What's wrong with that system?

In spirit, nothing. But, I think, much goes missing in the way things get implemented. There's a continuous tussle between the need to evaluate new work through a meticulous formation of credibility structures. The process has become so complex now it's not anymore possible to say if it's working.

Which means you can't even say if it's not working. Then why crib?

If you look at the output values, you will realise that I don't need to defend myself. There's severe inefficiency. If you count the number of good papers that get published, and the number of good stuff that gets done and thought, you won't find much coincidence. More and more number of students enter the profession of research with their eyes fixed on getting high impact publication. The whole thing eventually is no different from our current examination oriented education system. The trick boils down to cracking the system and fairing well in it. The way current research publication process fails in identifying good research is the same as the one in which current education system fails in identifying and nurturing intellectual talent in the society. And going by that comparison, the job this process must be doing in bringing out good research to the world for their fruitful consumption can't be very good!

That's a very roundabout argument.

Well, to tell you the truth, I am drawing from a bunch of my own personal experiences. In my own circles, I have seen a large number of good researchers competing and failing in this process of publication. They end up dejected and depressed. On the other hand, I have seen many people who aren't necessarily all that good as researchers, but have somehow conquered a way of thinking and presenting, which keeps a steady flow of publications coming in. I know, nobody means any harm in all this. But, nevertheless, the process ends up being very unfair and ineffective. Just like our education system.

I still don't see anything unfair. Is there anything wrong happening over here?

There are many researchers who start out very naive. Which is fine. They should pick up ways of working, learning, discovering, inventing and sharing their work as they go. Instead, the pressure of getting their work published puts a similar pressure on their minds which the fear of exams does on many. Often the fear is crippling for a large number of researchers. They aren't necessarily worse researchers. But they fear the prospect of being evaluated and written off. They fear the threat of not being allowed to belong to the community. May be, they have a weakness. But the weakness isn't scientific. It's psychological. The problem should be addressed instead of being dismissed as an inevitability, simply because the talent it is causing the society to lose out upon is sizable.

The Proposed System

OK. Enough of picking faults. How do you think, all this should work?

I feel, there are two things which get mixed up in the given model of research publication. One is reporting your work. And the other is earning credibility for your work. Inability to earn credibility shouldn't deter you from reporting your work. The basic idea of our alternative model of reporting research tries to decouple these two things. We say, reporting must happen immediately at any rate. And the moment you do it, you are in. All threats of ever being disowned, ignored and persecuted by the community are annihilated. Now comes the other part: of earning credibility, of doing something influential. Well, that's important too. But let that happen subsequently. In fact, ideally, you don't need to earn any credibility. It should come to you for your good work. Without your having to work separately for it. You focus on doing good work. Report it as soon as you have it ready to report. And let accolades flow in by themselves.

But how, unless you publish it somewhere where people are looking for good work?

Here's where I feel technology today is ripe enough to play a part. Google takes a bunch of keywords and pulls out anything you are looking for from the Web. I am sure that Google, or whatever engine that runs underneath, is capable enough to tell you what relates to your work. If you are writing an article, you anyway use Google to fish out related papers, don't you?

What's going to change?

Consider the scenario today. You work on something. You write it up in the form of a paper. And you go to these ACM, IEEE journals or all the other equivalent places for other fields. All this while, you are afraid that the hard-disc of your computer will be the grave of your paper if. That fear shapes your approach to the whole thing. You locate the influential people of your field. You adjust the tone of your paper to resemble the lingo these people have tacitly certified for that field. You take care not to say something that challenges their authority. Just novel enough so that it catches their attention. You have to be politically correct. In our so-called scientific world, you end caring too much about the politics of publication.

Now consider this other model. You just write it up. Put it up on the web for anyone willing to read. Now, it's in the interest of the ACMs and IEEEs to find your work out if it's good. And they have all the technologies to do that for them. They search the web. They do data mining. They do machine learning. They do whatever they want. But hell they must do a good job when someone asks them to feature a bunch of relevant articles on the web using some keywords. ACMs and IEEEs don't publish your work anymore. They just recommend.

They close their businesses, right?

I don't know. I don't think so. Recommending good stuff will be a big thing. And then there are ads and promotions. The whole business model will probably change. What will go is this big difference between publishing and not publishing which comes in the way of a researchers primary responsibility to the society: reporting his work.

Today, choosing the right forum to publish your work is a big thing. You get too ambitious, and you get rejections. You get too modest, and your work is tagged for oblivion forever. And each time either happens, you run a little run out of little bit more steam. Remember that in the current model, publication can happen only once. And publishing in a wrong place merely makes sure that your work will never probably be looked at with interest.

What should happen instead is that there ought to be only one publication platform: the Web. And the probability of a work being read by an interested audience shouldn't dwindle with time just because it's first weekend revenue didn't cross a mark. Research works are not feature films. They are potentially for the eternity.

So what's the difference? What happened earlier between publication and non-publication will now happen between credibility and non-credibility.

I agree. This model we propose is in no way a socialistic model swearing by equal wealth etc. And if research wants to be of any value, it must come with some way to measure its quality. However, understand that there's this huge artificially created chasm created by the current system of research publication: the chasm between publication and non-publication. You are either this way or that way. And the fear of falling into the chasm will keep a large number of people from even trying. On the other other hand, we propose to fill up this chasm. You do your best. And your rewards are somewhere in a continuous space depending on the quality of your work, your good luck, influence, whatever. But surely, there's no disgrace associated with trying and failing. There's only one failure in this model: that of not trying. Rest of it is all degree of success. And that, I agree, can vary as wildly as it does in the present day research world.

What gives you the confidence that what you are talking about is realistic and not a figment of your imagination?

I give you a few examples. Consider blogosphere. Today everyone blogs. There's immense crowding out there. But there are some blogs which are popular. And there are those which no one reads. Since there's Google to help us out, searching relevant online articles isn't such big headache, even if it may require some bit of work. Publishing a blog article is such a low entry barrier job: just a push of a button! But getting hits. Of course, that's a very different ball game. And people do play all sorts of silly games there. Links and backlinks. Guest posts. Ads. Promotions. It's again a you scratch me and I scratch you culture. But, you continue to publish, because there's no cost associated with it. And the only game that seems to really win is the game of quality. Put up good stuff, and you get hits.

Another example is of open source software. People write programs in thousands everyday. It's a breeze to upload your code. But not all of them are as popular as Linux or Eclipse or Apache. There's not such a big deal created out of whether you have contributed anything to the open community or not. But making a hugely popular piece of software is a big deal.

Yet another example is from one of the biggest computer scientists of our times: Edger Dijkstra. He wasn't a very keen publisher in the regular sense of the word. But he used to write profusely. And used to distribute his work among his peers. That was his way of reporting his work. All those notes which Dijkstra used to number as EWD #### are now archived in the University of Texas Austin website.

Now there's been only one Dijkstra in the history. And Dijkstra could afford to be unconventional. Doesn't mean everyone can.

I understand. I am not talking about what we can currently afford, but what's the best way to do things. The collection has all sorts of things: papers, letters, little rough notes, rebuttals... Dijktra never distinguished between them, I suppose. But the readers do, I am sure. I would bet my head on that some of the EWDs receive more hits than some others. The distinction is left to the reader, not on a broker. The need of brokers and agents is gradually becoming obsolete even in real estate. We have the Web and automatic recommender systems to do that job for us.

Wrap Up

OK. Can we have a quick summary of this new system of research publication?

Well. I will just sketch it out. You have an idea you wish to share. Well, write it up and put it out on the web. The information retrieval engines on the Web get down to work immediately. They fetch out links on other published stuff that may have a bearing on your work. It's your wish to notice or ignore them. However, it's in your benefit to notice those recommendations. The more you analyse, the better you will be able to place your work in a continuously evolving semantic web of related research.

People turn up at your page. They read it if they want. They rate it if they want. They provide comments if they want. The recommender system again comes to your rescue in sorting these feedback comments in terms of their relevance, importance, quality and potential impact. You work on the feedback comments and update your work to your heart's content. That way, a research paper isn't something done away with. It's an ever evolving working document. Hopefully you acknowledge the contribution of any review comment in any improvement that you are able to incorporate due to them.

Someone in ACM or IEEE may want to feed all this activity happening in the semantic neighbourhood of your article to compute some sort of an impact factor for it. Going forward, someone may decide to feature your article highly based on this impact factor.

Got it. And what, in very brief, would we gain from this change?

More research will get reported. No thoughts goes wasted. No work goes unreported.

The latency between a work and publication will almost disappear. 

More reviews will happen.

The ratings of a scholarly work will depend on automated algorithms, not on the private judgement of a select few.

A research missing an initial wave of popularity will not be doomed to an eternity of oblivion. It may spring back to popularity ages after it was reported if someone gets interested, because searching will be done by machines. And machines don't forget as easily as we humans do.

Just like bloggers, researchers will realise that the only surefire way to popularity is quality. They will direct their efforts into doing good work and writing well, not on knocking at the doors of brokers and agents.

There is plenty of work, good work, happening out there. It is not always backed up by timeliness, influence, alignment with `important' work, or some other technical reason. And it thus loses out. However, immediate publication makes sure it will probably be seen by an interested audience someday. At least the probability isn't ruled out. Our new model aims to give such work their much needed another chance.

Isn't that quite a handful? :)

Postscript

The above article is itself an example of how I think this new system of research publication should be implemented. I got an idea. I wrote it down in an informal tone. As of now, I stake claim only on this article, not on the idea. If I am fortunate, it may actually turn out to be a novel idea. But now, no one can steal it from me. But, if it happens to be a novel idea indeed, I put my faith on the ever-improving information retrieval technology to make sure that any other claim to coining the same idea will eventually be detected.

The above work is rather raw. I wanted to get it out the moment it occurs. I want to claim it to be my own, but I don't want to depend on keeping it secret for some period while I work on it with the fear that someone else may be faster than me in cashing it out. I believe that if someone else gets inspired by this idea and gets it into a shape before I can, it's perfectly OK. But I also promise that I will keep working on it as and when I have a way to improve it, either through my own ideas, or through those which my readers, or the search technology provide. In the latter case, I pledge to acknowledge the same.

If the above inspires you in any of your work, I invite you to cite it.

Showing the Lady Her Right Place

The eight queen puzzle is a well-known problem having been used in teaching algorithms design techniques and programming. The problem is simple: place 8 queens and place them on a chess board such that none of them is in the line of attack of any other. Does such a solution exist? Yes. 92 of them, apparently (keep reading).

In fact, finding a solution manually doesn't turn out to be too hard, but may be an interesting exercise if you are interested in that kind of puzzles. But our objective here is to find an algorithmic solution. That is, to write an algorithm that finds us the solution to the problem. Again, it's a solved problem. The algorithm is all there. Nothing new. But implementing it was a challenge nevertheless.

Let me try and summarise the approach as follows:

Firstly, a bit of staring at the problem will reveal that each queen must have her own row (column).

Consequently, a succinct representation of a solution would be a list of numbers corresponding to the column in which the queen is placed, the knowledge that they are placed in separate rows being implicit.

For example, to represent the following solution:

-----------------------------------------
|    |    |    |  X |    |    |    |    | 
-----------------------------------------
|    |    |    |    |    |  X |    |    | 
-----------------------------------------
|    |    |    |    |    |    |    |  X | 
-----------------------------------------
|    |    |  X |    |    |    |    |    | 
-----------------------------------------
|  X |    |    |    |    |    |    |    | 
-----------------------------------------
|    |    |    |    |    |    |  X |    | 
-----------------------------------------
|    |    |    |    |  X |    |    |    | 
-----------------------------------------
|    |  X |    |    |    |    |    |    | 
-----------------------------------------

 we just say:

[3, 5, 7, 2, 0, 6, 4, 1]

Now, for some bit of notations. Let's say we have come up with a positioning pos. We say, satisfy(pos, i), when the sublist of pos from i to 7 (denoted by pos[i:]) forms a satisfying solution, i.e. no pair of elements in pos[i:] attack, or conflict with, each other. The above very satisfactory condition can be described declaratively as follows:

for i < 7, satisfy(pos, i) <=> satisfy(pos, i + 1) and for all j in [i + 1...7], conflict(pos[i], pos[j]) = false

for i = 7, satisfy(pos, i)

which means satisfy(pos, i) is true if and only if satisfy(pos, i+1) is true and the ith element of pos (pos[i]) doesn't conflict with any of the subsequent elements. And the recursion bottoms up with i = 7, for which satisfy(pos, i) is true no matter what.

That's all the notation I can bear before I really dive into the algorithm, which is what I really want to present. But the above also pretty completes the conceptual groundwork for writing the algorithm, which is nearly a lexical replication of the above thought. And that should convince you why recursive thinking is such a good way of designing algorithms: because it allows you to write your algorithms as declaratively as possible. What may have appeared to be very complex a phenomenon if thought of as a procedure, becomes ridiculously simple if thought of as a condition to be satisfied.

#!/usr/bin/python
import random
from counter import *

def conflict(a, b, diff):
 return (a == b) or abs(a - b) == diff

def satisfy(lst):
 if(len(lst) == 1):
  return True
 if(satisfy(lst[1:])):
  for i in range(1, len(lst)):
   if(conflict(lst[0], lst[i], i)):
    return False
  return True

def solve(pos):
 inc = makeCounter_rec(8)
 while(not satisfy(pos)):
  pos = inc(pos)
 return pos

The function satisfy works recursively, calling itself as it goes down the board, one row at a time looking for smaller and smaller partial solutions.

Did you notice that this algorithm uses a base-8 counter to sweep through the search space of all solutions (which is 8 raised to 8)? And that should answer any doubt as to the practical application of the counter program that I presented here.

You want to see the above running? Just add the below main function to the above code.

if __name__ == '__main__':
 sol = solve([random.randint(0, 7)%8 for i in range(8) ])
 print sol

Want to see a pretty printed solution? Add the below function somewhere in the above code:

def printSolution(sol):
 hline = '-----------------------------------------'
 print hline
 for pos in sol:
  print '| ',
  for i in range(8):
   if(i != pos):
    print '  | ',
   else:
    print 'X | ',
  print
  print hline
 

...and add the following line in your main function shown above:

 printSolution(sol)

If you want to go ahead and find all the solutions, here's the function and the modified main function:

def solveAll():
 inc = makeCounter_rec(8)
 solutions = []
 pos = [0] * 8
 n = 0
 while(True):
  solution = solve(pos)
  if(solution in solutions):
   break
  else:
   print solution
   solutions.append(solution)
   pos = inc(solution)
   n = n + 1
 print 'found ' + str(n) + ' solutions.'
 return solutions

If you print out the output of this function, after running for a couple of minutes, it will show you all the solutions of the problem. As mentioned above, they turn out to be 92 in number.

Counter in Python

Presenting here two implementations of a counter.

What does the counter do?

Given a base n, this counter will allow you to do base n counting. What's base-n counting? There are n digits: 0, 1, 2, ..., n - 1. At each place, the digit changes from i to i + 1 if i < n - 1, and to 0 if i = n - 1. This change happens when the change at that place is triggered. And when does the trigger happen. For the unit's place, the trigger happens whenever the function is called. For all other places, the trigger happens when the previous place's digit rolls over from n - 1 to 0. That's all. That's a bit technical description for the simple act of counting we learn in our KG. But if we want to implement the counter, it needs to be written in this algorithmic language.

A 3-bit binary (base-2) counter goes like:

000, 001, 010, 011, 100, 101, 110, 111, 000, ...

A 2-digit base-4 counter would count as:

00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 00, ...

What do we usually do in day-to-day counting? decimal (base-10) counting.

How do we Use the Counter Program?

Below is a piece of code that could be used to implement a binary counter on a 3-bit number.

base = 2
inc = makeCounter_iter(base)
n = [0, 0, 0]
print n
for i in range(base ** len(n)):
    n = inc(n)
    print n

 The inc(n) gives n + 1 in the base n number system which is pre-decided while instantiating the counter:

base = 2

#!/usr/bin/python
def makeCounter_iter(base):
    def isZero(lst): return lst == [0] * len(lst)

    def inc(num):
        if(len(num) > 1):
            rem = inc(num[:-1])
            if(isZero(rem)):
                if(num[-1] == base - 1):    rem.extend([0]) 
                else:                rem.extend([num[-1] + 1])
            else:    rem.extend([num[-1]])
            return rem
        else:
            new = [0]
            if(not num[0] == base - 1):    new[0] = num[0] + 1
            return new
    return inc

Now follows the recursive version.

#!/usr/bin/python
def makeCounter_rec(base):
    def incDigit(num, pos):
        new = num[:]
        if(num[pos] == base - 1):
            new[pos] = 0
            if(pos < len(num) - 1):    return incDigit(new, pos + 1)
        else:
            new[pos] = new[pos] + 1
        return new

    def inc(num): return incDigit(num, 0)
    return inc

Any day, the recursive implementation trumps over the iterative version. The recursive implementation is smaller and more readable because it's very like the way the process of counting is formally defined in the beginning of the article.

Functional Programming Flavour

One thing to notice is that we use functional language aspect of python. The function makeCounter (makeCounter_iter and makeCounter_rec) is a higher order function that returns another function inc, the increment function. Also, the value of base is fixed in the creation context of inc inside the makeCounter function. The inc function uses the value of base at a place in the code which is typically outside the lexical scope where base is defined. This is known as the closure feature of functional programming. In a typical object-oriented scenario, this effect is achieved using the builder design pattern.