Of course, this is for a nine-by-nine. There is nothing intrinsic to the sudoku concept that requires a nine-by-nine matrix, as far as I know. That’s just the size that utilizes the non-zero digits. Smaller ones would just leave out the upper numbers, and larger ones could continue by using letters, as in hexadecimal (though they would get increasingly tough to solve as size increased). People think that sudoku is about math because it has numbers in it, but it’s really just a logic puzzle. It doesn’t have to use numbers at all, but everyone knows them, so they make handy symbols. You could just as well use mah-jong tiles, or animals for a kid’s version.
10 thoughts on “The Minimum Sudoku Problem”
Comments are closed.
All real math is a logic puzzle.
You could just as well use mah-jong tiles, or animals for a kid’s version.
That’s simply one of many symmetries in the puzzle.
I’m not sure I quite get the distinction you are trying to make between “logic” and “mathematics”. Isn’t logic a subset of mathematics? For that matter, it seems that you are confusing the method of solving a given puzzle from the analysis of the class of puzzles. If you read the McGuire paper, I think you have to agree that some fairly sophisticated mathematics went into the proof that 17 clues are required. Like Rubik’s cube, the puzzle doesn’t necessarily require mathematics (or even logic) to solve, but classifying solutions to the puzzle does. That’s why the puzzle is of interest to mathematicians.
Frankly, I think both sudoku and Rubik’s cube ought to be of interest to psychologists, too, as the mental processes involved are curious in themselves. Although you can program a computer to solve a given sudoku or Rubik’s cube configuration quickly, I’m fairly confident that humans don’t solve puzzles the same way a good algorithm would….
No, logic isn’t a “subset” of math, but math requires the use of logic. Logic is a discipline in itself. When I say it’s not math, I mean that it doesn’t involve calculation, and doesn’t even provide the symbolic ability to do so (as algebra does). That’s one of the appeals of it to the math phobic — “there is no math involved.”
There is no arithmetic or algebraic calculation but there is great deal of calculation by application of recursive rules.
Depends on the human. I’ve never gone beyond the level-by-level method for the cube because it is “easy” to memorize and always works. At 90 seconds, it won’t win any contests, but it gets the job done.
Yes, back in the day I learned a method for solving the cube and my times were under two minutes. In the case of the cube, I think the basic skill is pattern recognition rather than logic per se.
I have a method for solving Sudoku puzzles which basically targets a reduction of order, that is, I try to reduce the default chains of 3×3 dof states to chains of 2×2 dof states. I find that once I have a second-order chain, I often have to check one or both states of the chain to see if one is excluded by the states of other chains. The process of selecting which chains to check seems to be an intuitive one, rather than a matter of logical deduction. And because I never write down notes in the cells, as many do, Sudoku seems to be a good memory-building exercise….
Very much agreed, however I’m not entirely sure that the latter isn’t a subset of the former…
AFAICT, the “fun” of sudoku is the oscillation between procedural methods and intuitive ones, as you’ve described — there lies the “ah-ha!” factor not unlike that which draws people to whodunits and such. Honestly, the only niche it occupies in my life, however, is the dreaded trans-continental/global flight. My digest-sized $1.99 book from Walgreens represents a “lifetime buy” of the product.
And yes, obviously a lot of math went into solving this problem.
I’m thinking there must be applications in data compression and error checking.
Not as much math went into solving this problem as one might think–they merely brute-forced it. I could write a program for that in an afternoon, though I wouldn’t be able to devote the computer time to running it to completion.
I remember back in the 80s when I was a math grad student, after a visiting lecturer gave us an intro to Latin squares, someone remarked that there was a program running and expected to finish the next year that would settle whether there were any pairs of orthogonal Latin squares of order 10. A wag remarked that if it found any the researchers should be congratulated, but if it didn’t they should be severely punished, for wasting so much (then-precious) computer time demonstrating a result so unsurprising … and, of course, not providing a glimmer on WHY the design couldn’t exist.
I’ve always felt sudokus were more interesting when the regions could be arbitrary shapes, rather than squares. Relaxing that requirement makes them constructible for any size that I’ve tried, with as few as one clue per symbol.