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

31–40 of 64 posts

Re: Binary Puzzle

#31

Post by eriknstr »

bluetwo wrote: post #28
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'm curious how long it would take to solve a hard puzzle using this technique. Anyone know?

A hard variant of binary puzzle, or a puzzle that is different from the binary puzzle and is also hard?

If the former, the 10x10 puzzle for today (solved in parent comment) is classified as "very hard".

Re: Binary Puzzle

#34

Post by savanaly »

ralfd wrote: post #30

I am stuck. What is the next step here? (Aside from programming it in Prolog.) https://i.imgur.com/ezUHHBp.png

Look for columns and rows where you have four of the five of 0's or 1's. Knowing there can be only one more of that type in the remaining empty spots usually yields something unless it's down to two empty spots.

Re: Binary Puzzle

#35

Post by bluehawk »

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…

Click on "Tips" at the top. http://binarypuzzle.com/tips.php

Re: Binary Puzzle

#36

Post by taserian »

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.

Re: Binary Puzzle

#37

Post by tedmiston »

tedmiston wrote: post #11
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…

Sudoku puzzles are created both automatically and semi-automically / modified by hand to make them more elegant or enjoyable. I've bought a few sudoku puzzle books that usually discuss it like an art in the preface.

Oh and about designing for difficulty level — I think it's sort of reverse engineered from the fully solved state by continually removing numbers until it's more sparse / harder. I believe some of the apps do it by incubating puzzles then gathering aggregate statistics about how long it took people to solve then bucket easy, 5-10 min --> medium, 10-15 --> hard, 15+ min --> evil, etc.

Re: Binary Puzzle

#38

Post by tedmiston »

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…

From the page:

> "Algorithm X" is the name Donald Knuth used in his paper "Dancing Links" to refer to "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem. Technically, Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm. While Algorithm X is generally useful as a succinct explanation of how the exact cover problem may be solved, Knuth's intent in presenting it was merely to demonstrate the utility of the dancing links technique via an efficient implementation he called DLX.

Re: Binary Puzzle

#39

Post by zmonx »

bluetwo wrote: post #28
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'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
    cache size      : 8192 KB
Prolog is very well suited for solving such combinatorial tasks, and the powerful pruning algorithms of constraint-based solutions using Prolog will often outperform other formulations of such problems.

I have used the following Prolog code to benchmark the running time of a goal:

    goal_time(Goal, Time) :-
            statistics(runtime, [T0,_]),
            (   catch(Goal, error(resource_error(memory), _), E = memory) ->
                true
            ;   functor(Goal, F, A),
                portray_clause(failed(F/A))
            ),
            statistics(runtime, [T1,_]),
            T #= T1 - T0,
            (   nonvar(E) ->
                Time = exception(E, T)
            ;   Time = time(T)
            ).
For example, it takes about 1 second (990 milliseconds) to count from 1 to 10 million:

    ?- goal_time(ignore((between(1,10000000,_),false)), T).
    T = time(990).

Re: Binary Puzzle

#40

Post by rmidthun »

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…

The source code to Simon Tatham's Puzzles is open-source, so you could see how at least one person does it.

https://www.chiark.greenend.org.uk/~sgtatham/puzzles/devel/ https://git.tartarus.org/?p=simon/puzzles.git;a=summary

Post reply on HN