Feb 23 2013

Sudoku: more basics

Categories:

Sudoku

by

It's possible to solve a Gentle Sudoku with only a box-by-box search technique. While this is the first technique I will normally apply, it is not the only one necessary to solve most Gentle puzzles.

Sudoku has 3 rules: every 3x3 highlighted box must have 1-9, every row must have 1-9, and every column must have 1-9. In a box-by-box search, you use the row and column rules to solve squares in a given box. As you would guess, we can also do a row-by-row search that uses the box and column rule to solve squares.

Consider:

SudokuHarder1

A box-by-box search pattern allows the solution for 12 squares, indicated in yellow:

SudokuHarder2

No more such inferences can be made at this point. However, the puzzle is vulnerable to a row-by-row search. Notice that the 8th row can only have a 5 in its seventh space, due to the other squares being excluded by the 5s above them:SudokuHarder3

Thus, the 5 must go in box 9, square 4.

Technique 2: Row by row

Search pattern: go through each row and check every number that doesn't already appear in the row. Exclude squares from the row that would violate the column or box rule.

Logically, the final basic technique is a column by column search, exactly analogous to the row-by-row method.

Technique 3: Column by column

Search pattern: go through each column and check every number that doesn't already appear in the row. Exclude squares from the row that would violate the row or box rule.

In this case, the fifth column must have its 6 in sixth box:SudokuHarder3bA combination of the three basic techniques leads to the solution below.

SudokuHarder4

To get there I used 3 more column-by-column solves (box 5 square 2=9, box 3 square 8=3, box 7square 8=9), then nine more row-by-row inferences. The remaining square can be filled in with a box-by-box search or by following the direct Sudoku rules (filling the remaining square in a group with the only entry that isn't there).

Full solution:

(note: Boxes are numbered left to right, top to bottom like words on a page. Squares are numbered the same way within a box)

box-by-box:
2,5=1
4,4=1
1,8=1
2,2=7
5,3=1
Therefore 5,9=5
7,7=3
8,5=2
8,6=6
8,8=5
Therefore 8,9=4
9,2=1

row by row
9,4=5

col by col
5,8=6
Therefore 5,2=9
3,8=3
7,8=9

row by row
9,9=7
Therefore 9,8=8
7,4=7 (also possible box-by-box)
1,9=7
1,7=9
Therefore 3,7=6
9,3=6
9,1=3
6,3=3

Box-by-box
4,2=7
6,7=7
6,8=2
6,6=9
9,5=9
Therefore 9,6=4
Therefore 3,2=4
4,3=2
4,9=9
4,6=4
Therefore 4,7=8
Therefore 5,7=4
Therefore 5,1=8
Therefore 6,1=4
Therefore 6,4=8
7,2=2
Therefore 7,3=5
Therefore 1,6=8
3,3=8
Therefore 3,6=2
1,1=2
Therefore 1,4=6
1,5=4
Therefore 1,2=5
Therefore 2,1=6
Therefore 1,4=5

This post has no tag

Feb 22 2013

Thermo for Normals (part 30): Complicated things

Categories:

Thermo for Normals

by

All cars have to keep themselves cool. The reason for this, as we've seen, is the inefficiency of the engine: you can't convert the heat, made in the burning of gasoline, into work without creating some waste heat. If we take the energy stored in gasoline to be the "free energy" of the chemical bonds, then a car engine is about 18% efficient, which means that 18% of the heat created is turned into work by the engine. The other 82% of the heat has to be thrown off by the car somehow, or the temperature would just keep rising, which we know doesn't happen (the car would overheat, the oil would burn, etc. Bad things.) What is the technological method for getting rid of all this excess heat?

Quite obviously, the only place for the car to shed its heat is into the atmosphere. It does so by several methods. First, some (a lot) of the heat is in the exhaust gas emitted from the tailpipe. Second, there is a big fan that blows air into the engine from the front, so that the air carries away heat by convection. The car also conducts heat directly into air in contact with it, and because of convection this will be substantial. Finally, we have radiation. A motor circulates water through the engine and through something specifically designed to radiate heat well. It's called a, guess what, radiator. The radiator sends the heat out as IR photons that are absorbed by the hood of the car. The hood then either radiates that heat out into the world or conducts it to the world.

When the car first starts running, it is not capable of shedding all the heat. This is because the temperature is low, and we know that the rate of heat radiation per area is , and the rate of conduction is . When is low, these rates are low. But as the parts heat up, they can radiate and conduct better and better. The stable temperature is when the heat produced in the engine is equal to the heat flowing out through the body of the car by any means. In other words, steady state is when .

Let's see if we can estimate how hot the hood of a car gets, assuming the car throws off most of its heat just by radiation. When the car is going 65 miles an hour, it needs about 25 horsepower, which is about 18,600 watts (that's 18600 joules every second). 82% of that is waste, or about 15,200 watts. This is the amount of heat the car needs to get rid of when it reaches a stable temperature. The radiation rate per area is , times the emissivity which we will assume is 1. We need the area of a hood, which is about 1 square meter. So watts. With , this becomes celcius!!! That cannot be right! Car hoods are nowhere near that hot.

