Sudoku

Remarkably the evolutionary algorithm I developed for Eight Queens problem worked without modification for sudoku problem. The only differences were array size (DNA) and the fitness function.

This is perhaps not so surprising considering how evolution creates vastly different species (solutions) for different environmental conditions (problems).

Here is the pseudo-code of Evolutionary Algorithm:

Here is a diagrammatic representation:

It is simple really. You have a pool of population which is made of many solutions. At each iteration select fit parents, recombine their genes and allow mutation to make 2 distinct children. Sort the population by fitness score. Let the worst 2 die, and continue iteration until the best fit is found.

In the Eight Queens problem, from the chess-board, the array size is 8x8 = 64, whereas in Sudoku it is 9x9 = 81.

The fitness function calculates a positive number which increases with the level of fitness.

Usually the worst fit solution is calculable. In the case of Sudoku this is one of the worst solutions:

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
 
This is not even a legal acceptable final solution is Sudoku. But any solution in evolutionary landscape is legally born. When an individual solution's fitness is calculated it may or may not survive the next run (generation).

A perfectly fit Sudoku solution is achieved when all 1-9 digits present in 3x3 matrices along with no-clashing digits present across rows or columns.

Therefore in Sudoku the unfitness score is a number calculated by counting number of times a given digit is repeated across a row or a column and also adding the missing set of digits in all 3x3 sub-matrices.

The resultant fitness score is normalised form of unfitness score, i.e. fitness score is calculated by subtracting the calculated unfitness score from the maximum unfitness score (378).

Two runs from a typical output are given below:

-----------------------------------------
Run: 1
Best score 378
Found best '1' in 3540 iterations.
[4, 1, 3, 9, 8, 6, 2, 5, 7]
[7, 2, 9, 5, 3, 4, 8, 1, 6]
[6, 5, 8, 2, 1, 7, 3, 9, 4]
[2, 3, 7, 4, 5, 8, 9, 6, 1]
[8, 6, 4, 1, 2, 9, 5, 7, 3]
[1, 9, 5, 6, 7, 3, 4, 2, 8]
[9, 4, 2, 8, 6, 1, 7, 3, 5]
[3, 8, 6, 7, 9, 5, 1, 4, 2]
[5, 7, 1, 3, 4, 2, 6, 8, 9]
-----------------------------------------
Run: 2
Best score 378
Found best '1' in 8636 iterations.
[2, 7, 5, 3, 9, 4, 8, 6, 1]
[8, 1, 3, 5, 2, 6, 7, 9, 4]
[9, 6, 4, 8, 1, 7, 2, 5, 3]
[4, 2, 6, 9, 8, 3, 1, 7, 5]
[1, 8, 7, 2, 4, 5, 9, 3, 6]
[3, 5, 9, 6, 7, 1, 4, 2, 8]
[5, 4, 1, 7, 3, 2, 6, 8, 9]
[6, 9, 2, 1, 5, 8, 3, 4, 7]
[7, 3, 8, 4, 6, 9, 5, 1, 2]
...

I still have to tune the program for better performance. I may try different mutation or recombination strategies, play with population sizes and selection strategies to shorten the time required to create a sudoku solution.

The prototype was written in Python. Eventually I would like to port the algorithm to IOS 7 for creating the sexiest sudoku app ever.

The Evolutionary Algorithm I used was from the book Introduction to Evolutionary Computing¹.

References:
1. Introduction to Evolutionary Computing, Agoston E. Eiben, J.E. Smith, Springer, 01/01/2003
2. Sudoku - Wikipedia
3. Eight Queens - Wikipedia

The nose job

A duel to resolve scientific arguments? Well those were the days my friend..

"While studying at the University of Rostock[12] in Germany, on 29 December 1566 Tycho Brahe, a Danish nobleman known for his accurate and comprehensive astronomical and planetary observations, lost part of his nose in a sword duel against fellow Danish nobleman (and his third cousin), Manderup Parsberg.Tycho had earlier quarrelled with Parsbjerg over the legitimacy of a mathematical formula, at a wedding dance at professor Lucas Bachmeister's house on the 10th, and again on the 27th. Since neither had the resources to prove the other wrong, they ended up resolving the issue with a duel. Though the two later reconciled, the duel two days later (in the dark) resulted in Tycho losing the bridge of his nose.

In his De nova stella (On the new star) of 1573, Tycho Brahe refuted the Aristotelian belief in an unchanging celestial realm. His precise measurements indicated that "new stars," (stellae novae, now known as supernovae) in particular that of 1572, lacked the parallax expected in sub-lunar phenomena, and were therefore not "atmospheric" tailless comets as previously believed, but were above the atmosphere and moon."

