Solving Sudoku by depth first search

I am trying to remind myself of a little C++ and have decided the ideal project to do so would be to write a little solver for Sudoku. My aim is, given a board,  to find all valid solutions. A solution is valid if each number is present exactly once on each line and row and in each quadrant. There are two ideas that I use: updating the constraints and performing a depth first search.

Updating the constraints

Given a particular assigned position on the board, no other position on the same row or in the same quadrant is allowed to have that value. I therefore store in an array of 9bits the allowed values for each position. For example, if a particular position is allowed to be in any position its state would be “111111111″. If, however it is allowed to only have a value of ’1′ or a value of ’3′ its’ state would be: “000000101″.

There are two particular important states. If a position is not allowed to take any value, then its state will be 0. This means that the board configuration I am considering is not valid. If on the other hand the state has a single true bit, then the position is in a definite state and I can assign that position.  So the pseudo code for updating the constraints is:

1. UpdateConstraints(AssignedPositions):
2. for aPos in AssignedPositions:
3.       if aPos has not yet been assigned:
4.            assign aPos
5.            for neigh in (list of neighbour of aPos):
6.                 unset aPos as possible state of neigh
7.                 if neigh has no possible states left: return -1
8.            for Pos in AllPositions:
9.                  if Pos has a single state left: GOTO 1
10. return 0

Depth first search

The approach above is not sufficient, as given the initially assigned cells, it is possible for certain positions to still not have a determined state even after updating the constraints. In order to try out all possible states, I perform a depth first search, by creating all board states  that differ from the original one by having a single cell occupied and performing the algorithm above.

Testing

I first tested on a simple news paper problem.

Starting problem:

_____________
|304|610|005|
|708|000|306|
|000|903|400|
_____________
|807|000|510|
|020|705|040|
|600|091|002|
_____________
|480|352|007|
|000|000|900|
|106|009|280|
_____________

After a single guess I can find the solution to  be:

_____________
|394|617|825|
|718|524|396|
|562|983|471|
_____________
|837|246|519|
|921|735|648|
|645|891|732|
_____________
|489|352|167|
|273|168|954|
|156|479|283|
_____________

I then tried a 17 given problem from  Wolfram Alpha.

_____________
|030|000|900|
|006|000|000|
|000|241|030|
_____________
|000|900|700|
|000|002|004|
|080|070|020|
_____________
|850|000|000|
|090|704|000|
|000|006|001|
_____________

this problem is clearly much much harder. The problem still is solved in a fraction of a second, having tried just 88 guesses with solution:

_____________
|532|768|941|
|416|395|872|
|978|241|635|
_____________
|325|984|716|
|769|512|384|
|184|673|529|
_____________
|853|129|467|
|691|437|258|
|247|856|193|
_____________

unfortunately I seem to have also spat out another valid solution:

_____________
|532|768|941|
|416|593|872|
|978|241|635|
_____________
|325|984|716|
|769|312|584|
|184|675|329|
_____________
|853|129|467|
|691|437|258|
|247|856|193|
_____________

It turns out that a “mathematician’s” Sudoku is different from a regular Jo one. The maths ones are allowed to differ by certain symmetry operations that I do not understand. Still main objective – to brush up on my C++ is achieved! Here is the source code – if you like  you can inspect my code here

Are you more likely to give birth on a full moon? Revised

In my previous post Ratbag and Roland pointed out that there seems to be a slight increase in probability in the birth rate for the week after a full moon and they suggested I carry out a significance test. I returned to the original data and found that the assumption that birth is equally likely on all days is in  significant disagreement with the data: could it be that the moon actually has an effect on the probability of birth? Luckily, if I correct my assumptions by noting that births are less likely on weekends, the influence of the full moon disappears again. So you are not more likely to give birth on a full moon, but you are more likely to give birth during the week.

