I'm sure some of you have heard of the game Sherlock by Everett Kaser [color="#476c8e"]http://www.kaser.com/sherwin.html. I was wondering if anyone knew what kind of puzzle generation algorithm would be used in this? The executable is very small yet it holds 64k combinations, so each puzzle is most likely generated on the fly.
Any ideas?
Sherlock algorithm
The game description on the page you link is incomplete, but it seems the sort of puzzle that can be easily generated procedurally.
A computer player can attempt to solve a randomly generated (possibly inconsistent or unsolvable) puzzle candidate: if it succeeds, the puzzle can be submitted to the player (and you have an estimate of how difficult it is).
It might be possible to correct puzzles instead of starting from scratch after failure, or even to have an algorithm that guarantees to produce only correct puzzles.
A computer player can attempt to solve a randomly generated (possibly inconsistent or unsolvable) puzzle candidate: if it succeeds, the puzzle can be submitted to the player (and you have an estimate of how difficult it is).
It might be possible to correct puzzles instead of starting from scratch after failure, or even to have an algorithm that guarantees to produce only correct puzzles.
I would probably start with a completed field where each row has been shuffled somewhat, then pick x known images. After that I'd start generating clues while attempting to solve after each clue using humanoid methods.
Maybe keep a list of possibilities for each slot (image) after each clue was placed and only generate clues involving slots that have multiple possibilities. Once there's only one possibility for each slot, you have a complete solvable puzzle. Should be easy enough.
Next step would be generating fields with predictable difficulty levels. For easier levels, you might place a larger portion of known images to begin with, and perhaps more distributed.. For easy levels, you might also give the player a few extra clues. It seemed to me that having more column clues makes it easier (they were most useful) while 'X is to the left/right of Y' clues were least useful and therefore suited for harder games.
I'd also suggest generating clues 'recursively' (not sure that's the best word for it.. maybe iterative-deepening is better) and by that I mean you could for each step in the clue generation phase you could generate n 'candidate clues'. For each candidate, you'd compute it's usefulness (how many possibilities did it remove, ...) and select the most/least useful one depending on level.
Maybe keep a list of possibilities for each slot (image) after each clue was placed and only generate clues involving slots that have multiple possibilities. Once there's only one possibility for each slot, you have a complete solvable puzzle. Should be easy enough.
Next step would be generating fields with predictable difficulty levels. For easier levels, you might place a larger portion of known images to begin with, and perhaps more distributed.. For easy levels, you might also give the player a few extra clues. It seemed to me that having more column clues makes it easier (they were most useful) while 'X is to the left/right of Y' clues were least useful and therefore suited for harder games.
I'd also suggest generating clues 'recursively' (not sure that's the best word for it.. maybe iterative-deepening is better) and by that I mean you could for each step in the clue generation phase you could generate n 'candidate clues'. For each candidate, you'd compute it's usefulness (how many possibilities did it remove, ...) and select the most/least useful one depending on level.
Have you looked into the generation of Sudoku puzzles? There are quite a few articles and discussions online on that subject, and it seems to me that under the hood, this Sherlock puzzle can probably be thought of in rather similar terms as Sudoku. The problem can be expressed as that of finding a solution to a set of logical constraints, and puzzle generation consists of adding constraints while keeping the problem feasible, or removing constraints while keeping the solution unique.
So my thinking is that once you have read up on Sudoku, you could try to abstract the ideas used for puzzle generation in that context, and then transfer them to the type of puzzle you want to create.
So my thinking is that once you have read up on Sudoku, you could try to abstract the ideas used for puzzle generation in that context, and then transfer them to the type of puzzle you want to create.
Author
Have you looked into the generation of Sudoku puzzles? There are quite a few articles and discussions online on that subject, and it seems to me that under the hood, this Sherlock puzzle can probably be thought of in rather similar terms as Sudoku. The problem can be expressed as that of finding a solution to a set of logical constraints, and puzzle generation consists of adding constraints while keeping the problem feasible, or removing constraints while keeping the solution unique.
So my thinking is that once you have read up on Sudoku, you could try to abstract the ideas used for puzzle generation in that context, and then transfer them to the type of puzzle you want to create.
Thanks Prefect. I never thought of that. It is similar to Sudoku in some ways. I'll take a look.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement