Simple Brain Exercise Can Boost IQ

New Scientist ^ | 4-28-2008 | Alison Motluk

[dr_lew]

Not C++ ! No dear friends! The real thing!

This compiles and runs with gcc on cygwin. You may infer the input format from the input loop in main() ... ‘_’ for blanks and digits ‘1’-’9’ for themselves. Other characters are ignored, so I normally use spaces and newlines to from a grid for input.

The output is verbose, and it finds all solutions. Usually it doesn’t have to TRY (i.e. guess) but this is actually a very efficient strategy when it has to resort to it, which it does if the basic rules of uniqueness, and row, column, and square inference fail. Only rarely does it have to go to a second level of guessing.

[TChris]

That would be good, old-fashioned C there, FRiend. :-)

[DoughtyOne]

First time I’ve seen that. I think I could have it done by next March. LOL

[DoughtyOne]

Let me ask, is there only one answer, or can there be a variety of answers? At first blush, it looks like there could be more than one.

[RaceBannon]

I think there can be some with multiple answers, when within one 9 cell square, you have a 2 digit combination that is identical to the cell above it or beside it that is missing, and in the same column or row to the side

[MHGinTN]

The exercise is the goal, winning or losing is not; so long as the games are carried out without memory errors, the mind is exercised more than sufficiently. I used to play Chess for the winning and hated the losing. Now, at my age the mental exercise is more important to me.

[Revolting cat!]

Sudokus with multiple answers are considered flawed.

[luckystarmom]

We knew my daughter had brain damage, and it’s just useful information to know what part is working well and what isn’t.

For example, I used to have to repeat everything that I said to my daughter. I took her to the audiologist, and her hearing was fine.

The bad public school said she was fine, but I knew differently.

Finally, we had an independent evaluation from a neuropsychologist. She’s the one that found the short term memory problems. Now, I’ve learned tricks on how to make sure my daughter can remember something I tell her. If I can’t write something down, then I have her repeat what I say back to me. After she does that a few times, it gets put in long term memory and she’s okay.

Once we understood what wasn’t working well, we’ve been able to get her appropriate help. Also, there are things you can do to help short term memory. Practice actually does help.

[DoughtyOne]

Thanks to both of you for your thoughts on this. I can't believe that I've gotten this far in life without seeing a Sudokus before.

When I looked at the first blank provided by RaceBannon, it seemed to me like multiple solutions might be possible. It wasn't readily apparent that it was locked in to only one solution, especially with only one number on multiple rows and columns. I will say that it did occur to me that being a high level numbers brain teaser, that there could be just one solution if configured right. That's why I asked.

I can see rationality behind both your answers, and I appreciate your responses. I'm goint to check these out further.

[Revolting cat!]

A sudoku creator, and there are some celebrity sudoku creators, believe it or not, is supposed to test each puzzle on several solvers before publishing it, to verify that it is solvable and that it has a single unique solution. But, I've run into a sudoku in my local newspaper that had two solutions.

The mania hit England before it hit the States, and several years ago, some newspaper, I think it was the Guardian, organized a sudoku contest and promotion where they painted a puzzle on a hill somewhere challending the readers to solve it. Well, it turnout that the puzzle had not just two or four but hundreds of possible solutions, and the whole promotion went pop, pop, fizz, fizz!

[DoughtyOne]

Thanks for the background. It was interesting. That hillside blank figuring in the paper’s contest must have been very embarassing. It may have actully given the game some additional publicity. Hope it didn’t put people off Sudoku though.

[MonicaG]

My Friday night sushi waiter totally took everyone’s order by memory - he gets PAID to enhance his IQ. The extra-genius part was when the rolls arrived, though... mmmmMMm

[RaceBannon]

but there can easily be more than one solution

if, in one row, you need a 4 and a 7

AND in 2 columns you needed a 4 and 7, each column

it is possible to transpose the 4’s and 7’s

the same with 2 rows and one column

That is probably explained with a picture more

lets see

