Mind Expanding with a Cup of Java [Personal Growth Matters]

For me, COVID-19 Lockdown hasn't been a big change, since retirement means I have lots of free time anyway. I am very fortunate to live in a retirement village villa. I am sitting at the dining room table looking out over the golf course across our back fence - a large water trap with lots of bird life, the rushes, the fairway and the trees - ah, the serenity - too bad about the hacker golfers.

I regularly work on a book of puzzles, cross-words (straight and cryptic), 'code breakers', and of course Sudoku. Now I've never really been a Sudoku fan, preferring word puzzles. But the logic of solving a Sudoku puzzle intrigued me. My Computer Science post-graduate thesis back in the 70's involved programming a deduction 'engine' processing predicate calculus statements, so the method of solving Soduko was right up my alley.

I first learnt to program computers back in 1966, and have learned (and  forgotten) dozens of computer languages since. The later half of my career moved beyond mundane programming, into analysis, systems architecture, specification, quality assurance and management. But the mental stimulus of solving a problem in code, has never left me.

So as a personal growth project, I decided to teach myself a modern computer language, Java, and the problem I chose to was solving Sudoku puzzles.

A very hard puzzle.

Now the simplest program solution is to recursively try the digits 1..9 combinatorially in every empty cell. But I wanted to tackle the intelligent solution of how humans go about solving such puzzles.

<WARNING "descriptions of complex programming logic - skip if desired">

From the digits that exist in each row/column/sub-matrix, build lists of candidate digits that could appear in the empty cells of each row/column/sub-matrix. Then examine every empty cells' three lists of candidate digits that intersect at that cell and perform a logical AND of the three lists to get the candidate digits that satisfy all three row/column/sub-matrix constraints. If you are left with a single candidate in any of the row/column/sub-matrix, then that digit is the solution for that cell. After all empty cells have been processed, if there are still some cells that have not had a solution digit inserted, loop back and compute new lists of candidates.

I have found that puzzles of complexity up to 4 stars are soluble by the above method. A handful of ***** complexity puzzles still require a brute force method to solve the remaining empty cells after the above has finished. By using the lists of candidate digits at each empty cell, typically 2 or 3 digits, instead of trying all 1..9 digits, the size of the combination is much reduced. A classic 'block' that I have noticed that puzzle creators use, is to have a row/column/sub-matrix element with just 2 empty cells with the same 2 candidate digits, so there are only 2 combinations to test, 'x,y' and 'y,x'.

</WARNING>

Solution of above very hard puzzle.

By parameterizing the size of the puzzle, a simple 4x4 puzzle was used in initial debugging. A logical extension of the problem, would be to have a 25x25 puzzle that uses the 25 letters "A..Y" instead of the digits 1..9. Perhaps I could call it Nozeku! With a puzzle board that size, I suspect it would be too difficult to create problems by hand. Perhaps I will have to write a program to generate problems of Nozeku.

Another option I considered, is to use a phone camera to capture a picture of a puzzle and perform optical character recognition to input the puzzle into the program. At the press of a button, in a fraction of a second, the solution is displayed. But that program extension lacks intellectual stimulus for me.

So after that exercise, I feel my brain has 'grown' by a percentage point or two. Mind you, I have only just scratched the surface of the Object Oriented power of Java. I might have to look for another problem to solve.

Is programming sexy? Some programmers have reported experiencing algorisms! (that euphoric, Eureka, aha moment when you finally see an elegant solution to a difficult problem you have been mulling over for days or weeks). Do writers have such experiences when a beautiful plot inspiration blasts through a writer's block?

But in the mean time, I might go back to my landscape painting to relax for a while.

Addendum

Having programmed my 'obvious' strategy, I searched the internet literature for Sudoku solution strategies. Andrew Stuart's 'https://www.sudokuwiki.org/sudoku.htm' is probably the most comprehensive, listing 38 strategies. My program implements the first two basic strategies, 'Naked singles' and 'Hidden singles'.