This post is the next in a series that dates back several years. In fact, it's been going on for long enough that several posts ago I decided to upgrade the title from "50 Years of Science" to "60 Years of Science", And, if we group all of them together, this is the eighteenth main entry in the series. You can go to http://sigma5.blogspot.com/2017/04/50-years-of-science-links.html for a post that contains links to all of the posts in the series. I will update that post to include a link to this entry as soon as I have posted it.
I take Isaac Asimov's book "The Intelligent Man's guide to the Physical Sciences" as my baseline for the state of science when he wrote the book (1959 - 60). In this post I will be reviewing two sections: "Particles and Waves" from his chapter titled "The Waves", and "Fire and Steam" from his chapter titled "The Machines".
"Particles and Waves" is a discussion of the early days of Quantum Mechanics. Plank had introduced the idea that light, or more generally electromagnetic radiation, had both a particle aspect and a wave aspect.
By the 1920s it was obvious that dualism was not limited to electromagnetic radiation. Einstein had also introduced the dualism between mass and energy. His famous equation was just the way you converted one to the other. In 1915 with General Relativity he had done the same thing with space and time, creating the word spacetime to emphasize the degree with which they were intertwined.
And it was not just ethereal things like spacetime and electromagnetic radiation that had a dual nature. In 1923 de Broglie came along and predicted that down to earth particles, in this case electrons, could be made to behave in a distinctly wave-like manner. In 1927 an experiment done at Bell Labs proved this prediction correct. This surprising development was put to good use almost immediately in the form of the "electron microscope".
The sharpness with which a microscope is capable of resolving images depends on the wavelength of the "light". (Modern techniques have been developed to fudge this "rule" somewhat.) The wavelength associated with an electron microscope is in the X-Ray band, much shorter than the "visible" band our eyes are sensitive to. So electron microscopes are capable of taking sharp pictures of things that are much smaller than anything a standard light microscope can handle.
At the time of this discovery and right through to the time of publication of Asimov's book, electron microscopes were expensive and very hard to use. So they were used in very limited situations. Technological advances haven't make them as cheap and easy to use as a light microscope. But both cost and difficulty have plunged. So they are far more ubiquitous now. This has improved both their availability and their frequency of use.
The first crude electron microscope was built in 1932. The first practical one was built in 1937. But by "practical" I mean a device that was hand built by skilled technicians in a well equipped laboratory. All of these early machines were one of a kind devices with no two of them being identical. It would take a number of decades before you could order a standard model out of inventory from one of several "laboratory supply" companies.
Asimov speculates that some day a "Proton microscope" will be built. For reasons I am not going to get into, the heavier the particle, the shorter the wavelength. A Proton, weighing in at roughly 2,000 times as heavy as an electron, has a much smaller wavelength. That means that it can be used to "see" things that are even smaller than the kinds of things an electron microscope can see.
Proton microscopes are now a reality. As are devices that utilize even shorter wavelengths than the wavelength associated with a Proton microscope. These devices are all fantastically expensive and fantastically difficult to build and operate. So their usage is roughly similar to that of the electron microscope in the '30s.
By now, roughly 1930, things in this area of physics have been getting more and more confusing as the decades had passed. The simplicity and clarity of Newtonian mechanics kept getting dealt blow after blow. Things seemed to keep getting wronger and wronger. And for a long time it was not obvious how to build a new theory to replace Newtonian mechanics. Sure, it was wrong. But what was right?
The experimental proof of the existence of "matter waves" (particles like electrons demonstrating wave-like properties) actually helped rather than hurt. It pointed out the direction in which the new theory must lie. A consistent set of ideas kept popping up in situation after situation. They were completely bizarre but they seemed to be the way things worked in a wide variety of situations.
One of these places was in the nucleus of atoms. Bohr had come up with a model in which electrons orbited the nucleus. But if electrons behaved just like the planets in our solar system did then all kinds of problems arose. And by this time it was well known that electrons confined themselves to a small number of fixed "orbitals".
Electron orbitals were quantized in a way that planetary orbits were not. Schrodinger widened the gulf. He considered the wave nature of electrons and decided they did not travel in circular "planetary" orbits. He decided further that they didn't even have a fixed position in the way a planet orbiting the Sun does.
He could get things to work by focusing on the wavelength that de Broglie had calculated for the electron. He went on to come up with a whole "wave mechanics" to explain all this. Well, "explain" is not the right word. But what he did do was come up with a way to make calculations that got the right answer.
But trying to model the "reality" his equations described turned out to be a fools errand. There just wasn't a "planets orbiting the sun" (or any other kind of) model that could be created that matched either the equations or the reality.
Physics and much of science had made great progress by developing models and then using them to guide their exploration. But several decades of "quantum" this and that, now followed by "wave equations" and other developments left scientists feeling extremely uneasy. They did not want to be cut loose from their models.
But requiring a model that seemed anything like day to day experience was holding things back. At the time this concern was confined primarily to the physics community. Since then it has spread to all corners of society. It is one of the things driving the modern anti-science movement.
So Schrodinger dealt a blow to the idea that an electron was this tiny marble orbiting the nucleus like a small planet. Heisenberg proceeded to demolish this simple, comfortable model. He developed something called "matrix mechanics" do describe what was going on.
He replaced the simple "variable" of an Algebraic (or Calculus or other branches of higher mathematics) with a matrix. The "X" of "X + Y = Z" fame wasn't a number. It was a grid of numbers. The form looked the same. You still saw terms connected with operators like plus or minus or times or whatever. But a term had internal structure.
Mathematicians had worked out the "mathematics of matrixes" long since, if you restricted yourself to regular algebra. This new mathematics required much higher forms of math. But the techniques developed for dealing with matrixes in an algebraic situation could and were extended to provide techniques for dealing with this new regime. It was fiendishly difficult but it could be done. And Heisenberg showed how it should be done for his formulation.
I'm going to spare you from delving into any of this. But there is a consequence of Heisenberg's matrix mechanics that we have all become more or less familiar with. That's his "Uncertainty Principle".
Asimov, master explainer that he is, starts in the right place. Heisenberg concerned himself with a seemingly simple question: "where's the electron right now?" The obvious way to find out is to shine a light on it and look for it. But what, exactly does that mean? And what would you see if that's what you did?
Electrons are small and light. That means they can easily be pushed around by something like the photons that light is composed of. So, the very process of trying to find out where the electron is inevitably changes its position. In short, the process of trying to observe an electron introduces some uncertainty in its location. You can never be truly sure exactly where it is.
That's where Asimov leaves things. It is a "natural" explanation that doesn't give anybody any trouble. But Asimov is doing us a disservice. What Heisenberg really believed, and what physicists now also believe, is not that there was some technical limitation that rendered positions uncertain.
Rather, Heisenberg believed that the position of an electron is inherently uncertain. Even if you could come up with a clever experimental technique that would permit measuring the location of an electron without bouncing something off of it, that wouldn't be enough. Even though you avoided changing its location by bouncing your probe off of it, you would still find that you couldn't nail the exact location of the electron down.
Asimov then goes on to briefly discuss the philosophical ramifications of this uncertainty. They are widespread and profound. Religion has been debating the subject of "free will" for millennia.
If the world is "deterministic", then you can predict all future events with complete accuracy if only you know the present to a high enough degree of precision. In a deterministic universe free will is literally impossible. Instead, "what will be, will be."
If there is no free will then the concept of sin makes no sense. If you murder someone but the laws of the universe (determinism) tell us that you had no choice then it's not your fault. Since you had no choice in the matter you do not deserve to be punished. Uncertainty provides a scientific justification for believing that free will is possible.
Uncertainty means that we can't know everything. But that begs the question: can we know anything? I could go on. But lots of books have been written on all this. And some of the people who wrote them are a lot smarter than I am.
Asimov leaves us here on the verge of Quantum Mechanics. So he and we will now move on to a new chapter, "The Machine", and a new topic, "Fire and Steam".
With this section we move from the weirdness of Quantum Mechanics, or at least the run up to it, and to the world of backyard mechanics. As Asimov observes, "[t]he whole civilization of mankind has been built on finding new sources of energy and harnessing them in more efficient and sophisticated ways".
He blithely continues from there as if "onward and upward" was all there was to it. I'll have something to say about this later. In the mean time, "we shall make a rapid survey of the engines, machines, and instruments" that have made this ascent possible.
The first of these is fire, "discovered" perhaps a half a million years ago according to Asimov. Current suggestive but not definitive evidence for the use of fire puts the date at about 1.4 million years ago. The oldest date for which we currently have incontrovertible evidence of human use of fire is 780,000 years ago.
Fire provides warmth. But it also enables cooked food to become a diet staple. Cooking not only warms food. It also chemically modifies it in ways that make otherwise inedible food edible. There are numerous other benefits to cooked food.
Fire, or more broadly, the release of chemical energy, provides what Asimov describes as "a practically limitless supply of energy". But, as an energy supply, it has many limitations. This is particularly true in the pre-industrial age. In this period mankind was pretty much limited to burning wood.
Burning wood provides more energy than human muscle power can provide. But, by modern measures, the amount of available energy is limited. And in a pre-industrial world it can't be used for much beyond supplying heat for warmth and for cooking. Oh, and the development of the lamp did enable it to be used to provide a modest amount of lighting.
Early efforts to look beyond wood (and, to a modest extent, fats and oils burned in lamps and stoves) first began in the "Dark Ages", the medieval period in Europe. There some people discovered that coal could be burned.
The military necessity of making high quality swords and other military devices led to an interest in high temperature metallurgy. Coal made access to high temperature furnaces easier. And that led to a move from iron to steel in weaponry. But coal remained confined to this niche use for a long time.
The medieval period also saw the introduction of wind and water driven "mills" to grind grains and for other purposes. Asimov also notes that this period in time saw the introduction of explosives (a semi-legitimate adjunct to his subject), and the development of the magnetic compass (an illegitimate adjunct as it was not a method for harnessing significant amounts of energy). Finally, he notes the use of coal and other energy sources to produce glass started during this period. Very little glass was made before the industrial age so I will grant the subject only a very modest degree of legitimacy as an appropriate adjunct.
But almost all inanimate energy use was then derived from the burning of wood for heating and cooking purposes. And Asimov doesn't even mention the harnessing of wind power for transportation uses by means of sails. Using sails to power boats actually precedes the medieval period by perhaps a thousand years.
Asimov gives a brief history of the use of explosives in a military context, noting that cannons featured prominently in the Battle of Crecy in 1348 and were in general use from then on. He then takes a detour into movable type. That was an important development, Guttenberg's Bibles were printed in about 1450, but made little difference in the availability or use of "fire and steam". (He also notes the importance of the nearly simultaneous replacement of parchment with paper as being an important development.) He then returns to the subject at hand.
At the end of the seventeenth century attention was paid to the problem of removing water from mines. The obvious solution is the pump. This presented two subproblems. The first one was the most obvious. Where do you get the energy to run the pump from? The most obvious solutions were manpower and animal power. Both had limitations.
The second one was the odd fact that you could suck water up at most 33 feet. Why? Asimov doesn't address this issue here because he already talked about it elsewhere. See http://sigma5.blogspot.com/2017/04/50-years-of-science-part-8.html for my discussion of his section on "The Atmosphere". Water can only be pulled up 33 feet because that's how tall a column of water needs to be to balance out the pressure of the atmosphere at sea level (about 15 pounds per square inch). Back to pumps.
One idea was to fill a chamber with steam then pour some cold water in. This would cause the steam to condense. That would leave a vacuum behind which could be used to suck the water up out of the mine. The first one to get a "steam engine" to work was Savery. (BTW, at the time "engine" just meant any kind of clever device.) Savery's engine worked. But it was dangerous and inefficient.
But this is often true. Someone figures out how to do something "at all". The first device works but not very well. Then others can see what he did and refine it so that it works better. Soon the child or grandchild or great grandchild of the original device works very well. And that's what happened in this case.
Newcomen came along less than a decade later with his "new and improved" steam engine in 1698. It was far less dangerous and a lot more efficient. But it still didn't work all that well. Newcomen's design was state of the art for more than 60 years. But then Watt came along and came up with the first relatively efficient steam engine. That's why we associate Watt with the invention of the steam engine.
He also gets most of the credit because Watt engines were used for something other than pumping water out of mines. In 1787 an American, Fitch, put a Watt engine in a boat and made it move. The boat was a success from a technical point of view but a failure from a financial point of view. So we have forgotten Fitch and remember Fulton instead.
The "Clairmont", Fulton's steam powered ship, was a success in every way. In the 1830's, less than thirty years later, steam powered ships were routinely crossing the Atlantic Ocean. During this same period the "screw propeller" replaced "sidewheel" and "sternwheel" paddlewheels as the method of propulsion.
In parallel with the advent of waterborne steam propulsion came the advent of steam powered land vehicles. Stephenson built the first of what we now call "steam locomotives" to power what we now call a railroad train in 1814. Designs improved rapidly. As a result the first "transcontinental railroad" was in operation in the US by 1869.
Steam power created the ability to travel by sea more quickly and more comfortably that had heretofore been possible using wind power. Railroads were quicker, more comfortable, and cheaper, than traveling in a stagecoach powered by horses. The steam engine revolutionized transportation by making it possible to apply far more energy in a far more controlled fashion than had bee possible prior to its invention.
I could go into my discussion of the whole "onward and upward" business when it comes to energy consumption here. But I am going to leave that discussion for a later day and end here.
Monday, May 25, 2020
Tuesday, May 5, 2020
Computer vs. Sudoku
I'm in lockdown mode, just like everybody else. So what's a body to do to pass the time pleasantly? If you are this particular body you decide to write a computer program. I haven't gotten paid to write a computer program in more than a decade. And I haven't written one in a couple of years. It's time to dust off the old skills and take them out for a drive once again, or so I told myself.
If you are going to write a computer program it needs to do something. Otherwise, there is no point. So I'm sitting around one day when I thought "it would be fun to write a computer program to solve Sudoku puzzles". And with that I was off.
A little background. Sudoku puzzles became all the rage a few years ago. When they first showed up on the "puzzle" page of the local paper I took a look. It seemed interesting so I gave it a shot. I was a total failure. I could see how you might go about solving one. But I had neither the skills nor the patience to be successful.
I could see what needed to be done. But scanning here and there looking for a good next move wasn't something I had the patience nor the eyeball to be successful at. But I could see how it could be done, in theory.
Now what I am not good at is, in this case, what a computer is very good at. Computers have infinite amounts of patience and are very good at detail. If you add in my analytical ability you have everything you need. And to my eye, the problem was difficult enough to be interesting without being so difficult as to demand more effort than I was interested in expending. So let's look at the rules of the game.
A Sudoku puzzles consists of a 9 x 9 grid. Each box contains either a number or an empty square. You solve the puzzle by filling all the squares with numbers. But what constitutes a "legal" move? That's pretty simple too. Each square must end up with one of the digits running from one to nine. That's extremely simple. It is the additional constraints that make things interesting.
You can't duplicate numbers. There are nine squares in the first column. If there is a "5" in one square in the column then none of the other squares in the same column can contain a "5". In the end everything just fits. There are nine squares in a column and 9 digits. So it's a matter of putting the digits - one through nine - into the squares in the right order. And, if that was it, then the problem would be trivially simple.
But there is a similar row rule. There are nine squares in a row and nine digits. So it is again a matter of arranging all nine digits in the correct sequence so that each fills a square. So now things are more difficult but not all that difficult.
Imagine viewing the grid along the diagonal. In the first diagonal you put a "1". (There is only square in the first diagonal because it is up against a corner. In the next diagonal you put all "2"s. In the next, all "3's, and so on.
Once you have filled nine diagonals with "1" through "9" start over. fill the next diagonal with all "1"s and the one after that with all "2"s. Keep going and you will have a "solution" that meets the "no duplicates in a row" criteria while also meeting the "no duplicates in a column" criteria. So, to make things more interesting a third rule is added.
The 9 x 9 grid is divided into nine 3 x 3 sub-grids. The first sub-grid consists of rows 1-3 and columns 1-3. The second one consists of rows 1-3 but columns 4-6. When you are done you will have 9 sub-grids with the last one consisting of rows 7-9 and columns 7-9. Each sub-grid contains nine cells so you impose a "no duplicates" rule within each sub-grid. With this third rule the puzzle becomes hard but not impossible.
The way things work is that a grid is published. It has some but not all squares filled in. You are supposed to take it from there and figure out what number to put into each of the empty squares. Here's the starting position from a puzzle that was published in the local paper several weeks ago. (I have used white space to highlight the sub-grid boundaries):
Column: - 1 2 3 4 5 6 7 8 9
Row: 1 - * 1 8 * * 9 2 * *
Row: 2 - 4 * * * 3 5 7 * *
Row: 3 - 6 * 3 2 7 1 4 * *
Row: 4 - * 4 * * * * * 6 *
Row: 5 - * * 5 3 6 4 1 * *
Row: 6 - * 3 * * * * * 4 *
Row: 7 - * * 9 4 1 3 6 * 2
Row: 8 - * * 1 5 2 * * * 4
Row: 9 - * * 4 7 * 6 5 3 *
So what do we do next? Well, there's the brute force method. Row 1 - column 1 is empty ("*" denotes empty). We can try a "1" there and see what happens. That doesn't work because row 1 - column 2 already has a "1". But we can move on and try "2" and then "3" and so on. Then we can move on to the next empty square at row 1 - column 4 and do the same thing. After trying a bazillion combinations we will eventually hit on to a legal solution.
But, boy oh boy, will we have to try a lot of different combinations. Computers are very patient so this would eventually work. It is called a "brute force" method. You just try all the combinations until you find one that works. There are better ways.
And that was the one insight I developed about how to proceed. I came up with the idea of a "forced move". Look at square (1,4) - short for row 1 - column 4. If you work through all of the combinations then only move that works is "6". "6" is a forced move. Go ahead and check. You will see that 1-5 and 7-9 are all excluded by other squares that have already been filled in.
So what I had my program do was to look for forced moves. It boringly checked square (1,1) then (1,2) and so on. If the square was already filled it moved on. For each empty square it first tried "1", then "2", and so on up to "9". It counted the number of moves which were "legal", that didn't violate any of the constraints. I called this number LMC for "legal move count". The program moved along calculating the LMC for each empty square.
As it moved along it noted when it found a square whose LMC was lower than all the previous LMCs it had encountered. It remembered where it had found that move (and forgot what it had previously remembered about the old lowest LMC champ). And it remembered for that move the first (lowest - it tried 1 - 9 in that order) legal move it had found for that square. Finally, as soon as it found a square with an LMC of 1 it quit looking. LMC=1 squares are forced move squares.
So the program worked by first playing all the "setup" moves, those moves printed in the paper. Once that was done it tried the same thing over and over. It tried to find the square with the lowest LMC. It did this by scanning the entire grid as I have outlined above. It stopped and "played" the move if it found a square with an LMC of 1.
And if it got to the end, having scanned all 81 squares, and had found no empty squares then it said "I'm done". And for easy puzzles, that's it. It turns out that there is always at least one square with an LMC of 1, a forced move. The program finds it and plays it. Then it goes back to the top and starts a new scan. Eventually all the squares are full and the program is done. In the case of the puzzle above that looks like this:
Column: - 1 2 3 4 5 6 7 8 9
Row: 1 - 7 1 8 6 4 9 2 5 3
Row: 2 - 4 9 2 8 3 5 7 1 6
Row: 3 - 6 5 3 2 7 1 4 9 8
Row: 4 - 1 4 7 9 8 2 3 6 5
Row: 5 - 9 8 5 3 6 4 1 2 7
Row: 6 - 2 3 6 1 5 7 8 4 9
Row: 7 - 5 7 9 4 1 3 6 8 2
Row: 8 - 3 6 1 5 2 8 9 7 4
Row: 9 - 8 2 4 7 9 6 5 3 1
Remember, that as we fill in moves fewer and fewer moves remain valid. When we made our move of placing a "6" in square (1,4) that rendered "6" as an invalid move for any other square in row 1, column 4, and the sub-grid consisting of rows 1-3 and columns 4-6.
In solving the above puzzle the computer first places a "6" at square (1,4). For its next move it places a "4" at square (1,5). For its third move it places a "5" at square (1,8). It continues to proceed in this manner for move after move until it finally places a "1" in square (9,9). On each fresh move it is able to find a square with an LMC of 1. If you have a good enough eye and enough patience, you can too.
But what if the puzzle is harder? Then what? Well, the program is on the lookout for things going wrong. What if it finds an empty square for which there are no legal moves? It sounds like the puzzle has no solution. But there is another possibility.
In the easy puzzle listed above at every stage it is possible to find a forced move, a square with an LMC of 1. But that is not true when it comes to more difficult puzzles. With more difficult puzzles some scans may not turn up a square with an LMC of 1.
Remember, what the program actually does is to look for the square with the lowest LMC. It is certainly true that we don't want to bother with squares that have an LMC of 2 or more if we can find a different square with an LMC of 1.
But with more difficult puzzles sometimes a scan of all the unused squares in the puzzle does not turn up one with an LMC of 1. In that case the program just goes with a square with the lowest LMC it found.
In all the puzzles I have looked at the program invariably finds a square with an LMC of 2 if it can't find a square with an LMC of 1. But the program can deal with situations where the lowest LMC it finds is higher. Here's how that works.
If, on a scan the lowest LMC that is encountered is higher than 1, then the program selects the first square it encountered with that LMC, whatever it is. It plays that square and "guesses" whatever the lowest legal move is. It then goes on to find the next move. If we get to the end and have found a valid solution, hurray! We won.
But that may not happen. We may end up encountering a square that now has no valid moves. That's where a process that is easy for a computer to do and often hard for a person to do comes into play. We don't give up. We do what's called in the computer game "backing off". So how does that work?
As things are going along the computer keeps track of every move it has made. And it keeps track of the order they have been made in. And it remembers the LMC of each move.
Now some moves are special. They are the moves that were used to load the grid with the "setup", the initial configuration printed in the newspaper. These moves are flagged as "s" for setup moves. Later moves are flagged as "n" for normal moves. The first several moves are "s" moves. After that, the moves are all "n" moves.
So when a problem (no legal move) is detected here's what happens. The first thing that happens is that the move we were trying to make is abandoned. All trace of its existence is erased. Then the last move on the "queue" (the data structure used to keep track of moves) is examined. If it is an "s" move then the puzzle is unsolvable and it's time to quit. But it should be an "n" move.
The LMC of the move is examined. If it's 1 then the move is "backed off". All evidence that the move was every made is erased. Then we go back and examine the next oldest move to see what we find.
If, however, the LMC is greater than 1 there is something we can do. We can take a different "fork in the road". Here we take advantage of the fact that we always try the lowest legal value first. Let's say the LMC of the move is 2 and the value we used was "4". That means that besides "4" there should be another move that is higher than "4" that is also legal.
We go looking for it. Let's say it is "6". We then change the move to use "6" instead of "4". We also reduce the LMC by 1. In our example, the LMC is now 1 so, if the "back off" logic again reaches this point, then it would back the move off and keep looking. If perchance the LMC had been 3 it is now 2. So, if we later reach this point, then we can again look for a legal move that is higher than "6".
It is possible, at least theoretically, that we won't be able to find a higher legal move. But that means that the program has screwed up and it is time to look for code to fix.
But if all goes as it should we back off until we find a fork in the road. Then we go down a different fork. Once we've done that we return to business as usual. We jump back in the top and use the usual code to go looking for a move with an LMC of 1 to add onto the list of moves right after the one we ended up modifying.
It may be necessary to do this "two steps forward, one step back" dance several times. And it is common to end up putting the same LMC = 1 move on the stack only to later have to back it off as we look for an "LMC higher than 1" fork in the road. Then, still later after we have taken that different path, we end up just adding the same move back onto the move list again. But, after a certain amount of "toing" and "froing", we should end up with a set of legal moves that ends up filling the grid up completely.
So that's the rest of the logic my computer program uses to solve Sudoku puzzles. It has solved all of the puzzles I have presented it with successfully. And it solves them instantly.
It takes me a minute or so for me to create a file with the setup moves in it. It takes the computer a second or so to print out the "before" (setup) and "after" (solution) grids. But solving the puzzle is essentially instantaneous. Computers are very good at doing a lot of this sort of thing extremely quickly.
And with that, let me give you some background on Sudoku. It is part of a group of mathematical puzzles called "Latin Squares". They have been studied extensively for a period going back more than a hundred years. And it turns out that the origins of Sudoku also go back more than a hundred years.
A puzzle similar to Sudoku was first published in a French newspaper in 1892. Another French newspaper published a puzzle that was almost identical to Sudoku in 1895. About twenty years later they went out of fashion and stayed that way for a long time.
Then a puzzle identical to Sudoku was published in a Dell puzzle magazine in 1979. There it was called "Number Place". (Sudoku puzzles are regularly but infrequently called Number Place to this day.)
It was likely invented by a man named Howard Garnes. Mr. Garns was well known at the time in puzzle creation circles. No one knows if he was familiar with the earlier French puzzles but he was probably very familiar with Latin Squares. He died in 1989 before Sudoku became a giant phenomenon.
The Japanese attribution is not completely unreasonable. That's where the puzzle first became widely popular. It was introduced in a Japanese newspaper in 1984 as "Suji wa dokushin ni Kagiru". This unwieldy name was quickly shortened to Sudoku. It quickly developed a large and loyal following in Japan. So. it soon could be found in many newspapers there.
In 1997 Hong Kong judge Wayne Gould saw a Sudoku puzzle in a Japanese bookshop. He spent six years developing a computer program to quickly crank out new puzzles. The task he set out for himself was much more difficult than the one one I tackled. But, once he had it working, the result was a nearly inexhaustible supply of new puzzles. And they could be made available inexpensively.
He then sold the Times of London newspaper on the idea of regularly publishing Sudoku puzzles. They first published one in 2004. The first Sudoku puzzle appeared in a US newspaper later that same year. And the rest, as they say, is history.
Sudoku has attracted a lot of attention from both professional and amateur mathematicians. They had long been studying various kinds of Latin Squares when it came along. Sudoku fit right in.
So a lot is known about the mathematics behind the game but I am going to spare you all of it. I am also going to spare you from a discussion of the many variants of the game that have been developed in response to its popularity. If you care, the rich literature on this subject is easy to find.
As for me, I have moved on but not very far. There is a puzzle called Numbrix that newspaper columnist Marilyn vos Savant champions.
As a programming challenge, it looks very similar to Sudoku. So I am now writing a program to solve Numbrix puzzles. I expect to be able to reuse a lot of the code I wrote for my Sudoku program.
I am making slow progress. But this is because I'm not putting that many hours into it. It is, after all, a time waster. I only work on it when I have time to waste.
So that's what I am now up to.
If you are going to write a computer program it needs to do something. Otherwise, there is no point. So I'm sitting around one day when I thought "it would be fun to write a computer program to solve Sudoku puzzles". And with that I was off.
A little background. Sudoku puzzles became all the rage a few years ago. When they first showed up on the "puzzle" page of the local paper I took a look. It seemed interesting so I gave it a shot. I was a total failure. I could see how you might go about solving one. But I had neither the skills nor the patience to be successful.
I could see what needed to be done. But scanning here and there looking for a good next move wasn't something I had the patience nor the eyeball to be successful at. But I could see how it could be done, in theory.
Now what I am not good at is, in this case, what a computer is very good at. Computers have infinite amounts of patience and are very good at detail. If you add in my analytical ability you have everything you need. And to my eye, the problem was difficult enough to be interesting without being so difficult as to demand more effort than I was interested in expending. So let's look at the rules of the game.
A Sudoku puzzles consists of a 9 x 9 grid. Each box contains either a number or an empty square. You solve the puzzle by filling all the squares with numbers. But what constitutes a "legal" move? That's pretty simple too. Each square must end up with one of the digits running from one to nine. That's extremely simple. It is the additional constraints that make things interesting.
You can't duplicate numbers. There are nine squares in the first column. If there is a "5" in one square in the column then none of the other squares in the same column can contain a "5". In the end everything just fits. There are nine squares in a column and 9 digits. So it's a matter of putting the digits - one through nine - into the squares in the right order. And, if that was it, then the problem would be trivially simple.
But there is a similar row rule. There are nine squares in a row and nine digits. So it is again a matter of arranging all nine digits in the correct sequence so that each fills a square. So now things are more difficult but not all that difficult.
Imagine viewing the grid along the diagonal. In the first diagonal you put a "1". (There is only square in the first diagonal because it is up against a corner. In the next diagonal you put all "2"s. In the next, all "3's, and so on.
Once you have filled nine diagonals with "1" through "9" start over. fill the next diagonal with all "1"s and the one after that with all "2"s. Keep going and you will have a "solution" that meets the "no duplicates in a row" criteria while also meeting the "no duplicates in a column" criteria. So, to make things more interesting a third rule is added.
The 9 x 9 grid is divided into nine 3 x 3 sub-grids. The first sub-grid consists of rows 1-3 and columns 1-3. The second one consists of rows 1-3 but columns 4-6. When you are done you will have 9 sub-grids with the last one consisting of rows 7-9 and columns 7-9. Each sub-grid contains nine cells so you impose a "no duplicates" rule within each sub-grid. With this third rule the puzzle becomes hard but not impossible.
The way things work is that a grid is published. It has some but not all squares filled in. You are supposed to take it from there and figure out what number to put into each of the empty squares. Here's the starting position from a puzzle that was published in the local paper several weeks ago. (I have used white space to highlight the sub-grid boundaries):
Column: - 1 2 3 4 5 6 7 8 9
Row: 1 - * 1 8 * * 9 2 * *
Row: 2 - 4 * * * 3 5 7 * *
Row: 3 - 6 * 3 2 7 1 4 * *
Row: 4 - * 4 * * * * * 6 *
Row: 5 - * * 5 3 6 4 1 * *
Row: 6 - * 3 * * * * * 4 *
Row: 7 - * * 9 4 1 3 6 * 2
Row: 8 - * * 1 5 2 * * * 4
Row: 9 - * * 4 7 * 6 5 3 *
So what do we do next? Well, there's the brute force method. Row 1 - column 1 is empty ("*" denotes empty). We can try a "1" there and see what happens. That doesn't work because row 1 - column 2 already has a "1". But we can move on and try "2" and then "3" and so on. Then we can move on to the next empty square at row 1 - column 4 and do the same thing. After trying a bazillion combinations we will eventually hit on to a legal solution.
But, boy oh boy, will we have to try a lot of different combinations. Computers are very patient so this would eventually work. It is called a "brute force" method. You just try all the combinations until you find one that works. There are better ways.
And that was the one insight I developed about how to proceed. I came up with the idea of a "forced move". Look at square (1,4) - short for row 1 - column 4. If you work through all of the combinations then only move that works is "6". "6" is a forced move. Go ahead and check. You will see that 1-5 and 7-9 are all excluded by other squares that have already been filled in.
So what I had my program do was to look for forced moves. It boringly checked square (1,1) then (1,2) and so on. If the square was already filled it moved on. For each empty square it first tried "1", then "2", and so on up to "9". It counted the number of moves which were "legal", that didn't violate any of the constraints. I called this number LMC for "legal move count". The program moved along calculating the LMC for each empty square.
As it moved along it noted when it found a square whose LMC was lower than all the previous LMCs it had encountered. It remembered where it had found that move (and forgot what it had previously remembered about the old lowest LMC champ). And it remembered for that move the first (lowest - it tried 1 - 9 in that order) legal move it had found for that square. Finally, as soon as it found a square with an LMC of 1 it quit looking. LMC=1 squares are forced move squares.
So the program worked by first playing all the "setup" moves, those moves printed in the paper. Once that was done it tried the same thing over and over. It tried to find the square with the lowest LMC. It did this by scanning the entire grid as I have outlined above. It stopped and "played" the move if it found a square with an LMC of 1.
And if it got to the end, having scanned all 81 squares, and had found no empty squares then it said "I'm done". And for easy puzzles, that's it. It turns out that there is always at least one square with an LMC of 1, a forced move. The program finds it and plays it. Then it goes back to the top and starts a new scan. Eventually all the squares are full and the program is done. In the case of the puzzle above that looks like this:
Column: - 1 2 3 4 5 6 7 8 9
Row: 1 - 7 1 8 6 4 9 2 5 3
Row: 2 - 4 9 2 8 3 5 7 1 6
Row: 3 - 6 5 3 2 7 1 4 9 8
Row: 4 - 1 4 7 9 8 2 3 6 5
Row: 5 - 9 8 5 3 6 4 1 2 7
Row: 6 - 2 3 6 1 5 7 8 4 9
Row: 7 - 5 7 9 4 1 3 6 8 2
Row: 8 - 3 6 1 5 2 8 9 7 4
Row: 9 - 8 2 4 7 9 6 5 3 1
Remember, that as we fill in moves fewer and fewer moves remain valid. When we made our move of placing a "6" in square (1,4) that rendered "6" as an invalid move for any other square in row 1, column 4, and the sub-grid consisting of rows 1-3 and columns 4-6.
In solving the above puzzle the computer first places a "6" at square (1,4). For its next move it places a "4" at square (1,5). For its third move it places a "5" at square (1,8). It continues to proceed in this manner for move after move until it finally places a "1" in square (9,9). On each fresh move it is able to find a square with an LMC of 1. If you have a good enough eye and enough patience, you can too.
But what if the puzzle is harder? Then what? Well, the program is on the lookout for things going wrong. What if it finds an empty square for which there are no legal moves? It sounds like the puzzle has no solution. But there is another possibility.
In the easy puzzle listed above at every stage it is possible to find a forced move, a square with an LMC of 1. But that is not true when it comes to more difficult puzzles. With more difficult puzzles some scans may not turn up a square with an LMC of 1.
Remember, what the program actually does is to look for the square with the lowest LMC. It is certainly true that we don't want to bother with squares that have an LMC of 2 or more if we can find a different square with an LMC of 1.
But with more difficult puzzles sometimes a scan of all the unused squares in the puzzle does not turn up one with an LMC of 1. In that case the program just goes with a square with the lowest LMC it found.
In all the puzzles I have looked at the program invariably finds a square with an LMC of 2 if it can't find a square with an LMC of 1. But the program can deal with situations where the lowest LMC it finds is higher. Here's how that works.
If, on a scan the lowest LMC that is encountered is higher than 1, then the program selects the first square it encountered with that LMC, whatever it is. It plays that square and "guesses" whatever the lowest legal move is. It then goes on to find the next move. If we get to the end and have found a valid solution, hurray! We won.
But that may not happen. We may end up encountering a square that now has no valid moves. That's where a process that is easy for a computer to do and often hard for a person to do comes into play. We don't give up. We do what's called in the computer game "backing off". So how does that work?
As things are going along the computer keeps track of every move it has made. And it keeps track of the order they have been made in. And it remembers the LMC of each move.
Now some moves are special. They are the moves that were used to load the grid with the "setup", the initial configuration printed in the newspaper. These moves are flagged as "s" for setup moves. Later moves are flagged as "n" for normal moves. The first several moves are "s" moves. After that, the moves are all "n" moves.
So when a problem (no legal move) is detected here's what happens. The first thing that happens is that the move we were trying to make is abandoned. All trace of its existence is erased. Then the last move on the "queue" (the data structure used to keep track of moves) is examined. If it is an "s" move then the puzzle is unsolvable and it's time to quit. But it should be an "n" move.
The LMC of the move is examined. If it's 1 then the move is "backed off". All evidence that the move was every made is erased. Then we go back and examine the next oldest move to see what we find.
If, however, the LMC is greater than 1 there is something we can do. We can take a different "fork in the road". Here we take advantage of the fact that we always try the lowest legal value first. Let's say the LMC of the move is 2 and the value we used was "4". That means that besides "4" there should be another move that is higher than "4" that is also legal.
We go looking for it. Let's say it is "6". We then change the move to use "6" instead of "4". We also reduce the LMC by 1. In our example, the LMC is now 1 so, if the "back off" logic again reaches this point, then it would back the move off and keep looking. If perchance the LMC had been 3 it is now 2. So, if we later reach this point, then we can again look for a legal move that is higher than "6".
It is possible, at least theoretically, that we won't be able to find a higher legal move. But that means that the program has screwed up and it is time to look for code to fix.
But if all goes as it should we back off until we find a fork in the road. Then we go down a different fork. Once we've done that we return to business as usual. We jump back in the top and use the usual code to go looking for a move with an LMC of 1 to add onto the list of moves right after the one we ended up modifying.
It may be necessary to do this "two steps forward, one step back" dance several times. And it is common to end up putting the same LMC = 1 move on the stack only to later have to back it off as we look for an "LMC higher than 1" fork in the road. Then, still later after we have taken that different path, we end up just adding the same move back onto the move list again. But, after a certain amount of "toing" and "froing", we should end up with a set of legal moves that ends up filling the grid up completely.
So that's the rest of the logic my computer program uses to solve Sudoku puzzles. It has solved all of the puzzles I have presented it with successfully. And it solves them instantly.
It takes me a minute or so for me to create a file with the setup moves in it. It takes the computer a second or so to print out the "before" (setup) and "after" (solution) grids. But solving the puzzle is essentially instantaneous. Computers are very good at doing a lot of this sort of thing extremely quickly.
And with that, let me give you some background on Sudoku. It is part of a group of mathematical puzzles called "Latin Squares". They have been studied extensively for a period going back more than a hundred years. And it turns out that the origins of Sudoku also go back more than a hundred years.
A puzzle similar to Sudoku was first published in a French newspaper in 1892. Another French newspaper published a puzzle that was almost identical to Sudoku in 1895. About twenty years later they went out of fashion and stayed that way for a long time.
Then a puzzle identical to Sudoku was published in a Dell puzzle magazine in 1979. There it was called "Number Place". (Sudoku puzzles are regularly but infrequently called Number Place to this day.)
It was likely invented by a man named Howard Garnes. Mr. Garns was well known at the time in puzzle creation circles. No one knows if he was familiar with the earlier French puzzles but he was probably very familiar with Latin Squares. He died in 1989 before Sudoku became a giant phenomenon.
The Japanese attribution is not completely unreasonable. That's where the puzzle first became widely popular. It was introduced in a Japanese newspaper in 1984 as "Suji wa dokushin ni Kagiru". This unwieldy name was quickly shortened to Sudoku. It quickly developed a large and loyal following in Japan. So. it soon could be found in many newspapers there.
In 1997 Hong Kong judge Wayne Gould saw a Sudoku puzzle in a Japanese bookshop. He spent six years developing a computer program to quickly crank out new puzzles. The task he set out for himself was much more difficult than the one one I tackled. But, once he had it working, the result was a nearly inexhaustible supply of new puzzles. And they could be made available inexpensively.
He then sold the Times of London newspaper on the idea of regularly publishing Sudoku puzzles. They first published one in 2004. The first Sudoku puzzle appeared in a US newspaper later that same year. And the rest, as they say, is history.
Sudoku has attracted a lot of attention from both professional and amateur mathematicians. They had long been studying various kinds of Latin Squares when it came along. Sudoku fit right in.
So a lot is known about the mathematics behind the game but I am going to spare you all of it. I am also going to spare you from a discussion of the many variants of the game that have been developed in response to its popularity. If you care, the rich literature on this subject is easy to find.
As for me, I have moved on but not very far. There is a puzzle called Numbrix that newspaper columnist Marilyn vos Savant champions.
As a programming challenge, it looks very similar to Sudoku. So I am now writing a program to solve Numbrix puzzles. I expect to be able to reuse a lot of the code I wrote for my Sudoku program.
I am making slow progress. But this is because I'm not putting that many hours into it. It is, after all, a time waster. I only work on it when I have time to waste.
So that's what I am now up to.
Subscribe to:
Posts (Atom)