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

An antique shop in Amsterdam

An antique shop window in Amsterdam.. Delight of browsing through objects survived distant past. Just think about care, craftsmanship and love embedded in these objects, and happiness or sorrow they caused in fellow beings who are no longer with us. These objects whisper us stories they witnessed, life dramas they were part of. Alas we can't hear them.

The Avenue

Slender women with veil, every few hundred meters prostrate themselves on wide pavements of the Avenue des Champs-Élysées, a small plastic cup in their sun burnt hands. Passers, mostly tourists gazed at them briefly with indifference as they continue their stroll before large, bright shop windows.

The sun rapidly sets beyond the colossal arms of the Arc de Triomphe, small black cars and vespas are busily circling around it like fire flies attracted to bonfire.

Tourists, Europeans, Americans, Australians, Arabs, Chinese, Japanese, with track-pants, sneakers, and backpacks are scanning surrounding buildings in every direction, looking at reliefs above window frames, reliefs partly covered in gray exhaust dirt, watching the crowd below with a contemptuous look.

Native Parisians who just left their offices heading home choose to walk briskly on the road side, as shop fronts are packed with tourists.

A group of men is in desperation to grab attention of passers by; they play loud Arabic music and encourage crowd to dance. 

A security guard controlled tourist queue is hanging out of Louis Vuitton shop.

The Avenue, once a symbol of Parisian attitude, turned into a globalization showcase, its hay days are long gone and its distinct glamorous character was left behind like an old sweetheart’s sigh.

Nexus causality

According to John Tooby,  Professor of Anthropology, UC Santa Barbara:

Causality itself is an evolved conceptual tool that simplifies, schematizes, and focuses our representation of situations.

Nexus causality on the other hand is a different tool.

InWar and Peace, Tolstoy asks: 

'When an apple ripens and falls, why does it fall? Because of its attraction to the earth, because its stem withers, because it is dried by the sun, because it grows heavier, because the wind shakes it….?'

Nexus causality is what Police and FBI will be using in the analysis of Boston marathon bombings:

“For how long the suspects have been planning the bombings? How did they build the bombs? From whom, where and how did they get logistic support? Etc.”

But the analysis will stop, when bigger questions are asked:

“Is there a link between this event and US foreign policy in the Middle East and why?”

“Should US administration continue to support religious fundamentalists in the Middle East, especially in Syria and why?”

As simply stated by Tooby:

“Our minds evolved to represent situations in a way that highlighted the element in the nexus that we could manipulate to bring about a favoured outcome.”

References:

http://edge.org/annual-question/2011/response/11211

http://www.elisa-dbi.co.uk/blog/38-tools-for-beautiful-data-visualisations/

Too bleak?

Recently I watched a movie called 'Biutiful' directed by Mexican director Alejandro González Iñárritu, the protagonist played by Javier Bardem.

Most critics found the film too bleak. It was indeed. You need stomach to watch it in its entirety. I couldn't, as the movie reached its climax towards the finale, I threw the towel, and had to escape to my room, my wife whereas, was braver, she finished it.

But I still score the film 9 out of 10, simply because performances of actors were brilliant and too real, the story, despite being too bleak, taught me something valuable, I realized and absorbed something that I could learn or experience in no other way.

I was however shocked when I heard that two film critics whom I admire, Margaret Pomeranz and David Stratton gave low scores to the film, mostly on the basis of it being too real.

I too like what Tarantino qualifies as 'movie movies', ie. movies that entertain via fantasy, or via glossed reality. But I also like when reality strikes, when I capture something essential, something I missed out until then. I think crying and getting emotional for those bleak stories is ok, they are as real as they get, and the experience becomes an honest contract between the audience and the film maker. No packaging, as if you buy a completely transparent telephone with messed up ingredients, ready for you to face reality, understand and consume.

http://en.wikipedia.org/wiki/Biutiful

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.

A day of awakening

If I need to pick up just one day, among others; mother's day, father's day, valentine's day and so on, it would be the women's day.

Women’s day calls for action, a reminder for humankind, as it points to a shame we all share.

Hundreds of millions of women are oppressed around the world, deprived of freedom to shape their life. They are physically and mentally abused.

Everything we achieved on our planet so far in the name of “civilisation” will be meaningless, unless the other half of our species is treated equally.

Therefore this is not a day to celebrate. Not yet. It must be a day of awakening.

Why do we love reading some books?

Why do we love reading some books, but not the others?

Inspired by mathematician Roger Penrose's depiction of Platonic Mathematical World, Mental World, and Physical World, I would like to present my theory.

From the book: Roger Penrose, The Road to Reality, Vintage Books, 2005.

I begin by breaking the problem into several worlds.

The world the author perceives, the world he describes, and the world we perceive.

The discrepancies between these worlds are inevitable; they would have cues on their own, as well as hindrances for our view.

Regardless of the author’s intentions, we begin to build our own world from page one. We continue to fit our perception on the world we have been constructing, not on the world that the author saw or described. Similar to divergence in mathematics we diverge from intended world-view.

So the secret to good authorship must be to relieve both the author and the reader from a burden, the burden of mapping author's world.

Rather than pushing an answer down the throat of the reader, the author should pose a question, such that the world he perceives disappears, and the world his reader perceives gradually unfolds.

---

Links:

http://en.wikipedia.org/wiki/The_Road_to_Reality

http://aminotes.tumblr.com/post/1025534467/the-concept-of-laws-the-special-status-of-the

References:

1. Roger Penrose, The Road to Reality, Vintage Books, 2005