Create a Sudoku Solver In Java In 20 Minutes - Full Tutorial 

Wow ! I have been coding for arround 5 years and could'nt come up with a solution!

@@yahia1355 oh I didn't do anything smart. I literally brute forced a solution. Basically going over every single square and trying the first number that works, then if I got to one that had no possible correct number I would go back until the first square that I could have put a different number in and tried the different number. Do that until you can fill every square correctly. Just literally trying every combination until it works. There are much better ways to solve this. But the not so smart solution works.

@@19joni69 🤣🤣😂

Same)

Thanks!!

Well at least I've certainly gone well past 500

i guess this one is for beginners and that's why he chose this way of doing it

But that is dependent on the previous placements. So I do not immediately see how that improves this algorithm.

The argument of the hashmap needs to be both the board and the placement of the number. How does backtracking in your algorithm work? I am not sure how you intended to do it with hashmaps and make the code less complex than what you saw in this video. Can you elaborate further? One idea popped up in my mind, but it is more or less a copy of what you saw in the video but without recursion. First you have an array which holds the position which are given in the beginning. Then, you proceed filling in the board and every time you find out that you can't continue filling in the board you backtrack the i and j variables of the loop until you reach the next number which you filled in and continue trying filling it after setting number To Try to be 1+the previous numberToTry.

iirc the whole problem is a system of linear equation , and u can solve it in O(n) if u use multigrid method

sqrt(GRID_SIZE) would make no sense at all

@@Michael-se7ny Really? Doesn't a Sudoku box always have side length of sqrt(GRID_SIZE)? But I guess the really clean way would be to define the sudoku in terms of the BOX_SIZE, since GRID_SIZE has to be square number. so a normal sudoku is BOX_SIZE = 3. (GRID_SIZE = BOX_SIZE * BOX_SIZE)

@@JannisAdmek right

Interesting methodology! This definitely isn't the most efficient way to do it but the board is limited to 9x9, so even with a terrible time complexity any board is still solved pretty quickly

same! Why doesnt he use the board as an instance? Is there any special reason for this?

It's like O(k*10^(k^2 -n)) where k is the number of cells in a row and n is the number of placed numbers at the start. If you try with k greaters than 9 this algorithm would literally take years to find a solution. You can do better using sat solvers and translating the sudoko problem into cnf logical formulas.

@@robertoborelli3275 may I ask why do you have zero in the beginning of the expression 0(k * 10^(k^2 - n)) doesn't it just cancel everything to zero? Also, why do you have 10 to the power of cells to solve, how did you get 10? Did you mean k because with every added unsolved cell you need k times more traversing the loops (assuming that the number of rows = the number of digits you can fill a cell in) ? And why do you have k * in the beginning of the expression?

@@smrtfasizmu6161 it's been a while since I've watched the video and now I don't remember exactly the code but here I give you some explanations: 1) It's not a 0, but is a big O. This thing is called "Big O notation". Simplifying, you can read it as "the complexity is less or equal than..." but there are some formal and accurate mathematical definitions behind this intuition I gave. 2) The intuition behind the formula is that this code is clearly exponential in the number of unsolved cells (k^2 - n). 3) each time you call the function to see if a number is valid in cell you spend O(k) time. 4) For each cell there are (exactly) k possible values (in the case of normal sudoku k is 9). So to sum the important thing here are: - exponential in the number of unsolved cells. - you take linear time in k, each time you check if a number is valid So as I wrote in the previous comment this is a pretty easy solution to write and implement but it's very inefficient since it uses the technique 'guess and verify'. It's much better (but also a bit more difficult) to use a sat solver for this kinds of problems.

Time complexity looks to be O(n^3) worst case. Average, eyeballing it, I would say is n^2*log(n)

​@@juanmalpartida1333 no. just because you have 3 nested loops you can't always say that you have O(n^3). Inside this loop there is a recursion! This solution is exponential for sure, infact there are situations in which you guessed j correct values, than you are trying to fill the j+1-th value and you discover that there is no such a solution. In this case the algorithm does "backtracking" and there are situations in which all the j guessed valuesare wrong and the algorithm must re guess the entire solution. This leads to exponential cost!

Thanks! Glad you're getting something out of them. I'll keep making them if people keep watching them!

I'm a man of many talents

Oh, yes. Right. It just makes it clear for us maybe.

So, “board[row][column] = 0” can be moved to the place before return false For more informations, It must be one of these places, right?

wouldn't having it there cause elimination of 1 possibility while going for previously placed index?

@@Leo_banana That is correct.

@@fandusmercius723 It wouldn't.

"What about the condition where it places 3 but the problem is 4 spaces away? What happens in the algorithm?" I had the same question. Here is my understanding. The algorithm sets for board[row][col] the first number that it finds (from 1-9) that is a valid placement. It does this even if that number is not ultimately correct. The problem could come from the very next empty square, as in the video, or it could come from a square much farther away on the board, as you point out. When the algorithm places a number in a square that was valid (when placed) but that is not correct, it will later reach a point where it is unable to find a valid number for a subsequent square (call that square i). When this happens, the current invocation of solveBoard will return false, causing the previous square (square i-1) to be reset to 0 and the numToTry for that square (square i-1) to be incremented and the search continued. If a valid placement cannot be found for square i-1 (e.g., because it was already correct), that invocation will also return false. This process of returning false will cascade backwards as the search continues to find valid placements for squares, resetting previously set squares to 0 and continuing the search from earlier locations in the board. So, when the algorithm hits a point at which, using the board in its current state, it cannot solve the puzzle, it backtracks to try other values in previous squares, working in a kind of "forward and backwards" way.

I did the same in Python in AI class in college. I think that's a cooler solution, but I liked the simplicity that this one offered for someone newer to coding, for purposes of this video

It is clearly just a fancy excuse to make a fiercly overpowered recusion process, basically like a 90's batch file. Have you found anyone who made an actual OOPS solver, because I want to watch that if you know where one is?

Thanks! Let me know if you have any ideas for programs like this. It's tough because they have to be complex enough to be interesting but small enough to fit in a reasonable video.

@@CodingWithJohn yes, thanks. I just bought a book about Ai and python where they also take small projects that can perfectly fit to your devs. There is the classic 8puzzle, The shortest way, Snake, Tetris, Spam search, And I don't know how you say in English : O|X|O _|X|O O|X|_

@@CodingWithJohn pack man is more complex but can maybe make a video for the moves?

Same

That, or make the board an instance variable (which you could inject with a constructor) - and make all methods instance methods....

This can then also be used for printing the horizontal and vertical lines. Printing numbers greater than 9, could then continue with capitals.

And I assume you would then do a 16x16 with box 4x4, as the number of digits in a row, column and box need to be equal. Thus a 12x12 could have a box of 4x3 or 3x4.

I was thinking about that as I was watching it, wondering if it was going to capture the 9, being that it is 0 indexed.