Further assorted waffling about puzzles [entries|reading|network|archive]
simont

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

Mon 2005-05-23 09:59
Further assorted waffling about puzzles

I spent the weekend working on my puzzle games (again). This time I arranged for Net to guarantee a unique solution, and also wrote code to print out Net puzzles so you can solve them on paper. The latter was a crazy idea I had on Saturday, but actually seemed quite playable once I'd got used to the idea and tweaked the graphic design a bit. If anyone's interested, I've put up a sample sheet (one wrapping and one not) at http://www.tartarus.org/~simon/20050523-netsample.pdf.

I was staggered by the low quality of the competition I'm up against in the desktop-puzzle-games niche. I discovered this week that there are several more implementations of the Net concept than mine and the one I pinched the idea from; quite a lot of the others go by the name of ‘NetWalk’ or trivial variations on same, and I count two or three Linux versions and a Windows one. The Windows one is particularly impressive: as far as I could tell from the website, it has no ability to generate its puzzles automatically, relying instead on a large stored database of them. Once you use up the database, you're stuffed, unless you design your own by hand – at which point you're apparently encouraged to submit them back to the authors for inclusion in the next version. And for this privilege they charge you $10 for a copy (and I wouldn't be surprised if they also charge for upgrades and extra puzzle designs), while all the free versions generate an endless supply of random puzzles. That's the Windows world for you.

Also it occurred to me recently that writing solvers and generators for puzzle games is a field in which I feel extremely at home, for some reason. I think it hits a sweet spot between several of my skills. I'm first and foremost a programmer, but also I have maths training, which means I'm well placed to be able to prove properties of the puzzles I'm working with and thus simplify my code. Also, writing solvers is about half algorithms – a particular interest of mine – and the other half is figuring out how to write an automated solver for the puzzle in question in the first place, which seems to me to be a self-awareness thing: solve one by hand and pay attention to the things you're thinking as you do it. And self-awareness itself is something that's always interested me. As a result, when I'm been doing this sort of stuff, I get extremely absorbed and enthused by it and it's a terrible let-down to come back to (say) work, at which I usually get to use at most one or two of my core skills at any one time.

Oh well. I'd better get back to work anyway…

LinkReply
[identity profile] rillaith.livejournal.comMon 2005-05-23 09:56
How does that puzzle work? *looks at your sample and has no idea what's expected of the puzzler*
Link Reply to this | Thread
[personal profile] simontMon 2005-05-23 10:04
*nods* It would probably make more sense if you'd encountered the electronic version already, which I was expecting most interested readers of this LJ to have done by now. If I were to publish a book of these (which seems unlikely :-) I'd make sure to provide a clear explanation at the front, and some sample problems with solutions.

The aim is to fill in the grid with a network of lines connecting together all the blobs and using all of the squares. Each square is either a T-piece, an endpoint (blob), a corner or a straight-edge, as shown by the small symbol in the corner of the square. So in each square you have to draw a large version of the small symbol, but it can be in any orientation so you have to work out which way round each one has to go.

The one without a thick border is the harder version, in which each edge of the grid is considered to be connected to the opposite edge, so that some of the connections in the network can wrap round from one side to the other. The thick-bordered one is the easier one in which this doesn't happen.
Link Reply to this | Parent | Thread
[identity profile] rillaith.livejournal.comMon 2005-05-23 10:30
Although I really like logic based puzzles, you have a tendency to refer to ones which I hadn't encountered previously - I've aquired a small Su Doku addiction after your last post ;) Probably me being a Windows user these days, I guess.

I'd not come across this puzzle before, but your explanation is clear and concise, and I will be printing these out to have a play. In fact, I've just found your puzzle games page... must resist downloading at work.... (Thanks!)
Link Reply to this | Parent | Thread
[personal profile] simontMon 2005-05-23 10:38
Argh, I forgot to mention two important points: the correct solution is a single connected network (you can reach any square from any other square by following lines), and is also acyclic (there are no loops, i.e. there is always only one way to get from any square to any other). Knowing those things allows you to make a lot of useful deductions, and the puzzle is probably not uniquely solvable without making use of at least one of them.

(In the electronic version, these are enforced by the solution checker so you have some chance of figuring them out for yourself...)
Link Reply to this | Parent | Thread
[identity profile] rillaith.livejournal.comTue 2005-05-24 12:32
Ohhhkay, Net is good; can get the bordered ones done pretty quickly.

