4 ms·

As a college project in C, we were to write a soduku solver. Smart people solved it by programming in fancy heuristics. Not being smart, I just brute forced it.

As a college project in C, we were to write a soduku solver. Smart people solved it by programming in fancy heuristics. Not being smart, I just brute forced it...though I tried to be fancy by representing the data at the bit level. I doubt it made it any faster lol. That said, 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. But I suppose that is why I'm still just a mediocre programmer :) The brute force method was basically move forward until you hit a dead end, backtrack, go forward again until you hit another dead end, etc. Edit: I'm not being dismissive of people who implemented better solutions. Honestly, at the time I was amazed at their skill. But I still chuckle just because the problem is trivially sized for brute force methods, and would have to be scaled much larger to actually make more sophisticated methods worth the effort in any situation other than personal satisfaction and education. In a business situation in which you do not expect the problem to scale, spending more time for a sophisticated solver may not be worth the effort. But yes, Soduku is for entertainment and R&R

shultays 6y ago
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
- 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.
goto11 6y ago
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
- SubiculumCode 6y ago
  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.
  - helsinkiandrew 6y ago
    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 https://www.youtube.com/watch?v=G_UYXzGuqvM
    - SubiculumCode 6y ago
      That brought back some memories...that was pretty much what I did.
mikejb 6y ago
> 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. ;)
- SubiculumCode 6y ago
  Good point. Thanks for bringing that up. I've edited my comment to bring context to my perspective.

shultays 6y ago

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

goto11 6y ago

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

SubiculumCode 6y ago
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.
- helsinkiandrew 6y ago
  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 https://www.youtube.com/watch?v=G_UYXzGuqvM
  - SubiculumCode 6y ago
    That brought back some memories...that was pretty much what I did.

mikejb 6y ago

> 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. ;)

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