x x x .. _ _ x .. x x x .. 4, 7
x x x .. x x x.. x x x
x x x .. x x x .. x x x

x x x .. x x x .. x x x
x x x .. _ _ x .. x x x .. 4,7
x x x .. x x x .. x x x

x x x .. x x x .. x x x
x x x .. x x x .. x x x
x x x .. x x x .. x x x

now, look at the matrix
each _ is where a 4 or 7 could go to complete the puzzle
horizontally, you need only ONE of them, a 4 OR a 7 to complete the row, and vertically the same, but if you look how they are arranged, the 4 and 7 are interchangable

this is the easiest way to show that more than 1 answer is okay

[RaceBannon]

but I do get your point. :)

[dan1123]

Why type all that when you can have a sudoku solver like this:

def r(a):i=a.find(’0’);~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in’%d’%5**18]
from sys import*;r(argv[1])

(The above code is in Python)
(I didn’t write the above code)
(Who said Python was readable?)

[dr_lew]

This program is “pure trial”. Here’s the C equivalent, which to be sure is more prolix than Python. It’s very slow, but it does work. Actually, it solved the puzzle in this thread in 0.562 seconds, compared to 0.016 seconds for mine, so what the heck. BTW, I never heard of Python before, so thanks for mentioning it.

main(argc,argv)
int argc;
char **argv;
{ s(argv[1]); }
s(p)
char *p;
{
char grid[81]; int i,j; char m;
for( i=0 ; i<81 && p[i] != ‘0’; ++i);
if( i == 81 ){ printf(”%.81s\n”,p); exit(0); }
for( j=0 ; j<81 ; j++ ) grid[j]=p[j];
for( m=’1’ ; m<=’9’ ; ++m ) { for( j=0 ; j<81 ; j++ ){
if( ( i%9 == j%9 || i/9 == j/9 ||( i/27 == j/27 && (i%9)/3 == (j%9)/3 ) ) && p[j] == m ){ break;} }
if( j == 81 ){
grid[i] = m; s( grid );
}}}

[dr_lew]

Actually, this can be tightened up a little bit by eliminating the duplication of the grid for each recursion, as this isn’t necessary. ( Of course, I cheated by doubling up the lines a little bit more. ) The recursion works its way up and down the grid, and can “cover its tracks” by resetting the spot its working on to ‘0’. This runs only slightly faster: 0.531 sec vs. 0.562 sec for this test case. I’m sure the C version of this “pure trial” algorithm runs faster as compiled object than the Python version does on its virtual machine, but how much faster, I don’t know. I would think that the Python version would be at least 5 times as slow, but I’m quite often wrong about this sort of thing.

main(argc,argv)int argc; char **argv;{ s(argv[1],0); }
s(p,i) char *p; int i; { int j; char m;
while( i<81 && p[i] != ‘0’) ++i; if( i == 81 ){ printf(”%.81s\n”,p); exit(0); }
for( m=’1’ ; m<=’9’ ; ++m ) { for( j=0 ; j<81 ; j++ )
if( ( i%9 == j%9 || i/9 == j/9 || ( i/27 == j/27 && (i%9)/3 == (j%9)/3 ) ) && p[j] == m )break;
if( j == 81 ){ p[i] = m; s( p, i+1 ); } } p[i]=’0’; }

[dan1123]

I would think that the Python version would be at least 5 times as slow, but I’m quite often wrong about this sort of thing.

Yes, Python tends to be slow, but there is a Python "compiler" to C++ called ShedSkin that is slightly more rigid with types than Python. They report an 18x speedup with a slightly modified version of the original algorithm.

def r(a):
i=a.find('0')
if not ~i: print a; exit()
[m in [a[j] for j in range(81) if not
(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)] or r(a[:i]+m+a[i+1:]) for m in '3814697265625']
from sys import *;r(argv[1])

[Walmartian]

I'm working on drawing one of these in 3DS. I can get the acanthus leaves but the scrolls present an array of challenges.

[MrB]

That’s a matter of maturity, not IQ.