If an empty cell has only a single candidate digit, then that digit is in the final solution - it is known as a ‘naked singleton.’ A simple scan identifies these. Basically, start by assuming all nine digits as candidates in a cell, then eliminate those digits that already exist elsewhere in any of the row/column/sub-matrix that intersect at that cell. This is a very straightforward deductive type algorithm. CandidatesĪll the smarter strategies rely on determining the set of candidate digits for each empty cell based on the completed clue digits in the row, column, and sub-matrix that intersect at each empty cell. There are methods to prune the search tree that are discussed below. If there are 20 prefilled clues, then with 61 empty cells, there are 9⁶¹ possible combinations to test, obviously an impossibly large method. The base computational method is ‘brute force,’ whereby all the empty cells are filled in turn with the nine digits, and each potential solution is checked for validity. The goal of the puzzle: given a number of cells are prefilled with solution digits/clues, is to complete each row, column, and sub-matrix with the digits 1-9.Īn example ‘Hard’ Sudoku puzzle. The board comprises a 9x9 grid which is further divided into nine sub-matrices of 3x3 cells. Sudokuįor the one in a million that don’t know Sudoku, here is a brief description. So now, in retirement, I was looking for some new stimulation and decided to teach myself Java and tackle a Sudoku solution. ![]() In retirement, I did some web development (HTML+CSS) and a bit of XML-XSLT. So technically, I never moved into OOPs, although I used Simula67 in ’69 (object-oriented Algol60). The latter half of my career moved to technical writing, quality assurance, consulting, and project management. My programming languages span FORTRAN, assemblers, Lisp, SNOBOL, functional, SQL, then several traditional 3GLs, then progressing to some 4GLs and SQL. My IT career has always involved a large business analysis component, starting as an analyst programming. Sudoku is my favourite game due to the need for a variety of problem-solving strategies, and with my IT background, I got thinking about algorithmic approaches to Soduko solving. ![]() So reading, writing/blogging, crosswords, and games are good brain trainers. ![]() As we age, it is increasingly important to maintain an active body and mind. Being my wife’s carer has meant that retirement mostly involves activities at home.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |