simont | Thoughts on thoughts

Thoughts on thoughts

Since I added two new games to my puzzle collection recently, I've had a renewed interest in playing puzzle games. As has happened before, this has led me to notice things about the way I play them and start having deep thoughts about how I – and how people in general – think.

I notice when playing Solo (my Su Doku implementation, renamed to avoid confusion with www.sudoku.com and/or trademark law) that by far the most difficult thing for me is to scan a large grid and find the one deduction that can currently be made. Solo has configurable difficulty levels (each one requires more sophisticated forms of deductive reasoning than the last) and also a configurable grid size; it turns out that I find playing 2x3 Advanced to be significantly easier than 3x3 Trivial, because I prefer a complex problem I can find to a boringly simple one that I have to go hunting for.

This fits with previous things I've noticed about myself. I used to play a lot of Mao, and always tended to prefer games containing two or three difficult rules to games with fifteen utterly trivial ones; in the former case I tended to feel that the game was a complex mechanism which I was piloting skilfully, whereas in the latter case I tended to feel that I was frantically running back and forth trying to be everywhere at once and invariably missed something.

And it's the same when I'm programming: give me a big hard problem to sit and chew on and I'll eventually solve it (assuming it's not too hard of course), but give me lots of fiddly little things to fix and my to-do list will become disorganised, I'll miss things and get stressed about it. This is why PuTTY is so fortunate to have recruited people who can polish up all the tiny little loose ends after I've done major pieces of development.

Presumably this isn't the same for everybody. I wonder if people reading this have the same tendency as me in this area, or the opposite one (preferring tracking lots of little things to addressing a big thing). Or, even more interestingly, if there's anyone reading this who thinks that distinction is meaningless or misleading, or finds they can work in both modes with equal facility but find some other interesting distinction to be drawn between modes of thought they find easy and hard.

Flat | Top-Level Comments Only

3x3 Trivial is surprisingly tough, I find. The boring problems it raises do seem to take a lot of hunting for, more I think than for human-set puzzles.

Ah, that's interesting; perhaps there's more to difficulty grading than I've so far done. Perhaps I ought to be paying attention, at each stage of deduction, to how many possible deductions there are to be made; if you ever get down to a point where there's only one thing you can deduce, that's harder than if there are always eight or nine things you could usefully be doing.

On the other hand, it seems to me that a puzzle entirely composed of a single linear chain of reasoning, where there was only one deduction to be made at any stage, might actually be quite easy because every time you filled in a number you'd be easily able to find the next step just by asking yourself "now what additional information have I gained right here?", and wouldn't have to go looking over the whole grid each time. It's all terribly difficult and subjective.

I think it's different - some of the deductions themselves may be harder or easier to spot. I think it's easier to do positional elimination within a 3x3 cell than on a row/column (only need to scan 6 intersecting elements, vs. 12 on a row, and those elements don't cover the whole board), and I think there's some other factors, too. I suspect also that it's easier with lots of filled-in positions, where you don't need so many clues from outside the cell.

For a really advanced analysis, you could generate a "tech tree" for being able to discover the contents of cells. As you get more information on each cell, they move from being indeterminate through being hard-to-deduce (many scattered clues, no redundancy) to being easy (much redundancy, few clues needed, those that are are close at hand). The easiest puzzles would have a solution path with no hard deductions on, and the hardest would have critical points where you have to make one tough deduction before you proceed. In between would be puzzles where you have a choice of hard deductions - making one makes the others easy.

I'm already distinguishing blockwise positional elimination from row- or column-wise positional elimination; that's what separates my Trivial and Basic difficulty levels.

However, I agree this could be done better by paying attention to the number of empty cells. Basic difficulty level also introduces numeric elimination (observing that all but one of the possible numbers in a given square are ruled out, which will probably be due to a combination of row, column and block clues); but this is the obvious method of deduction used to fill in the last number in a block, a row, or a column, and that's definitely something that ought to be allowed in Trivial level. (Currently, in any puzzle labelled Trivial, there's always a blockwise-positional-elimination way to fill in any such single empty cell :-)

So perhaps I should rejig Trivial versus Basic so that all those modes of deduction are permitted in both levels, but it checks how quantitatively complex the deductions are in each case. Hmmm.

