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