Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Binary Puzzle

binarypuzzle.com

Post reply on HN
Print view View original

51–60 of 64 posts

Re: Binary Puzzle

#51

Post by codeulike »

tome wrote: post #6

I wonder how one creates puzzles like this (or indeed creates Sudoku puzzles). I can think of a few strategies 1. Lovingly hand craft them. Extremely labour intensive! 2. Generate random grids and repeatedly remove elements. If that leads to a puzzle with more than one solution, backtrack. 3. Add random elements to an empty grid. Eventually the grid will have one or zero solutions. If zero, backtrack. If one, stop. F…

I came to the conclusion that in any _decent_ puzzle there is unlikely to be an analytic short-cut that lets you create the puzzles. I've written a maths/maze game called Numplussed and wrote a level generator for it that was essentially random puzzle + brute force with a few optimisations. The level generator means that game has over 300,000 levels.

http://numplussed.com (free on iOS and Android)

The random+brute force approach turned out to be very interesting - the algorithm came up with puzzles that I never would have thought of if I was hand-crafting the levels. Or, say, if I had written a level generator with a specific sort of problem/solution in mind.

e.g. here's one of the hard levels that got generated: http://imgur.com/bqIvDCw . See here for the rules: https://www.youtube.com/watch?v=7D0i2Ce9Ujo

Re: Binary Puzzle

#52

Post by bsurmanski »

alangpierce wrote: post #17

If anyone else was confused by the rule "No more than two similar numbers below or next to each other are allowed", I think it means that you aren't allowed to have three in a row of the same number, horizontally or vertically.

Why? Is this a property to guarantee there are no duplicate binary numbers, or an arbitrary rule to make the puzzle tractable?

Re: Binary Puzzle

#53

Post by ZephyrP »

zmonx wrote: post #4

The declarative programming language Prolog is a natural choice for solving such combinatorial tasks. Here is a Prolog formulation of the puzzle, using constraint logic programming over integers that ships with typical Prolog systems: binary_puzzle(Rows) :- length(Rows, L), maplist(same_length(Rows), Rows), maplist(only_two_next_to_each_other, Rows), transpose(Rows, Cols), maplist(only_two_next_to_each_other, Cols),…

