Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was requesting somebody to help me discuss how the prime number rule helps to solve easily the sudoku game in just a few minutes and an example showing the relevant steps on how the rule is used

share|improve this question
3  
I cannot tell what is being asked here... –  Mariano Suárez-Alvarez Feb 9 '11 at 4:30
1  
What the heck is the "prime number rule"? Google gives no hits whatsoever for "prime number rule" sudoku –  Arturo Magidin Feb 9 '11 at 4:32
    
@Mariano: If I understand correclty (big "if") he is asking someone to explain to him how something called "the prime number rule" can be used to solve sudoku puzzles. –  Arturo Magidin Feb 9 '11 at 4:33
6  
-1 Several of us seem to have no idea what the "prime number rule" is. Can you state it? I see no connection between prime numbers and sudoku problems. –  Ross Millikan Feb 9 '11 at 4:43
1  
Maybe "prime" just means "most important" or "first"? –  Yuval Filmus Feb 9 '11 at 6:12

3 Answers 3

Here's a working example. Let $p(i)$ be the $i$th prime number. Suppose you have reached the following state and want to solve the puzzle:

$$\left( \begin{array}{cccc} & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \\ 2 & 4 & 1 & 3 \\ 4 & 3 & 2 & 1 \\ \end{array} \right)$$

We know that the product of $p(i)$ over all entries in the completed grid will be $P = p(1)^4p(2)^4p(3)^4p(4)^4$. Therefore, to find the missing entry, simply divide P by the product of $p(i)$ where $i$ ranges over all the entries that appear so far:

$${{p(1)^4p(2)^4p(3)^4p(4)^4} \over {p(2)p(3)p(4)p(3)p(1)p(4)p(2)p(2)p(4)p(1)p(3)p(4)p(3)p(2)p(1)}} = {{1 944 810 000} \over {972 405 000}} = 2.$$

Now use the fact that 2 uniquely factorizes to (2). We can conclude that there is exactly one missing number, and it must be $i$ where $p(i) = 2$. A short search finds that $i = 1$.

This example gives you an idea of how efficient the method is. (Granted, we could have accelerated it by only calculating the product over the first row or column instead of the whole grid.)

share|improve this answer

Perhaps this is what you mean by "the prime number rule:"

The problem with deducing missing numbers does not arise if we use a form of Gödel numbers. Here we don't just multiply the Sudoku numbers together we use the corresponding prime number. So for a '1' we use the first prime number '2', for '2' use the second prime '3'; for '3' use '5'; for '4' use '7' and so on... We can use this trick for finding any number of missing numbers in a Sudoku group (of any size) just by a little multiplication and division. Why does this work? Because prime numbers are well, prime, we can't make a prime number by multiplying two other numbers together.

From the Gödel numbers section on Sodoku Dragon

share|improve this answer
    
This particular rule doesn't seem to be enough to solve a sudoku in a couple of minutes by hand since the calculation feels unwieldy (to me) and I can more readily just spot which numbers are missing given a row or column. Even for a computer I would expect a solver to be practically instantaneous whether they used this technique or not. The other rules on the page do offer helpful advice, however. –  Joshua Shane Liberman Feb 9 '11 at 15:44
1  
As far as I can tell, the only purpose of this "rule" is to find some far-fetched way to relate prime numbers to Sudoku. It works like this: let $p(i)$ be the $i$th prime number. Now suppose I choose a subset of $\{1,2,3,4\}$; say, $\{1,4\}$. What's missing? Well, just calculate ${{p(1)p(2)p(3)p(4)} \over {p(1)p(4)}} = p(2)p(3) = 15$. There is only one way to factorize 15, viz., $(3)(5)$, so the missing numbers must correspond to 3 and 5. Looking at our prime number table, lo! we find that the missing numbers are 2 and 3. –  Théophile May 4 '12 at 13:07

The prime number rule is an improvement over simple multiplication as used as an analysis technique. For instance, because all of the numbers involved are square-free, finding the least common multiple or greatest common divisor equates to finding the union or intersection of the set of prime factors.

However as the page goes on to point out, you can use powers of two as an improvement over simple addition as an analysis technique, as this allows you for instance to use bitwise arithmetic to represent the union or intersection of two sets of powers of two.

share|improve this answer
4  
It looks like you are the only person who knows what "the prime number rule" is, so perhaps you wouldn't mind letting the rest of us in on the secret? Also, you refer to "the page" without any indication of what page it is that you are talking about. –  Gerry Myerson May 4 '12 at 12:40
    
@GerryMyerson You're right, I was answering the wrong question. Sorry about that. –  Neil May 4 '12 at 20:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.