I feel that I break big hard problems into smaller ones, but that may just be a feature of the sort of problems I get handed/tend to take on.

I have no idea, really. I can work on a list of small brainless things, and I can work on big things, but I do them differently. Working on the GaN project this year, for example, I had lots of small tasks that were more or less boring but still vital, and then I had the one huge hurdle of understanding what was going on. I just sort of put the information in my head and a theory came out. Writing down the theory was back to small brainless tasks again, and since it involved sentences it was terrible but I'd rather that than let the Senior Examiners read my mind!

With regard to your puzzles, I can do the Net games easily, but I find Solo nearly impossible. I can do the 2x2 one moderately well, I've completed the 2x3 one once and not been able to many times. It's the same confusion that I used to feel when I played netball at school - too many things to be looking for at once.

It occurs to me that the GaN project had more things to be looking for, but I could do that. Then, the next step came into my head by itself from the bit of me that was procesing it; with Solo, I wait for it and it doesn't come. Maybe it's to do with the importance of the problem: the secret idea-producing bit of my brain knows that GaN was important but that Solo is just a game and it doesn't matter if I get it wrong or don't finish.

Then, the next step came into my head by itself from the bit of me that was processing it; with Solo, I wait for it and it doesn't come.

Hmm, that sounds vaguely familiar. I actually found the same thing when I first started playing Net, and I had a completely different theory about why it was. I wrote a rather long LJ entry on the subject at the time.

Oh, I'm glad it's not just me. (There was no reason why it should be!)

Do you ever get, when you change what you're working on or what technique you use, little bits of oddness that feel like a ship creaking when it turns around something? Forgetting something of a kind you normally wouldn't forget, or not being able to do a certain task automatically for a while?

I'm not entirely sure what you mean. Certainly I find that if I try to do something I used to be able to do automatically but haven't done in a while, it feels unfamiliar until it comes back to me, but I'm not sure I'd describe that as "oddness": it seems obviously natural that things should work that way. I therefore suspect I'm not thinking of the same thing you are.

I mean when you learn something completely new. Do it and see if you get weird things happening with the rest of your brain. (If you have time!)

Hmm. When I learned to play Solo recently I suddenly found it really odd to look at a (say) seven-digit number which had a repeated digit; I'd got so used to ensuring that never happened that I felt a subtle wrongness if I caught sight of, say, a catalogue number on some packaging. Is that the sort of thing, or are you thinking of glitches that have no obvious relation to the new thing being learned?

Things that have no obvious relation to the new thing, sort of.

This is interesting. I think on the whole I'm the opposite. I like organising lots of small things to come together or working out how lots of ideas relate to each other. It's why I enjoy my current job but didn't enjoy doing my doctorate.

I'm obviously not totally like this as hard mathematical problems do interest me more than they would the average person, but I was usually interested in solving them to see how the solution relates to solving other problems and how important the solution of the problem is rather than because I was interested in the solution per se (either that or I have a small competitive streak hidden in me somewhere!)

There's also still a limit to what I can juggle in my brain at once (is it seven things you can keep in short-term memory?) and I will still inevitably do things better if I'm tracking half a dozen main things rather than twenty.

I wonder if there's any link with gender here and the whole 'women are better at multitasking' thing. I suspect that the combination of being a mathematical type person / liking things to be logical and thinking like this rather than the way you do could be relatively unusual but I'm not sure.

I'm similar. I can wrestle with a big problem all night, but give me lots of irritating little houseworky jobs to do and I let them slide until I have a whole evening's worth mounting up, and then still fail to get round to it..

I don't mind having lots of little fiddly tasks, as long as they all have fairly immediate deadlines (else I don't get any of them done, because they're all too small to worry about, and then I get stressed because my To Do list is too long). I'm actually far less comfortable with one big project, and always break it down into managable sized tasks: I have to feel like I'm achieving something to derive any satifaction and security from my work. Having 50 min class periods is helpful for this!

In games I like both short rule-sets with far-reaching implications, and long complicated sets (I've been playing games like Carcasonne and Puerto Rico recently). I'm not so fond of games like Uno though, where the ability to memorize long lists of really trivial rules seems to be a bonus to the game. I did buy it recently, but only because my good friends children (who are 11 and 13) like to play, and I wanted it here for when they come round. I could never get to grips with Mao.

On a completely unrelated note, in case you don't already know them which you probably do,

bopeepsheep just plugged:

http://www.ok-foods.co.uk/

The only other attempt I've seen to algorithmically calculate the difficulty of this sort of puzzle is http://www.latinsquares.com/Explain.html#difficulty - the Latin Squares puzzles generated there are like Su Doku (never been quite sure how that pluralises) except that the boxes can be arbitrary n-ominos.

Thank you, by the way, for writing all this software and distributing it freely - the Su Doku solver is extremely powerful and very pleasant. Can I point you at the World Puzzle Championship (http://www.worldpuzzle.org/) which has a very wide variety of types of this sort of culture-free logic puzzle? I think you'd enjoy the puzzles therein.

My Mao preference was for lots of fairly easy interlocking rules, but I have strong preferences in Mao (and Nomic) that are at the fluffier end of the scale, sometimes attracting disdain from the hardcore intellects. :-)

When I'm developing, I find that I tend to be solidly focused but the scale of what I'm focused on switches back and forth.

The usual pattern is that I start out with some large scale goal in mind that I work steadily towards, often with little attention to the side issues. Sooner or later things are complete enough that the large scale goal is satisfied but the focus is still there unless I've burned out on the whole endeavour. With nothing big to tackle, I flip over to working away on the smaller things that I ignored before; their imperfections are big enough to annoy me, so I polish them.

The problem is that I can easily wind up gnawing and gnawing away on ever smaller things in what is not really a sensible use of time. I should just declare the whole thing good enough and move on, but my focus won't let me let go, so until I can find another large scale goal to chase I wind up polishing ever smaller bits that have ever more dubious alleged imperfections. This is especially bad in documentation, where I can repeatedly second-guess and water down perfectly good first pass writing.

(Writing this comment pretty much went that way: bang out the initial idea, then obsessively rewrite bits well past when I should have clicked 'submit' and gone on.)

I find big tasks more satisfying (when they're done) but also much harder to think about and more daunting. I like having all of the thing in my head at once, which makes some things easier but most hings much harder. I'm currently trying to learn how to cope without fitting the entire program into my head when writing assembler.

Observation: Solo uses an annoyingly large window for larger grid sizes which won't fit on a 1024x768 display :/

I'm turning over in my mind a Sudoku solver at the moment. My naive algorithm is this:

For each cell, determine the set of possible digits it can contain.
At the end of this scan, if there are 'easy' cells (with only one possible solution), fill these in and re-scan the grid until there are no more easy cells.
Take the cell with the smallest number of solutions and try the first. Continue scanning until either the grid is complete or we encounter a cell with no possible solutions. In this case, backtrack to the faulty decision and choose the next alternative solution. If there are no remaining alternative solutions, the puzzle is invalid.

This is rather unsatisfying, though; is there a more elegant procedure?

That sounds like exactly the recursive solver algorithm used in Solo. I actually have two solvers embedded in the program: that one, and a non-recursive one supporting all the reasoning techniques I know of short of guesswork. The non-recursive one is used to gauge the difficulty of a puzzle so that I can be sure of not accidentally setting one that requires recursive (guessing/backtracking) reasoning. But precisely because of this (and by design), the non-recursive solver cannot solve all puzzles that have a unique solution, while the recursive one can in principle.

I use the recursive solver to generate a filled grid to begin with (if you feed it no clues at all, randomise its choice of next square if there are more than one with the same smallest number of solutions, and randomise the order in which it works through the solutions for each square, then it will generate a random filled grid from nothing), and also to check solubility when deliberately generating Unreasonable-level (backtracking required) puzzles. I use the non-recursive solver to check solubility at all other levels.

I see what you mean about it being unsatisfying - certainly when I was told about this as a viable grid generation algorithm I felt disappointment because I'd been hoping for something much more interestingly combinatorial - but on reflection it's quite a clever recursive algorithm, because of the way it avoids running through all 10^23-odd possible filled grids. By always selecting the most constrained square to recurse into next, it prunes the search tree early and often, and thereby ends up running quite a lot faster than a more naive recursive approach.

Flat | Top-Level Comments Only

Thoughts on thoughts

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject