Any keen computer science people here want to critique my approach to writing a sudoku solver?

Ah crap the formatting got all messed up, I hope this is not too unreadable

try chatgpt ask it to critique your code

Write out a text description first. It only needs to be a few sentences, but it should have specifics on what you are inputting, what is output, and then something about what it does.

Then write out a text description of what each step in the process is. Turn that into pseudo code by noting where your loops and function calls are.

Does your current code line up with those step?

Wanted to add that this should be specific. What if someone doesn't know what sudoku is, or how to solve it? If you can explain it to someone simply, then you can write the code for it.

It’s bad manners and insulting to expect others to read your code.

This seems like a non-scalable, computationally intensive approach but, as written, it should work. Add a comment for each function or line so we can critique better.

The worst case computation counts are like 9^(50), no?

• Each row should have numbers 1-9, no repeats.
• Each column should have numbers 1-9, no repeats.
• Each 3x3 quadrant should have numbers 1-9, no repeats.

It definitely is super inefficient, but I wanted to try and get the "naive" solution first since I'm not very good/experienced at coding so far. Greatly appreciate your input though, thank you! Also, apologies to all as well, I should have documented the code/game better as well, and thank you to the poster above who actually did that. So here's the code again:

public int[][] solve(int[][] board) { // function returns a 2d array
if (solved? (board)) { // solved?() loops through board and returns true if no empty spaces.
return board; // Idea is to identify a board that is solved in any given recursive call
} // to the solve() method, and to stop the search here
generateValidBranches(board);

}

// In the function above, generateValidBranches(board) is reached and called if solved?(board) is false. Here, the board is not a solution (it has empty spaces), so we go into this method which will find the first empty space in the board and try all possible numbers in that spot. For each number tried in that spot, a new "sub-board" is generated, and once all numbers have been tried we filter for the sub-boards that are valid: those boards where the numbers tried do not lead to a row, column, or 3x3 grid that also contains that number tried. Once these valid sub-boards are generated, we pass them to the mutually recursive call to solve() and check if they are a solution. My idea was that this would continue until a board was generated that was a solution.

public void generateValidBranches(int[][] board) {
List<int[][]> subBoards = < method that generates valid subboards and returns them >
int i = 0;
while (i < subBoards.size()) {
solve(subBoards.get(i)); // in this loop, we pass each sub-board generated from a particular
i++; // board back into solve() to see if it's a solution. i is then
} // incremented to ensure no infinite loop occurs (as it will eventually
} // not be less than the number of sub-boards in subBoards

I hope this makes the code a little bit clearer, thanks to all the other replies so far as well!

As for the worst-case computation (time complexity?), I'm not quite sure but I have a feeling it would be something like 9^81: I think this is basically how many possible board configurations there could be. It's ridiculously inefficient lol

This is great advice as well thank you, I should be more careful about how I specify/document/plan out the various methods responsible for building up the solver. Pseudocode is a fantastic idea for mapping out the thought process here

Super interesting, looking more into that!

OP, here's my C# solution following your thought process. (Note: Only tested one 3x3 case)

Sometimes brute force is in fact the best-known or proven-best solution to a problem. And this is often the case for puzzle/game problems.

There aren't exactly 9^81 (as you thought) boards to try, not even the worst case. Think about it like a tree. Every time you go down a branch (use a number to fill a blank), that reduces the branches (possible numbers for other blanks) of the subtree.

Image:i.ibb.co/m8NM4dH/sudoku-solution.png

You need to focus on the concept rather than the code, this mix between both doesn't work. Explain your program in words and pseudocode or give the full code. Also stop using < > for comments. Rather make a pseudo-function, f.ex validSubboards().

Full solution Accepted by LeetCode: