Well, I was also taken by a small "Sudoku fever", obviously mine is a computer fever ...
So I jumped headlong into creating an Excel program, which would solve even the most complicated Sudoku by itself.
To do this, of course, I had to think of some simple resolution rules, so I said to myself: why not publish them?
Done !
Sudoku consists of a table, usually made up of 9x9 little squares, which is also divided into 9 boxes of size 3x3 little squares.
There are also versions of 16x16 squares around, divided into 16 boxes of 4x4 squares ...
The purpose of sudoku is very simple: you have to fill it with numbers (but random symbols would also be good). How many numbers? The answer is: exactly as many as the dimension of the sudoku.
So if the scheme is a 9x9, with 9 boxes of 3x3, I will have to place 9 different symbols, usually the numbers from 1 to 9 ... If it were the 16x16 scheme, which is divided into 4x4 boxes, I will have to place 16 different symbols (or the numbers 1 to 16, which we do first)
AND HOW should they be positioned? Simple ! The only rule is this: every row, every column and every box of the scheme must contain ALL the numbers, but each one must be repeated ONLY.
Once in each row, once in each column and once in each box, just to be clear!
Normally some numbers are already put in the pattern, and it's our cabbage to complete the pattern.
I reassure you immediately: despite what you will read around, the sudoku is of a disarming simplicity, and its solution is found simply by applying a series of standard "patterns", one after the other, until there are two cases: solved, or you MUST PUT A RANDOM NUMBER, and continue.
Now let's see what it takes to solve a sudoku scheme:
- a pencil, because it's easy to erase
- rubber eraser
- a pen
- patience
- some free time
First thing to do, is apply a method I call "TRIPS" (trip of 1, trip of 2, ad so on...)
It's very simple, look at the figure above, look at the three 3x3 boxes, on the right, and check the number 6 (= trip of the 6).
In the first box it is in the left column, in the second box it is in the right column, therefore in the third box the 6 can only be in the central column!
If there was only one free position in that column in the third box, I could have written it immediately.
Since this is not the case, do not panic .... just see that on the left, in the central row, there is another 6, so the 6 can only be in the yellow cell!
This method must be repeated, starting from 1, for all the numbers, and then restarted, and repeated, until all 9 "TRIPS" are made without putting more numbers in the right position. At this point, we move on to the next methods:
The trick is to reason on the list of numbers that are allowed in every single cell of the scheme, deleting them as the reasoning makes you understand that in that cell, that particular number cannot fit, until, for each cell, you have put the THE ONLY number that suits us.
Eh, I know, said it seems easy ... but I assure you it really is:
Now look at the figure below: (sorry if I change the example, but I had this ready ...)
Do you see the yellow cell? So, we said that for each row, for each column and for each box the numbers must be repeated ONLY ....
In the box there are already 2, 4, 5 and 9.
In the row of the yellow cell there are already 3, 4, 5 and 7.
In the column there are already 3, 4, 7 and 9.
Then in the yellow cell there can only be 1 or 6 or 8! We write them in pencil, so we can then edit the cell when we discover other numbers that are prohibited for that cell, and then we will refine the list of allowed numbers ...
Let's now see the green cell ... With the same method we discover that there can ONLY fit on the 6, because ALL the other numbers are already in the same row, in the same column or in the same box as the green cell.
Then we write the 6. And NOW that we wrote it, WE REMOVE it from the possibilities of the other cells, therefore, for example, the yellow cell, in which we had previously written 1,6,8 as possible numbers, now becomes 1,8 and STOP, because the 6 -at this point - is already in the row (and also in the box) to which the yellow cell belongs.
After we have repeated this reasoning, which we can call "SINGLE ADMITTED", we will find ourselves as in the following figure:
Now we go hunting for "EQUAL COUPLES": do you see the pair 1.8 in the yellow cells? Well, you also see it standing on the same column, and moreover in the same box.
This means MANDATORY that there is 1 in one yellow cell and MANDATORY 8 in the other. in one of the yellow cells, then in the rest of the box and in the rest of the column (because they are in the same column), 1 and 8 CANNOT BE, so I remove them from the list of possibilities for NON YELLOW cells that are in the same box and in the same column as the yellow cells.
This creates a whole series of linked moves! Meanwhile, we immediately see that in the green cells, if I remove the 8, another EQUAL COUPLE is created: 3.7 which is on the same row and in the same box. Unfortunately, nothing is simplified in the box, because there were no other 3 or 7, but along the row, in the NON GREEN cells, I can remove all 3 and 7, because they cannot fit, as they MUST BE IN THE GREEN CELLS !
Then do you see at the top of the column of yellow cells? The first cell is 6.8 and the second is 5.6.8 and I know that the 8 cannot fit, so I remove it from the possibilities, then in the first at the top it ends that there can be ONLY the 6 !!
But by setting the 6 in that cell, I can automatically remove the 6 from the possibilities for all the other cells of that row, that column and that box! So in the cell that was 5,6,8 (I had already removed the 8 before), also removing the 6, I understand that there can be ONLY the 5 !!
By setting the 5 in that cell, I understand that in the penultimate cell at the bottom of that column, which was 2.5 at this point there can only be the 2 !!
After having done all these simplifications (remove the 6, 5 and 2 from the rows, columns and boxes, after I have fixed them in a certain position) I arrive at the situation that can be seen below:
Let's now look at the yellow cell: do you see that it contains the 6? Do you see that the 6 does not appear in the possibilities of ANY OTHER cell in the whole row ?? (N.B. 6 does not even appear in any other cell in the whole box)
Of these two conditions, which I call "MONO-POSITION", even just one is enough, to conclude that the 6 can be ONLY THERE !! Obviously it was valid even if that cell had been the only one in the COLUMN to contain the 6. And we therefore arrived here:
Do you see the usual yellow cells? THREE, and the possible numbers for those cells ARE THREE ONLY, we have the "THREExTHREE" situation.
And do not pay attention to the fact that, by chance, the three cells are the same, the reasoning applies to THREE ALIGNED CELLS (row or column) in which ONLY THREE NUMBERS can fit. To understand, it was fine if the three cells had been 2.8 / 8.9 / 2.9 or even 2.8.9 / 8.9 / 2.8 ... they are THREE cells and there can be ONLY THREE numbers.
So I remove those three numbers from the possibilities of all the OTHER cells of the row or column (it was also valid for the box, if the three cells had NOT been aligned, but inside the same box, I could simplify the rest of the box, but this could rarely occurs)
In summary we have 4 simplification methods::
- SINGLE ALLOWED
- MONO-POSITION
- EQUAL COUPLES
- THREExTHREE
You can apply these methods as many times as you want, as long as you are in one of the following two cases: either you have solved the game, or you can no longer apply any of the 4 methods.
(NOTE: Obviously the THREExTHREE method can also be generalized in the case in which in 4 or 5 aligned cells there can be ONLY 4 or 5 numbers, obviously in this case I can simplify those numbers from the other cells of the row or column. For a 9x9 sudoku it is quite difficult that it can happen, while for a 16x16 sudoku, it is more likely)
If you haven't solved the sudoku yet, the 5th method remains: "BET"
This is also simple: before proceeding, write with the ballpoint pen all the numbers whose position you have identified so far, and erase all the numbers that are not possible in each cell with the eraser, so as not to erase with pencil strokes. This is the starting situation for the BET.
Now take an EQUAL PAIR (if there are any, otherwise a cell with only two possible numbers is fine) and put the two numbers at random. (Or one of two random numbers, if you had no pairs).
At this point, start using the 4 methods seen before, until you come to one of these three cases:
- Resolved
- Impossible
- Unresolved, Not impossible, the 4 methods can no longer be applied
Impossible means that for a certain cell there are NO allowed numbers.
If IMPOSSIBLE: you must go back and reverse the last bet made (if you had put, for example 3 in one cell and 5 in another, you must reverse this choice; if you had put ONE random number from a cell with two possible numbers : put the other one). Unfortunately you have to cancel all the simplification operations that you had made as a result of the bet.
Put in the new numbers, and start again with the 4 methods.
If instead you have arrived at case 3 you just have to make another bet .... and start again with the 4 methods.
I know, betting in this way seems complicated, and perhaps it is, but I find it easier than applying any other method, which certainly will exist, but which will be at least as complicated as pulling at random and continuing ... This obviously according to my humble opinion ...
Here is a program, made with Visual Basic 6.0, to solve Sudoku puzzles
SUDOKU SOLVER (C) Eugy 2005 [V 1.1]
Compared to version 1.0, I added a NON-recursive "brute force" attack procedure, it activates when it is the case, asking you if to start.
99.99% of the sudokus you'll find out there, wherever they are, do NOT require brute force attack.
The program tries first with logic, and if it does not solve it asks you whether to continue "FORCE BRUTA" or "PULLING AT RANDOM".
I repeat: if you have taken the sudoku somewhere, if it does not resolve itself with logic alone, and therefore you come to this choice, it is enough to "throw at random".
The Brute Force is not yet perfected, if used with a 9x9 scheme it works very well, but if called with a 16x16 sudoku, with few (but not very few) numbers, it risks nailing itself without arriving at a solution.
No problem: under the FILE menu the EXIT command remains active ("ESCI" in Italian), which interrupts the program.
Since errors or inaccuracies are always lurking ... if someone notices something wrong, please, USE THE CONTACT FORM (in the menu above)
Do the same thing if I had been unclear, and you want further clarification on this topic, remembering to also put your e-mail, so that I can answer you.