I like your Prolog solution! I thought I'd take a crack at a Python SAT-solver solution, also done in less than 1 second.

  from z3 import *
  
  # we use '-1' for empty
  instance  = ((-1,-1,-1,-1,-1,1,-1,-1,-1,1),
             (1,-1,-1,-1,-1,-1,-1,0,-1,-1),
             (-1,-1,0,-1,-1,-1,-1,0,-1,-1),
             (-1,0,0,-1,-1,-1,0,-1,-1,1),
             (1,-1,-1,-1,-1,-1,-1,-1,-1,1),
             (-1,-1,-1,0,-1,-1,1,-1,-1,-1),
             (0,-1,-1,-1,-1,1,-1,-1,-1,-1),
             (-1,-1,-1,-1,-1,-1,-1,0,-1,0),
             (0,-1,-1,-1,-1,-1,-1,-1,-1,0),
             (-1,0,-1,0,-1,1,-1,-1,-1,-1))

  
  size = len(instance)
  
  # we could use bitvecs here too
  X = [ [ Int("x_%s_%s" % (i+1, j+1)) for j in range(size) ]
        for i in range(size) ]
  
  # each cell is a 1 or a 0
  cells_c  = [ And(0
Generates:

  [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
   [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
   [0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
   [1, 0, 0, 1, 0, 1, 0, 1, 0, 1],
   [1, 0, 1, 0, 1, 0, 0, 1, 0, 1],
   [0, 1, 1, 0, 1, 0, 1, 0, 1, 0],
   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
   [1, 0, 1, 0, 0, 1, 1, 0, 1, 0],
   [0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
   [1, 0, 1, 0, 0, 1, 1, 0, 0, 1]]

Re: Binary Puzzle

#54

Post by snarf21 »

GrantSolar wrote: post #18

I feel that the rules should contain some examples. I spent a while battling a puzzle to realise that I had been interpretting "No more than two similar numbers next to or below each other are allowed." as "A box must have no more than 2 neighbours of each number" i.e. Exactly 2 0s and exactly 2 1s in the non-diagonal neighbours. I think that what's being referred to is runs of numbers, so if you see 0,0,_ you know t…

I wish there was a simple option to right click on a square you know that makes it read only while you figure out the rest.

Re: Binary Puzzle

#55

Post by thomasahle »

zmonx wrote: post #39
bluetwo wrote: post #28

Earlier quoted context omitted.

I'm curious how long it would take to solve a hard puzzle using this technique. Anyone know?

As eriknstr correctly points out, the puzzle I have included above is already classified as "very hard". SICStus Prolog 4.3.2 takes about 20 milliseconds to find the solution with the formulation I posted. I tested this on a machine where cat /dev/cpuinfo yields: vendor_id : GenuineIntel cpu family : 6 model : 26 model name : Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz stepping : 5 microcode : 0x11 cpu MHz : 2668.000 cach…

Did you try graphing how runtime scales as a function of puzzle size? (Assuming there are puzzles available of large sizes.) It would also be cool if your program could be used to generate new puzzles?

Re: Binary Puzzle

#56

Post by jnbiche »

taserian wrote: post #36
tome wrote: post #6

I wonder how one creates puzzles like this (or indeed creates Sudoku puzzles). I can think of a few strategies 1. Lovingly hand craft them. Extremely labour intensive! 2. Generate random grids and repeatedly remove elements. If that leads to a puzzle with more than one solution, backtrack. 3. Add random elements to an empty grid. Eventually the grid will have one or zero solutions. If zero, backtrack. If one, stop. F…

I've been searching for this myself for some time, but either I don't know the proper search terms, or the knowledge is scattered such that the terminology isn't fixed.

This would be some sort of "constraint satisfaction" algorithm (ie, the same basic approach as used in Computer Algebra Systems(CAS) ). There are various approaches to these kinds of problems: someone above mentioned a backtracking algorithm.

Re: Binary Puzzle

#58

Post by kybernetikos »

fenomas wrote: post #14
tome wrote: post #6

I wonder how one creates puzzles like this (or indeed creates Sudoku puzzles). I can think of a few strategies 1. Lovingly hand craft them. Extremely labour intensive! 2. Generate random grids and repeatedly remove elements. If that leads to a puzzle with more than one solution, backtrack. 3. Add random elements to an empty grid. Eventually the grid will have one or zero solutions. If zero, backtrack. If one, stop. F…

> Is there some "analytic" property that guarantees uniqueness of solutions without resorting to some black box solver? Check out Knuth's Algorithm X. It's an elegant way of analyzing constraint-satisfaction sorts of problems (of which both Sudoku and the linked puzzle are examples). https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X edit: at least I think the linked puzzle is a constraint problem that could be mode…

Algorithm X can 'solve' puzzles with multiple solutions, so it doesn't guarantee a unique solution.

Here's my implementation: http://dancing-links.herokuapp.com/ It's happy enough solving an empty sudoku grid (you can try it near the bottom of that page).

And yes, I think I could model this game as an exact cover problem (and therefore suitable for algorithm X) - you have a choice for each square to put a 1 in it or a 0 in it, you have the constraints that the rules tell you that you have. (e.g. col 1 must not be equal to col 2, and so on for all possible column pairings, and the same for rows, and col 1 has the same number of 1s as 0s for all columns, and col 1 does not contain more than 2 1s next to each other, etc...) It shouldn't be all that hard to modify my code above to solve it.

Re: Binary Puzzle

#59

Post by KGIII »

ZephyrP wrote: post #53
zmonx wrote: post #4

The declarative programming language Prolog is a natural choice for solving such combinatorial tasks. Here is a Prolog formulation of the puzzle, using constraint logic programming over integers that ships with typical Prolog systems: binary_puzzle(Rows) :- length(Rows, L), maplist(same_length(Rows), Rows), maplist(only_two_next_to_each_other, Rows), transpose(Rows, Cols), maplist(only_two_next_to_each_other, Cols),…

I like your Prolog solution! I thought I'd take a crack at a Python SAT-solver solution, also done in less than 1 second. from z3 import * # we use '-1' for empty instance = ((-1,-1,-1,-1,-1,1,-1,-1,-1,1), (1,-1,-1,-1,-1,-1,-1,0,-1,-1), (-1,-1,0,-1,-1,-1,-1,0,-1,-1), (-1,0,0,-1,-1,-1,0,-1,-1,1), (1,-1,-1,-1,-1,-1,-1,-1,-1,1), (-1,-1,-1,0,-1,-1,1,-1,-1,-1), (0,-1,-1,-1,-1,1,-1,-1,-1,-1), (-1,-1,-1,-1,-1,-1,-1,0,-1,0),…

This may be frowned upon, but the above post and the parent post are why I visit, even if I don't comment much.

Re: Binary Puzzle

#60

Post by fenomas »

kybernetikos wrote: post #58
fenomas wrote: post #14

Earlier quoted context omitted.

> Is there some "analytic" property that guarantees uniqueness of solutions without resorting to some black box solver? Check out Knuth's Algorithm X. It's an elegant way of analyzing constraint-satisfaction sorts of problems (of which both Sudoku and the linked puzzle are examples). https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X edit: at least I think the linked puzzle is a constraint problem that could be mode…

Algorithm X can 'solve' puzzles with multiple solutions, so it doesn't guarantee a unique solution. Here's my implementation: http://dancing-links.herokuapp.com/ It's happy enough solving an empty sudoku grid (you can try it near the bottom of that page). And yes, I think I could model this game as an exact cover problem (and therefore suitable for algorithm X) - you have a choice for each square to put a 1 in it or…

> Algorithm X can 'solve' puzzles with multiple solutions, so it doesn't guarantee a unique solution.

It can be used in a straightforward way to count how many solutions are possible for a given layout.

So for generating games, you could add numbers to an empty board until there are less than n solutions, then pick one of the solutions and add numbers from it until the solution is unique, then add a few more until it's overspecified to be a bit easier, etc.

Post reply on HN