OT: "Puzzle" solving

I went home, entered through the back door and quickly walked to the living room, where I stood for 20 minutes, motionless, with the lights off, watching the street through a crack in the blinds.

When I felt confident nobody had followed me, I moved silently to what looks to others as a bookshelf built into the wall.

A few slight touches on the right places, and the bookshelf moved to one side. I stepped into the dark and begun going down the invisible staircase, with the whistling of the secret door closing back behind me as my only companion.

Got to the bottom of the stairs. If there had been any light at all, I could have seen that the basement was empty. Yet, there was a maze there, and without tracing its ever changing path I could not complete the mission that had brought me here. So I did. 3 steps, left, 5 steps, right, 3 steps right...

I ended up at the same place I started. But I was not the same place. The maze key had worked, the lock was open, and the immense power that my family had kept secret for generations was, once again, under my finger tips. Basking in the faint orange glow coming from everywhere and nowhere, I felt the energy levels rising all around me as I said, in a tongue that mankind has forgotten,

"I summon the powers of the Google!!!!"

Suddenly, [CENSORED] [CENSORED] [CENSORED] [CENSORED] [CENSORED] bright [CENSORED] [CENSORED] gigantic [CENSORED] [CENSORED] [CENSORED] [CENSORED] in [CENSORED] [CENSORED] and [CENSORED] [CENSORED] [CENSORED] [CENSORED] then [CENSORED] [CENSORED] no more.

I was back in the living room. The bookshelf was just a bookshelf. A quick peek through the window showed a still empty street. I made a cup of coffee and sat, thinking how to solve the new problem. There must be a way I could share this precious information with my fellow men without revealing how I obtained it...

( With apologies to cliché writers everywhere. )

-- Roberto Waltman

Bwah-hah-hah-hah! *Very* good!

Theres also a book: Programming Sudoku by Wei-Meng Lee

Randy

Look up "generating functions." I think a good exposition comes from "Concrete Mathematics: A Foundation for Computer Science." (Graham, Knuth, and Patashnik.) If you don't have the book, you should definitely get a copy.

Instinct only suggests it as an avenue to pursue.

Jon

Thank you. In case I was too obtuse, the message was you could have search for this yourself in the same time it took to post to c.a.e.

-- Roberto Waltman

Yes, I know that. But, I was hoping to get some ideas from others as to how to *approach* the problem.

Thanks! I'll ask my local library to bring in a copy!

My wife and I played with this question for a few hours once after dinner. She was taking Discrete Mathematics at the time and I just like math problems, as long as they aren't *too* hard.

We realized that it was becoming quite complicated to solve, and didn't ever finish it off.

My strategy was to manually work out the number of possible games for the smaller 4x4 case hoping to gain insight into the nature of the scaling functions.

My wife just resorted to continuing to play Sudoku, and being an insomniac I woke up at 3:30am last night, so today will be another unfortunate day of my life where I accomplish nothing.

When I've got to start counting on my *toes*, I know things are getting tricky!!

That's an interesting idea. But, I suspect there aren't enough of those 3x3 "cells" in the entire puzzle to be able to gauge the shape of the "scaling function".

TTT is relatively easy to reduce to a fixed set of "games" because the rules are few and you know there are only *6* winning configurations (think about it!) -- plus a bunch of dead ends.

The interactions between "moves" in Sudoku are much more complex -- it's not just a question of whether or not a square is "taken"...

I suspect Sudoku helps refine deduction -- to a point (once you suss out the "tricks", it becomes almost mechanical). I imagine the bigger benefit is sharpening short term memory (since, to effectively solve them quickly, you need to be tracking several "points" concurrently).

As for the insomnia... use it as an opportunity to sneak some ice cream while she's asleep! :>

Hmmm... this looks interesting! I'll have to stew on it for a while to see how (if at all) I could leverage this idea (too early in the morning for that many neurons to be engaged!).

Thanks!

