I feel like the 'search' function is missing the point. The sudoku puzzles are generated in such a way that there is always a next move to be deduced: there is never any need to guess. If you have to guess, then you have missed something.
Solving Every Sudoku Puzzle (2006)
21–28 of 28 posts
Re: Solving Every Sudoku Puzzle (2006)
#22I love that this code is so elegant, but (and!) chooses strings and string manipulation for storage of the possible cell values.
It seems like he started with lists and switched when he got to the search method ("This is why I chose to implement the set of possible values for a square as a string: I can copy values with values.copy() which is simple and efficient.") - It's probably not an amazing insight, but I'm sure my brain would have been yelling at me "don't use strings! don't use strings!".
Re: Solving Every Sudoku Puzzle (2006)
#23I've noticed that solving a sudoku is something of a rosetta stone for how people program. Norvig's solution is very straightforward in hindsight, but I think that code was either the result of many iterations or of a career of making progressively more readable code. Here are some other sudoku solvers that give more insight into the coder than the problem: Sudoku in APL: https://www.youtube.com/watch?v=DmT80OseAGs T…
A lot was discussed about Norvig's elegant solution compared to Ron Jeffries effort and what it said about TDD: http://ravimohan.blogspot.co.uk/2007/04/learning-from-sudoku...
To be fair, the reason Norvig was so successful was he knew exactly the sort of problem soduku was and how to solve it, whereas Ron lacked this background knowledge.
Re: Solving Every Sudoku Puzzle (2006)
#24I've noticed that solving a sudoku is something of a rosetta stone for how people program. Norvig's solution is very straightforward in hindsight, but I think that code was either the result of many iterations or of a career of making progressively more readable code. Here are some other sudoku solvers that give more insight into the coder than the problem: Sudoku in APL: https://www.youtube.com/watch?v=DmT80OseAGs T…
A lot was discussed about Norvig's elegant solution compared to Ron Jeffries effort and what it said about TDD: http://ravimohan.blogspot.co.uk/2007/04/learning-from-sudoku... To be fair, the reason Norvig was so successful was he knew exactly the sort of problem soduku was and how to solve it, whereas Ron lacked this background knowledge.
I think you're missing the point. TDD forces you to choose data representations that best fit your tests. But in most cases of complex programming you want to choose representations that reflect your current understanding of the problem and then evolve them as your understanding evolves.
In TDD your test will always predate your understanding. So it forces you to solve (part of) the problem in your head first, rather than combine the act of problem-solving and writing. And you do this over and over again. And when you change your mind about something, you have twice the code to refactor.
It's a difference between recording your thinking in code and actually thinking in code.
This reminds me of an old article that exemplifies this: http://insideofthebox.tumblr.com/post/52002125683/prime-fact...
Prime factor kata is often used as an introductory example of TDD, yet it is clearly impractical and produces garbage code. Not to mention that I've actually seen people do it, stumble, and hectically reach for their notes to see what's the next step. And it's a pretty darn simple problem.
Re: Solving Every Sudoku Puzzle (2006)
#25I feel like the 'search' function is missing the point. The sudoku puzzles are generated in such a way that there is always a next move to be deduced: there is never any need to guess. If you have to guess, then you have missed something.
Depending on what you mean here, you are misrepresenting the problem. You may not have to guess for what is a valid move that can be done on the board as it is. But you do have to guess for a valid move that will lead you to a completed board. Hence, you search among the possible moves for the one(s) that will lead to a completed board state.
Re: Solving Every Sudoku Puzzle (2006)
#26If someone is interested in seeing Sudoku solved in other languages, here's a nice page: http://rosettacode.org/wiki/Sudoku
Not all of the code is efficient, but it's interesting nevertheless.
Re: Solving Every Sudoku Puzzle (2006)
#27I've noticed that solving a sudoku is something of a rosetta stone for how people program. Norvig's solution is very straightforward in hindsight, but I think that code was either the result of many iterations or of a career of making progressively more readable code. Here are some other sudoku solvers that give more insight into the coder than the problem: Sudoku in APL: https://www.youtube.com/watch?v=DmT80OseAGs T…
A lot was discussed about Norvig's elegant solution compared to Ron Jeffries effort and what it said about TDD: http://ravimohan.blogspot.co.uk/2007/04/learning-from-sudoku... To be fair, the reason Norvig was so successful was he knew exactly the sort of problem soduku was and how to solve it, whereas Ron lacked this background knowledge.
The odd thing is that, on the evidence of those blog posts, Jeffries, doesn't appear to understand TDD. If you're using TDD to write a sudoku solver, surely the first thing you should write is a test for your "solve_sudoku" function; then your design is supposed to evolve out of the code you write to pass that test (and the further tests you write for parts of that solution, iteratively). But Jeffries starts writing a bunch of tests for a the low-level details of the representation of a sudoku board. There isn't really any "design" in those posts at all; just a guess at something you might use in a solution to the problem.
Re: Solving Every Sudoku Puzzle (2006)
#28Earlier quoted context omitted.
A lot was discussed about Norvig's elegant solution compared to Ron Jeffries effort and what it said about TDD: http://ravimohan.blogspot.co.uk/2007/04/learning-from-sudoku... To be fair, the reason Norvig was so successful was he knew exactly the sort of problem soduku was and how to solve it, whereas Ron lacked this background knowledge.
I think you're missing the point. TDD forces you to choose data representations that best fit your tests. But in most cases of complex programming you want to choose representations that reflect your current understanding of the problem and then evolve them as your understanding evolves. In TDD your test will always predate your understanding. So it forces you to solve (part of) the problem in your head first, rather…
Err, I'm missing the point of my own point? You raise an interesting point, but I don't think TDD was what stumped Ron. It's not a simple problem to solve without a lot of thought unless you have the requisite background knowledge like constraint problems. TDD did however have him going round in circles, partly for the reasons you describe.