Sodoku solving program - Broke Down

It began as a challenge from my father who is a truly exceptional Sudoku puzzle solver. When I suggested I could write a program which could solve any puzzle he flatly declared “That’s impossible. There are too many permutations. Especially on the extremely hard ones”.

So began my quest to prove him wrong. The first decision I made was what language. I chose C++. It is ideally suited to problems like this.

Next, I decided “OOP or functional”. I decided” functional”, to save on overhead and typing since the problem domain is finite, the solutions are unique and the data structures are especially amenable to the use of fixed-length arrays of dimension 1 and 2.

If I had it to do over, I would have used OOD methods for the practice and also for that certain elegance that that paradigm encourages. However I don’t think that design method would yield a program that executes with the efficiency of the current program. In fact, recently I had to go back and add microseconds for elapsed times because my program is solving some puzzles now in as little as 100 microseconds on my pretty slow old i7 laptop.

Next I made the decision to never, ever look at any existing solving programs if they existed, or any mathematical or algorithmic white papers, etc., until after my program was completed.

I wanted my solution to be 100% original with no influences from any outside source.

Since I finished my program, I found out there is quite a bit of research out there on the mathematics of Sudoku and some programming technique lore.

Mathematics of Sudoku - Wikipedia

I knew that the number of permutations of the puzzles was very large as my father pointed out. I had no idea of the actual numbers but discovered after I finished my program that in fact, the number of Sudoku grids was calculated by Bertram Felgenhauer and Frazer Jarvis in 2005 to be the largish number 6,670,903,752,021,072,936,960, although this number was pared down a bit to eliminate some symmetries.

My instinct as a veteran software developer was that I couldn’t just try to randomly insert numbers and then back-track to some randomly arbitrary previous point where an incorrect number had been inserted, try a different number in that square, rinse and repeat. I visualized the heat transfer paste on my CPU boiling off as my laptop went permanently dark.

So if the brute force guessing-then-correcting methodology wasn’t going to work in this lifetime, what to do??

Long ago, my dad taught me the number one Sudoku rule to strictly follow if I wanted to ever have any success of solving “EVIL”-level puzzles:

“Never guess!”

He said that if I guessed even just once, I would fail every time. This didn’t seem reasonable at all at first. I thought “If I know a square can only contain one of two possible numbers, then if I can’t figure out either number and decide to guess and pick one, that should mean I have a 50% chance of solving the puzzle if that was the only guess I made”. Seems reasonable, doesn’t it?

Here’s the problem with that conjecture. That only holds true in our normal reality. In Sudoku reality, that 50% chance becomes 0% chance 100% of the time, just like my dad said.

If you have ever experimented with “guessing methods” on very difficult Sudoku puzzles, you very well know the truth of this anomaly which defies mathematics itself. In fact no mathematician has every presented a plausible explanation for the inconceivable severity of the Sudoku “guess penalty”.

“OK then. I’ll design my program so it doesn’t guess. I know it will be very difficult to emulate advanced (and even simple for that matter) human solving techniques in code, but that’s the only way I stand a chance of “winning the bet” and proving old dad wrong”.

So that’s the premise under which I started writing the code. I began with Easy level puzzles from the websudoku site, figuring I could at least eventually solve a puzzle and then advance on to the harder ones next, depending on how well things were going.

I would print a puzzle out and get my first number and analyze “how did I do that?” “How can I translate that method into code?”

I decided I would need some basic “toolkit” methods first which weren’t actual solution algorithms. Like reading in a puzzle, writing out a puzzle. Getting all the missing numbers in a row, column box or group of 3 horizontal or vertical boxes, etc.

Let’s say I want to be able to easily find out the row with the least number of blank squares. ;

Little tools like this to make the actual algorithm code easier.

I identified things I would be doing a lot of and encapsulated those things in methods. For instance, I knew I would be wanting a quick list of where the blank spots are in a row, column or box. I also would like a list of all the missing numbers in a row, column or box. To make things efficient, I would like those numbers returned sorted in ascending numerical order, along with a count for how many. Here is the routine for getting all the blanks in order, with the count,etc. Looks a little complicated, but I only had to figure this out once instead of a gazillion times:

The entire main method can be viewed as a single snip of a screenshot:

This implements the least number of guesses to solve a puzzle. Most puzzles can be solved with zero guesses. If not, a very good candidate guess is made and then execution goes back to algorithmic solving. The algorithmic solving part is so good at what it does that sometimes only a single extra number is required to lock into a deterministic solution that completes with no more prediction required from that point forward.

An example of some toolkit methods follow:

