Binary Puzzle(binarypuzzle.com)

137 pointsby mabynogy9 anni fa60 comments

http://binarypuzzle.com/

63 comments

It's actually a little bit like doing deductions in minesweeper... without the random probabilities and timer

Very cool! It keeps saying that it's not solved correctly, but i cannot find the mistake: http://i.imgur.com/qPJLafH.png

Already ironed out identical columns but can't seem to find anything else. Any idea?

coroxout9 anni fa

I also have a filled-in square which it says is incorrect with no indication of where/why it's incorrect, which is quite frustrating. Would it really be too easy if you could guess and then be told why it was inconsistent?

cerebrum9 anni fa

1. and 6. row identical.

sushimako9 anni fa

1 & 7, thanks!

EvanKelly9 anni fa

Oh Hi (https://play.google.com/store/apps/details?id=com.presto.ohh...) is an app I have that has these puzzles.

Simple rules and can get surprisingly difficult.

eldavojohn9 anni fa

What's the difference between your app (that has 100-500 downloads) and this app that has 100,000-500,000 downloads?

https://play.google.com/store/apps/details?id=com.q42.ohhi&h...

EvanKelly9 anni fa

Ha, oops, my wording was bad...I meant I had it on my phone...not my app and I just searched the app store. I'll change my link.

EDIT: No way to edit old posts, but the link I posted is obviously a rip-off of the Q42 app linked elsewhere.

pavel_lishin9 anni fa

Even the description is a word-for-word copy of 0h h1.

grumph9 anni fa

It's "Unruly" in Simon Tatham's puzzle collection[1]. There is also an android version [2].

In the manual: "This puzzle type was invented by Adolfo Zanellati, under the name ‘Tohu wa Vohu’."

[1] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

[2] https://chris.boyle.name/projects/android-puzzles/ or https://f-droid.org/repository/browse/?fdfilter=puzzles&fdid...

schoen9 anni fa

Nice! For people who don't get the reference in the name Zanellati gave,

https://en.wikipedia.org/wiki/Tohu_wa-bohu

Edit: I didn't realize that, as Wikipedia says, this Hebrew phrase is used as a loanword in several European languages to refer to disorder, which in turn explains why Tatham called it "Unruly".

zmonx9 anni fa

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),
            maplist(booleans_integer, Rows, RIs),
            all_different(RIs),
            maplist(booleans_integer, Cols, CIs),
            all_different(CIs),
            Half #= L // 2,
            maplist(equally_distributed(Half), Rows),
            maplist(equally_distributed(Half), Cols).

    equally_distributed(L, Bs) :-
            global_cardinality(Bs, [0-L,1-L]).

    booleans_integer(Bs, I) :-
            foldl(pow, Bs, 0-0, I-_).

    pow(B, N0-I0, N-I) :-
            B in 0..1,
            N #= N0 + B*2^I0,
            I #= I0 + 1.

    only_two_next_to_each_other([]).
    only_two_next_to_each_other([_,_]).
    only_two_next_to_each_other([A,B,C|Rest]) :-
            ( A #= B ) #==> ( C #\= B ),
            ( B #= C ) #==> ( B #\= A ),
            only_two_next_to_each_other([B,C|Rest]).

For example, let us consider the concrete 10x10 puzzle of today:

    puzzle([[_,_,_,_,_,1,_,_,_,1],
            [1,_,_,_,_,_,_,0,_,_],
            [_,_,0,_,_,_,_,0,_,_],
            [_,0,0,_,_,_,0,_,_,1],
            [1,_,_,_,_,_,_,_,_,1],
            [_,_,_,0,_,_,1,_,_,_],
            [0,_,_,_,_,1,_,_,_,_],
            [_,_,_,_,_,_,_,0,_,0],
            [0,_,_,_,_,_,_,_,_,0],
            [_,0,_,0,_,1,_,_,_,_]]).

You can solve it with the above formulation, using for example SICStus Prolog and its CLP(FD) library, with the following query:

    ?- puzzle(Rows),
       binary_puzzle(Rows),
       maplist(label, Rows),
       maplist(portray_clause, Rows).

The unique solution is:

    [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, 1, 0, 1, 0].
    [1, 0, 0, 1, 1, 0, 0, 1, 0, 1].
    [1, 0, 1, 0, 0, 1, 0, 0, 1, 1].
    [0, 1, 1, 0, 1, 0, 1, 1, 0, 0].
    [0, 1, 0, 1, 0, 1, 0, 0, 1, 1].
    [1, 0, 1, 0, 1, 0, 1, 0, 1, 0].
    [0, 1, 0, 1, 1, 0, 1, 1, 0, 0].
    [1, 0, 1, 0, 0, 1, 0, 1, 0, 1].

It is found within a second on current machines.

The above formulation is also quite general. For example, you can use it to complete, test and generate solutions:

    ?- binary_puzzle(Rows),
       maplist(label, Rows),
       maplist(portray_clause, Rows).

This generates valid solutions of the puzzle for all board sizes:

    Rows = [] ;
    [0, 1].
    [1, 0].
    Rows = [[0, 1], [1, 0]] ;
    [1, 0].
    [0, 1].
    Rows = [[1, 0], [0, 1]] ;
    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 0, 1, 0].
    [1, 1, 0, 0].
    Rows = [[0, 0, 1, 1], [0, 1, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0]] ;
    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 1, 0, 0].
    [1, 0, 1, 0].
    Rows = [[0, 0, 1, 1], [0, 1, 0, 1], [1, 1, 0, 0], [1, 0, 1, 0]] ;
    etc.