In order to make a significance test it is necessary to have  a model of the underlying probability. In this case, we need to make some assumption about the probability of being born at a certain number of days distance from the nearest full moon. The most naive assumption is that babies are born with equal probability on each day of the year. In 1969 there were 13 full moons. Of the 12 intervals between each full moon, 6 were 29 days long and 6 were 30 days  long. Thus, assuming each day of the year is equally probable for birth, we can compute that the  probability of a baby being born between -14 and +14 days from a full moon is 0.03391 (to 4 s.f.) and  that  the probability of a baby being born 15 days from a full moon is 0.01667 (to 4 s.f.). The variance of a binomial distribution is , where p is the probability of an even and n is the number of events considered. Since about 1.8 million births is the sample size used, this leads to a standard deviation . Since any deviations from the probabilities of more than would be significant, the increase in probability in the ten days after full moons seems significant.

This result surprised me: are women’s wombs really in tune to the music of the spheres? To make my mind up, I decided to look at the distribution of births as a function of day of the year, which is shown in the graph below.

Every 7 days there seems to be an event which leads to a significant reduction in births. This event happens on Saturdays and Sundays.  I am not sure why, but I reckon that doctors and nurses being on holidays might have something to do with it .

A better model for the probability of being born a certain number of days away from the full moon, must take this variation into account. If I do this, I obtain the curve shown in green in the graph below.

The error bars on the green and red line show the 99.7% confidence interval (3 ) . Notice that they match the data very closely indeed.

So the bottom line is that you are certainly more likely to give birth during the week, but the moon has nothing to do with it.

Are you more likely to give birth on a full moon?

I have been attending ante-natal classes recently and, although I greatly appreciated our teacher, I found myself skeptical about some of her claims.  For example, our instructor was adamant that it is more likely to give birth during a full moon than on other days. She even told us that maternity wards are over-run during full moon nights!

In order to investigate this claim, I decided to look at some birth records. The centre for disease control in the US keeps very thorough records of births. These can be freely downloaded from: http://www.cdc.gov/nchs/data_access/Vitalstatsonline.htm . It is also possible to download the date for full moons from this website .

Having obtained data for dates of birth and dates of full moon, I  wrote a program to extract the probability of giving birth as a function of phase in the moon. The following graph shows the results for births in the US in 1969.

The x axis shows the number of days between the birth and the full moon and the y axis shows the probability of birth. If there was a correlation between full moon and likelihood of giving birth, there should be a peak in the distribution about x=0. However, clearly, the distribution is flat. Therefore there is no correlation between these two quantities. I guess it is still possible that only british women feel the influence of the moon. I somehow doubt that!

Here is the code I used to analyse the data:

import bisect
#birth data from CDC: http://www.cdc.gov/nchs/data_access/Vitalstatsonline.htm
#Phases of the moon from http://moonphases.info/past_full_moon_dates_calendar.html#1970

codeToYear={'9':1969, '0':1970, '1':1971}


FullMoon1969 = [ [03,01,1969], [02,02,1969], [04,03,1969], [02,04,1969], [02,05,1969], [31,05,1969], [29,06,1969], \
[29,07,1969], [27, 8,1969], [25, 9,1969], [25,10,1969], [23,11,1969], [23,12,1969] ]

#here i build the cumulative number of days from the beginning of a year to a certain month, in order to convert a date
#into an integer describing the # of the day of the year
length_of_month = [ 31, 28, 31, 30, 31,30,31,31,30,31, 30,31]
cum_day_by_month = dict()
cum = 0;
for i in range(1, 13):
cum_day_by_month[i] = cum
cum += length_of_month[i-1]

def get_birth_day(s):
year = codeToYear[s[0]]
month = int(s[83:85])
day   = int(s[85:87])
return [ day, month, year]

def hash_date(date):
[d,m,y] = date
# when the day is not recored, the field is entered with a 99
if d != 99 :
return cum_day_by_month[m] + d
else :
return - 1

def get_hash_birth_day(s):
return hash_date(get_birth_day(s))

# this list contains the day of the year when a full moon occured
full_moon_hashed = map(lambda x : hash_date(x) , FullMoon1969)

def d_from_full_moon(h):
# bisect_left ensures that h <= full_moon[i]
i = bisect.bisect_left(full_moon_hashed, h)
if i != len(full_moon_hashed) :
d1 = h-full_moon_hashed[i]
d2 = h-full_moon_hashed[i-1]
if abs(d1) < abs(d2) :
return d1
else:
return d2
else:
return h-full_moon_hashed[i-1]


distribution_full_moon_d = list()
for i in range(36):
distribution_full_moon_d.append(0)

f = open("NATL1969.PUB", 'r')
count = 0
for line in f:
hd = get_hash_birth_day(line)
#ignore the births where the date is non-reported
if hd != -1 :
d = d_from_full_moon(hd)
distribution_full_moon_d[d+18] += 1
count += 1

print "#number of records counted: " , count
print "#days from/to full moon, probability"
for d in range(36):
print d-18, float(distribution_full_moon_d[d])/count

Which way round do the pedals go?

Since my last post was cycle related, I thought I would share the most fiendish problem regarding bikes that I have come across so far, courtesy of one my colleagues from Southampton (GR!).  It has resurfaced with a colleague at Imperial (PB) and I fear I may in the spur of the moment given the wrong solution. Here is my attempt to right my wrongs.

Imagine you have a bike with its pedals in the vertical position. The bike is assumed to be magically balancing and not falling sidewise, whilst still being free to move backwards and forwards. You grab the bottom pedal and push it backwards. Will the bike move forwards or backwards?

Consider the diagram below:

The two important points on this diagram are: 1), the bottom of the rear wheel and 2) the bottom pedal.What the problem boils down to is the position of the bike as a function of the position of 2.  The other quantities shown on the diagram are the angles φ and θ describing the positions of 1 and 2 relative to the bike itself, the radius of the back wheel ‘r’ and the length of the pedal cranks ‘k’.

Assuming that the bike travels in a straight line, the centre of the cranks (the bottom bracket) is at a point with coordinates (d,0), where d is the distance that the bike has travelled. I will define d such that it is positive if the bike is moving forward and that it has a value of 0 when the pedal and the bottom of the wheel are in the positions shown in the diagram. It is very straightforward to relate d to the angle φ:

,

this is simply because the wheel is not allowed to slip, therefore for each inch that the bike moves forward the wheel must rotate anti-clockwise. Notice that φ is implicitly defined to be positive when the wheel is rotating anti-clockwise.

Next we want to relate φ to θ. In order to do this, we need to know the gearing g of the bike. I define this as the number of turns the wheel makes for every turn the pedals make. So a high gearing is the one you use when speeding downhill and a low gearing when struggling to get up a steep mountain.  With this definition in mind, it is clear that the two angles can be related by:

Now we know φ, all that is left to do is to write down the position of the pedal in cartesian coordinates. Since the position of the centre of the cranks is (d,0) and since the pedals are turning in a circle of radius k and defining φ as 0 when in the position shown in the diagram above we conclude that the position of the cranks can be written as:

we can use our other formulae to eliminate d for φ:

When we push the pedal backwards, we are making the x position of the pedal small and negative. The question boils down to whether this corresponds to φ being positive or negative. It is evident from the formula above that the answer must be “it depends” on the values of g,r and k. Let’s do a little bit more analysis to show exactly how. If the x position is small, then we can assume that φ is also small and that the sin can be approximated linearly. If we then measure distance in units of k and divide the whole problem through by k we find:

