4 ms·

> a sudoku solver Sorry to hear about all the stresses you were dealing with but if it's okay, i'd like to follow up on your sudoku solver. Are you doing the

> a sudoku solver Sorry to hear about all the stresses you were dealing with but if it's okay, i'd like to follow up on your sudoku solver. Are you doing the brute force/general way or are you implementing sudoku specific logic? Here's my understanding of the general way: it tries to insert different values in different squares until it finds a conflict. A sudoku specific way, in my mind, would implement the algorithms we humans use to solve a sudoku. E.g., look at a block, see which numbers are missing, see if open squares in that block can be filled with numbers by eliminating options along the vertical or horizontal of that square. Hope this isn't too callous given everything else you wrote. Also, big fan of journaling which you too have called out.

nanidin 5y ago
No worries, it's a fun topic! For any given position on the board, there are only 9 possible moves that can be made (1,2,3,4,5,6,7,8,9). One could try each possible move without regard to the rules of Sudoku, then evaluate whether the new state is correct - and this is what I understand you mean by brute force. My implementation goes to the next step and only considers valid moves for a given position by looking within the current 3x3 square, and also by looking along the row+column to eliminate numbers that have already been used. This is slightly better than brute force and reduces the search space quite a bit. At a high level, my sudoku solver does a guided DFS by generating the full list of moves that can be made from the current board state, then sorts them according to heuristics that match how I play sudoku (first try to fill in positions with less options, first try to use numbers that have been used more), then starts trying values and backtracking once it reaches a point where there are no more remaining valid moves. The problem with heuristics like those is that sudoku puzzles can be created that exploit the heuristics and make the search take forever. My implementation solves easy and medium sudokus very quickly. My implementation can't solve most hard sudokus even after letting it run for hours.
- saimiam 5y ago
  Thank you! I'm starting to work on a sudoku solver. Let's see how far I can get.
- nanidin 5y ago
  On re-examination, the search is BFS by the way.

nanidin 5y ago

No worries, it's a fun topic! For any given position on the board, there are only 9 possible moves that can be made (1,2,3,4,5,6,7,8,9). One could try each possible move without regard to the rules of Sudoku, then evaluate whether the new state is correct - and this is what I understand you mean by brute force. My implementation goes to the next step and only considers valid moves for a given position by looking within the current 3x3 square, and also by looking along the row+column to eliminate numbers that have already been used. This is slightly better than brute force and reduces the search space quite a bit. At a high level, my sudoku solver does a guided DFS by generating the full list of moves that can be made from the current board state, then sorts them according to heuristics that match how I play sudoku (first try to fill in positions with less options, first try to use numbers that have been used more), then starts trying values and backtracking once it reaches a point where there are no more remaining valid moves. The problem with heuristics like those is that sudoku puzzles can be created that exploit the heuristics and make the search take forever. My implementation solves easy and medium sudokus very quickly. My implementation can't solve most hard sudokus even after letting it run for hours.

saimiam 5y ago
Thank you! I'm starting to work on a sudoku solver. Let's see how far I can get.
nanidin 5y ago
On re-examination, the search is BFS by the way.