You will find learning about it worth every single second it takes. It is raw, unbridled power in your hands. In fact, the entire book I mentioned is worth a thorough and thoughtful reading and it reads easily, too. It's so good, in fact, that I can't find my damn copy anymore!! I think I've lent it out too many times. I consider it one of the very few ABSOLUTELY MUST MASTER/READ books for folks like you (and me.)

Best wishes, Jon

That is distressing. I have been working very hard to

(sigh) I'll just have to find a few *extra* titles to discard to accommodate it.

Thanks!

--don

I assume that he means 4x4, i.e. a 2x2 grid of 2x2 grids using the numbers

BTW, if you just want the solution (including the method) handed to you on a plate:

The basic question about how many soduko's there are is too easy for projecteuler.net. A sudoku is a filled in field. It becomes more interesting if asked about different sudoku's. If you swap the first two lines, the sudoku is essentially the same, or equivalent. A puzzle where you swap the number 3 and the number

Then the question about puzzle states. A puzzle state is a partly filled in sudoku that can only be completed in one way. A question about how many puzzle states are associated with a given sudoku is probably the right difficulty for a projecteuler problem.

The question about finding how many puzzle states there are is too hard. Especially if you must ignore the difference between equivalent puzzles (e.g. completing to equivalent sudoku's.) If we allow puzzles with several solutions, some questions become easy. Every sudoku is a solution for a puzzle with one field filled in, ignoring equivalence.

Groetjes Albert

--

Dunno.

Gack! Too much to absorb this early in the day! (or, possibly

From a first read, it doesn't seem like they are addressing the issue that I'm raising.

To use their terminology, I am only interested in "proper puzzles". Whether they are irreducible or not. I.e., consider:

and

and

as three different puzzles? (each with the same solution) I.e., all three would be considered "irreducible".

Then, complicate that with what they call "Sudoku preserving symmetries".

Finally, layer the solution methodology as a further constraint -- i.e., proper, irreducible puzzles that can be solved without "backup".

I can't see any "closed form" way of approaching the problem. It seems like you would just have to brute force enumerate each potential solution and determine which criteria (if any) it violates...

OTOH, consider the similar problem when applied to TTT...

Puzzles in the sense of the number of soluble starting grids? I don't think that has a solution other than brute force. The article mentions that much brute-force searching has been performed to determine whether there are any grids which are soluble with only 16 givens (no solutions to date).

The article links to this program:

for enumeration of possible starting grids for a single solution grid and a fixed number of givens. Running time is between 20 minutes and one day depending upon the solution grid. Clearly, doing that for all possible solution grids isn't feasable.

The calculations given in the article deal with the number of valid solution grids, i.e. how many ways you can assign numbers to squares such that each number occurs exactly once in each row, column and 3x3 block, and the number of distinct solution grids if you exclude rotations, reflections and/or permutations.

TTT only has one valid starting grid: the blank one. I don't know if there is an algorithmic solution; it's simple enough to brute force.

Yes -- if you assume these all define "proper" puzzles (their term)

That's what I fear.

Exactly. Hence the hope that their was some more "rational" way of arriving at the solution -- or, a ballpark estimate thereof.

But, the point with TTT is that you can come up with a reasonable estimate very quickly without resorting to brute force.

E.g., you know there are only 6 winning results (three for X, three for O). Further, you know that the X-wins can have at most two additional "moves" while the O-wins can have at most *one*. I.e., you can enumerate all of these "winning configurations" while accounting for reflections and rotations without much effort.

Then, you just have to figure out how many "non-winning" configurations to add to the mix to get a total number of unique "game possibilities".

Or any two lines or columns that are constrained within a particular "sub grid".

Likewise, reflections and rotations are equivalent.

To be more explicit, there can be a number of "puzzle states" reflecting a *single* "proper puzzle" in various degrees of completion. I.e., every "move" beginning from the "givens" to the "completed puzzle" represents a "puzzle state". Any one of which uniquely defines that *single* "proper puzzle".

(I think you have to deal with only the irreducible states to come to a meaningful answer. E.g., a puzzle state can represent a proper puzzle yet not be arrivable incrementally from some other puzzle state embodied in the current state!)

I.e., 81 puzzles. But, that isn't a useful answer! :>