Resource: http://en.wikipedia.org/wiki/Tycho_Brahe

Friction

The Physicist Laurence Krauss said:

"Philosophers are threatened by science because “science progresses and philosophy doesn’t."

I imagine Philosophy is like an annoying five year old, constantly bombarding an adult (Science) with deceivingly simple but in essence deeper questions.

According to late Physicist Richard Feynman ‘doubt’ constitutes the central tenet of Science.

“Now, we scientists … take it for granted that it is perfectly consistent to be unsure — that it is possible to live and not know. But I don’t know whether everyone realizes that this is true. Our freedom to doubt was born of a struggle against authority in the early days of science. It was a very deep and strong struggle. Permit us to question — to doubt, that’s all — not to be sure. And I think it is important that we do not forget the importance of this struggle and thus perhaps lose what we have gained. Here lies a responsibility to society.”

Hence “doubt” it seems an area of agreement between Science and Philosophy.  Both use doubt as a key in their quest to understand the nature of reality.

Note Feynman also stated:

“We can't define anything precisely. If we attempt to, we get into that paralysis of thought that comes to philosophers… one saying to the other: "you don't know what you are talking about!". The second one says: "what do you mean by talking? What do you mean by you? What do you mean by know?"”

Indeed Science and Philosophy have conflict of interest, a point of friction. Science is most notably progressive. It marks whatever in its checklist, and after removing shadows of doubts moves on with new doubts. Whereas Philosophy it seems is stuck with questions and doubts with little intent to seek answers. One strongly favours seeking answers; the other one favours seeking questions.

Having said that progressive nature of science should not mean ‘anything goes’. It should not be “blind progression” regardless of moral questions or despite humanity. Scientists should have and do have moral responsibilities. 

I do think classical education and understanding Philosophy of Science are crucial tools for scientists to understand their role and responsibilities in the society, in answering questions like where they come from, how Science progressed, and what are moral and social challenges they are confronted with.

But I also think there may be a simpler reason for Krauss’ and others’ strong reaction against Philosophy, in essence it may indeed be a reaction against “Science Denialism”. They may be seeing Philosophy as a breeding ground for that. This would of course be a bold generalisation; nevertheless I believe has been a factor.

Time

Time is one of the most enigmatic terms one would have trouble describing. Take a breath and try describing it now. What is time?

Most simplistically time is simply a mathematical dimension describing change in the position of objects in space. It is not a physical quantity like matter but a virtual quantity.

But fundamentally time or more accurately the arrow of time points to a direction in which a quantity we call Entropy increases.

Entropy is disorder in the Universe and it is always on the rise. The order does not come back by itself; it is as if the arrow of time prevents it from happening.

There is also constant loss during the process of making order. Even if we spend energy to restore the order there will always be an amount of entropy we could not restore (conservation of energy).

This is a war we cannot win.

It is for Entropy dust disperses, disorder increases and decay starts to prevail in a room if we don’t clean it up regularly by adding more energy. Ultimately all living species borrow this energy from the Sun so that we could restore stuff and experience living.

The reason we have an illusion that there appears to be an eternal order in the Universe is because in our limited part of the Universe and in our pathetically short life span it appears so.

Life (plants and animals) constantly restores order by spending energy they borrow from the Sun. In our short-life span we avoid realisation of distant-past and far future that have no practical implications.

But in reality the fuel of Sun is not endless end it will die in about 5 billion years into the future. That would be the time when the debt of energy borrowed by all living species for the duration of life would be settled. Entropy will win or rather we would pay our debt by turning into dust.

In its ultimate twilight the increase in entropy will slow down, and the Universe will be in its heat-death. No heat to restore anything.

References:

The Temperature of History

Recommended background music: Blade Runner End Title.

Say NO to Indoctrination

Please don't indoctrinate me with religion. Teach me to think for myself.

I would like to draw your attention to the word indoctrinate. Indoctrination is filling a child’s mind with one-sided subjective opinions that do not rely on facts. I guess we may reach an agreement to qualify those opinions and where they originate from as non-factual, mystical, spiritual or supernatural. I don’t mean necessarily they are bad or evil please note.

Influencing someone with non-factual opinions may not always be harmful. If someone believes fairies that glow at night in their backyard, or they believe star signs, or they believe a soul, or a spirit to grant everlasting life these seem pretty harmless and we should tolerate them.

Also if someone takes only peaceful messages from a religion and ignores the evil parts such as disrespecting or killing others, then perhaps pains religions inflicted in human beings throughout history may be set aside; we then may consider such benign realisations as cultural nuances, embrace those individuals, say “good for you”, and move on.

But it is one thing that a child believes in Santa Claus, it is another thing if you teach them other religions are evil and he should one day blow himself up and kill as many as possible from the other side for reserving a good seat in heaven.

Or it is one thing to teach peaceful attributes of a religion and respect for others and it is another thing to inflict hostility in the heart of an innocent child by labelling all other religions as fake and their believers inferior.

Or it could be another thing to teach a child all religions and atheism in the context of ethics and objective history along with science and theory of evolution, and eventually let them decide whichever religion to believe or not to believe anything at all.

The issue here is not about legislating how parents should raise their kids but whether world nations should any longer endorse religious indoctrination through publicly or privately funded faith schools.

In Britain recently the UK Government passed a law to abolish public funding of faith schools. This is an important step if we want to build peaceful democratic societies.

This is also a clear message from a Western government on the dangers of sponsoring faiths schools, which often singlehandedly indoctrinate kids with hatred and cause painful segregation inside the larger civil society they breed within.

Hence this is in my opinion the way the message on the billboard should be read.

Children are pillars of our future. Can we afford to let them be raised in intolerance?

Put another way do we need to tolerate the intolerant?

Just as we don’t indoctrinate children with racism and holocaust denial we should not indoctrinate them with subjective one-sided religious thinking, fear mongering, bigotry and hatred for others.

It is wrong.

I think anyone with common sense, religious or non-religious alike, would see merits of these arguments.

The scope of survival

This news is from Canberra Times, dated 4 June 2011:

“Australian National University has confirmed it moved several high-profile climate scientists, economists and policy researchers into more secure buildings, following explicit threats to their personal safety….

More than 30 researchers across Australia ranging from ecologists and environmental policy experts to meteorologists and atmospheric physicists told The Canberra Times they are receiving a stream of abusive emails threatening violence, sexual assault, public smear campaigns and attacks on family members.”

As bitter truths about our approach to the tipping point in climate change are unveiled by scientists, and governments sluggishly but nevertheless close in to intervene, the carbon lobby is becoming more aggressive in their tactics.

Regardless of how bitter confrontations are going to be, there is no escaping from science. Science is telling us by as close as 2100 our planet will be warmed up by 2-4°C. 2°C rise is certain regardless of what we do now.

The consequences are dire. There are various scenarios depending on timing of intermittent tipping points such as effects of release of CO₂ from the vast permafrost of Siberia, driven by temperature rise in Arctic, which at nearly 4°C is three to for times than the average. For example, a 4°C rise would kill off 85% of the Amazon rainforest, a 2°C rise now seen as inevitable would kill of 20-40%. Sea levels can rise up to 70 meters.

These things will happen.

---

Our genes copy themselves. The quality of being copied by a Darwinian selection process is what drives life on Earth. Life has a sense of space and change. Sense of change led to emergence of concept of time in humans. Our gene setup endlessly reconfigures itself; generations who can better exploit the information gained by knowing space and time, survive best.

“If that vast fire over the far mountain range isn't likely to effect my tribe now, I should probably not worry, and go by my everyday business of hunting. Only if the fire seems to be closing in I should think about moving, but then this hunting ground and nearby water seem too good to give up so perhaps I should stay.”

There is always room for failure in judgement of space and time. The fire could be advancing much faster than our humanoid ancestor thinks. In that case his tribe will be engulfed in flames.

When our humanoid ancestors walked in savannas of Africa 2.3 - 2.4 million years ago, their genes’ scope of survival was limited to their immediate vicinity, perhaps within a diameter of tens of kilometers for each group.

Today our capacity to comprehend space and time is much widened. We now know what is going on in every part of the world. We started to make sense of what made us, we look at skies and our universe’s distant past. With science our capacity to accurately reflect on future and farther increased.

Despite these advancements our judgements about survival strategies are still largely affected by selfish interests.

Humanity now is divided roughly in two. Those who think “Well, it’s not going to happen in my lifetime, so I don’t care”, and those who worry about their grandchildren and their grandchildren’s future.

People in the first group think much like our ancestor watching the fire in distant mountain range. People in the second group are super humans who have the capacity to extend humanity’s survival beyond stars.

References:

Requiem For A Species - Clive Hamilton

Canberra Times - News

Ultimate bit

How many bits of digital storage capacity humanity has right now in hard disks?

"How many computers?" I asked Wolfram Alpha search engine.

The answer came back as:

Estimated number of personal computers worldwide:

over 1 billion

Then I had to make a bold part guess of average storage per computer. Big fat machines that belong to governments and fortune 100 companies will have substantial capacity per computer. But there must still be many old machines around with small capacity as well. I estimated that 64 GB per machine would be too conservative as it was the benchmark 4-5 years ago. I thought 100GB would be a good figure.

So the number of bits came out as:

1 billion X 100 GB = 100 EB (exabytes) = 8 X 10²⁰ bits

That is

800,000,000,000,000,000,000 bits

This number would be equal to eight times estimated information content of all human knowledge (10EB).

This means we have a growing memory surplus that we could meaningfully fill, also we still have no operational or economical capacity to store everything we know on hard disks.

I am not ignoring the fact that gene technology trends will require huge amount of storage to keep gigantic databases of gene sequences required by genetically modified food, bio-fuel research and so forth. But I still think it will lag behind available storage capacity as the global consumer market will always put huge pressure on reducing storage cost. Also the main problems in gene research seems to be indexing and CPU cycles rather than storage capacity.

So I estimate available storage will always be 10 times of human knowledge and at least 100 times of used storage.

Where is the most vulnerable of those useable bits that when flipped would cause the maximum catastrophic impact on humanity I wonder?

One nasty bit that its redundancy is incidentally non-existent.

Like all physical systems hard disks do fail. When hard disk fails software almost always fails.

On ageing nuclear missile sites?

On ageing GPS satellites?

One freak magnetic storm in space?

Where?

It would take just one bit to flip forever from 1 to 0 or from 0 to 1 out of 8,00,000,000,000,000,000,000.

I would like to buy a new notebook computer nowadays. I think I am going to pick a machine with a solid state drive (SSD).

Patchwork

Human body is full of evidence indicating it is not an elaborate form of design by a supernatural force but more of a jumbled patchwork shaped by evolution.

Vestiges are structures, anatomical configurations that has lost or nearly lost its primary function. If it has any current function, it is either a persisting secondary function, or a function gained sometime after the loss of primary one. This process is called exaptation or co-opting.

Examples of vestiges are plenty.

The middle ear bones of mammals are derived from former jaw-bones (Shubin 2007).

Early tetrapod limbs were modified from lobe-fins and probably functioned in pushing through aquatic vegetation; at some point, they became sufficiently modified to allow movement on to land (Shubin et al. 2006).

The vestigial hind limbs of boid snakes are now used in mating (Hall 2003).

But the most impressive of all, my personal favourite, is evolution of gonads –a gonad is an organ that produces gametes; a testis or ovary-.

The gonads of sharks, other fish, and even humans develop in same place, the chest. This works well for sharks, since they stay there, but in human males, as the embryo grows the gonads need to travel all the way down into the scrotum to keep cool. This causes an unnecessary looping of the spermatic cord, which causes a weakness in the body wall, leaving them prone to developing a hernia (Shubin, 2009). This is consistent with descend with modification from an ancestor we share with modern fish.

Click to enlarge

Evolution presents countless examples of co-opting. Whether you like it or not the theory of evolution is strongly supported by empirical evidence and scientific studies including DNA analysis that weren’t known in Darwin’s time.

There is mountain of strong evidence for evolution, and each day research laboratories around the world conduce more. At the same time the case for designer god is weakening.

The next question to ask is if it wasn’t design what is god for?

Resources:


Original Scientific American article by Neil H. Shubin (PDF):
http://www.mukto-mona.com/Special_Event_/Darwin_day/2009/english/SA_old_bodyShubin.pdf

Vestigial evidence:
http://www.evolutionarymodel.com/vestigialevidence.htm

Contact Opening Scene Under the Knife

I am reading "Selected Stories of H.G Wells", edited and with an introduction by Ursula K. Le Guin.

The protagonist in the short story "Under the Knife" undergoes a surgery. During the operation he sees himself as being elevated and detached from his body. He then leaves the room, rising up, watching London in bird's eye view, then rapidly flying up over the British Isles, Europe, and so on. He eventually leaves the Earth, crosses the solar system even briefly going through the rings of Saturn as brilliantly depicted by Wells:

":..and then I saw that a bright spot of light, that shone a little to one side of my path, was growing very rapidly larger, and perceived that it was the planet Saturn rushing towards me. Larger and larger it grew, swallowing up the heavens behind it, and hiding every moment a fresh multitude of stars. I perceived its flattened, whirling body, its disc-lite belt, and seven of its satellites. It grew, and grew, till it towered enormous; and then I plunged amid a streaming multitude of clashing stones and dancing dust-particles and gas-eddies, and saw for a moment the mighty triple belt like three concentric arches of moonlight above me, its shadow black on the boiling tumult below.."

When I finished reading the story I couldn't help but think that Wells perhaps became an inspiration to 1997 movie Contact's opening scene (from Carl Sagan's novel of the same name):

Just watch this and make your own mind up:

No wonder they call him, H.G Wells, "The Father of Science Fiction".