Will Geulleu

 Will Geulleu

By Bobby Neal Winters

One day last week I was sitting in the faculty lounge and separating decks of playing cards that someone had shuffled together for some reason.  Doing tasks like this is my karma, both in the literal and the metaphorical sense.  I was working happily away when Will Geulleu, a well-known member of the faculty walked in.  

Will is not well-known because he’s a great teacher; he might very well be.  He’s not well known because he’s a careful researcher; I can’t say one way or the other.  

He is well-known, however, to be a card shark.

Will, looking at the cards in my hands and their state of disarray, smiled.

“I bet I can tell you exactly how many cards you have in your hands,” he said with a twinkle.

“I don’t bet,” I replied because indeed I don’t.  I remember, but I didn’t tell him, that line from “Guys and Dolls” about a card jumping from a deck and spitting cider in your ear.  “I don’t bet,” I repeated, “but I would be interested in you telling me how many cards I have.”

Will thought a spell before replying.

“Okay,” he finally replied, “but it will require effort on your part.  This is magic, but it comes at a cost.”

It was my turn to smile.  I don’t believe in magic anymore than I believe in taking someone else’s bet, but know I was curious to see how his game played out.

Will then outlined a procedure for me to follow, which I will now share with you.

Deal out (almost) all of the cards into four stacks; each of the stacks will contain exactly the same number of cards.

When dealing out the cards into four stacks, they might not come out even, i.e. there might be 1, 2, or 3 left over.  If there are cards left over, put them into their own stack in a particular case.  If the cards come out even, put down a poker chip in the place where you would’ve stacked the cards. 

Once all of the cards have been dealt and either the left over cards (or the chip) have been put in their place, pick up exactly one of the four equal piles and move the remaining three stacks out of the way.

Take the one stack you took from the four equal stacks produced by your dealing, and repeat steps 1-3 from above with it. Again, when you are done, put down either the left over cards or the poker chip to the right of your previous cards or poker chip.

Continue this process until all of the chips are gone.

I asked Will to leave the room while I did this because I wanted to be sure he wasn’t counting the cards as I dealt them out. That wouldn’t  have been fun at all.  Once he was safely out of the room, I began the process.

The first round of dealing came out even, so I put down a poker chip.  The second round I only had one card left over, so I put it down to the right of the poker chip.  After the third round, I had two cards left; to make the easy to count, I put them down in a vee shape to the right of the single card from round two.

At this point, each of the stacks had only one card, so I was momentarily confused.  I became very literal-minded at this point, and dealt it out into four stacks of 0 cards and had only one left over.  When I was done, it looked as in the picture below:

At this point, I invited Will back into the lounge.  He looked at the cards, knitted his brow a bit, and moved his lips silently, giving the appearance of great concentration.  Once he was done with his dramatics, he gave his pronouncement.

There are 100 cards.

I gathered all of the cards together and this time used my own algorithm, counting them into stacks of ten.  When I was done, I had ten stacks of ten.  Will was right, there were 100 cards.

The reader is at this point invited to pause to figure out how it was done.

The Explanation

As a mathematician, I realized immediately how he did it.  Actually, it took a minute or two, but there was no way I was going to let him know that, so I played it cool until I figured it out and then--and butter would not have melted in my mouth--I told him how he did it.

Now I will tell you.

The process Will described was a sneakily disguised algorithm for rendering numbers into base 4.  You can use it to put numbers into any base, actually, by having the number of equal stacks be equal to the desired base.  In this process, we represented the number of cards by

But in standard written notation it would be 1210 (base 4); note the reversed order which makes it even sneakier.  Expanding this number from base 4 gives (1)(64) + (2)(16) + (1)(4) + (0)(1) =100 base 10.

The dealing process and reserving the number of left over cards is a physical representation of what mathematicians call the Division Algorithm.

The process of yielding a number into a particular base can be put into a simple algorithm that we represent in pseudo-code below:

Digit_list = []

While N > 0:

N, r := N // base, N % base
        Digit_list.append(r)
Return Digit_list

Where // denotes integer division and % denotes keeping the remainder from division. 

Doing this on a computer seems like cheating when compared to the elegant simplicity of the Dealing Algorithm. To use a computer, one must know what the number is to begin with and have a representation of it in some base already.  With the Dealing Algorithm, the number of cards is unknown at the beginning.  Performing the algorithm reveals the name of the number, like tricking out the name of Rumplestilskin. 

A Final Walk-Through

To achieve a fuller understanding from the barebones level, let’s trace through the Dealing Algorithm again.

Recall, in the first round everything came out even and a put down a poker chip that represented 0.  Add 0 times 1 to the total.

I had four stacks of cards each having exactly the same (unknown) number of cards.  I only took one of those stacks to the next round, but each card in that one stack is standing for four cards, one from each of the stacks.

In the second round, when I deal out the cards and have one card left over, that one card is standing in for four cards.  I now add 4 cards to my previous total making 4 cards all together now. 

I take one of the four stacks to the third round, but each card in that stack is standing for four from the previous stack and each of those was standing for four from the first round.  That means when I have two cards left over, they are representing 2 time 16 = 32 cards.  Adding this to the total brings it to 36.

My equal “stacks” of cards each now consists of one card.  That one card will be the remainder of the fourth round dealing process.  It stands for four third round cards, and therefore for 64 cards total. So this round contributes 64.  Adding this to the total brinks us to one hundred. 

This is a simple physical process, but it does arithmetic for us.

Solving Sudoku on the Computer

Solving Sudoku on the Computer

By Bobby Neal Winters

Introduction

My journey toward writing a decent computer program to solve Sudoku puzzles began with free time and a question.  The free time was Christmas Break and the question was whether I could write such a program.  This journey led me to learn some new things--some new mathematics--that I can now share with you, the gentle reader.  I hope that, having read this far, you will stick around for the story of my journey.

The truth is that I wrote two such programs.  I wrote them both in Python using the pandas library.  The initial puzzles, i.e. the clues for the puzzles, were input using Excel spreadsheets.  My reason for using Python, pandas, and Excel is an ancient one: “When all you have is a hammer, everything looks like a nail.”  However, in this case, these tools were indeed sufficient for my purposes.
This first of these two programs, which I will refer to as “the Naive Program,” was very...naive.  I will expand on it briefly in the sequel.  The second program required that I learned some new mathematics.  New to me, at least. I will share this with you at length in the sequel, but it will all be kept at an informal level.

The Structure of the Sudoku Board

I am virtually positive that any of you who have made it this far are at least as familiar with Sudoku puzzles as I am, but for the sake of exposition--and setting up notation--let me explain Sudoku puzzles.

Each Sudoku puzzle begins with a 9 by 9 grid of cells that can be partitioned three ways: 9 horizontal rows and 9 vertical columns.  We number the rows beginning at the top as R1, R2, R3,...,R9.  We number the columns beginning on the left as C1, C2, C3,...,C9.  The cell where Rr meets Cc will be denoted as RrCc.

Each of these cells RrCc is ultimately to be filled with a value v that is one of the numbers 1,2, 3,..., 9. (Here I should say that any nine distinct symbols would work, but that using another symbol set offers no advantage.)

In addition to rows and columns, there is structure of 9, disjoint, 3 by 3 squares of cells that we shall denote by B1, B2, B3,..., B9.  Note that the cell RrCc will belong to the block Bb where

b = [( r - 1) // 3] * 3 + (c -1) // 3 + 1

With // denoting integer division, i.e. 4 // 3 = 1.

To fill out a Sudoku puzzle correctly, one must obey the following requirements:

1. Each cell RrCc must contain a value v from the set {1,2,3,..., 9}.
2. Each row Rr must contain each value from the set {1,2,3,..., 9}.
3. Each column Cc must contain each value from the set {1,2,3,..., 9}.
4. Each block Bb mush contain each value from the set {1,2,3,..., 9}.
5. A Sudoku puzzle is said to be solved when all of the requirements above are met.

The Naive Program

I designed the Naive Program in the following way.  I thought of the cells in the Sudoku puzzle as being ordered like the words on a page: Every cell in a higher row precedes every cell on a lower row; given two cells on the same row, the cell on the left precedes the cell on the right.  The algorithm I follow proceeded as below:

1. Place the cells that do not hold an initial value in a list which is ordered as described above.
2. Set a pointer to the first cell.
3. In the cell pointed to by the pointer, place the smallest untried value for that cell that doesn’t cause duplicate entries for the row, column, and block.  If such a value can be found go to step 5; otherwise proceed to step 4.
4. Forget about all values tried in this cell; decrement the pointer; go back to step 3.
5. Put the value found in step 3 in a used this for this cell; decrement the pointer; go to step 3.

This ends positively when the pointer can no longer be incremented and negatively when it can no longer be decremented.

I applied this algorithm to a small number of test cases, one of which required 3537 seconds to find a solution.  The save you the arithmetic, this works out to about an hour.  A college of mine did the same puzzle in half an hour while talking to a colleague. Clearly it may be improved upon.

A More Informed Approach

At this point, I decided to to a bit of light research.  By “light” I mean I didn’t use any source deeper than Wikipedia.  It was there (see Wikipedia: Exact Cover) that I discovered the Exact Cover Problem, the Exact Hitting Problem, and Algorithm X (Wikipedia: Knuth’s Algorithm X)  by Donald Knuth. This provides us with an opportunity to display the value of abstraction in mathematics:  An algorithm that will solve problems about finite sets of integers and Sudoku puzzles with no transparent connection between the two.

The Exact Cover and Exact Hitting problems are stated in terms of finite sets and there is a good exposition of both and Algorithm X applied to both in the links given above.  It is shown how they can be translated into a problem about a finite bipartite graph.  The bipartite graph can then be translated into a matrix of zeros and ones (the incidence matrix of the bipartite graphs), and Algorithm X can then be applied to this matrix.

Were I teaching a class on this, I would work examples based on sets at this point, but since the sources above already does a nice job of that, let me instead proceed by explaining a way of thinking that led me to a better understanding of the problem at hand.

Activities and Requirements

The totality of a Sudoku puzzle, especially using the model we will be using, is quite a big thing.  Let’s think first about a smaller problem: Graduating from school.  In order to graduate from school, there are certain requirements we must meet.  To meet these requirements, there are certain activities we can engage in. If you want to think about this as a graph, you can list the activities on the left side of a piece of paper; list the requirements on the right; and then connect each activity to the requirements it satisfies by  line segments.  Since the requirements for a given school can still be ridiculously complicated, let’s look at a simple one below.

Wildwood Academy

Wildwood Academy is an institution of higher learning not too far from here.  At Wildwood Academy, there are six requirements that need to be met.  They are denoted as follows: Woodsmanship, Nature, Religion, Culture, Survival, and Art.  The activities that are offered to satisfy these requirements are: Noodling, Moonshine, Shape Note Singing, Bible Study, Water Witching, Indian Lore, and Square Dancing.  While there has been (and no doubt will be) endless debate as to which activity satisfies which requirement, the following is what is currently on paper:

1. Noodling satisfies Woodsmanship, Nature, and Survival;
2. Moonshine satisfies Nature. (This has been debated vociferously.)
3. Shape Note Singing satisfies Religion and Art;
4. Bible Study satisfies Religion and Culture;
5. Water Witching satisfies Woodsmanship, Nature, and Survival;
6. Indian Lore satisfies Woodsmanship, Nature, and Culture; and
7. Square Dancing satisfies Art.

These are summarized in a matrix as below:

The empty cells can be thought of as having zeros in them.

Like students everywhere, the folks who attend Wildwood Academy don’t necessarily want to take more classes than they have to take in order to satisfy their requirements.  Because of this, the rule has been legislated than no requirement can be satisfied twice.  This is ridiculous and self-defeating, of course, but it is nonetheless the rule.

We will state an algorithm formally in a later section, but before we will work through an example heuristically, explaining our reasons as we go alone.  The example is in the figure below which will be explained by the text that follow the images:

Heuristically, we want to make sure the requirements are satisfied, so we first choose the requirements that have the fewest activities that satisfy them.  For example, Religion, Culture, and Art each have only two activities that satisfy them.  We choose religion because it is leftmost and for no other reason.

Religion is satisfied by Shape Note Singing and Bible Study.  We choose Shape Note Singing because it is listed before Bible Study and for no other reason.  Observe that Shape Note Singing satisfies Art in addition to Religion.  Since Art and Religion are satisfied and we don’t want anything satisfied twice we eliminate the activities that satisfy those.  We are are left with Woodsmanship, Nature, Culture, and Survival to be satisfied and with Noodling, Moonshine, Water Witching, and Indian Lore to satisfy them.

Going to the next stage, we note that Culture has a single activity that satisfies it, namely Indian Lore.  Indian Lore also satisfies Woodsmanship, and Nature. As Woodsmanship and Nature are collectively satisfied by Noodling, Moonshing, and Water Witching, we remove them all.  Having done this, all of the activities have been removed, but the Survival requirement remains.  We must back up.

Going up one level is not even as there was no choice of activities there. We must go to the first level.  There we chose between Shape Note Singing and Bible Study.  Let’s choose Bible Study on this occasion.  Doing this will drive us to choosing Square Dancing which, in turn, will drive us to choose Noodling.  

We may check this against the original matrix to verify that Noodling, Bible Study, and Square Dancing will satisfy Wildwood Academy’s requirements.

Algorithm X

It is my hope that the previous example will provide motivation for Algorithm X but, failing that, will at least provide enlightenment for someone trying to understand the algorithm.

I am not presenting Algorithm X in its greatest generality, but in a form that more transparently connects with our application.  With this caveat, let me say that the algorithm assumes that, as in our example, we are trying to satisfy each of our requirements with exactly one activity, and that we have our activities and requirements organized in an incidence matrix as in that example.

The Algorithm

1. If your matrix has no columns, you are done as all of your requirements have been satisfied.
2. Choose the column of your matrix that has the fewest ones.  (This assumes that no column has zero ones.)
3. Collect all of the rows that are incident to your column and put them on a stack.  You will return to this stack if the algorithm hits a dead end. 
4. Pop a row off of that stack created in step 3.  Push this onto a new stack called the partial solution stack.
5. Take the newest row from the partial solution stack and determine all of the columns it is incident to. Determine all of the rows that are incident to all of these columns; this will include the original row.  Create a new matrix by dropping all of these rows and columns.
6. If this new matrix has a column that is all zeros, pop the row off of the top of the partial solution stack and go back to step 4. Otherwise apply step 1 recursively to the new matrix.

It turns out that this matrix is easy to implement when one uses a pandas dataframe as a matrix.

Setting up the Matrix for Sudoku

We will now describe how this algorithm can be used to solve a Sudoku puzzle that the construction of an appropriate matrix.  Earlier we listed out the rules of Sudoku.  Let’s do it again thinking more specifically in terms of the context of requirements and activities, using precise symbolism.

Requirements

1. RrCc is the requirement of having some value in the cell RrCc.
2. Rr#v is the requirement of having the value v in the row Rr.
3. Cc#v is the requirement of having the value v in the column Cc.
4. Bb#v is the requirement of having the value v in the block Bb.

There are 81 each of the requirements (1) through (4) which comes to a total of 324 requirements.

Activities

What are the activities?  The sole type of activity consists of putting a particular value in a particular cell.  We will let RrCc#v denote the activity of putting the value v in the cell RrCc.  There are 81 cells with 9 values, so the comes to 729 activities.  Our matrix will by 729 by 324.  What will its entries be?

Matrix Entries in General

Note that RrCc#v satisfies RrCc, Rr#v, Cc#vk, and Bb#v, where b is calculated as in the section on the structure of the Sudoku board. Conversely, note that RrCc is satisfied by RrCc#w for any value w; Rr#v is satisfied by RrCd#v for any column Cd; Cc#v is satisfied by RsCc#v for any row Rs; and Bb#v is satisfied by RsCd#v for any s, d that will yield b according to our formula.

The Matrix for a Particular Puzzle

As was noted before, the incidence matrix for all activities and all requirements is 729 by 324.  However, each Sudoku puzzle begins with some cells that have already been filled in.  That is some activities have already satisfied some requirements.  This means we will have to drop some rows and columns from our matrix before we apply Algorithm X to it.

Let us consider the puzzle that has initial data as below:

Note that there are 29 cells that have been filled in with values; 29 activities have been completed.  Rather can calculate all of the rows and columns to be eliminated with all of these activities, let’s pick one activity that is not too special: R2C4#1.

It is easy to see at once the following requirements are satisfied: R2C4, R2#1, C4#1, and B2#1 so that the corresponding columns will have to be eliminated, but it doesn’t stop there.  Rows corresponding to the following activities:

R2C4#1, R2C4#2, R2C4#3, R2C4#4,..., R2C4#9

R2C1#1, R2C2#1,R2C3#1, R2C4#1,..., R2C9#1

R1C4#1, R2C4#1, R3C4#1, R4C4#1,..., R9C4#1

R1C4#1, R1C5#1, R1C6#1, R2C4#1, R2C5#1, R2C6#1, R3C4#1, R3C5#1, R3C6#1

will also have to be eliminated. 

Perhaps I am making a mistake in giving so much emphasis to this part of the implementation but I lots many fruitless hours in debugging my implementation of Algorithm X because I got the matrix wrong.

Once the initial matrix is modified with respect to the initial data, Algorithm X works remarkably well in producing a solution.  For example, the puzzle that took 3537 seconds to solve with the Naive program was solved in just over a second by Algorithm X.

Concluding Remarks and Future Directions

While I am incredibly pleased by improving the execution time by a factor of 3000, I am still impressed that a human being could solve the puzzle twice as fast as a computer operating naively.  Those of you who have played Sudoku seriously--and some of you are very serious--know some shortcuts.  One question is whether these could be worked into an algorithm. Another question that has captured my interest, given my interest in Python computing, is whether machine learning (or artificial intelligence or whatever you call it) in the form of a neural network can be taught to solve Sudoku well.  I am putting this on my list for possible future activities.