jdyer wrote:
Erik made a reference to this in his G4G speech, and I was wondering if there was more detail since it's just a line in the outline.
As promised, I'll expand on this a little informally here, and my thoughts now may not be the same as what I had in my head back then. It's a topic I like a lot. JDyer, I'm curious about your thoughts on it too. You mentioned some potential overlap with your work.
I first started thinking about this when I was a senior in high school, and my great friend Alan Reid gave me the
8 Queen puzzle to solve with code.
If you scan through every possible board state and evaluate for a solution, it takes a lot of time to solve, or at least much more time than the computer really needs with a more optimized solver.
You can break down the solution process different ways. But one obvious way is to think of the chess board like a combination lock, with each column of the board containing a number between 0 and 7 representing a proposed row position of a Queen in that column. You know that a winning state will never have two Queens in the same column, so just using a representation that assumes this throws out most of the potential board states.
Other optimizations are possible, The board has symmetry, so you could look through all the combinations for the first four columns and have found every solution. You just need to flip them horizontally to generate the mirror image solutions.
It hides the lazy puzzle solving idea to use a computer. Because it's still a computer marching through possible solutions, and doesn't illuminate the idea of laziness as practiced by the human puzzle solver. Instead imagine yourself sitting with a physical chessboard, no computer for miles around you. And you have to solve the Eight Queens Puzzle. In fact, go get a chessboard and try it.
You might, to get a sense of the stupidity and inhuman tediousness of it, try moving the eight queens through every possible state:
1. Line them all up along the top row. (NOT a solution)
2. Move the rightmost queen down one row. (NOT a solution)
3. Move the rightmost queen down another row. (NOT a solution)
etc, etc.
Also to do it like a perfect brute, be sure to try all the board states with queens in the same column.
The point of this exercise would be to note the impatience of your mind straining at the leash. If you solve this puzzle more naturally, you'll be finding shortcuts and general principles. Little rules and concepts form with you barely needing to try. And some of these rules will be visual in nature, using the fast pattern-matching capabilities of your brain. You'll know after a little bit of play that lines are *bad*. Whenever you see a line, be it horizontal, vertical, or diagonal, made up of 2 or more pieces, that is a non-solution. The pattern you are looking for is something like the lack of a pattern--perfectly disorganized.
LATE THOUGHT: Not quite right. Several of the solutions look fairly organized with lines at 2/1 slopes and so on.
We are too smart to be satisfied with plodding through busywork. And any puzzle that yields no opportunity for us to apply insights is at best a kind of meditation exercise. Good maybe for killing the last four hours of a transatlantic plane flight, when you can't sleep, but are too tired to do any proper thinking.
-Erik
____________________________
The Godkiller - Chapter 1 available now on Steam. It's a DROD-like puzzle adventure game.
dev journals |
twitch stream |
youtube archive (NSFW)
[Last edited by ErikH2000 at 04-06-2019 02:02 AM]