Sudoku solver program, do it like a human!

[audioinstinct]

Making program to solve Sudoku like a human is far from being easy. So if you are novice programmer this might be a bit to much for you now. Now I don't say tht you can't do it but only that it won't be eazy. And if you are not stubbern enough I'm afraid that you might quit in the middle. Belive me I know becouse I was in your position about 5 years ago becouse I was trying to do something that was way beyond my knowledge at that time.

Anywhay the simpliest way to program Sudoku solver is by searching for posible candidates and then eliminating singles which you already implemented I belive. Now what you lack is what to do when there are no more signles.

So what do you do when you encounter situation when there are no singles? At this time you are on a crossroad with multiple choices. So you have to chose one. But which one is correct. You can't know this unless you test it out. Now the advantage of computers is that at any time you can save curent state of your Sudoku. And this is what you do when you come to this crossroads.
You save current state of your sudoku and then in one cell that has only two candidates you chose one of them. After that you try to solve the sudoku till the end. If you can't (you come to a unsolvable state) then you revert to the previosly saved state and chose other candidate from thet cell.
This approach guaratees you to solve any Sudoku. And if yo are interested in speeding this process up you can tgest both posibilities after encountering a crossroad concurently each in its own thread - requires good knowledge on multithreading and thread sycronizations).

I belive I must still have the code for this somewhere on my old laptop but to be honest I wouldn't show it to anyone as it is quite awfull. Probably much similar to your code

Anywhay if you are really interested in making Sudoku solver which will be solving it much like a human I recomend you learn about making decision trees becouse this will allow you to make much nicer code.
As for the need to use objects to make this Sudoku solver I don't think they are required.

Oh man, I just see that for some reason my reply didn't get posted. Well, anyway. Short story is that I don't feel like doing this decision tree method, because the goal is not really to write a program that can solve any sudoku, I could do that, I'm confident in that, it's not that hard. The goal is to implement the human-like strategies, so that later when I do a visual interface for it, it can actually show you how to solve it.

I'm not really stuck when there are no more singles, as I've said, I've already written quite a few methods for this. The most complicated one is the XY-Wing, which is a real mess if you looked at the code, you'd see, but it does work, and it is fast thanks to that I used pointers for the arrays. So even if it has to loop for 80000 times, not only this procedure alone, but the entire solution takes less than a second, if it is easy enough that the XY-wing is the most advanced strategy required for the solution.

Where I am really stuck is when I'd need the program do something, that is called "Chaining" in sudoku strategy. This is not based on general rules and different formations on the grid like the X-wing, or XY-wing. These strategies work with assumptions.

For example I choose a Cell where only 2 candidates are left, and I follow a chain with strong links, so I pretty much only care about cells that only have 2 candidates, and my target cells are going to be cells that are seen by multiple cells with strong links. So first I choose a candidate, and follow the chain. Then I choose the second candidate and follow the chain. If at any cell on the grid, there is a match between the two chains(e.g. a cell can not take a value, or a cell takes a value in both cases), then that must be correct. This is called an XY-chain, it is one of the more advanced strategies that are required to solve the hardest puzzles.

Another idea is a bit more simple, it's called Simple coluring, or Singles chaining. In this case, we only pay attention for one candidate, and search for cells that are linked strongly together. Strong link between two cells mean that for at least one candidate they are the only two cells in a house(row, column, or box). Why this is important is because we know for sure that one of them HAS to take the value of that candidate. So I can follow these strong links for this one candidate and assign a colour to each cell inside the chain, one for a colour "A" and one for a colour "B". And then I can draw the consequences, we know that either all cells coloured "A" are correct, or all cells coloured "B" are correct, there is no way some of "A" and some of "B" could be correct it would lead to a contradiction. So if an uncoloured cell sees two cells with different colours, then that candidate can not exist there. Or, for example if two cells of the same colour share a house, then we know that this colour can not be the solution, the other colour has to be correct.

This sounds a bit complicated, but it's actually very easy for a human to applicate, it's a bit more tough to code it though, especially the XY-Chains, because those can involve "weak links" , and the program would have to be able to differentiate between strong and weak links and how to use both of them too, this is crucial, or else it will start searching for completely useless chains, so to make it efficient, there is a bit of theory the program needs to "know".