Comment by saimiam | Hacker News Reader

Comment by saimiam | Hacker News Reader

Parent Full thread

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

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.

Thank you! I'm starting to work on a sudoku solver. Let's see how far I can get.

On re-examination, the search is BFS by the way.

Reply on news.ycombinator.com