Author Archives: dbrady

Sudoku: Math Is Hard, Let’s Go Shopping

4 Replies

I’ve been researching others’ techniques for generating sudoku puzzles, and I have come to the conclusion that nobody actually knows how to do it.

Seriously, if you Google for “generating sudoku puzzles”, most of the methods boil down to “randomly throw numbers at the board and see if it’s a sudoku”. Oh, there’s some cleverness you can do to try to intelligently preserve the randomness of a partially-complete sudoku puzzle (like not randomly putting a 9 into a column that already has one) but at the end of the day all of the solutions basically amount to bogosort.

I promised yesterday that I’d reveal the identity board math. I had planned a big reveal here with lots of mathy explanationing, but the math just isn’t that exotic. There’s a trick to it, but that’s about it. Here’s the math:

A Sudoku board of dimension n is n2xn2 digits, and has nxn sectors, each with n2 digits. Let’s write a function to find the number at position x, y on the board. The whole trick to my F(x,y) math is simply this: the numbers in every sector other than (0,0) are rotations or shifts of the numbers in sector (0,0).

Make sense? Here. The numbers in sector(0,0) are simply the digits 1..n2, arranged in a grid, so that’s easy:

F(x,y): y*n+x

And the math for every other sector is simply a selection into sector 0, 0. Specifically, for F(x,y) outside of sector (0,0), choose the F(x’,y’) IN sector 0,0 such that

