Examples & name for this category of puzzle?
April 8, 2015 5:18 PM Subscribe
Do you have a name and/or other examples for this class of puzzle like Sudoku, or 0h n0 or 0h h1?
I guess how I'd define what is in common between them, is the player is given a set of rules for what is permitted plus a subset of the board, and then must deduce the whole board from that.
I think magic squares can fit if you're given a starting point. N-queens problems also could fit, if you're given a starting point. So in these cases the "set of rules" would be "rows and columns add up to X" for magic squares, and "no queen threatens another queen" for N-queens problems.
I think Minesweeper and Mastermind would not fit, because you reveal new information as you play.
Crossword puzzles I think don't fit, because it relies more on the word clues than on deducing from the set of rules.
Do you have other examples of puzzles that might fit this category, and/or a name for it as a genre?
I guess how I'd define what is in common between them, is the player is given a set of rules for what is permitted plus a subset of the board, and then must deduce the whole board from that.
I think magic squares can fit if you're given a starting point. N-queens problems also could fit, if you're given a starting point. So in these cases the "set of rules" would be "rows and columns add up to X" for magic squares, and "no queen threatens another queen" for N-queens problems.
I think Minesweeper and Mastermind would not fit, because you reveal new information as you play.
Crossword puzzles I think don't fit, because it relies more on the word clues than on deducing from the set of rules.
Do you have other examples of puzzles that might fit this category, and/or a name for it as a genre?
I don't have a particular name for them, but I think most of the puzzles at Conceptis fit your description.
posted by ktkt at 5:39 PM on April 8, 2015
posted by ktkt at 5:39 PM on April 8, 2015
Logic puzzles is probably the best term that most people will understand, even though it's overly broad. Certainly it applies to mastermind, but also all kinds of riddles and bogus interview questions. Japanese publisher Nikoli invented a ton of them (including Sudoku) and to some puzzle people "Nikoli-style puzzle" probably would be a reasonable description for similar puzzles like 0h n0. Constraint satisfaction puzzles might also be a good term, but I don't think it's in that wide usage.
All these different puzzle types are, from a theoretical computer science point of view, in the computational complexity class "NP-complete". I do know a few dozen people for whom I could say "NP-complete constraints satisfaction puzzle" and they'd know exactly what I meant. But that's because I know a lot of giant nerds.
Incidentally, there is a full information variant of Minesweeper, that can be printed and solved on paper. It's a grid, and some spaces have numbers showing how many mines are next to them. You can use those to figure out where all the mines are. The reasoning ends up being sort of like all these other ones where you wind up with the same kind of cascading logic where maybe you know either A or B is a mine and either C or D is a mine but A and C can't both be mines. The downside is that there's no picture of the sun wearing cool shades.
posted by aubilenon at 5:43 PM on April 8, 2015 [2 favorites]
All these different puzzle types are, from a theoretical computer science point of view, in the computational complexity class "NP-complete". I do know a few dozen people for whom I could say "NP-complete constraints satisfaction puzzle" and they'd know exactly what I meant. But that's because I know a lot of giant nerds.
Incidentally, there is a full information variant of Minesweeper, that can be printed and solved on paper. It's a grid, and some spaces have numbers showing how many mines are next to them. You can use those to figure out where all the mines are. The reasoning ends up being sort of like all these other ones where you wind up with the same kind of cascading logic where maybe you know either A or B is a mine and either C or D is a mine but A and C can't both be mines. The downside is that there's no picture of the sun wearing cool shades.
posted by aubilenon at 5:43 PM on April 8, 2015 [2 favorites]
Hexcells, Hexcells Plus, and Hexcells Infinite (available on Steam) seem like appropriate additions to the genre--they are pretty much minesweeper, but with a Hex board, and the puzzle clues attempt to give you all the information to logically deduce the remainder of the board.
posted by foxfirefey at 5:48 PM on April 8, 2015
posted by foxfirefey at 5:48 PM on April 8, 2015
Actually, I take it back; I think it's too much new information revealing like Minesweeper, you have to follow the logic as you reveal more and more information; before I was thinking of how often in Minesweeper I've had to just...make a guess and hope it worked, having no logical deductions left to guide me, which seemed beside the point.
posted by foxfirefey at 5:50 PM on April 8, 2015
posted by foxfirefey at 5:50 PM on April 8, 2015
Slitherlink puzzles seem to fit the category (whatever it's called).
posted by Lexica at 9:21 PM on April 8, 2015
posted by Lexica at 9:21 PM on April 8, 2015
Here is a link to a horde of similar puzzles, including many variants of what others have described above. It's hard to give a name to each one beyond 'logic puzzles' since they all seem to have their own origins and original names, but in most cases the rules fit exactly what you are describing: Here's a board with some clues / hints, and you have to fill the rest in.
posted by SquidLips at 9:32 PM on April 8, 2015
posted by SquidLips at 9:32 PM on April 8, 2015
In my computer science classes they were called "constraint satisfaction problems."
posted by Nerd of the North at 11:33 PM on April 8, 2015
posted by Nerd of the North at 11:33 PM on April 8, 2015
My favorite version of a KenKen puzzle is EverydayGenius' Square Logic puzzle. I like having the computer keep track of the numbers I've eliminated, and I love having huge 9x9 boards to solve.
posted by CathyG at 10:58 AM on April 9, 2015
posted by CathyG at 10:58 AM on April 9, 2015
Many of the puzzles in Simon Tatham's collection are like this. (previously)
posted by teraflop at 11:04 AM on April 9, 2015
posted by teraflop at 11:04 AM on April 9, 2015
This thread is closed to new comments.
* "the process of reasoning from one or more statements (premises) to reach a logically certain conclusion"
posted by Rhaomi at 5:32 PM on April 8, 2015