Firstly, I thought about "rule of 45"1, but all that does is validates quickly for horizontal and verticals that are all populated. I think it can indeed be also be used for what are the potential left overs, but problem is that is that it's not able to test for duplicate.
Perhaps, if the UI itself prechecked to make sure users are not allowed to enter duplicates, ideally that is nice, but that's not the concern of solvers. Solvers needs to just look at currently occupied cells that was either generated by Generator and/or has some cells already populated by users, or hand-entered data from some puzzle book (perhaps using OCR), etc. It needs to just look at the current state, and validate whether it can be solved, whether it has illegal numbers, etc.
For more information, read The Math Behind Sudoku: How to Solve Sudoku Mathematically2.
In a nutshell, for this excercise, all it'll do are:
- For each row, verify that there are no duplicate numbers, and if all cells are filled, verify that it totals 45 (also, keep total of all encountered digits for this row)
- For each column, verify that there are no duplicate numbers, and if all cells are filled, verify that it totals 45 (also keep total of all encountered digits for this column)
- For each 3x3 block, verify that there are no duplicate numbers, and if all cells are filled, verify that it totals 45 (also keep total of all encountered digits for this block)
In some games I've played on my Android, I've seen some apps that even told me how many of each digits are already filled. For example, the number 2 are found on block 0, 1, 3, 5, 6, 7, and 8; which means blocks 2 and 4 are missing 2's. So maybe even keeping track of encountered digits may be useful as well.
Lastly, validations can only spot duplicates, and until it is run through the solver, it cannot offer any more hints.
For now (starter), it'll just be brute force based on first passing it down to validation process to make sure no illegal values are set, and then take account of the sums from each column/row/blocks to determine what are the potential missing numbers. For example, if the sum was 44, then obviously, 8 cells out of 9 are populated, and 1 is the only legal number for that column/row/block. Once all round-trip is working, I'll most likely switch over to implementing Dancing Links1. The beauty of developing each micro-services are that it's quite isolated/decoupled that once prototype is functioning, you can easily swap out the implementation (or on a team-based environment, we can work in parallel).
As for hints, the basic hints of what are available can be discovered from validation process, but what the potential values should be (either 1 or 2 digits) can only be discovered from solver (this occurs when initial puzzle has 16 or fewer digits, causing the puzzle to not have a unique solution). And even with that, solver will in some cases, be in a position where it may be situated with a cell to have a choice of 2 numbers, in which case, it'll always bias towards lower number, so that other cell will be forced to take the higher number. This is to avoid having to backtrack, and it's a good enough heuristic for now. If it's not good enough, then it'll have to be a more sophisticated solver, which may be a topic for another day.