x’ = ((x+y/n)%n

y’ = ((y+x/n)%n

So at the end of the day the whole function looks like this in ruby:

def idfx(x, y, n)
  if x<n && y<n
    y*n+x
  else
    idfx( ((x+y/n)%n, ((y+x/n)%n )
  end
end

I should point out that I am operating under the belief that a sudoku puzzle is like a Rubik’s Cube: that a set of transformations can be performed on a valid puzzle that leave the puzzle changed but always valid, and that you can turn any sudoku puzzle into any other sudoku puzzle via these transformations. If I am right, I can take my identity puzzle board and shuffle it using these transformations, and just like scrambling a Rubik’s Cube I will be left with a unique and interesting puzzle that is, most importantly, still valid.

I have proven the first half of my assumption–there are transformations that will change a sudoku without affecting its validity. What I haven’t proven is the second half. I cannot yet transform puzzles arbitrarily. It may not be possible at all, but right now I’m simply hoping that I don’t know enough transformations yet.

Sudoku: Creating Identity Boards

Leave a reply

I’m building a Sudoku generator. There’s just enough wicked math in there to make things interesting. One thing that caught my attention was that there is a sort of “identity” board that you should be able to build for any dimension of sudoku. For the standard 3×3 matrix, it looks like this:

+------+------+------+
| 1 2 3| 4 5 6| 7 8 9|
| 4 5 6| 7 8 9| 1 2 3|
| 7 8 9| 1 2 3| 4 5 6|
+------+------+------+
| 2 3 1| 5 6 4| 8 9 7|
| 5 6 4| 8 9 7| 2 3 1|
| 8 9 7| 2 3 1| 5 6 4|
+------+------+------+
| 3 1 2| 6 4 5| 9 7 8|
| 6 4 5| 9 7 8| 3 1 2|
| 9 7 8| 3 1 2| 6 4 5|
+------+------+------+

The way you write an identity board is this: You write the digits 1..9 in order in the top left sector and across the top line of the puzzle. If you look at it in terms of triplets, however, you build the top line by copying the 2nd triplet row (4 5 6) and then the 1st triplet row (7 8 9) across the top line.

The second row starts with (4 5 6) so you naturally continue with (7 8 9) in the next sector, and then roll around to the beginning to end with (1 2 3). The third row then follows naturally: (7 8 9) (1 2 3) (4 5 6).

You can build the entire board this way if you do the same thing vertically. Copying the first sector’s columns down the board’s first column, you get (1 4 7), (2 5 8), (3 6 9). Do this across the entire board and you end up with the completed puzzle.

The really neat part of this for me is that it works with any dimension of sudoku. For example, here’s a 2×2 and a 4×4 identity board built the same way:

+-----+-----+
| 0 1 | 2 3 |
| 2 3 | 0 1 |
+-----+-----+
| 1 0 | 3 2 |
| 3 2 | 1 0 |
+-----+-----+

+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 6 7 | 8 9 A B | C D E F | 0 1 2 3 |
| 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |
| C D E F | 0 1 2 3 | 4 5 6 7 | 8 9 A B |
+---------+---------+---------+---------+
| 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |
| 5 6 7 4 | 9 A B 8 | D E F C | 1 2 3 0 |
| 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |
| D E F C | 1 2 3 0 | 5 6 7 4 | 9 A B 8 |
+---------+---------+---------+---------+
| 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |
| 6 7 4 5 | A B 8 9 | E F C D | 2 3 0 1 |
| A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |
| E F C D | 2 3 0 1 | 6 7 4 5 | A B 8 9 |
+---------+---------+---------+---------+
| 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |
| 7 4 5 6 | B 8 9 A | F C D E | 3 0 1 2 |
| B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |
| F C D E | 3 0 1 2 | 7 4 5 6 | B 8 9 A |
+---------+---------+---------+---------+

The neatness of this pleased me, but when I tried to implement it in code it got hopelessly complicated very fast. On the drive home from work last week, I found an elegant mathematical function to produce this board. Can you guess it? I’ll post it tomorrow. If you can’t wait, dig around in my twitter feed–the entire function is less than 72 characters.

How to Install RSpec and RSpec-rails

1 Reply

I’ve done this so many times this week that I’m writing it down here where I can Google it later. What I’m looking for is the specific three commands you type to install rspec and rspec-rails as plugins into my rails project.

To find this data normally, I do this:

  1. Go to http://rspec.info because that’s the URL I can remember.
  2. Click on Spec::Rails in the menu bar.
  3. Click on Install in THAT menu bar.
  4. This takes you to a page that tells you that the Install instructions are no longer here, they’ve moved to http://wiki.github.com/dchelimsky/rspec/rails
  5. Hooray! THIS is the page you want to be at. Sure enough, scroll down to see

Okay, now… ready for the kicker? This documentation is ALSO out of date. (There’s a crash bug in tag 1.2.9 when you call model.should be_valid.) As of this writing, if you clone the rspec-rails repo and examine the tags, you will see that 1.3.2 is available. So here’s the updated command. For now.

ruby script/plugin install git://github.com/dchelimsky/rspec.git -r 'refs/tags/1.3.2'
ruby script/plugin install git://github.com/dchelimsky/rspec-rails.git -r 'refs/tags/1.3.2'
ruby script/generate rspec

…But lately I just get the latest and it seems to work:

ruby script/plugin install git://github.com/dchelimsky/rspec.git
ruby script/plugin install git://github.com/dchelimsky/rspec-rails.git
ruby script/generate rspec

Peer Ethos: Safety and Doubt

Leave a reply

I’ve had some GREAT feedback, online and off, about my Peer Ethos post. Thank you to everyone for the emails, tweets and comments.

Several new epiphanies resulted. The first is that the Peer Ethos is not just a single clique, or even the set of cliques you belong to. It is a universal ecosystem; it has tight niches and broad climes. James Britt rightly pointed out that there are differences between the Peer Ethos of your close friends and everyone on the internet. This triggered the epiphany that I was seeing BOTH close family and everybody on the internet as part of a universal ecosystem, and that practical meaning—the environmental conditions—change as you move around the landscape.

James says that some things that shouldn’t be shared with the Twitterverse can be shared with close family. I agree totally. There are some things that you can share with everybody, other things you should never share, and still more things that you should share only if the conditions in the peer ethos  are favorable.

I see two new dimensions of the peer ethos here: safety and doubt. The safety dimension is how supportive or antagonistic the peer ethos is at this point (“this point” meaning “your current audience”). Family and friends are very supportive because they want you to succeed; trolls and antagonists are destructive because want you to fail. The doubt dimension has nothing to do with the peer ethos and everything to do with yourself: it is simply an internal measure of your confidence that you will complete the task.

Here’s the interplay:

  • If you have high doubt, DO share your hopes and dreams with your family. Their nurturing support and love can encourage you to take that first risk.
  • Do NOT share your dreams with the internet until you’ve made them real: Trolls have a much harder time saying something is not possible when it’s just been done.
  • If you have low doubt, your goals are likely to be quite specific. Keep them to yourself, especially if telling your family won’t help you reach them!
  • You may, however, want to tell the world at large. Throwing your hat in the ring can be a huge motivator to drive you to live up to your word. Trolls may attack, but if you are confident in yourself these attacks do not discourage but rather come off sounding like “Oh yeah? Well, I dare you!“

It’s a tradeoff. Family will be forgiving if you fail; this can provide the safety to take the first step, but can also smother your urgency. For this reason I say that some ideas should never be shared until they are reality. If sharing them won’t help you but can definitely hurt you, why would you take the risk? On the other side, trolls will heap scorn upon you if you fall short, but can also stiffen your resolve to be true to your word.

Before talking about your goals, consider your audience and means of delivery. If your intention is a mere ember of hope, protect it. Share it only with those who will blow on it gently to help it grow. But if your intention is already burning fiercely, hold it up for the world to see! All the huffing of your detractors will do is fan the flames brighter. Perhaps spicy food is a better metaphor: you know when you want exciting, racy food and you know when you want filling, hearty fare; you also know what level of spice will ruin your meal and what level of blandness will suck out all the joy. So it is with sharing your intentions with your peer ethos: know when you need to be challenged by your peers and when you need to be supported by them.

The trick, ultimately, is not so much to be aware of the landscape of the peer ethos, but to be aware that the landscape even exists, and to choose to interact with it appropriately. Move around in it, find the appropriate audience, and share when it can help you move forward.

Peer Ethos

Leave a reply

I’ve been hit in the head repeatedly with some epiphanic lightning recently.

Recently Giles Bowkett blogged “Right now I’m stuck between two competing ideas. The ideas are superficially opposite, which bothers me a great deal, because I think they both contain some truth.”

The competing ideas come first from Derek Sivers: Shut up! Announcing your plans makes you less motivated to accomplish them.

and second from Dallas Travers: “If you sheepishly talk about your acting career only in safe environments after much poking and prodding, expect your goals to be reached just some of the time and only in safe environments.”

In an offline discussion, Giles wrote: peer pressure is important, although I’m searching for a new term for peer pressure, because it’s not really about pressure—it’s more like peer subconscious feedback.

There is a very clear delineation between these thoughts. What they share in common is a group of peers: people you would tell your intentions to, people you would announce your goals to. But why is one case bad and the other good?

Simple. In the first case, you have this crazy idea. You really need to go do something about it, and it’s ticking away in the back of your head, bugging you to get it done. When you blurt it out to your peer group, you are doing enough of something about it to scratch that itch, and you no longer need to follow through with the actual work. This is especially true of writers; you should never talk about a story idea until it’s written. An untold story fires the mind and drives you to write, but once you tell somebody your clever idea, you no longer have the need to tell your story. I have recently learned that I can’t talk about something on Twitter if I need to blog about it. Twitter is too short to really explore a topic, but once I tweet I no longer have any need to get the idea out there.

The second case is very different, however. When my wife and I decided to start the adoption process, we told everybody we knew. The process is long and discouraging, but every time we see friends they always ask us, “So… how’s the adoption coming along?” In the second case an expectation was created with our peer group that we need to satisfy. At best, outstanding, unmet expectations niggle away at the back of our minds incessantly; at worst they hook into our very tribal identities. We must satisfy or reject the expectations placed on us by others or go mad.

Giles, I have your word for you: Peer Ethos.

In rhetoric, the Greeks used “ethos” to describe “argumentation by character”. It has to do with how much we trust and accept the arguer. It’s very much a tribal identity thing, but here’s the interesting bit: ethos means “accustomed place” or “habitat”. It means psychological or social environment. So ethos, in argumentation, really just means whether or not you meet the cultural expectations of your listener.

I like this concept. It’s succinct, yet loaded with contextual information:

1. Participating in your peer ethos means that you understand that cultural expectations are placed upon you by your peers.

2. Because ethos also means character, the cultural expectations aren’t just about what you do, but about who you are. There is an incredibly strong motivator available to us here.

3. (For intermediate readers) Because you can choose your peers, you can change your peer ethos. You can examine the kind of character demands that your peer ethos places on you, and consciously seek out folks who will help you get where you need.

4. (For advanced readers) Because cultures are living ecosystems, and because you contribute to it as much as you draw from it, you can change the culture of your peers.

Peer ethos. I can’t begin to tell you how excited this makes me.

But wait! There’s more! (I seriously can’t begin to tell you how excited this makes me.)

Ethos is the same word we get “ethics” from. Ethics are the ethos of an entire culture: what is acceptable, what is good, what is right. This has always bothered me, because good and evil, right and wrong are unchanging concepts… yet our culture’s ethics have been continuously shifting and changing. 30 years ago it was ethical to smoke. 50 years ago it was ethical to castrate gays. 150 years ago it was ethical to inject heroin, own blacks, and shoot mormons.

Ethics, then, change over time. But do you see it? Do you SEE it? Our culture’s ethos draws from US as much as we draw from it!

Get busy, guys. Your peer ethos needs you.

Drive

Leave a reply

I like to synthesize ideas by taking disparate concepts, putting them in a bag and shaking it up. One difficulty that often arises is that in order for me to communicate these synthesized ideas, you need to be up to speed on the underlying concepts.

One big concept bouncing around in my head is the notion of what motivates us. I’m not talking about carrot-and-stick here, I’m talking about things that electrify our souls: things that bounce us out of bed in the morning, engage us joyfully all day and then keep up at night wondering about what the next day will bring.

Dan Pink has a pretty good insight into this. This animation is excellent, but incomplete; if you like it go to YouTube and watch the full version of his talk.

Math Joke 3

Leave a reply

Until last week I only knew 2 good math jokes. But then I heard this one! Without further ado, I hereby inflict it upon you:

An engineer, a physicist and a mathematician are chatting over lunch when the engineer says, “I just don’t get problems in higher dimensions. I mean, stuff in 3 dimensions I can visualize quite easily, but how do you visualize something with more?”

The physicist shrugs and says “You just have to imagine integrating. For example, if you have an object in three dimensions and integrate it over time, you have added a fourth dimension, time. It’s like taking an object’s position and integrating it to get the object’s velocity. You can do it again with time, to get the object’s acceleration, or with another dimension; each integration changes the units appropriately.”

The engineer thinks for a minute and says, “That’s okay for a few dimensions, but what about some of the really wacky stuff like 17 dimensions?”

The mathematician looks up and says, “Oh, that’s really easy, actually. Just imagine an n-dimensional space and set n=17.”

Math Joke 2

Leave a reply

Until last week I knew exactly 2 funny math jokes. Now I know three. I’ll post the third one tomorrow. Here’s the second one.

An engineer, a physicist, and a mathematician are asleep in a hotel when the curtains in each of their rooms catch fire. (Inexplicably, and all at the same time. Don’t ask why, it’s not important.)

The engineer wakes up and sees the fire, runs into the bathroom, fills the wastebasket with water, comes back and throws it on the fire. The fire goes out immediately, but there’s quite a bit of water damage.

The physicist wakes up and sees the fire, and pauses to estimate the rate at which the curtains are being consumed. He runs into the bathroom, fills the wastebasket with exactly 1.7 liters of water, comes back and carefully pours it on the fire. There’s a bit more fire and smoke damage due to the delay, but not a drop of water is spilled unnecessarily.

The mathematician wakes up and sees the fire, and pauses to contemplate the problem. Then he calmly walks into the bathroom. He turns on the faucet and strikes a match, then douses the match under the running water. He examines the match closely for a minute, then says, “Ah yes, this problem has a solution.” And then he goes back to bed.

Math Joke 1

Leave a reply

Until yesterday I knew exactly 2 funny math jokes. Now I know three. Here’s the first one.

Two math professors are arguing in a cafe about the education level of the average person. One insists that the average person has little grasp of mathematics beyond arithmetic. The other asserts that the average person knows at least rudimentary calculus. They pass their lunch in fruitless debate.

Finally, the first professor goes to the bathroom. The second professor waves the waitress over. “I am having a bit of a debate with my friend here. When he returns, I’ll ask you a question. If you answer with the exact phrase ‘one third x cubed’, I’ll leave a ten dollar tip.”

“Ten bucks? You bet,” says the waitress.

The first professor returns. The second professor announces, “Here, I’ll prove it to you.” He turns to the waitress and asks, “What is the integral of x squared?”

“One third x cubed,” replies the waitress. They both laugh and the second professor leaves the $10 tip.

As they’re leaving, the waitress mutters, “…plus a constant.”

Create Your Own Programming Language

2 Replies

I’ll write more about this soon. For now, you need to be writing your own programming language, and this book will show you how.


Click Here (Disclaimer: Marc is marketing his book through affiliates, and I make a commission if you buy this book.)

I’ve read this book and it’s amazing. I will post a full review soon, along with tidbits of the languages I’m creating. Short version: in a few hours you’ll write an interpreter; in a weekend you’ll write both a native compiler and a bytecode compiler. By next Monday your language will be running on the JVM. It really is that awesome.