So to get ordered lists of all the missing numbers and all the blanks spaces in a row, column or box, all I have to do is:

mcnt=gm(zcol,c); // mcol[1..mcnt] contains the missing nums in order
bcnt=gbls(zcol,c); // blcol[1..bcnt] for blank squares
or :
mcnt=gm(zrow,r); //mrow[1..mcnt] missing nums in row ascending
bcnt=gbls(zrow,r); //blrow[1..bcnt}

or:
mcnt=gm(zbox,b); //mbox[1..mcnt] missing nums in box ascending
bcnt=gbls(zbox,b); //blbox[1..bcnt]

In case any of you mathematically inclined folks out there are wondering “Shouldn’t the count of missing numbers match the number of missing blanks?”

Ding! Yes mcnt=bcnt; always. If you have 6 numbers and only 5 places to put them, you’ve got a big problem.

That’s it. I know mcnt is always going to have the right count of missing numbers. Same thing with blanks and bcnt. I waste the 0 position in all arrays to make things match 1–9,1–9 in puzzle notation.

If I want to insert the first missing number in the last available square in the 7th row all I do is (assume 7 for ,r in the two method calls above):

lb=blrow[bcnt]; //lb=last blank
fm=mrow[1]; //fm=first missing

But first, I want to do a minimum verification to make sure that number is not already present in the relevant row, column or box. So I have some easy methods.

int inrow=finrow(7,fm); //is that first missing number already in that row?
int incol=fincol(7,fm); //or in the column?
int tbox=gboxfromrowandcol(7, lb);
int inbox=(tbox,fm); // Or in corresponding box?

if the number to insert is not found in any of the rows, columns or boxes, everything will be zero, otherwise, a location where it is found will be returned. We want all 0s:

if ((!inrow)&&(!inbox)&&(!incol)){ //write the number into puzzle:
int res=inspuzzle(7,lb,fm);
return res;
 }//Done!

Big question: “How do I know if my solution is correct? I mean it could be some random print of some random single digits. How can I instantly validate the solution so that I am always 100% sure the answer is correct?”

This part turned out to be easier than I thought. Firstly I had to have a controlled way to insert numbers into the puzzle so that it was impossible to overwrite an original clue number. By centralizing the writing of values in a single method and never cheating and writing a number somewhere else in the program, that solved the first aspect of validation. But what about the rest of the numbers?

Thought experiment: Take a super easy newspaper puzzle and fill it out with some mistakes. Now add up the total for each row 1–9. Do the same thing for columns 1–9. Do the same thing for boxes 1–9.

What did you come up with? Probably quite a few 45’s, some 43’s. Maybe a 51.
That’s the trick! If the puzzle is correctly solved, all rows, all boxes and all columns will each add up to 1+2+3+4+5+6+7+8+9=45. Presto! Infallible validation which is child’s play to calculate.

This is getting really long. If you ask another question about “Can you give an example of a Sudoku puzzle solution algorithm in code?” in a new question, we can advance to the next stage. And then finally another question like “Can you describe a hybrid Sudoku solution design which incorporates “logical and likely” extrapolation techniques for the world’s hardest puzzles combined with deterministic and heuristic “non guessing” methods?” as a final question. That one is a little technical.

In the mean time, if you want to play around with my program, here it is:

MarionBarbee/Sudoku_solver

I put some .bat files in the repository t.bat is 10 “EVIL” puzzles from websudoku site. s.bat is the 10 hardest Sudoku puzzles in the world created by Arto Inkala, Prof. Mathematics U of Helsinki. When I sent all 10 solutions to him he emailed me back “I am astounded!”. Pretty much made the rest of my day. If you can hit the sweet spot in your CPU clocking and cache this program is almost too fast to believe. 70 ms is a pretty decent time to solve all 10 EVIL puzzles on my slow computer. I can run s.bat a few times and get really good performance. I think the low batch time for the 10 world’s hardest is about 1170 milliseconds on my 2.5 GHz i7 4770HQ. I would be interested to see a run on a powerful computer. Thanks for reading all this if you did. If you did, you must be a number geek like me. Welcome! The next installment will be a medium difficulty algorithm with some diagrams and code as soon as I get the new question.

I’m getting some weird rounding results on microseconds elapsed times. It seems like times <500 microseconds are getting rounded down to 0, most but not all of the time. I am using the C++11 chrono library. Here is a puzzle between 500 microseconds and 1 millisecond. It is OK:

Here is my final elapsed time calculation:

auto gltime2 = chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count();

auto gelapsedtime = gltime2 - gltime1;