Sudokus

[Zeno Swijtink]

Anybody else addicted to solving sudokus??

I have a question of a theoretical nature:

Is there a measure for the complexity of a sudoku puzzle?

They are often labelled: Easy Medium Hard Evil. On what measure is this labeling based?

The complexity of a sudoku must have to do with how deep you have to search for information to solve the puzzle. What is this depth of search measure? Does it give a linear order of the space of complexities?

Since there are only finitely many puzzles of the standard kind is there an interesting extension of the definition of sudoku that creates a space of puzzles of size Aleph-null? Applying an extension of the depth of search measure to this set, and assuming this creates a linear order, what is the ordinal structure of this set?

What other questions can be asked about this topic?

[Braggi]

Anybody else addicted to solving sudokus??
...


Zeno, stop it!!!!

How do you have time for sudokus? You read more esoteric stuff than anyone I've ever heard of, you seem to have a real job and a real life, yet you find time for the most amazing distractions.

Are you doing something weird with time? The rest of us have only about 24 hours in a day.

I'm continuously surprised at the stuff you come up with.

-Jeff

[Zeno Swijtink]

Zeno, stop it!!!!

How do you have time for sudokus? You read more esoteric stuff than anyone I've ever heard of, you seem to have a real job and a real life, yet you find time for the most amazing distractions.

Are you doing something weird with time? The rest of us have only about 24 hours in a day.

I'm continuously surprised at the stuff you come up with.

-Jeff

In fact I am still on sick leave from my throat cancer treatment. I'll go back to teaching next semester, at the end of January. And I'll be away during most of January, traveling around Chile with my son and my sweetheart.

So enjoy me as long as you have me. :wink:

[MsTerry]

What other questions can be asked about this topic?

is this an healthy or social addiction?

[Kermit1941]

Anybody else addicted to solving sudokus??

I have a question of a theoretical nature:

Is there a measure for the complexity of a sudoku puzzle?

They are often labelled: Easy Medium Hard Evil. On what measure is this labeling based?





https://en.wikipedia.org/wiki/Sudoku

is the wikipedia article on Sudoku.





Difficulty ratings
The difficulty of a puzzle is based on the relevance and the positioning of the given numbers rather than their quantity. Surprisingly, most of the time the number of givens does not reflect a puzzle's difficulty. Computer solvers can estimate the difficulty for a human to find the solution, based on the complexity of the solving techniques required. Some online versions offer several difficulty levels.

Most publications sort their Sudoku puzzles into four or five rating levels, although the actual cut-off points and the names of the levels themselves can vary widely. Typically, however, the titles are synonyms of "easy", "intermediate", and "hard". (Extremely difficult puzzles are known as "diabolical" or "evil"). An easy puzzle can be solved using only scanning; an intermediate puzzle may take markup to solve; a hard puzzle will usually take analysis.

Another approach is to rely on the experience of a group of human test solvers. Puzzles can be published with a median solving time rather than an algorithmically defined difficulty level.

Difficulty is a very complex topic, subject to much debate on the Sudoku forums, because it may depend on the concepts and visual representations one is ready to use.



https://www.conceptispuzzles.com/articles/sudoku/diff_levels.htm

also discusses
measuring the complexity of Sudoku.



Perhaps a way to get insight into the complexity is to set up

4 by 4 sudoku's, 6 by 6 sudoku's, etc. Note. The number of cells must be
the square of a composite number.


https://www.setbb.com/phpbb/viewtopic.php?t=1333&sid=7d52d93d06ad7509b7bbc155820d536f&mforum=sudoku

discusses how to create sudoku puzzles.




https://number-puzzle.com/

sells the sudoku puzzle in many forms.


https://ed.markovich.googlepages.com/matlab_doku

is a web page that discusses the guessing algorithm for solving any Sudoku.


In it Ed explains that easy and medium Sudokus are distinguished from the

hard and easy by what methods are needed to solve them.


https://www.gamezebo.com/reviews/sudoku_maya_gold_review.html

is a description of an electronic sudoku puzzle game.





The complexity of a sudoku must have to do with how deep you have to search for information to solve the puzzle. What is this depth of search measure? Does it give a linear order of the space of complexities?



For the easy and medium puzzles, you need only consider 1 digit at a time.
You can solve these by asking repetitiously two questions.
(1) For a given space, which digits can go in it.
(2) For a given region, ( row, column, or 3 by 3 block), and a given digit,
which squares in the region can contain that digit.

For the hard and evil puzzles, you need to be able to consider 2 or more digits at a time. (Or you may make guesses and backtrack when you reach an inconsistency.)

For two digits at a time, the question is:
(1) For a given region, (row, column, or 3 by 3 block), are there two spaces that have only the same two candidates?
If so, then the other spaces in that region, do not contain either of those candidates.


There are corresponding rules for 3 digits at a time, but I'm guessing that
those can be reduced to the two at a time rules.

I have not studied it enough to know for sure.










Since there are only finitely many puzzles of the standard kind is there an interesting extension of the definition of sudoku that creates a space of puzzles of size Aleph-null? Applying an extension of the depth of search measure to this set, and assuming this creates a linear order, what is the ordinal structure of this set?



I will guess that the search measure will be three dimensional for the three regions, row, column, and 3 by 3 block.




What other questions can be asked about this topic?


:) Invites some non-mathematical responses.

What is the least number of starting squares that have to be filled in for a unique solution?

For the 9 by 9, the least number, empirically is 18.



How many distinct sudoko puzzles, ( of a given size ) are there?
( Requires defining what is meant by distinct.)


and other questions which I have not ( yet ) thought of.


Kermit Rose < [email protected] >

[shellebelle]

I love them and often use them to gauge how mind ready I am for my accounting. If my soduko numbers are off or timing is way too high - I need a break. Food and knitting usually clear the head, take the eyes off the screen and lets everything just come back to "normal" whatever that may be. I tend to stick to "easy" though and now am intrigued by "evil".


Anybody else addicted to solving sudokus??

I have a question of a theoretical nature:

Is there a measure for the complexity of a sudoku puzzle?

They are often labelled: Easy Medium Hard Evil. On what measure is this labeling based?

The complexity of a sudoku must have to do with how deep you have to search for information to solve the puzzle. What is this depth of search measure? Does it give a linear order of the space of complexities?

Since there are only finitely many puzzles of the standard kind is there an interesting extension of the definition of sudoku that creates a space of puzzles of size Aleph-null? Applying an extension of the depth of search measure to this set, and assuming this creates a linear order, what is the ordinal structure of this set?

What other questions can be asked about this topic?

[Tars]

Anybody else addicted to solving sudokus??

I have a question of a theoretical nature:

Is there a measure for the complexity of a sudoku puzzle?

They are often labelled: Easy Medium Hard Evil. On what measure is this labeling based?

My brain churns along all the time; it can be annoying. I've found Sudoku very helpful to keep it occupied. People who know me publicly probably think of me as the puzzle geek. I've almost always got one at hand, to fill the spaces when something else isn't occupying my attention.

I do Sudoku daily, but get most of my puzzles (at least currently) from a program called "Sudoku Up (https://www.sudokuup.com/)", and a website called "Daily Sudoku (https://www.dailysudoku.com/sudoku/archive/2007/10/2007-10-1.shtml)". I've found them to be much more consistent than the ones available in the PD.

I think the person who "writes" and rates the puzzles in the PD, Michael Mepham, actually just uses a computer program to generate them. And they pay him for it too - nice gig! The reason I think this is that his ratings, "Gentle", "Moderate", and "Diabolical" don't seem to have a very close correlation to the actual difficulty of the puzzle. I've done some of the Diabolical ones, which were fairly easy, then found some "Gentle" ones that were extremely difficult.

The difficulty of the puzzles seems to correlate to how many numbers are pre-set in the puzzle - fewer numbers, more difficulty. The other main factor seems to be distribution of the numbers across the grids. There can be more numbers, but if they're concentrated in fewer of the nine-cell grids, the puzzle is more difficult. Mepham sometimes calls a puzzle "moderate", but there are a few empty grids, which makes it much more difficult to solve.

For "Gentle" and "Moderate" puzzles, I've found that there is always a definite solution. Sometimes it takes time & patience to find, but it's there. The "Difficult" or "Diabolical" ones usually involve making best-guesses, then scratching out & re-trying.

I do them in pen. If I have to erase, then the puzzle won.

[Willie Lumplump]

I love themI despise them because I am totally inept. I am also totally inept at scrabble, crossword puzzles, and many other things that it seems I should be good at. In fact, in all matters of this sort I seem to be relatively devoid of talent--except one. I have an almost preternatural talent for taking multiple-choice tests, and it served me well through the years.

[shellebelle]

In fact, in all matters of this sort I seem to be relatively devoid of talent--except one.

Interesting - so problem solving is not in your forte?

[Willie Lumplump]

Interesting - so problem solving is not in your forte?If I can write out the problem in full sentences, I can make a stab at solving it. Otherwise, no.

[Willie Lumplump]

In fact I am still on sick leave from my throat cancer treatment. I'll go back to teaching next semester, at the end of January. And I'll be away during most of January, traveling around Chile with my son and my sweetheart.

So enjoy me as long as you have me. :wink:

Some sort of response is needed, and here's the only one I can think of:

Let's hear it for Zeno!
Hip-hip, hooray!
Hip-hip, hooray!
Hip-hip, hooray!

[shellebelle]

Very interesting. I can create these as word problems in my head. Never really thought about it past doing it. Hmmmmm very intriguing.


If I can write out the problem in full sentences, I can make a stab at solving it. Otherwise, no.

[Kermit1941]

If I can write out the problem in full sentences, I can make a stab at solving it. Otherwise, no.



Logic puzzle to substitute for sudoko:


On Monday, Hank ate eggs for breakfast at home.
On Monday, Fred ate Fish for supper at home.
On Monday, Billy ate Pancakes for lunch at a buffet.
On Monday, Cecil ate eggs for breakfast at a buffet.
On Monday, Elmer ate fish for supper at a buffet.
On Monday, George ate pancakes for breakfast at a campground.
On Monday, Irvin ate eggs for breakfast at a campground.
On Monday, Albert ate fish for supper at a campground.

On Tuesday, Daryl ate pancakes for breakfast at home.
On Tuesday, Irvin ate eggs for lunch at home.
On Tuesday, Elmer ate fish for lunch at home.
On Tuesday, Hank ate pancakes for breakfast at a buffet.
On Tuesday, Albert ate eggs for breakfast at a buffet.
On Tuesday, George ate pancakes for lunch at a buffet.
On Tuesday, Fred ate fish for lunch at a buffet.
On Tuesday, Billy ate pancakes for lunch at a campground.
On Tuesday, Cecil ate eggs for lunch at a campground.
On Tuesday, Daryl ate fish for supper at a campground.


On Wednesday, George ate pancakes for breakfast at home.
On Wednesday, Albert ate eggs for supper at home.
On Wednesday, Elmer ate fish for supper at home.
On Wednesday, Irvin ate Pancakes for breakfast at a buffet place.
On Wednesday, Daryl ate fish for lunch at a buffet place.
On Wednesday, Fred ate eggs for supper at buffet place.
On Wednesday, Elmer ate pancakes for breakfast at a campground.
On Wednesday, Hank ate eggs for supper at a campground.


What did each of the nine eat for breakfast, lunch, and supper, on
Monday, Tuesday, and Wednesday, and where did they eat it?

On a given day, at a given type of place,
No two of the nine ate the same thing for the same time of day.

For example, among the nine people,
on monday, at home,
exactly one ate pancakes for breakfast;
exactly one ate pancakes for lunch;
exactly one ate pancakes for supper;
exactly one ate eggs for breakfast;
exactly one ate eggs for lunch;
exactly one ate eggs for supper;
exactly one ate fish for breakfast;
exactly one ate fish for lunch;
exactly one ate fish for supper.


For a given type of food, on the same day, no two of the nine
ate at the same time.

For example, among the nine people,
For eating pancakes on Monday,
exactly one ate pancakes for breakfast at home;
exactly one ate pancakes for breakfast at a buffet;
exactly one ate pancakes for breakfast at a campground;
exactly one ate pancakes for lunch at home;
exactly one ate pancakes for lunch at a buffet;
exactly one ate pancakes for lunch at a campground ;
exactly one ate pancakes for supper at home;
exactly one ate panckaes for supper at a buffet;
exactly one ate panckes for supper at a campground.

For a given place to eat and time of day for the meal, no two of the nine
ate the same food on the same day.

For example, among the nine people,
eating breakfast at home,
exactly one ate pancakes for breakfast on Monday;
exactly one ate eggs for breakfast on Monday;
exactly one ate fish for breakfast on Monday;
exactly one ate pancakes for breakfast on Tuesday;
exactly one ate eggs for breakfast on Tuesday;
exactly one ate fish for breakfast on Tuesday;
exactly one ate pancakes for breakfast on Wednesday;
exactly one ate eggs for breakfast on Wednesday;
exactly one ate fish for breakfast on Wednesday.



Each day each of the nine ate pancakes for one meal, eggs for another meal,
and fish for another meal.

At each place of eating a meal, each of the nine ate breakfast, lunch, and supper.

[shellebelle]

Great Job!


Logic puzzle to substitute for sudoko:

What did each of the nine eat for breakfast, lunch, and supper, on
Monday, Tuesday, and Wednesday, and where did they eat it?