project a sudoku whitout a computer

profnassif

Before computers, how to project a sudoku?

mistermac · Posted: Sat May 03, 2008 9:25 am Post subject:

This is my first post, and I apologise if I am treading over well worn ground.

I also do not know the right place to put my first post, but seeing this one was almost empty, i thought I would use it!

I am an amateur mathematician, which means i do not have a degree which incorporates same, and am on old retired COBOL programmer, which makes me an amateur programmer also. I Have none of the current languages, which are i am sure very elegant and efficient.

From reading Wiki, and a few posts here, it seems that no one has ever provided a valid puzzle with less than 17 initial clues.

I am surprised that with so much computer power around, and so much effort, that if it were possible, that a 16 clue puzzle has not been found.

Without knowing any real theory, it seems to me in my present that state of knowledge that it is not possible. BUT, if taht were so, it would probably have been mathematically proven. So, I am probably wrong.

Can someone who knows the theory, please explain, if they can, why the hope is held out for a 16 or less sulution.

I was wrong many years ago, whwn i trie d to find out the shortest way to get 10 Chinese Checkers across a board with no opposing pieces, and found that my solution was 1 move short of the best possible.

Perhaps the same here.

A search for information theory has prompted my joining this Forum, as I feel Sudoku is a way to develop a larger theory of packing meaningful information as economically as possible.

Would Kelly, who helped developed the theory of overcoming the problem of more accurate data transmission over "noisy" communication lines be known to any members of the forum.

I was also interested to see that some of you try to generate Sudokus using raw random numbers as "seeds" in an attempt to make the whole problem more interesting.

Best!

Adak · Posted: Sat May 03, 2008 10:25 am Post subject:

Hi Mac,

Best to just start a new thread, rather than "bring back" a 2 year old thread, to "life".

And "Welcome" to the forum. Smile

Glenn (gsf), amongst others, are doing a lot of testing to see if they can find all the 17 givens puzzles, and at the same time, checking many 16 givens puzzles, as well.

There is also a Sudoku Project on BOINC, but it's working from the 12's on up. Seems quite flawed to me.

north55

mistermac · Posted: Wed May 07, 2008 4:47 am Post subject:

coloin · Posted: Wed May 07, 2008 12:42 pm Post subject:

I think north55 is trying to show you how to make a symmetrical puzzle [not essential IMO], perhaps confusing the making of the grid and the removal of clues.

There are two stages
1 make the grid [i believe you have done this already]
2 remove clues

Stage 1
Insert 25 clues into an empty grid. Keeping basic constraints in mind it is unlikely that there will be no solutions. Add clues carefully and with luck you will get a complete valid grid.
Stage 2
It is easy to get less than 50 clues straight off
Remove all clues from boxes 3,5,7.
Remove a single clue form all the remaining 6 boxes.
You will have a valid non minimal puzzle with 48 clues. Remove a good few more if you feel lucky.

It would be quite tricky to get down to a minimal puzzle by hand.

If you remove clues [from the solution grid already made in stage one] you have a 50 percent chance of a valid [non-minimal] puzzle around the 42 clue stage. The validity depends on all the clues hitting all the unavoidable sets in the complete grid. There are many > 10000. unavoidable sets in every complete grid.

If you insert clues into an empty grid [but use the solution grid made in stage one] you could quite easily make a puzzle with <35 clues.

C

Jean-Christophe

north55 · Posted: Thu May 08, 2008 2:52 am Post subject:

north55

Jean-Christophe · Posted: Thu May 08, 2008 8:37 am Post subject:

There is also another page, but in Japanese only
Babelfish Translation
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

coloin · Posted: Thu May 08, 2008 9:13 am Post subject:

Apologies to north55 but mistermac appeared desperate to make a puzzle with less than 50 clues.

I agree inserting clues preferentially will tend to generate puzzles with slightly less clues - and it will be easier perhaps to add the final clues which define the solution.

Inserting clues from a predetermined grid will remove the chance of generating an invalid puzzle. You will always get a puzzle at the end - although it might have around 40 clues. It might even be symmetrical.

However i dont think it is worth trying to make a symmetric and minimal puzzle by hand.

C

mistermac · Posted: Fri May 09, 2008 8:56 am Post subject:

m_b_metcalf · Posted: Mon May 12, 2008 12:00 pm Post subject:

mistermac · Posted: Tue May 13, 2008 8:15 am Post subject:

I will have to look in my currant account to see if I owe anyone here.

Besides, I have trouble rolling my r's the way the French do.

BTW, the NYY's owe me a bit, can you do anything about that?

Meanwhile, I am plugging on with my Sudoku, I only hope it has only one solution.

Otherwise, I will have to settle for a Latin Square.