That is an interesting post. However, a much more interesting challenge is solving larger Sudoku puzzles, as 9x9 is (as evidenced in the pos) a trivial problem to solve. 16x16 starts to get somewhat interesting, but at 25x25 it gets really interesting. Most solvers are trivially extensible to larger sizes, making it quite easy to benchmark.
In my testing, 25x25 Sudokus are algorithmically challenging. Solving times for a naive but well-tuned algorithm with reasonable heuristics can easily be on the order of an hour for a single puzzle. A smart system with advanced reasoning can be many orders of magnitude faster.
It does backtracking with recursion. It uses bitwise operations for fast conflict detection in rows, columns and 3x3 blocks. But one very important heuristics is that it firstly sorts the cells in such a way that the backtracking brute force starts from the most densely filled side. This eliminates a lot of wrong branches early, and actually helps a lot. I'm thinking maybe I can extend this to 16x16 or 25x25 as well. Not sure if this will scale up adequately. But this one usually cracks puzzles in a fraction of second. It only become slow for extremely hard killer sudoku puzzles.
You will most likely need both smarter heuristics and better deductions for larger instances. As mentioned, I've seen well-engineered custom tight C++-solvers with decent heuristics and the normal deductions take >1 hour on some instances. Most cases I've tried can be solved reasonably quickly when using OR-Tools CP-SAT which uses constraint programming style lazy clause generation to a SAT solver and custom MIP relaxations in a portfolio.
does not really do what you seem to intend. Sort requires a comparison function that is stable, and there are a lot of things that could go wrong if this is not supplied.
For shuffling, use a shuffle algorithm. Fisher-Yates is the common suggestion on what to use.
This is just for generation of sudoku image. The actual solver doesn't do this this expensive operation (the sudoku generator just reuses the solver function to fill with random numbers). From my experience for just generation it works good enough and fast enough. Yes I know how to efficiently shuffle by swaps in O(n) time with the correct distribution of probabilities (I didn't know that algorithm name BTW), I'm just too lazy =).
While Fisher-Yates or similar algorithms are more efficient, the real reason I wanted to mention it is that in many systems the sorting algorithm might crash or corrupt memory when used with a randomized comparison operator. It is inherently unsafe.
In JavaScript it's OK. At that time I knew that it is not the most efficient solution (for generation O(n log n) shuffle is not critical), just wanted to do this with simple one liner. With C++ I would definitely use this https://en.cppreference.com/w/cpp/algorithm/random_shuffle.h... .
The specification says that if the comparator is not a consistent comparator, the sort order is implementation defined: https://tc39.es/ecma262/multipage/indexed-collections.html#s... Further along, it is specified that only if the sort order is correct, are you guaranteed to get a permutation of the input as the result. I would not write code expecting this to work.
Thanks. I changed to a proper shuffling. Although there was nothing catastrophic in JS (like corruption, duplication / loss of elements), just more biased randomness and slower execution time (not critical for generation). But yeah, it was worth it for fair randomness.
Is there any property in particular of dancing links that you think helps in determining this, or is it just that a backtracking search can be used to test all cases?
For pen-and-paper puzzles like Sudoku there is usually the goal that a solution should be findable by a series of deductive steps. For 9x9 Sudoku, most deductive steps used correspond to the effects well-known propagation techniques offer[1]. With a suitable propagation level, if the puzzle is solved search-free, then one knows that both there is only one solution and that there is a deductive path to solve it.
Dancing links is a very cute data-structure for a backtracking search, but there are a lot more aspects of writing a good Sudoku solver than just having a good data-structure for backtracking. Propagation (making deductions), heuristics, learning, parallelism, restarts, no-goods, ...
While 9x9 Sudoku problems are trivial to solve for more or less any program, 25x25 Sudoku instances are quite tricky and a simple and fast but naive search for a solution can easily take hours.
That representation of a Sudoku is elegant, but I think it is not the most natural representation. The base constraint programming style will use a variable per square with domain 1-9, and then 27 all_different constraints. This representation is a lot closer to how people talk about the rules of Sudoku, which in my mind makes it more natural.
A full MiniZinc program would look like this
int: n = 3;
int: s = n*n;
set of int: S = 1..s;
array[S, S] of opt S: puzzle;
array[S, S] of var S: board;
% Sudoku constraints
constraint forall(row in S) ( all_different(board[row, ..]) );
constraint forall(col in S) ( all_different(board[.., col]) );
constraint forall(r, c in {1, 4, 7}) (
all_different(board[r..<r+n, c..<c+n])
);
% Set up puzzle
constraint forall (r, c in S where occurs(puzzle[r, c])) (
board[r, c] = puzzle[r, c]
);
solve satisfy;
My process is generally that I want to prototype the model in MiniZinc and use that to run benchmarks. If the problem to solve is large or batch-oriented, I might also use MiniZinc in production (probably via the python wrapper for the toolchain).
If on the other hand the problem is smaller, is more meant as an interactive system, or there is a need for deep integration, then I would re-implement the model in the API for a solver, or I might even write a dedicated solver. As a Gecode developer, I naturally think that Gecode is very useful for the cases where the problem is not a traditional model / instance / solve / done process, but I've used many other solvers as well depending on circumstances and need.
I've never really felt that Optaplanner / Timefold has been that useful of effective. In the cases I might have used it, I've instead written a custom local search system or constraint programming like system, and I think that has been a more effective approach. Do you have an example of what kind of problem you used it for?
That is more the area of workforce management systems, and they are really big business.
I’ve previously tried starting a scheduling company, and even when one has a product that in testing shows that it would save the potential customers lots of money, it is really hard to gain traction.
Very nice project. Do you have some statistics for how long it takes to solve the harder instances for different solvers? One thing to note for that, is that I saw the default parallelism of 4 in the run file. OR-Tools CP-SAT works best if it is given at least 8 threads to work with.
Have you considered using records for some of the data definitions? For example, a record `(row: int, col: int, piece: Piece)` for pre-placed pieces to avoid having .1, .2 and so on in the models. If you are concerned with the size of the data files, one way to handle that is to have the data as a list of tuples that are mapped via a function from a tulle to the record.
Thanks for the great feedback! I didn't know OR-Tools CP-SAT worked best with at least 8 threads; I'll definitely try that out.
In my local tests, Chuffed is often faster on the simpler instances. However, I've noticed on the harder puzzles, Chuffed can take over 10 minutes, while OR-Tools (with just 4 threads) solves them in about 5.
You're also right about the records. I started with tuples for simplicity, but as the model grew more complex, it's clear that records would be a much better approach for readability.
One thing that might be interesting (and might be useful for some solvers) is to change from checking if there is a solution and requiring each part to be used in the solution, to find solutions and minimize the number of unused parts.
One additional constraint that you could add that I don't think I've seen is distance to goal. In essence, for each grid position (without considering any tracks) there is a shortest time it would take from that position to get to the final position. If a train is in (a, b) and would take at least time t to get to the exit, there is no way to solve the problem if it is in (a, b) at time MAX_TIME-t. Might be useful for some solvers, worth testing.
Finally, adding some simple heuristic might help some solvers (I'm thinking of Gecode in particular here). My initial guess would be to add an interleaving over time steps of the train_row, train_col, and train dir for each train and search in order. That would as a basic heuristic represent a search from the start snaking out. Value choice is trickier to specify in MiniZinc of course.
The "distance to goal" constraint is a clever idea, though it's tricky to implement because the tunnels act as teleporters, so a simple distance metric doesn't apply. I'd likely need to pre-calculate a shortest-path graph first.
I'm benchmarking Huub and Pumpkin now. My main goal is raw performance, as a friend's imperative brute-force solver (https://github.com/FoxtrotOnce/RailboundSolver) solves most levels in under 2 seconds. It's a high bar to meet with a declarative model, but I'm keen to see how close I can get with these optimizations.
When using minizinc or other constraint programming tools to solve puzzles that require a single solution, I typically run them asking for 2 solutions. If I get 1 solution only, I know the puzzle is well formed, if I get more than one solution I know the puzzle is mal-formed.
Any tool that can solver hard problems will also have non-trivial runtime behavior. That is an unfortunate fact. But you are also correct in that combinatorial optimizaton solvers (CP, SAT, SMT, MIP, ...) often have quite sharp edges that are non-intuitive.
For the iOS AutoLayout, what kind of issues have you seen, and how complex were the problems?
If you want to work in Python, I would either use OR-Tools which has a Python library or CPMpy which is a solver agnostic Python library using numpy style for modeling combinatorial optimization problems.
There is a Python package for MiniZinc, but it is aimed at structuring calls to MiniZinc, not as a modeling layer for MiniZinc.
Personally, I think it is better to start with constraint programming style modeling as it is more flexible, and then move to SMT style models like Z3 if or when it is needed. One of the reasons I think CP is a better initial choice is the focus on higher-level concepts and global constraints.
If you do want to start with SMT though, z3 has quite good bindings. I found it intuitive to use, and its ability to give you answers to very hard problems is like owning a magic wand.
In my testing, 25x25 Sudokus are algorithmically challenging. Solving times for a naive but well-tuned algorithm with reasonable heuristics can easily be on the order of an hour for a single puzzle. A smart system with advanced reasoning can be many orders of magnitude faster.