Thank you for sharing!

ZephyrP9 anni fa

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 <= X[i][j], X[i][j] <= 1) for i in range(size) for j in range(size) ]
  
  # each row contains as many 1s as 0s
  rows_c   = [ Sum(X[i]) == size / 2 for i in range(size) ]
  
  # each column contains as many 1s as 0s
  cols_c   = [ (Sum([ X[i][j] for i in range(size) ]) == size / 2)
               for j in range(size) ]
  
  # each cell can only have 2 neighbors sharing it's number.
  rows_not_alike = [ If(X[i][j] == X[i][j-1], X[i][j+1] != X[i][j-1], True) for i in range(size)
                     for j in range(size-1) ]
  
  cols_not_alike = [ If(X[i][j] == X[i-1][j], X[i-1][j] != X[i+1][j], True) for i in range(size-1)
                     for j in range(size) ]
  
  puzzle_c = cells_c + rows_c + cols_c + rows_not_alike + cols_not_alike
  
  instance_c = [ If(instance[i][j] == -1, True, X[i][j] == instance[i][j]) for i in range(size) for j in range(size) ]
  
  s = Solver()
  s.add(puzzle_c + instance_c)
  print s.to_smt2()
  if s.check() == sat:
      m = s.model()
      r = [ [ m.evaluate(X[i][j]) for j in range(size) ] for i in range(size) ]
      print_matrix(r)
  else:
      print "failed to solve"

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]]

KGIII9 anni fa

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

zmonx9 anni fa

Very nice! I see you are using a way to express the constrant "at most two cells of the same value in direct succession in each row and column " that is shorter than the formulation I have posted.

I used a conjunction of two constraints, for each triple of cells A, B, C in direct succession:

    ( A #= B ) #==> ( C #\= B ),
    ( B #= C ) #==> ( B #\= A )

And you are using only one constraint:

    B #= A #==> C #\= A

To the SAT purist, the question may now arise: Are these ways really equivalent, do they state the same constraint?

One way to check it is to apply CLP(B): Constraint Logic Programming over Boolean variables, which ships for example in SICStus Prolog and is provided as library(clpb).

Using this library, we can ask:

    ?- taut((((A =:= B) =< ( C =\= B))*
             ((B =:= C) =< ( B =\= A)))
         =:= ((B =:= A) =< ( C =\= A)),
             T).

This asks whether it is a tautology (taut/2) that the two ways to express the constraint are equivalent.

The system answers:

    T = 1,
    sat(A=:=A),
    sat(B=:=B),
    sat(C=:=C).

So: Yes, the two ways are in fact equivalent, because this equivalence always holds. Yours being shorter, I would in fact prefer it and could also use it in the Prolog solution! Well done!

One additional neat thing about the Prolog solution: Since no further solution is found on backtracking in this case, we have in fact also verified that the reported solution is indeed unique. I suppose this check could also be added to your solution somehow to make such observations possible?

For example, suppose I modify the puzzle to read:

    puzzle([[_,_,_,_,_,_,_,_,_,1],
            [1,_,_,_,_,_,_,0,_,_],
            [_,_,0,_,_,_,_,0,_,_],
            [_,0,0,_,_,_,0,_,_,1],
            [1,_,_,_,_,_,_,_,_,1],
            [_,_,_,0,_,_,1,_,_,_],
            [0,_,_,_,_,1,_,_,_,_],
            [_,_,_,_,_,_,_,0,_,0],
            [0,_,_,_,_,_,_,_,_,0],
            [_,0,_,0,_,1,_,_,_,_]]).

Then there are 144 solutions (I have removed the first "1" from the first row), which I can generate with the Prolog solution within a second.

bluetwo9 anni fa

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

zmonx9 anni fa

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).

thomasahle9 anni fa

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?

zmonx9 anni fa

You can readily use the Prolog code I posted to generate such puzzles.

For example, you can go about it as follows. First, let us define the following relation that yields the N-th solution of a given Prolog goal:

    call_nth(Goal_0, C) :-
       State = count(0,_),
       Goal_0,
       arg(1, State, C1),
       C2 #= C1+1,
       nb_setarg(1, State, C2),
       C = C2.

We can use this as a building block to determine whether a given puzzle is still well-defined in the sense that it only admits a single solution. If call_nth(Goal, 2) for a given Goal succeeds, then we know that there are at least 2 answers, which is what we want to avoid in this case.

So, I define single_solution/1 to be true iff there are not two solutions:

    single_solution(Rows) :-
            \+ ( binary_puzzle(Rows),
                   append(Rows, Vs),
                   call_nth(label(Vs), 2) ).

As a further building block, consider the definition of generalize_row/2, which relates a given roster with hints to a generalized version where at most one hint has been removed:

    generalize_row([], []).
    generalize_row([Row|Rows0], [Row|Rows]) :-
            generalize_row(Rows0, Rows).
    generalize_row([Row0|Rows], [Row|Rows]) :-
            generalize_element(Row0, Row).

    generalize_element([], []).
    generalize_element([I|Es], [_|Es]) :- integer(I).
    generalize_element([E|Es0], [E|Es]) :-
            generalize_element(Es0, Es).

For example, here are the various possible generalizations for a single row, obtained by removing at most a single hint in each case, and replacing it by a logical variable:

    ?- generalize_element([1,0,1], Ls).
    Ls = [_54540, 0, 1] ;
    Ls = [1, _54546, 1] ;
    Ls = [1, 0, _54552] ;
    Ls = [1, 0, 1].

Note how different generalizations are naturally obtained via backtracking.

With these building blacks, everything is in place to generate such puzzles, with code that could look as follows:

    generate_puzzle(N, Hints, Rows) :-
            length(Rows0, N),
            binary_puzzle(Rows0),
            append(Rows0, Vs),
            once(label(Vs)),
            Hints #= N^2 - R,
            length(Rs, R),
            foldl(remove_hints, Rs, Rows0, Rows).

    remove_hints(_, Rows0, Rows) :-
            generalize_row(Rows0, Rows),
            Rows0 \== Rows,
            single_solution(Rows).

This starts from a fully instantiated roster of size NxN, and then successively removes hints. It is a ternary relation, also yielding the number of hints that remain, and of course the list of rows that constitute the found puzzle.

Here is an example invocation for N=4:

    ?- generate_puzzle(4, H, Rows),
       maplist(portray_clause, Rows).

The first two answers are:

    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 0, 1, 0].
    [1, 1, 0, 0].
    H = 16,

    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [1, 0, 1, 0].
    [_, 1, 0, 0].
    H = 15

In the first solution, all hints are still present, and in the second solution, exactly one hint was removed.

You can use the second argument to specify the number of hints you want for the final puzzle, which you can regard as setting a difficulty (lower makes it harder). For example, let us try to find solutions with only 10 (instead of 16 or 15) hints:

    ?- generate_puzzle(4, 10, Rows),
       maplist(portray_clause, Rows).

In that case, we find for example:

    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [_, _, 1, 0].
    [_, _, _, _].

and also:

    [0, 0, 1, 1].
    [0, 1, 0, 1].
    [_, 0, _, 0].
    [_, _, _, _].

In the 10x10 puzzle I showed earlier, only 22 hints are present, making it classified as "very hard". Let us generate 10x10 puzzles that are easier by containing more hints. For example, let us generate a 10x10 puzzle with 30 hints via the query:

    ?- generate_puzzle(10, 30, Rows),
       maplist(portray_clause, Rows).

