Nonogram solver
This morning, I discovered that the Nonogram solver did not make much progress
since yesterday evening. It is down to 4627 unknown
cells. It looks like it got stuck somewhere in trying all combinations in the
square consisting of the cells in the rows 66 to 72 and columns 44 to 49,
which is coloured orange in the image on the right.
In a seven by seven square there are 140737488355328 possible patterns.
Early in the afternoon, the solver terminated after not finding any
additional improvements, then the one given in the image on the left.
About 61% of the nonogram is still unresolved. I modified the program
such that is searches all ten by ten squares but with a time limit of
five minutes.
(follow-up)
During the day it snowed several times, one time quite
strong, but the snow did not stay on the ground. This evening, Annabel and I went to the university to play Go.
Again it was snowing a little, but this time it was cold enough for some
of the snow to stay. When we arrived only Ton was there. We drank some
tea, and waited for any play materials to arrive. It was around nine,
when we were not expecting anybody anymore that Rudi showed up. He had
been slowed because of snow fall on the road from a city to the North-West.
Ton asked Annabel for a game, and I played against Rudi. I was given nine
stones ahead, and I lost with 18 points. Not that bad. Annabel went outside
to play in the snow. On the car there was a thick 3 cm (1 inch) of snow.
I had to drive slowly, because the roads were slippery. At our place
there was less snow.
More snow
This morning there was some more snow when we
looked outside. The sky was mostly clear with some clouds on the horizon.
When I biked to my office the sun added its colour to the landscape.
When I biked under the railroad, I was greeted with a cloud of snow dust
and when I looked up, I saw that the whole train was surrounded by a
cloud of snow. This means that the snow is still rather dry.
The modifications that I made yesterday on the Nonogram
solver, have so far not resulted in any progress. I think it all has to
do with the time limit, because exactly those squares that could result
in making some progress are likely to take a long time. I already have
some ideas on "improving" the algorithm for searching a solution. At
this moment, I first try to find a single solution to a given square,
and next, I will try to find counter solutions that cover the first
solution with opposing values. For finding counter solutions, I am
using a the same algorithm to find a single solution. The algorithm to
find a single solution simple tries to fill the cells row by row. For
small number of cells to be filled, this is not such a problem. But if
the number of cells that need to be filled, grows, there is a chance
that you make a wrong choice early on, and that you have to search a
larg number of possibilities. A better strategy is to see if there is
a cell that can only be filled with one value, and continue with that
cell being filled with that value. Of course, it is also possible to
find that a cell cannot be filled with any value, in which case you
can immediately back-track. This algorithm is slower in each step,
but for a large number of cells, it might be more effective. Maybe it
is a good idea to use this second algorithm when the first one fails to
find a solution within a reasonable time, say something like one minute.
In all the years that I have been writing programs to solve problems,
I have never used a timer to determine to use an alternative algorithm.
Interesting.
At the end of the day, I implemented the alternative algorithm in
the lateste version of the Nonogram
solver and started the program.
(follow-up)
This evening, when I went swimming, I took the opportunity to swim
in the snow, by going outside. The water was rather cold, so I did
not stay outside too long.
Some more snow
This morning, there was some more snow on
the ground. It was less than a centimeter.
This morning, the Nonogram solver, which I started yesterday did not resolve any more cells. I started it again,
now checking all fourteen by fourteen squares. In the meanwhile, I
am also thinking about other methods, but so far, I haven't got any
good idea. During the day, I discovered that the alternative
algorithm sometimes also uses considerable amouths of time. It had
trouble with the square on the rows 58-71 and columns 80-93. This
one required more than 73000 calls to try_all_in_square_slow.
At the end of the day it was working on the square on the rows 67-80
and the columns 59-72. Both squares had 120 unknown cells. This means
that there is still room for improvement. Maybe I should develop an
even "slower" alternative algorithm.
(follow-up)
This afternoon, I arrived at 15:20 at the city administrative office
for applying for a new passport. I had made an appointment through
the internet. Li-Xia was already there, and
Andy was playing with some Lego. I went outside
to look for Annabel who was coming by bike
straight from school. After a few minutes, I went inside again. Annabel
arrived at 15:25. Half past three we were called. Annabel and Andy
had to be there because we wanted them to be included in my passport.
The lady asked some questions to Annabel to verify that she was our
daughter. When she also wanted to question Andy, I told her that he
was mentally handicapped. We called him, because he was still playing
with the Lego, but he refused to answer any question. The lady said
it was okay, and he could continue playing with the Lego. Then Li-Xia
and I had to sign some forms. Li-Xia had to sign to allow our children
to be included in my passport. It was at 15:42:38 that I paid 55.88 €
for my new passport. Next Friday, I can collect it.
But before I left, I looked together with Annabel at the Mammoth skeleton
that was put on display in the center of the hall. The skeleton was made
from the bones of about two hundred different animals.
Some snow again
During the day there was some snow again.
The snow did not stay. There are still some patches of snow from
earlier days here and there.
Small snow storm
This morning, there was already a thin layer of snow
on the ground when we woke up. Around ten o'clock, it started to snow again.
Quite strong within five minutes there was at least one centimeter of snow
on the ground. By the end of the day everything was gone again. It
is long ago that it has been snowing for such a long periode of time.
It will still continue for some days, they expect.
Guess what: snow again
Around half past seven in the morning, it started to snow
again. Big snow flakes were falling from the sky, quickly forming a thin white
layer on the ground. In the past weekend the whole Alp region was hit by heavy
snow storms and many Dutch got stuck in the traffic while going or returning
from their sky holidays.
Rain
It was raining this evening, when Annabel and I drove to the university to play Go. When we
arrived, Erik was already there. Not much later Rudi
and Marcel arrived. Rudi invited Marcel for a game,
and Erik and I decided to play. A little later, Ton
arrived, and he played a game against Annabel. Erik
and I did not use any handicap. I had to resign, after
I lost a big group, which I could have saved, as Erik
pointed out. I made some other small mistakes. Because
it was still early, we decided to play another game,
which he won with 78 against 56 points. It was still
raining when we left. It looks like we wont get any
snow anymore.
Hunters of Dune
I just read first chapter of Hunters of Dune the first novel
out of two that Brain Herbert and Kevin Anderson have written
as their version of Dune 7, the
never written final novel in the Dune Sage by Frank Herbert
(the father of Brian). According to Brain and Kevin these
two novels are based on the detailed outline that Frank Herbert
left behind. So far, the have not shown the intention to publish
this outline and the detailed notes that Frank left behind on
two 3.5 inch floppies. The first chapter acts as a bridge and
does not give us any new information, except that the no-ship
has been floating through space for three years without knowing
where they are.
(follow-up)
Passport
This morning, I collected my new passport and
handed in the old one. My picture looks a little pale. The
pictures of Annabel and Andy look good. For some reason, Andy is on top.
This afternoon, Annabel gave a talk
on Go in school. This morning, I already
helped her with bringing a large demonstration board. Yesterday,
I bought some black and white magnets. It went well. The children
asked a lot of questions when she was finished. She got a 8- on
a scale from 1 to 10. Afterwards she played a game of Go against
everyone, most of the time playing against two at the same time.
She lost only one game, against her teacher, also because she was
concentrating on the other game she was playing.
(follow-up on demonstration board)
This evening, I watched the arrival of the
Mars Reconnaissance Orbiter on NASA TV on the computer.
Really interesting that you can follow this life. I wonder how
many people followed it here in the Netherlands.
Snow again
I don't believe it, but when we opened the curtains this morning,
it was snowing again. Although the snow did
not stay on the ground there was enough of it on the roofs, the cars,
the plants, and trees.
Treble
Yesterday, Treble won the national contest for the
Eurovision Song Contest with
the song 'Amambanda'. In November 2004,
I bought there CD 'No Trouble'. It has been some time ago that
I played it. I still like the song 'True Friend' the most.
This morning, I made some phone calls for the vaccinations
we need for out trip to China. I especially made some
inquiries with respect to the ITP that Andy has had
twice, the last time in 2003.
According to them, it should not be a problem, but we
agreed to spread the vaccinations. I have made appointments
for Monday, April 24 at 16:30
(the first possible date) and Monday, May 29 at 16:00. The first time is for Andy alone,
the second time for all of us. The children get vaccinations
for Hepatitus A/B and Typhoid. We get Hepatitus A, Typhoid and
probably the default DTP.
The Nonogram solver is still trying all 14x14
squares. It took a long time to process the square on the rows 53
to 66 and columsn 24 to 37. More than 95000 partial solutions were
examined. At the moment it is working on the square on the
rows 62 to 75 and columns 74 to 87. Both are squares with 180
unknown cells. The last weekend, I have been working on an
algorithm which finds all solutions starting from the top. Until
row 10, this looked rather successful, but then it hit the
combinatorial explosion, and I stopped the program.
(follow-up)
Computer problems
When I arrived home, Li-Xia told me
that the lixia computer
was behaving strange. And indeed it did stop early during the
Windows NT boot. After many problems, I managed to start it
up in safe mode with everything else enabled using msconfig.
It is funny to see, how much is working in safe mode. On
Bob Cerelli's Windows Page, I read the tip to use
winnt32 /unattend to reinstall Windows NT with leaving
all settings intact. When I tried that, I rather quickly got
a message stating that some other program was still in the
progress of installing something. That could be possible,
because I attempted to deinstall CA Antivirus. I had noted
that some files were downloaded when Li-Xia started up the
computer around one o'clock this afternoon. These files must
have been downloaded early during the startup, because I could
not find any other events in the various events logs indicating
that the computer had startup around that time. So, I thought
it was a good idea to uninstall CA Antivirus, also because it
was long ago that it had been updated. This morning, when I
switched off the computer, two security updates from Mircosoft
were installed as well. At first, I thought that these were
to blame for all the trouble. I have been googling around to
figure out how I can remove the software installation that
appears during startup, but I haven't found anything interesting.
I did come across Freeware
Sysinternals page with lots of interesting tools.
Computer problems (continued)
The problems have not been resolved yet. Yesterday, I did not have
time. Today, I have been studying the wikipedia article on
Windows NT Startup Process that is also used by Windows XP.
I understand that it is the Session Manager that is responsible
for the delayed rename and delete operations. When I checked the registery at
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\FileRenameOperations
I found that there are no pending file rename operations. So, that
cannot be the problem.
I removed the Computer Associates keys from HKEY_LOCAL_MACHINE\SOFTWARE
and also from CA_LIC_CLNT and CA_LIC_SRVR from HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services
and HKEY_LOCAL_MACHINE\SYSTEM\ControlSet003\Services. Following, I
tried to reboot the system without safe mode, but it failed.
Some time later, I found a RmvHomeDir call in
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\RunOnce to
remove the eTrust Antivirus directory. But I suppose that it is never called.
There is also a winnt32RunOnceWarning which executes user.exe. I do not
know what that means. I decided to remove the RmvHomeDir thing.
I also studied Troubleshooting the Startup Process. But I did not solve the problem.
Computer problems (continued)
I finally found the English text of the error message that I get
during running winnt32.exe. It is
"Existing software
not fully installed". But the advices to fix this problem, were not
applicable to my situation. I decided to try an
XP Repair install as a last resort. That did go fine, until setup
rebooted the computer, and reported that it could not continue setup
in safe mode. I realized that in boot.ini it still said that the computer
should boot in safe mode. What a stupid mistake. Luckily, I played around
a little and discovered that if I do start press R on the first choice
of the Windows setup CD, you arrive in a very limited command prompt.
Very limited indeed, because it does not even have a simple text editor.
After some more poking around, I discovered that you could add a new
entry to the boot.ini file with the command "bootcfg /add". In this
way, I managed to continue the setup. But somewhere halfway the setup,
the computer would simply reboot. After having gone through this loop
a number of times, I finally conclude, that I should go for a full
reinstall of Windows XP. I used the original Windows XP home edition
CD for this. (Later I realized that it might have been better to use
the recovery CD that came with the computer.) So, after some hour, I
end up with an almost empty PC. No data lost, and most application still
being executable, while not being installed. It is going to take some
weeks, I guess, before everything will be installed again. I decided to
keep a logbook of all installment details, just in case I encounter
problems again.
Computer problems (continued)
Today, I spend most of my time trying to get lixia working again.
Loosing weight
In the past weeks, my weight has dropped
rather suddenly, to my surprise. It always makes me a little nervous
if my weight suddenly changes. I recently started eating red grapefruits
almost every day. This afternoon, I discovered that research has
indicated that grapefruits do have a weight reducing effect. It seems
that this recent diet change, might explain
the sudden weight loss.
(follow-up)
I have often said that in about twenty years, cars that drive
by themselves will be regarded safer than "maual" steering. Today,
I discovered that Mobileye
has developed a integrated camera and image processor that is
able to perform some rather complex image recognition real time.
The image processor runs on 120Mhz, but has the theoretical equivalent
computation power of an Intel Pentium IV processor, running at
4Ghz clock rate. It's architecture somehow resembles the
Cell architecture.
Minister Donner
Yesterday, Minister Donner of Justice, quoted the first lines of the chorus of
his rap "De Don" in the parlement, saying: "Here speakes Donner of Justice.
I do it together with the police". The president of the parlement
immediately made some critical remark about this. The evening before, after
the government had discussed means to reduce beaucracy, he made the
suggestion (as a joke) to abolish marriage, because that would reduce
the amouth of paperwork related to divorces.
Tonight, Annabel and I went to the university to
play Go. Soon after we arrived, most of the others also
arrived. I played a game against Taco (with 8 stones ahead) and Annabel played
against Rudi (with 15 stones ahead). She lost with 44 stones. Not too bad. My
game was progressing okay, until Taco played a big monkey move, and I messed
it up. I resigned, when it became obvious to me that I was going to loose the
group. Would I not have lost the group the score would have been close. We
analyze the game a little.
Online Go game
Today, I finished an interesting Go game
(SGF), which I
played on It's Your Turn against
bbruneau. He is one of my fixed playing partners, and we often play
quit intensive games while taking time to think about our moves.
(follow-up)
Spring
Finally, spring has arrived. Just this day the temperatures have
gone up. In the past weeks the temperatures have been much lower
than average. Botanic experts have said that spring is delayed with
about three to four weeks, compared to the past years.
Synchronized swimming
This morning, Annabel left around eight with
a people from her synchronized swimming club to travel to the swimming pool
De Wiemel in Deurne.
It is almost 200 Km driving from Enschede. We had to get up around seven,
but because we switched to summer time, it was six o'clock winter time.
She was in one of the two teams from Enschede that joined in the national
contest for "figure floating" (I am not sure whether this is the correct
English term). Her team consisted of seven girls and one boy of her age.
The other team consisted of girls ranging in the age 13 to 16. The other
team won the first price. The team of Annabel became last. But that might
not have been completely their fault, because they did not get points for
two of the four figures that the performed, becaused they were swapped
according to the program that was send in. Although, I understand that
that is how the rules are of this contest, I still do not find it very
fair, also because the mistake was not of their doing and that for most
of them it was the first contest that they joined. Maybe, they should have
given them points, but disqualify them from the contest, than they would
have known how they would have scored, if the mistake would not have been
made.
(follow-up)
Gaining weight
Did I report last Tuesday that my weight had dropped, since that time it has been going up again.
Dinner
This evening, we had a dinner with a group of my colleagues in
"Het Kosterhoes". We arrived
around six o'clock and planned to stay till half past eight. We
were finished with the main dish around seven. (I had salmon.)
We decided that there was still some time left for dessert. I
decided to just have a cup of tea. But it took a long time for
the dessert to arrive. Just after half past seven, we made some
inquiries about how long it was still going to take. They said
it was just ready, and indeed within a few minutes they brought
in the plates with dessert. These were normal size plates with
large desserts. I was happy, I did not choose a dessert, because
it was obvious that these dessert contained more calories than
the main dishes. I tried to finish my tea as quickly as possible,
but it was hot, and then I left for home. It was just after eight
that I arrived at home.
When Annabel and I arrived at the
university to play Go, Ton and Marcel
were talking. Not much later Taco arrived, and I asked Taco
if we could analyse the online game that I finished last Thursday, and he agreed. Marcel and Ton decided to
play a game as well. After we were ready, Rudi arrived, and
Taco and Marcel decided to play a game, while Ton played
against Annabel. Rudi and I decided to watch both games.
Annabel got nine stones ahead. She was doing quite good at
pushing Ton into the corners and getting a large territorium
in the center. At one point Ton hit is bowl, filling one corner
of the board with white stones. Ton tried to restore the the
original layout, but quickly Rudi got up and whiped the corner
clean, and replayed the moves. With some help from Ton and I,
he restored the board. At home, I integrated the remarks from
Taco with the game.
Price
This evening, Annabel went to
synchronized swimming again. Afterwards, there was a small
ceremony to celebrate the results of the contest
of last Sunday. A local newspaper came to take some
pictures. The older team got flowers, and everyone from the
younger team got a large red rose. The older team also decided
to give the cup to the younger team. In the coming weeks,
Annabel will get the opportunity to bring it home for one
week and show it to her classmates. For the two figures that
did get points for, they got quite high points. They did
quite well, their trainers said. At least they should not
have ended at the last place. And they were the youngest
team. So, in a sense, they did very good. Over two years,
when the contest is held again, they should have a good
opportunity to win the first price.
This months interesting links
Home |
February 2006 |
April 2006 |
Random memories
Tuesday, March 21, 2006
Monday, March 27, 2006