There's nothing wrong with the physics, we just made a bad assumption (that most of the heat leaves by radiation). This proves a point: thermodynamics in a real system like a car is hard to analyze. We have to start thinking about other ways that heat could be lost. The most obvious way is through exhaust. Exhaust gases are about 530 Kelvin. So the heat loss from that is the volume of gas, times its heat capacity per volume, times the temperature, and that's liable to be pretty high, especially given the relatively high heat capacity of water vapor. The car is also radiating downward from the undercarriage to the street. Finally, there is air flow over the car, carrying away a significant amount of heat from convection.

Human beings are even more complicated. Do humans always need to lose heat? Yes, they do. People are constantly running various machines in our body, and all of that machinery creates waste heat. In fact, your normal metabolism creates about 90 watts (90 J of heat every second), the same as a pretty bright light bulb, and that's when your body isn't even moving. If you couldn't shed that heat, body temperature would rise, and that would spell death before too long. But how does it shed the heat? Here are some ways:

  1. heat conduction through your clothes to the air or through your skin directly into the air.
  2. radiation by your skin or clothes
  3. evaporative cooling from sweat
  4. energy stored in your outgoing breath
  5. convection (especially if there's air flow)

Unlike a car, we don't exhaust that much heat through breathing. Most of our heat loss is due to radiation.
The temperature you feel like is dependent on whether the amount of heat you're shedding per second is above or below 90 W. But humans respond to the changes in heat loss to counteract them. They sweat, which carries heat away by evaporative cooling, but how much heat depends on the relative humidity and the rate of air flow
(a good pic of this is here).

Now suppose you move around a bit. Your metabolic rate increases due to extra chemical processes, or extra engine cycles. And the airflow is different because you're moving through the air, so the effect of evaporative cooling is enhanced, but only if it's dry outside. And if you're even receiving indirect sunlight, then the radiation is larger. Very complicated.

If you're standing in a room at temperature , there is heat conduction through your clothing or from out of your bare skin. This happens until the layer of air directly around you reaches the skin temperature, whereupon it stops. In a very still room this happens fairly quickly. If any of the air is moving, though, the air around you will be replaced with room temperature air and heat conduction resumes. If there is steady flow, then you have constant heat flow from your skin. If it's relatively cool, a breeze will carry a lot of heat away from you. But the temperature in the room is the same whether or not there's a breeze! A thermometer will register no difference between a breezy cool day and a still cool day. However, of course you feel cooler with the breeze.

People don't feel the temperature of things we come into contact with, but rather we feel the temperature of our skin. If your skin is colder than about 93 F, it is losing heat at a rate faster than normal, and you feel cold, and if it's gaining heat so that skin temp rises above 93 F, if feels hot. So, if you're walking on red hot ( C) coals, your skin never says "1000C!!!", it only states how much the skin has risen in temperature. Walk quickly enough, and minimize the time your foot is in contact with the coals, and your feet stay at a low temperature, because there hadn't been enough time for significant heat to transfer. Walk slowly, and you can expect to be nursing a nasty burn.

Even the way your body feels in a still room is affected by multiple factors. Suppose you set your thermostat to 77 F all year. When you get home in the evening during the winter, your walls have a lower temperature than the air in the room. Therefore the radiation from the walls is relatively low compared to other times. In the summer, your walls are warmer than the air, and so they radiate more. The conduction is the same for both, since your body is the same temperature and so is the room. But the actual feeling depends also on the radiation. So people feel colder in the winter, even though the air is the same temperature inside, because there is less radiation hitting them from the outside world than during the summer.

Now, as complicated as all of this sounds, thinking about the thermodynamics of the whole Earth isn't quite so bad. This is because the atmosphere has NO conduction or convection with anything else. The temperature of Earth is totally determined by radiation. The sun shines a certain energy and the earth re-radiates the same amount. If that didn't happen, our planet would be uninhabitable in a hurry.

This post has no tag

Feb 18 2013

Sudoku: the basics

Categories:

Sudoku

by

Those of us who think we'll live a long time (not me) have a couple near certain conditions to look forward to. For men, it's prostate cancer. But for either gender, it's dementia. Puzzles ward off dementia. I'm not all that good at puzzles. Over the years I've done crosswords, but they require a bit too much outside knowledge (not to mention having a large lexical database with words like oleo, Olin, Gynt, etc). For awhile I did the newspaper Cryptoquote, but those became a bit too easy.

But eventually, I did the LA Times' Sudoku, which I found appealing because it's somewhat more logical in nature than those other ones. I want to dig into some advanced techniques, because solving a Sudoku should (almost) never involve guessing. However, it's worth going over the basics of Sudoku.

All people can learn Sudoku. Sudoku has several difficulty levels, and the puzzle is classified roughly by how advanced the solution technique is. Gentle/easy is the lowest difficulty. These can be finished with only basic (direct) techniques. Moderate and Tough generally speaking require indirect techniques. Expert/Diabolical require the most advanced techniques. Today I only want to talk about basic technique.

Consider the following puzzle:

SudokuBasic1

The Sudoku board is a 9 x 9 square board with squares of 3 x 3 grouped by dark lines (in the puzzle above, the darker colors of green also denote a separate box). There is only one rule: each line, column, and 3 x 3 box must contain every number between 1 and 9. Because each of those groups has nine entries, we can also say that no line, column, or 3 x 3 box will contain more than one of the same digit. This is how we solve the puzzle.

Any solution technique for Sudoku should also come along with it a search pattern. A strategy is not useful unless you know how to look for an instance of where it gets used. So, I'm going to go through the techniques I would use to first attack the puzzle.

Technique 1: Box by box

I start by looking at the upper left 3 x 3 box. I start with number 1, which is not filled in. Can I find out where 1 must be in that box? No. The only 1 that "touches" that box is the 1 in the next box over to the right, but that one only tells me that the 1 in the first box is not in the middle row, which is not enough to go on.

Then I count 2. Already there. 3, already there. Now 4.

SudokuBasic2

The 4s in the next two boxes are in the first row and the second row. Mentally, I draw a line from each of these through the box I'm focusing on. I see that once those boxes that are excluded by those 4s are eliminated, there is only one possibility for where the 4 goes, in the bottom right square of the box.

SudokuBasic3

I'm leaving the solved squares in yellow to remind us that they weren't in the original puzzle. I continue in this way. Can 5 be solved in the first box? No. 6? Yes.

SudokuBasic4

The 6 in the box below it excludes it being in the first column, and the 6 in the upper right box excludes it from being in the center row. Had we not already solved for 4, we would still have two possibilities, but since we have, we know it must be in the upper right square.

SudokuBasic5

Let's adopt a naming scheme. Let's call the upper left box "box 1", then number them going left to right. So, the box to its right is "box 2" and the one under box 1 is "box 4". "box 8" is the middle box of the bottom row of boxes. Then, we'll name each square in the box the same way. Rather than go through each deduction, I'll just summarize the ones I find by continuing with this strategy, then show you the board with all of them filled in.

Box 1, square 1 = 1
Box 1, square 5 = 7
Now in Box 1 there is only one square left open, so square 6 must = 5
Box 3, square 5 = 8
Box 4, square 4 = 2
Box 4, square 1 = 7
Box 4, square 8 = 5
Box 4 square 6 = 8
Now in Box 4, there is only one square left open, so square 9 must = 1
Box 5, square 8 = 3
Box 5, square 2 = 8
Box 5, square 5 = 1
Box 5, square 6 = 7
Therefore Box 5, square 4 = 5
Box 6, square 1 = 5
Box 6, square 2 = 1
Box 6, square 4 = 6
Box 6, square 9 = 7
Therefore Box 6, square 6 = 9
Box 7, square 5 = 1
Box 7, square 3 = 3
Box 7, square 2 = 6
Box 7, square 7 = 8
Therefore Box 7, square 1 = 4
Box 8, square 7 = 4
Box 8, square 8 = 6
Box 8, square 2 = 7
Box 8, square 3 = 5
Therefore Box 8, square 6 = 9
Box 9, square 1 = 2
Box 9, square 4 = 4
Box 9, square 5 = 6
Box 9, square 7 = 7
Therefore Box 9, square 9 = 1

At this point I've done one "pass" through the puzzle with only this technique. The board looks like this:

SudokuBasic6

Wow, just one pass through the puzzle with the box-by-box search filled in most of the puzzle.

At this point, we actually have three columns with only one blank entry, and so we know that entry must be whichever number doesn't appear. Column 6 is missing an 8, column 7 is missing a 1, column 8 is missing a 7. Also, row 2 is missing a 2. Thus, these can be filled in immediately.

SudokuBasic7

The remaining entries can be filled in without any other techniques necessary. That is, we got through the entire puzzle with just one strategy.

SudokuBasic8

The full solution has all digits in every row, column, and box. Once you get good enough, such a puzzle takes about 3 minutes.

More to come.

This post has no tag

Feb 06 2013

Thermo for Normals (part 29): Radiation, continued

Categories:

Science, Thermo for Normals

by

Now we know the amount of radiation coming from an object with a surface at temperature . And we know the amount for each frequency of light. It's


where is frequency you're interested in, is the speed of light, and is a property of the object called emissivity. Emissivity measures the fraction of white light that is emitted and absorbed by the surface, and could be a function of if, say, something absorbed blue but not red and green (such an object would be yellow). This equation tells you the energy radiated per time and per surface area in the neighborhood of :

\begin{align*}\mathcal{P}(f) \, df = & \text{The amount of energy that leaves a body at temperature $T$} \\
& \text{as radiation at frequency $f$, per second and per square meter}.\end{align*}

(This isn't precise. Technically this only gives you the amount in a small range around , and the only way to get the amount is to integrate. However, that's confusing as hell until you get used to it.) To get the actual amount of energy radiated out of it, you have to add up the values for the frequencies you want to know about, multiply by the surface area of the object, and multiply by the time it radiates for.

But let's assume we just want to know the total amount of all radiation, no matter what frequencies it's composed of. Then we just need to add up for every frequency. That will give us the cooling rate for a body with surface temperature due to radiation:

Important!

The total amount of energy radiation per unit area per unit time is


The integral of is quite difficult, so I'll just quote the result (but see here for the calculation) which is . We have to get rid of the in the exponential to use this, so let , . Therefore,


Now, and this is a very important assumption, assume that the emissivity is the same for all frequencies. That is, is a constant for a given object. Then,


Let's wrap all those constants into a number called .

The total radiation from a body at surface temperature per time per surface area is, then,

This is the Stefan-Boltzmann Law, and it's quite a simple law, really. The total radiation (per surface area per time) is just a constant ( W m K) times , times the emissivity. The temperature is the temp at the surface, which might not be the same as the temperature of the interior! The interior of the Sun is millions of kelvin, but its radiation temperature is 6000 K because that's the temperature of the surface.

If you have an object with surface area , then in time it radiates of energy. Human skin is an almost perfect emitter in the IR (emissivity is 0.98), and so is clothing for that matter. Assuming that an average person has about 2 square meters of skin, and that skin is 33 °C = 306 K, then the amount of heat radiated every second by a naked person is 1000 J. You are emitting 1000 watts if you're standing around naked. At that rate, you'd be freezing in a very short time! Now, the thing is that the environment around you is radiating back at you as well (unless you're in outer space without a suit ...). If the walls are 20 °C = 293 K, then they radiate an energy per unit area of , and drywall emissivity is also close to 1. You absorb of energy every second from your environment. So the net loss is only watts, or 158 joules every second if you're naked. If you're clothed, then the temperature of the surface is the temperature of clothing, which is more like 28 °C = 301 K. In that case, usually you are losing 95 watts in radiation, enough to power a very bright light bulb (in principle). Of course, I've left out any effects of the other two ways heat gets around: conduction and convection. We come back to that next time, where I'll speak about the way humans experience and perceive heat.

Now think about the Earth. It has no conduction or convection with the rest of the universe, since all that there is outside of the thermosphere is vacuum. The Sun is the same. So the Earth radiates some energy for its surface temperature , surface area , and emissivity ; and the Sun emits for its surface temperature and area . Now, the radiation from the Sun has spread out in all directions, so the energy per area is lower by , where is the distance from the Sun. So if we take the distance from the Sun to the Earth to be , then the amount of radiation the Earth emits is

and the amount it absorbs from the Sun is

Why? Because is both the fraction emitted and the fraction absorbed, and is the area that the radiation density is incident on. So long as the Earth's temperature isn't rapidly changing, then these two values must balance. This gives you a small taste of the thermodynamics of climate change, which we'll take up in detail later.

During the calculation, one has to assume that the object emits and absorbs all frequencies at the same rate for all frequencies or light, which is to say that emissivity is just a number. This is not always going to be very accurate. Tungsten, which is used as the filament in light bulbs, has an emissivity that looks like this:

er

Spectral emissivity of tungsten at high temperatures (from R.D. Larrabee, MIT Technical Report 328 (1957))

You can see that the value for emissivity actually depends not only frequency, but also on temperature. Nevertheless, observe that the vertical axis is not a very big range (from 0.4 to 0.5), so if you were to say that the emissivity of tungsten is about , you'd be correct within 10%. To do any better, you have to calculate the above numerically, using the data from experiments. The point is, tungsten radiates more at 1000 THz than it does at 400 THz, but not by a huge amount. However, the emissivity for things such as clouds in the atmosphere may be very important, so keep it in mind.

This post has no tag

Feb 01 2013

New American Cancer Society report

Categories:

Science

by

The American Cancer Society just published their 2013 Facts and Figures report. It's kind of interesting to look at the time dependence of the rates. First for men:

Males

Cancer death rates for males (click for full size)

Since 1990, the rate of lung (mostly smoking induced) cancer has been falling, presumably due to the government's concerted effort to force people to stop---absent any other compelling reason that we should believe rates would be falling so fast, this is reasonable and not surprising.

It's notable that, due to H. Pylori being wiped out by antibiotics, rates for stomach cancer have steadily fallen from 45/100,000 to only about 5/100,000, a factor of 9 decrease since 1930. For most intents and purposes, that cancer has been "cured", although its decline is due to prevention rather than actual curing once a patient has it.

Prostate cancer is the largest non-lung cancer. Oddly, "for reasons that remain unclear, incidence rates are 70% higher in African Americans than in whites", the report states. The two possibilities are difference in lifestyle or differences in genetics, but determining which is contributing is so far elusive. The death rate among African Americans to prostate cancer is double that of whites; presumably the balance is due to poverty and lack of good medical care. Deaths due to prostate cancer are falling for America overall. However, incidence rates for prostate cancer are also falling, at a rate of about 2% per year between 2005 and 2009.

For Women:

Females

Cancer death rates for females (click for full size)

The vertical scale on these two charts is the same, and while all these curves are significantly smaller than that of men, it should not be construed that women die less often from cancer. In fact, the rate of death for women from all cancers is only about 10% smaller than men. The death from lady-parts cancers (breast and genitals) is about 68,000 per year, whereas men die of man-parts only about 31,000 cases per year, which explains this apparent discrepancy. Dispensing with gender-exclusive body parts, women have lower deaths of cancer of almost every part of the body.

Male Female
Oral 5500 2390
Digestive 82700 61870
Respiratory 90600 73290
Bones 810 630
Soft tissue 2500 1890
Skin 8560 4090
Breast 410 39620
Genitals 30400 28080
Urinary 20120 9670
Eye 120 200
Lymphoma 11250 8950
Myeloma 6070 4640
Leukemia 13660 10060
Other 25020 20400
Total 306920 273420

Survival rates (5 years past diagnosis) are highly dependent on body part. 90% of women will live 5 years beyond their diagnosis of breast cancer, and nearly 100% of men past their prostate cancer diagnosis. On the other hand, pancreatic cancer survival is a mere 6%, with liver and lung about 16-17%.

Survival

Medical science has made little progress in pancreatic cancers, but has nearly cured prostate and breast cancer since the 1970s. Significant improvement in leukemia, lymphoma, and testicular cancers has also been seen. For most categories, however, the decrease in deaths has been due not to treatment, but rather to prevention.

This post has no tag

Older posts «

» Newer posts