Reversing a Queue

There was a question in the discussion as to how to reverse a queue without a stack.

Reversing a queue using a stack is quite easy.

 private static void reverseWithStack(Queue<Integer> queue) {
    Stack<Integer> stack = new Stack<Integer>();

    while(queue.isEmpty() == false) {
      stack.push(queue.remove());
    }

    while(stack.isEmpty() == false) {
      queue.add(stack.pop());
    }
  }

How to do it without a stack. I think, there may be convoluted ways. But here's a simple way using recursion:

  private static void reverseWithoutStack(Queue<Integer> queue) {
    if(queue.isEmpty()) {
      return;
    }
    int n = queue.remove();
    reverseWithoutStack(queue);
    queue.add(n);
  }

Well, there's no magic happening here. Actually, we are cheating a bit here. How? We have simulated the behaviour of a stack through recursion. In fact, there's still a stack -- an actual stack -- in action which enables us to solve this problem. It's the program stack! Just that it's hidden.

Many algorithms which could be implemented using a loop and a stack could be rephrased into a simpler one with recursion, simply because recursion hides the stack within itself and allows us to reap its benefits all the same! A classical example is depth first search of trees, which can be implemented using a stack, but a simpler and elegant implementation can be created using recursion.

Here's the complete code:

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;

public class Reverse {

  public static void main(String[] args) {

    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(1);
    queue.add(2);
    queue.add(3);

    System.out.println("Before reversing ...");
    printQueue(queue);
    // reverseWithoutStack(queue);
    reverseWithoutStack(queue);
    System.out.println("After reversing ...");
    printQueue(queue);
  }

  private static void reverseWithStack(Queue<Integer> queue) {
    Stack<Integer> stack = new Stack<Integer>();

    while(queue.isEmpty() == false) {
      stack.push(queue.remove());
    }

    while(stack.isEmpty() == false) {
      queue.add(stack.pop());
    }
  }

  private static void reverseWithoutStack(Queue<Integer> queue) {
    if(queue.isEmpty()) {
      return;
    }
    int n = queue.remove();
    reverseWithoutStack(queue);
    queue.add(n);
  }

  private static void printQueue(Queue<Integer> queue) {
    String s = "[ ";
    for(int i = 0; i < queue.size(); i++) {
      int n = queue.remove();
      if(i <= queue.size() - 1) {
        s += n + ", ";
      }
      else {
        s += n + " ";
      }
      queue.add(n);
    }
    s += "]";
    System.out.println(s);
  }
}

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

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.