Wow, I just read the original Sudoku post by Norvig yesterday for the first time, and now today this shows up here!
Reflections on Sudoku, or the Impossibility of Systematizing Thought
41–50 of 67 posts
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#42Earlier quoted context omitted.
The smart way to write a Suduoku solver these days is to formulate the problem for an SMT solver, which is specifically intended to solve that kind of problem. The SMT solver already has tests, so you don't need to write tests. When I wrote my first Sudoku solver I started out with a solver that solved easy problems where, at each step, there was some square with only one possible solution. That didn't work for harde…
I have only once written a Suduoku solver. It brute-forced the whole problem space in a second or 2. This works because it's very easy to prune invalid branches according to the rules of the game. It just tried putting "1" in the top-left most empty square and checking if the configuration is valid. If not, try "2". recurse until you find a branch that completes. Is this the smart way? IDK, but I was quite pleased wi…
I also wrote a brute force, kinda dumb, depth-first Suduoku solver. I think it took me a few hours in C or C++. At every node in the search tree, I just checked to make sure no constraints were violated. If I remember correctly, it would run in less than 30 seconds and it would always find a solution if a solution existed. (It might have been a lot less than 30 seconds. I only remember thinking, "That was quick".)
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#43Earlier quoted context omitted.
Obvious counters aside (like syntax issues or whatever) I have almost the opposite intuition. Most of my programs start out as partial solutions to a problem I don't fully understand, and it is only through interaction with the environment (users, or other machines sometimes) that the edge-cases and incorrect assumptions become clear. These programs have a lifecycle of refinement to deployment to analysis to refineme…
>I imagine this wouldn't work so well for hard algorithmic stuff where there are mathematical properties you need to be aware of and maintain Mathematical properties are often even more ideal candidates for being encoded into either types or property tests. Business oriented code is usually where most people see TDD (how it is normally taught) fall down - where you need "some kind of dashboard with x, y and z" but th…
Okay interesting, I've never heard of snapshot testing. I'll have to play with it some time.
I agree that mathematical problems are much easier to test, but I think only once you know the mathematics. Like I think it's possible that TDD fell flat for the sudoku solver because the dude just didn't know what properties he wanted. In that situation writing tests is like casting bones.
But I'm not convinced one way or the other... for me tests have always been most useful for regression and basic quality checks. Which is very useful! Means you never (hopefully anyway) take a step backwards as you evolve a program.
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#44Earlier quoted context omitted.
Aren't snapshot tests regression tests? "Snapshot test driven development" to me implies that you would generate the snapshot you want (somehow) and write code until the output matched the snapshot.
Snapshot test driven development is: 1. Write test. 2. Write code that gets the test to pass, generating a snapshot. 3. Iterate on the code until the snapshot looks right (maybe bringing stakeholders in the loop to ask "does this dashboard look right?"). 4. Lock the snapshot down and commit. 5. Refactor (same as with vanilla TDD). Arguably the "test" is fully written by stage 1, the only part missing is the correct g…
That sounds pretty cool, did you have any framework in mind in that last paragraph? Sounds miles better than what I'm currently doing, which is occasionally click through features I know are prone to bugs and manually check them... and manually writing documentation too.
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#45Earlier quoted context omitted.
I have only once written a Suduoku solver. It brute-forced the whole problem space in a second or 2. This works because it's very easy to prune invalid branches according to the rules of the game. It just tried putting "1" in the top-left most empty square and checking if the configuration is valid. If not, try "2". recurse until you find a branch that completes. Is this the smart way? IDK, but I was quite pleased wi…
I also wrote a brute force, kinda dumb, depth-first Suduoku solver. I think it took me a few hours in C or C++. At every node in the search tree, I just checked to make sure no constraints were violated. If I remember correctly, it would run in less than 30 seconds and it would always find a solution if a solution existed. (It might have been a lot less than 30 seconds. I only remember thinking, "That was quick".)
Yep, pretty much the same approach and experience, only mine was in c# as I was learning the language then. "brute force" by definition will find a solution, if it exists.
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#46Earlier quoted context omitted.
I have only once written a Suduoku solver. It brute-forced the whole problem space in a second or 2. This works because it's very easy to prune invalid branches according to the rules of the game. It just tried putting "1" in the top-left most empty square and checking if the configuration is valid. If not, try "2". recurse until you find a branch that completes. Is this the smart way? IDK, but I was quite pleased wi…
I also wrote a brute force, kinda dumb, depth-first Suduoku solver. I think it took me a few hours in C or C++. At every node in the search tree, I just checked to make sure no constraints were violated. If I remember correctly, it would run in less than 30 seconds and it would always find a solution if a solution existed. (It might have been a lot less than 30 seconds. I only remember thinking, "That was quick".)
I wrote a sudoku solver, that will create 9x9 array of arrays filled with numbers 1-9 for "blank" fields and only the number in defined field. Then for each square with only one number, I removed the number in that square from all arrays in row, column and subsquare. That typically left me with a solved array, but will contain all possible results for "guessing" fields. It was written in php (the thing I leaned at the time) and ran too fast for me to bother measuring, less than a second. Since I've "solved all sudokus" they stopped being fun.
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#47Earlier quoted context omitted.
Snapshot test driven development is: 1. Write test. 2. Write code that gets the test to pass, generating a snapshot. 3. Iterate on the code until the snapshot looks right (maybe bringing stakeholders in the loop to ask "does this dashboard look right?"). 4. Lock the snapshot down and commit. 5. Refactor (same as with vanilla TDD). Arguably the "test" is fully written by stage 1, the only part missing is the correct g…
That sounds pretty cool, did you have any framework in mind in that last paragraph? Sounds miles better than what I'm currently doing, which is occasionally click through features I know are prone to bugs and manually check them... and manually writing documentation too.
hitchstory
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#48Earlier quoted context omitted.
> but it is faster if you start with the square that has the minimum number of choices available Alternatively, find the digit that, in its row/column/square/whatever, has the minimum number of choices available, and try each of them. Ideally, combine the two and use Knuth’s dancing links algorithm ( https://en.wikipedia.org/wiki/Dancing_Links ). It, at every step, picks the one of those two approaches that has the l…
In Sudoku I usually find it's easier to just keep track of guesses on the stack, by `solve` recursively when you make a guess. That leads to nice memory re-use characteristics and without the overhead of link pairs that might end up blowing out your level 1 data cache. But you certainly want to be guessing on the most constrained spot you can. Also, bitfields are a nice compact way of representing the possible values…
This is how I implemented it: https://codeberg.org/uecker/toys/src/branch/main/sudoku.c
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#49Isn't there a less-conceptual (but still conceptual) problem that correctness of software is commonly abrupt rather than continuous? You don't get a series of almost-right programs gradually approximating the right program, you have a correct program and variations on it may fail completely. Of course, whether this is literally true depends on what sort of algorithmic problem you're approaching. But there must be man…
Working large systems overwhelmingly started out as working small systems, with working systems all in-between.
This is not an endorsement of TDD, but shows that there is a correctness path from small to large, without usually needing to take large leaps in-between, and taking such a path tends to be the most successful strategy.
Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought
#50It's making the same reasoning mistake that a lot of discussion of the Entscheidungsproblem makes - the problem talks about a generic algorithm to answer for all programs P if they can solve T, for all tasks T, the discussion assumes that you can't decide if P solves T for any P or T.
With that in mind, let's look at the crux of the argument: "If we can't decide if a program P solves a task T, then we certainly can't solve the even harder problem of finding a program P that solves a given task."
That's simply not true. We can decide if a program P solves a task T, for a specific program. Moreover, that means that for large classes of tasks, we actually can throw mud at the wall and see if it sticks - as long as it's decidable if the particular program P solves the particular task T.
And for any problems you can exhaustively test, hey, you really can rely entirely on TDD and hill-climbing the problem space. Hence, bowling scores being easier than Sudoku solvers.
As soon as you leave the (almost) exhaustively testable space, things become harder. And it's worth keeping in mind that TDD originates from a payroll system - something that's more amenable to exhaustive testing ("do all of our employees get the right amount, and did HR/finance stop yelling, and is our CFO not getting jailed for tax evasion") than a systematic approach. (Government plus corporate bureuacracy means that there are absolutely no deep structures to find. It's all about the special cases)
You can still do "TDD" at a higher level. You just need to accept that TDD is simply a primitive form of formally establishing your constraints, and that some constraints are hard to establish purely through testing. But that there exist many formalism to allow you to express higher level constraints.
This is at the core of the Haskell/Rust quip that "once the type checker/borrow checker is quiet, you can be confident the solution works".
Maybe constraint-driven design would've been a better name.