Reflections on Sudoku, or the Impossibility of Systematizing Thought • Hacker News Board

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#21

Post by PaulHoule » Thu, Jun 12, 2025, 1:54 PM UTC

JonChesterfield wrote: post #15

This was an interesting read but the source article is fascinating https://explaining.software/archive/the-sudoku-affair/ TDD as an incremental search from a simple start point towards a solutions. Put in those terms, it'll work when the path from start to solution is smoothly differentiable.

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 harder problems where you have to guess. Eventually I realized that you could just pick any square, try all the numbers, and recursively solve the remaining problem. This works no matter which square you pick but it is faster if you start with the square that has the minimum number of choices available.

If you write a solver haphazardly like that you're very likely to wind up with two or more copies of the board because you're not sure what kind of queries you'll need to do. If you understand the problem, you won't.

The role of the tests is complex here. In principle they could help you refactor your data structures, in practice the sheer bulk of them could reify the data structures you have and add to the burden of refactoring them. A code-golfed version of the solver could be smaller than the tests.

Writing a chess program I found testing was a challenge. Move generators are easy to test, evaluation functions are easy to test. A decent alpha-beta search with transposition tables, killer heuristic and such is not so easy to test in terms of unit tests. Before I'd have the program play anyone I'd run a set of integration tests based on

https://www.chessprogramming.org/Bratko-Kopec_Test

I think of a system I inherited that had a part that was prone to race conditions, part of vanquishing the race conditions was writing a "super hammer" test that would run a few 1000 threads for about 40 seconds. Maybe it still has race conditions, but they won't be triggered often.

Long-running tests like that aren't really unit tests but for some problems they're the right tool. In general though long-running tests are a big problem because slow builds are a problem.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#22

Post by MoreQARespect » Thu, Jun 12, 2025, 1:58 PM UTC

bubblyworld wrote: post #18

schoen wrote: post #3

Isn'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…

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 the exact details arent precisely nailed down. However, if you can do it right these scenarios work extremely well with snapshot test driven development. Most people just dont do it or dont know how.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#23

Post by awanderingmind » Thu, Jun 12, 2025, 1:59 PM UTC

This is a rare type of article - a concrete analysis of different approaches to programming (that are arguably themselves reflections of different cognitive styles), that outlines the shortcomings of one approach in a specific domain, without generalising too much.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#24

Post by MoreQARespect » Thu, Jun 12, 2025, 2:05 PM UTC

aleph_minus_one wrote: post #17

jerf wrote: post #16

Earlier quoted context omitted.

"Scrum" isn't really "Agile", though. Maybe someone developed it through a truly Agile process, but then they froze it and held it up as an unchanged ideal and started down the oh-so-appealing road of telling anyone that finds it doesn't work for them that it's because they weren't doing it right. I find myself having to distinguish between what I call "Real Agile" and Scrum quite a bit, because Scrum is exactly the…

> "Scrum" isn't really "Agile", though. Wikipedia: > https://en.wikipedia.org/wiki/Scrum_(software_development) "Scrum is an agile team collaboration framework commonly used in software development and other industries." In other words: people who claim to do Scrum, but in a non-agile way are simply scammers.

Scrum is training wheels for agile. If your team were truly terrible and previously had 6 monthly iterations or something you'll be seeing some "agile" benefits which may seem amazing compared to the bullshit you put up with before.

Training wheels do ultimately need to come off, though.

If you were using kanban, TDD, pairing, CI, close customer feedback, multiple daily releases and all that good stuff, enforcing Scrum is little different to putting training wheels on a tour de france team's bikes, patting the cyclists on the head telling them that if they use the wheels correctly it'll give them a speed boost.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#25

Post by Someone » Thu, Jun 12, 2025, 2:10 PM UTC

PaulHoule wrote: post #21

JonChesterfield wrote: post #15

This was an interesting read but the source article is fascinating https://explaining.software/archive/the-sudoku-affair/ TDD as an incremental search from a simple start point towards a solutions. Put in those terms, it'll work when the path from start to solution is smoothly differentiable.

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…

> 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 lower number of possibilities, typically getting a lower branching factor, without spending much more time at each step.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#26

Post by Noumenon72 » Thu, Jun 12, 2025, 2:19 PM UTC

MoreQARespect wrote: post #22

bubblyworld wrote: post #18

Earlier 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…

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.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#27

Post by Yossarrian22 » Thu, Jun 12, 2025, 2:20 PM UTC

rjpower9000 wrote: post #2

I was fascinated by the "Sudoku Affair", found myself speculating on the internal mindset of TDD advocates, and ended up with an unsatisfying conclusion that you can't systematize thought. Not my best writing but thought I'd share nonetheless.

I'd be somewhat more charitable and say that it's an attempt to break down a big, complicated problem into chunks that are more easily digestible. The problem I think Jeffries ran into is that Sudoku and the search space is essentially atomic, where breaking it down further isn't helpful, while seeming like it's simple to break it down to row, column, and box and work from there.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#28

Post by MoreQARespect » Thu, Jun 12, 2025, 2:28 PM UTC

Noumenon72 wrote: post #26

MoreQARespect wrote: post #22

Earlier quoted context omitted.

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

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 generated artefact. I dont really give a fuck about semantics of the word "test" though, the process is what matters.

The snapshots and test steps and metadata can also be compiled together to generate documentation with the right framework - documentation as a side effect of TDD.

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#29

Post by 9rx » Thu, Jun 12, 2025, 2:29 PM UTC

aleph_minus_one wrote: post #17

jerf wrote: post #16

Earlier quoted context omitted.

"Scrum" isn't really "Agile", though. Maybe someone developed it through a truly Agile process, but then they froze it and held it up as an unchanged ideal and started down the oh-so-appealing road of telling anyone that finds it doesn't work for them that it's because they weren't doing it right. I find myself having to distinguish between what I call "Real Agile" and Scrum quite a bit, because Scrum is exactly the…

> "Scrum" isn't really "Agile", though. Wikipedia: > https://en.wikipedia.org/wiki/Scrum_(software_development) "Scrum is an agile team collaboration framework commonly used in software development and other industries." In other words: people who claim to do Scrum, but in a non-agile way are simply scammers.

Agile is a set of considerations to ponder if you think you want to operate in a manager-less environment. The supplemental 12 Principles[1] goes into a bit more detail, explaining that developers need to take on jobs like communicating with the business people and amongst themselves to supplant what a manager would normally take care of.

Scrum, on the other hand, is a "process" to manage teams. It even assigns what it calls a "Scrum Master" to act as a manager. Literally the opposite of Agile. Scrum does propose that if you follow it, it can help lead you to eventual reach a state of Agile, which seems to be the source of the association, but when have you actually ever seen that happen?

[1] https://agilemanifesto.org/principles.html

Re: Reflections on Sudoku, or the Impossibility of Systematizing Thought

#30

Post by taeric » Thu, Jun 12, 2025, 2:30 PM UTC

You see similar in other arenas, too. And sometimes, as annoying as it is, popular techniques really do have better success than not. Even more annoying, unpopular techniques can often have better success rate than we care to acknowledge.

The examples in my mind are: outlining, task breakdown, object modeling, and rote repetition.