Hacker News Reader

> when the hardest Soduku problems in the world succumbed to a brute force search to my lame program in less than a few something something ms, I kind of shrugged at the fancy methods.

I think you're coming off as dismissive, which is why you're getting downvoted. Puzzles like these have the purpose to entertain a human solving them, and they do that pretty well.

If you seek entertainment in developing algorithms to solve these puzzles, you should adjust your challenge to modern computers: Up the size to 100x100 or more, see how your algorithm performs, and go from there. Spoiler: NxN Sudoku is NP-hard (NP-complete, to be precise), so have fun - maybe you'll even win a million dollars.

Now, if you want to really challenge yourself: Write an algorithm to create Sudoku puzzles that have a unique solution and as few initial numbers set as possible. Maybe you'll even improve your coding skills beyond mediocre. ;)

Good point. Thanks for bringing that up. I've edited my comment to bring context to my perspective.

Wouldn't brute force be enumerating all possible combinations of numbers until you find one where all sums are correct? Your approach with backtracking sounds more fancy

It was a long time ago, but I think I randomly filled in numbers, save if numbers were already used in each row or column, then when it reached an impossible solution, it would work backwards one level, trying new numbers. If it ran out of numbers, it would go back two columns, and try a new number.

I doubt it was anything fancy. At the time, it bent my mind into knots. Programming is a wonderful mind trainer.

For those who want to see how a backtracking algorithm would work. Computerphile walked through a python approach (11 lines) a few months ago: https://www.youtube.com/watch?v=G_UYXzGuqvM

That brought back some memories...that was pretty much what I did.

I was discussing this with a friend. I too made a brute force sudoku solver. It was somewhat smart since it was keeping track of what options are available for each cell and updates those options as it puts/removes digits.

The friend told me he was working on a sudoku solver and was trying to explain his non-brute force algorithm. I told him I did a solver back in collage and it was basically instant even though it is brute force.

Similar story. A friend and i were arguing about whether you could solve sudokus by brute force in reasonable time. So we whipped out a couple of laptops and tried it. I had a brute force solver (kind of branch-and-bound-ish, ISTR) finished before he had his constraint-based approach running, and it solved any puzzle in the blink of an eye.

To capture some of the fun of human Sudoku-solving, i think you'd want to have some sort of metric for how brute the force is, and then see if you can write a solver which is as unbrutal as possible. I'm not sure what that metric would be, though.

Amazing. I got down voted for my story. HackerNews does not like Mediocre Programmers I guess lol.

I bet I could write a better algorithm today if I was motivated. Back then I was not as experienced in programming, and I struggled with even figuring out how to represent the data and the state. Its all about learning from where you were at the time.

It's more that solving Sudoku by Brute Force is easy.

But the trouble with brute force sudoku solvers is you can't use them to create sudokus solveable by humans with a unique solution.

That's the fun stuff in writing a sudoku solver/generator.

Sure you can, just brute force your way to ensure there is only a single solution. You can try all combinations and count how many reached to the end and check if count == 1.

Generating sudokus while all you have a sudoku solver seems an interesting challenge. Sounds like it can be done though, just a matter of creating random boards by adding one digit at a time that doesn't break rules and check if # of solutions is 1. I imagine even that would be fast enough, at least enough to create sudokus at a reasonable rate that can supply entire human population.

You can do anything given enough brute force!

That doesn't guarantee you that you generate a Sudoku solveable without backtracking.

The human techniques are all about forward actions only, never guesses.

Hmm I don't get what you mean. For a valid sudoku there shouldn't be any guessing involved? So during any stage of solution, there should be always a single move that is the only option option move solution forward?

But even then humans do "moves" like "if i put that number here then that eliminates all other possibilities, that leaves us only that other number", which is kinda like guessing. So even if there are no single so human also tries if a valid move will block all future valid moves. A brute force algorithm does just that, except that it has a much larger memory and computation speed so it can think that at 9x9 depth to find a perfect solution

> For a valid sudoku there shouldn't be any guessing involved?

In the philosophy presented on that channel, it's not that such a Sudoku puzzle is "invalid," it's just not particularly interesting or 'beautiful'.

From my viewing, there appear to be two differences between "logic" and "guessing" (or "bifurcation"):

* Bifurcation/guessing is just as happy with a correct guess as an incorrect one. If I guess that a square is a '1' and then fill out the rest of the puzzle without finding a contradiction, then that's a good (in fact the best!) guess. "Logic," on the other hand, seeks contradictions to rule out possibilities * "Guessing" is content to proceed arbitrarily far down the solution tree to find a solution (or contradiction), whereas "logic" limits itself to a few steps that can stay in a human's working memory.

The latter point is certainly fuzzy, and it leads to developing some heuristics (such as https://www.sudokuoftheday.com/techniques/hidden-pairs-tripl... or https://www.learn-sudoku.com/x-wing.html) to reduce more complicated deductive chains into "single steps."

However, the difference is clearer with the kinds of puzzles highlighted on the linked channel. These puzzles often include additional constraints, such as "the first three cells in the row form an increasing/decreasing sequence." "Logic" then provides universal derived constraints (such as "a 9/1 can never be in the middle of this sequence") that are more obviously distinct from depth-first-search guessing.

I've never understood the difference. When I solve sudokus, including this one, I use backtracking all the time. "The 2 goes here or here, if it goes here then I get a 2 here, a 2 here and there's no room for the 6 there...so the 2 goes in the other spot after all". The "forward methods" are equivalent: just shortcuts to the same thing, spotting reusable patterns like the "ringing the domino" motif the solver identifies in the video.