3 ms·

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 motiva

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.

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.