4 ms·

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

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.

SubiculumCode 6y ago
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.
- Marazan 6y ago
  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.
  - shultays 6y ago
    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!
    - Marazan 6y ago
      That doesn't guarantee you that you generate a Sudoku solveable without backtracking. The human techniques are all about forward actions only, never guesses.
      - dmurray 6y ago
        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.
      - shultays 6y ago
        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
        Majromax 6y ago
        > 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-triples/ https://www.sudokuoftheday.com/techniques/hidden-pairs-tripl... or https://www.learn-sudoku.com/x-wing.html 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.
twic 6y ago
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.

SubiculumCode 6y ago

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.

Marazan 6y ago
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.
- shultays 6y ago
  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!
  - Marazan 6y ago
    That doesn't guarantee you that you generate a Sudoku solveable without backtracking. The human techniques are all about forward actions only, never guesses.
    - dmurray 6y ago
      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.
    - shultays 6y ago
      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
      - Majromax 6y ago
        > 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-triples/ https://www.sudokuoftheday.com/techniques/hidden-pairs-tripl... or https://www.learn-sudoku.com/x-wing.html 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.

twic 6y ago

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.