Within at most seconds, we get for example:

    [0, 0, 1, 0, 0, 1, 1, 0, 1, 1].
    [0, 0, 1, 0, 1, 0, 1, 0, 1, 1].
    [_, _, _, _, _, _, _, _, _, 0].
    [_, _, _, _, 1, _, 1, 1, _, 1].
    [_, 1, _, _, _, _, _, _, _, 1].
    [_, _, 1, _, _, _, _, 1, 1, _].
    [_, _, _, _, _, _, _, _, _, _].
    [_, _, _, _, _, _, _, _, _, _].
    [_, _, _, _, _, _, _, _, _, _].
    [_, _, _, _, _, _, _, _, _, _].

This should provide a nice basis for further experiments to automatically generate such puzzles. For example, as you can see, the puzzle has a certain shape to it, and you can generate different shapes more readily by choosing random elements for generalization, instead of going so systematically about it.

eriknstr9 anni fa

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".

rgerganov9 anni fa

This is copy paste of http://0hh1.com

mhei9 anni fa

Or possibly the other way round? 0hh1.com was registered in 2014 according to whois info, the puzzles on this site go back to 2011. (I'm not claiming this is proof, of course)

kmm9 anni fa

They're older than that, this kind of puzzle is called a Takuzu or Binairo and was invented in 2009 by a pair of Belgians: https://fr.wikipedia.org/wiki/Takuzu

rplnt9 anni fa

Also, the list of puzzles on the site goes to March 2011.

I think this is a nice case of taking something interesting and making it more approachable, perhaps even fun.

tome9 anni fa

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.

Finally, classify the difficulty using some heuristic.

Does anyone have a better strategy? Is there some "analytic" property that guarantees uniqueness of solutions without resorting to some black box solver?

tzs9 anni fa

> 3. Add random elements to an empty grid. Eventually the grid will have one or zero solutions. If zero, backtrack. If one, stop.

You can use that approach to make a multiplayer version of Sudoku. Start with an empty grid, and the players take turns filling in numbers. If a player on their turn is unable to fill in a number without making an on-the-board violation of the non-duplicate requirements for rows, columns, and sub-squares that player is eliminated.

Note that this can be played without a computer, because elimination happens when there is forced to be a duplicate actually on the grid.

If playing on a computer a more difficult multiplayer Sudoku is possible. After every move the computer checks to see if it is still possible to complete the grid according to Sudoku rules. If it is not, the player who made the last move is eliminated, and their move is erased.

Note that a similar approach can be used with many other single-person puzzles. For example, the 8 queens puzzle as a two-player game becomes the players take turns placing queens on a chess board, and the first player who places a queen that is attacked by an already placed queen loses.

As with Sudoku, two-player 8 queens could be done without a computer with the game terminating when a queen is placed on the board that is attacked, or it could be played with a computer with the game terminating when someone places a queen that makes it impossible for the game to end in a draw.

In early 2011 at work we were brainstorming mobile app ideas, and I suggested both of the above but there was not much interest. They have been on my "todo" list for whenever I get around to learning iOS and/or Android programming...but I've had "learn iOS programming" on my list since 2008, so I doubt I'm ever going to get around to it.

rmidthun9 anni fa

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

codeulike9 anni fa

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

tedmiston9 anni fa

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.

tedmiston9 anni fa

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 < 5 min --> easy, 5-10 min --> medium, 10-15 --> hard, 15+ min --> evil, etc.

jmull9 anni fa

I've done this for Sudoku, cross sums and similar. Generally, I used a backtracking algorithm to fill an empty grid until a valid grid was found.

Assuming you want to control the level of difficulty of the puzzle generated, you want to incorporate the difficulty heuristics into the step-by-step filling-in algorithm (rather than just use them to score the puzzle after the fact).

Also, this probably should have been obvious, but at first I didn't do this: you get better control of the difficulty by basing your heuristics directly on the actual solving methods that people use. (If you don't somehow know already, you can, e.g., get a good book on solving sudoku which will enumerate the techniques and classify the difficulty as well. Once you understand the specific solving strategies for sudoku, you can probably generalize them to other logic puzzles.)

fenomas9 anni fa