where g’ has been defined as . So there are two cases. If g’ is greater than 1, then a negative x corresponds to a negative φ. This means that moving the pedal backwards corresponds to the cranks and the wheel rotating clockwise and hence to the bike moving backwards. On the other hand, if g’ is smaller than 1, then a negative x corresponds to a positive φ. In this case, moving the pedal backward makes the wheel turn anti-clockwise and hence the bike moves forward. Since most normal bikes have a gearing g greater than 1, and since it would be hard to design a bike with cranks longer than the radius of the wheel, g’ is almost always greater than 1 therefore for a normal bike, if you push the pedals back, the bike moves back!

Times cycle campaign

I invite you guys to subscribe to the Times’ cycle campaign to make British roads safer for cyclist.

Making a “hovering box” in Tkinter

I have found myself programming GUIs recently using python and Tkinter. I was particularly interested in the providing users with help by creating hover boxes that display a certain message when the mouse is hovering over a certain widget.

I would like to post the code I used to develop this, hopefully someone will find it useful!

from Tkinter import *
import re

class HoverInfo(Menu):
def __init__(self, parent, text, command=None):
   self._com = command
   Menu.__init__(self,parent, tearoff=0)
   if not isinstance(text, str):
      raise TypeError('Trying to initialise a Hover Menu with a non string type: ' + text.__class__.__name__)
   toktext=re.split('\n', text)
   for t in toktext:
      self.add_command(label = t)
   self._displayed=False
      self.master.bind("<Enter>",self.Display )
      self.master.bind("<Leave>",self.Remove )

def __del__(self):
   self.master.unbind("<Enter>")
   self.master.unbind("<Leave>")

def Display(self,event):
   if not self._displayed:
      self._displayed=True
      self.post(event.x_root, event.y_root)
   if self._com != None:
      self.master.unbind_all("<Return>")
      self.master.bind_all("<Return>", self.Click)

def Remove(self, event):
 if self._displayed:
   self._displayed=False
   self.unpost()
 if self._com != None:
   self.unbind_all("<Return>")

def Click(self, event):
   self._com()

 

I decided to use Menu widgets because of the post method that allows you to place the floating menu where you like, but I was also interested in allowing for having messages on multiple lines. This works, but is kind of hacky – I am interested in superior solutions!

I also include a simple App that uses this hover box:

from Tkinter import *
from HoverInfo import HoverInfo
class MyApp(Frame):
   def __init__(self, parent=None):
      Frame.__init__(self, parent)
      self.grid()
      self.lbl = Label(self, text='testing')
      self.lbl.grid()

      self.hover = HoverInfo(self, 'while hovering press return \n for an exciting msg', self.HelloWorld)

   def HelloWorld(self):
      print 'Hello World'

app = MyApp()
app.master.title('test')
app.mainloop()

 

 

 

 

 

Poor Mr Boole

Numerical integration is awfully useful. Most of us will remember the trapezoid rule that we learn at school, where the function we are integrating is substituted by a straight line and the integral as estimated as the are under the curve:

where h is the interval that we split the curve into and and are the values of the function on either side of the function.

One way to obtain better methods is to interpolate higher order polynomials, and the integrate those. It is possible to, for example, use three points and interpolate with a parabola, four points and interpolate with a cubic or five points and interpolate with a quartic. This latter method is often called Bode’s rule. But here comes the shocking news: it wasn’t Bode who came up with, but the English mathematician Boole. It became known as Bode’s rule because of a misprint in a maths textbook from the 70s. I guess the consolation prize is that Boole got a whole branch of logic named after him.

So does Boole’s rule make a better approximation than the just applying the trapezoidal rule? In this picture I will show sin(x) with x between 0 and fitted with 5 straight lines (green curve) and with the polynomial used in Boole’s rule (red curve):

 

 

 

 

 

 

 

The red (corresponding to Boole’s rule) is pretty much right on the sin curve. If we actually take the difference between the fits and the sine curve we obtain the error:

where blue is the error using trapezoidal rule and green sticking with Boole.

 

 

 

 

The moral of the story is that you can get the name wrong, so long as you get the Maths rights!