But, I haven't yet managed to get any of the wrapping ones solved. I've got a few to a point of being hopelessly tangled in knots, with several squares blatantly not connectable with the rest of the configuration, but I haven't found any obvious starting points (like straights/Ts on the edges in the bordered version, for example), apart from occassionally-occuring straights between two end points. This makes it seem a lot more like trial and error (or randomly twisting things round and restarting again several times from the beginning for ages until stumbling over the correct solution) than anything involving logic. Am I missing some key point, or is the wrapping version really that ... random?
Link Reply to this | Parent | Thread
[identity profile] rillaith.livejournal.comTue 2005-05-24 12:35
I also meant to ask whether there's a size that's easier for the wrapping version, to get the hang of it?
Link Reply to this | Parent
[identity profile] rillaith.livejournal.comTue 2005-05-24 12:36
... apart from the straights between two ends - and grouped ends where there's only one direction out for some of them, I should have said.
Link Reply to this | Parent
[personal profile] simontTue 2005-05-24 12:45
There are quite a few possible starting patterns you can look for in a wrapping grid. You're correct that a straight between two endpoints is one of them. Others include:
  • an endpoint surrounded on three sides by other endpoints (the centre one only has one direction it can point)
  • a corner piece surrounded on three sides by endpoints (the corner piece must have a connection on the remaining edge so as not to connect two endpoints into a dead end)
  • a T-piece surrounded on three sides by endpoints (again, it must connect on the remaining edge otherwise it just connects the three endpoints together)
  • two endpoints and two straights arranged in a 2x2 square with opposite pieces identical (considering both ways for one of the straights to point should convince you that the endpoints cannot possibly connect on either of the two sides that don't border one of the two straights).
Also, keep in mind that a corner piece is always connected on one side if and only if it is not connected on the opposite side; so if one of the above deductions allows you to deduce that some piece has a connection on a particular side, and the next piece in that direction is a corner, then you know the piece beyond the corner does not have a connection on the near side - which allows you to nail down its orientation completely if it's a T-piece.

There are others as well, mostly more complex forms of dead-end avoidance. Those are just the first few that sprang to mind. It's certainly not random guesswork - I wouldn't expect to ever meet a wrapping Net puzzle I couldn't find somewhere to start on.

Link Reply to this | Parent | Thread
[identity profile] rillaith.livejournal.comTue 2005-05-24 13:57
Thank you! That clarifies several things I'd been doing instinctively in the bordered versions, that I hadn't extrapolated into conscious thought for the wrapping ones. I shall tackle them later. (Not now, not at work. Really not. Honest. I can resist. *cough*)

Now all I need is a "lock" option for tiles so I don't forget which ones were set that way for a reason darnit... ;)
Link Reply to this | Parent | Thread
[personal profile] simontTue 2005-05-24 14:05
Middle-click, or shift-click if you don't have a middle mouse button.
Link Reply to this | Parent | Thread
[identity profile] rillaith.livejournal.comTue 2005-05-24 15:09
Woo! Excellent.

And I just solved one, too *beam*
Link Reply to this | Parent
[identity profile] rillaith.livejournal.comTue 2005-05-24 17:37
Oddly, that has made more difference to solving the wrapping ones than anything else! Much obliged :)
Link Reply to this | Parent
[identity profile] geekette8.livejournal.comMon 2005-05-23 10:36
Currently trying to avoid going to look at your puzzle page....

BTW, there was a 3D Sudoku in Saturday's Telegraph (3x3x3, each vertical column through the cube, and each 3x3 sqaure in both vertical planes, is valid as well as each horizontal plane being a valid 3x3 grid in the normal way). The setter said he had constructed it to foil all those 2D Sudoku solvers that people have written... I immediately thought of you :-)
Link Reply to this | Thread
[identity profile] ptc24.livejournal.comMon 2005-05-23 12:03
Well some people will write solvers in 3D then. It'd probably take less time to adapt the solver to the puzzle, than to solve it by hand.
Link Reply to this | Parent
[personal profile] simontMon 2005-05-23 12:16
So you're saying it's a 9x9x9 cube, such that every 9x9 slice through it in any direction is a valid 2D Sudoku grid?

That's interesting, and different from the only other suggestion I've heard for 3D Sudoku. Since 2D Sudoku is a grid N^2 entries across, it seemed obvious that 3D Sudoku would have to be N^3: so for the usual N=3, you'd have a 27x27x27 cube, with every number from 1 to 27 appearing once in every row, once in every column, once in every row-in-the-other-direction, and once in every 3x3x3 sub-cube. Of course this would make N=3 rather unwieldy, so dropping down to N=2 and an 8x8x8 cube would probably be more sensible.

The version you describe seems somehow less "truly" 3-D, since there's no block constraint based on three-dimensional cubelets. It reminds me very much of the sense of letdown I experienced on seeing the "official" 3-D sequel to Tetris, Welltris. It seemed obvious to me that the right way to do 3-D Tetris was the way Block Out did it.

Ideally, though, it would be nice to find a form of 3-D puzzle which had all of 1-D (row and column), 2-D (subsquare in a single plane) and 3-D (subcube) constraints. I fear there's no way to do that, though.

(I don't see any need to update my solvers, incidentally: they're not there so I can cheat at published Sudoku puzzles, they're there as part of the necessary mechanism for automatically generating my own. Unless I plan to generate 3D puzzles myself, there's no need to bother.)
Link Reply to this | Parent | Thread
[identity profile] geekette8.livejournal.comMon 2005-05-23 12:23
So you're saying it's a 9x9x9 cube, such that every 9x9 slice through it in any direction is a valid 2D Sudoku grid?

Yep. I also felt the same disappointment that there's no constraint on the 3x3x3 sub-cubes.
Link Reply to this | Parent
navigation
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]