> 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 modeled this way. But now that I consider it it's not so obvious...

kybernetikos9 anni fa

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.

fenomas9 anni fa

> 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.

tedmiston9 anni fa

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.

taserian9 anni fa

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.

jnbiche9 anni fa

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.

sarah20799 anni fa

Nooooooo! I clicked "The rules in more detail..." and it cleared my half-finished puzzle.

pavel_lishin9 anni fa

Yeah, I really wish it remembered your current puzzle state.

tedmiston9 anni fa

An example of the easy 6x6 puzzle instead of starting with a very hard 10x10:

http://binarypuzzle.com/puzzles.php?size=6

adictator9 anni fa

alangpierce9 anni fa

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.

bsurmanski9 anni fa

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

jmull9 anni fa

Yes, that's what I found.

(I too had trouble with that instruction.)

GrantSolar9 anni fa

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 the last one must be a 1

panic9 anni fa

http://0hh1.com is a much better place to learn the rules.

jasonkostempski9 anni fa

I spent a ridiculous amount of time playing that a few years ago, didn't even realize I was just playing the same game :)

Edit: Does 0h h1 have the every row/column has to be unique rule? Edit Edit: It does. I don't think I knew that all the times I had played it years ago, probably would have helped on a few puzzles I got stuck on. Edit 3: It just came into play twice on my first 10x10.

BatFastard9 anni fa

Indeed it is, it explains the rule, gives you feedback, and it better looking in general.

HiroshiSan9 anni fa

I find it's easier than the puzzle linked since my brain can't unsee '1' and '0' as one and zero, whereas with the blocks, they're just abstract shapes with no meaning aside from colour.

Avshalom9 anni fa

I on the other managed to completely not read the part where each row/column is split between 1s and 0s.

Tatham's version helpfully yells at you when you break the rules which is how I realized I was missing an important bit of information.

cookingrobot9 anni fa

I got past that and then realized every row/column needs to be unique.

bluehawk9 anni fa

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

savanaly9 anni fa

Yep, I made the exact same mistake. The hints have examples that disambiguate it which is how I found out in the end.

snarf219 anni fa

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.

GrantSolar9 anni fa

ralfd9 anni fa

I am stuck. What is the next step here? (Aside from programming it in Prolog.)

https://i.imgur.com/ezUHHBp.png

Jtsummers9 anni fa

Last year my desk calendar had a bunch of these sorts of puzzles, so some things I learned:

Any time you see "0..1" you have to have a 0 and 1 between them. This is useful since each row/column must have the same number of 0s and 1s (5 each in your puzzle). So counting from (1,1) as the top left, what does (6,3) have to be? You may not know the position of all the 0s and 1s in row 6, but you have most of them accounted for because of this specific relationship, and one free space. Figure it out and you get at least 5 positions resolved.

Keeping in mind that the number of 0s and 1s have to be the same, find rows where the number of 0s or 1s is near the max but the other is far from it. Your row 3 is one such location. There has to be one more 0 and three more 1s. Since the 1s can't all be together, you get some constraints on the outside of that four space gap "010...010". If you put the 0 on the outside of the gap, the 1s must be all in a row which is invalid.

Your column 2 offers a similar situation. 4x0s and 2x1s. (from the top) ".01001...0". Where can the one remaining 0 go, or where can't it go?

Repeating this I can spot about 15-20 spaces that'll be filled in very quickly, and the rest probably falls into place after that.

savanaly9 anni fa

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.

kevlened9 anni fa

Look at row 3 (0,1,0, , , , ,0,1,0)

aqme289 anni fa

That's exactly where i got stuck too

lilyball9 anni fa

If you like puzzles like this, you should check out Nikoli (http://www.nikoli.com/en/). They're a Japanese gaming company with a bunch of puzzles online. They don't have this particular puzzle, but they have similar ones, like Hitori (http://www.nikoli.com/en/puzzles/hitori/).

scscsc9 anni fa

I have implemented a while ago an Android version (https://play.google.com/store/apps/details?hl=en-gb&id=com.o...).

By far, the most interesting part is automatically generating the levels by difficulty. In my implementation, I first generate a full puzzle and then start removing pieces one by one, as long as the part just removed can be logically deduced. The only difference between easy/medium/hard is the amount of work performed in the logical deduction: one step for easy, two steps for medium and three for hard.

[deleted]9 anni fa