
QuickBASIC
programs 



SUDOKU Solver
Ver 8.2 

A typical SUDOKU board
is divided into nine grids of nine cells. The object of the
game is to fill in all the cells with a number from 1 to 9,
without a double in any grid, row or column. This program
attempts to do just that, even if it has to try it a million times! 




SUDOKU solver screen after typing numbers in
from a book. 



The solved puzzle. 



This early version of the
program took over ten
minutes and 5.2 MILLION attempts to solve this puzzle!
The program was originally named "Pseudo Sudoku Solver." 


A later version solved it on
a single pass. 


How the program
works 

First, type in the numbers from an
actual Sudoku puzzle. (You can type in random numbers, but
you will occasionally create an invalid puzzle that has no
solution.) After the last number is placed, press <ENTER>
and the program will begin.
The program has two main subroutines where
the "puzzle solving" is done, named
Board0 and Board1. Subroutines
called ViewGrid1 to ViewGrid9 are used by both to find numbers in the nine 3X3 grids.
Board0 looks for cells that only have one solution,
based on numbers populated in other cells. It goes through
each empty cell, starting at the topleft, making a list of all possible numbers for each
cell. It looks in the 3X3 grid that contains the cell, then
across the row and up and down the column. If the list has a
single digit on it, it puts it in the cell. If the list
contains
more than one digit, it ignores the list and goes to the
next cell. Each number that it finds increases the chances it will find another number. It scans the
puzzle until no more numbers are found, then exits.
If it's an "easy" puzzle, it will sometimes solve the puzzle
during this phase, but don't count on it.

Flaw in the program
logic 
It's obvious that the only
digit that can go in the leftcenter cell is a "2." However, the
program doesn't see it.
It only "looks" in the direction of the arrows, blind to the other
2s. That's OK, it will eventually find it. 

Board1
then starts in the topleft cell. It finds the first
available empty cell. It generates
a random number, and looks within the 3X3 grid for any numbers
already there. If there is a number in the grid that matches
the random number it just generated, it generates a new
number.
If a matching number is not
found in the 3X3 grid, it looks left and right, and up and
down. If a matching number
is found, it generates a new random number. If a matching
number is NOT found, it puts the number in the cell. If no
number can be put into the cell, it erases all the numbers
in the 3X3 grid and starts over. The process repeats till all 81 cells contain a
number.
The exception is the last cell in each grid. Since eight
digits have already been used, there is only one digit that
can possibly go into the space. If it can't be used, the
grid is erased and reprocessed.







This image shows how the "Board1
" subroutine works.
In this case, it has randomly selected the digit
"5."






Both the cells and the grids are
processed in the order below, from 1 to 9.
Changing the order does not seem to have an advantage.
Starting in grid 5 is counterproductive. I don't know why. 




When a grid is filled, the next grid
is begun starting at the topleft cell. If a number can't be
entered into a cell after 20 attempts, the grid will start over. If the grid
has restarted 20 times and still can't be completed,
the whole board starts over.
Why 20 times to enter a number? You may well ask! The numbers are generated
randomly. If you generate random numbers between 1 and 9
you're going to get some doubles before you get every digit.
I analyzed the minimum number of attempts needed to generate
every digit from 1 to 9, and it seems to be about 20, though occasionally
a number will be missed. (I
initially had it set to 40.)
For example,
If you generate 20 random digits from 1 to 9 you get something like
this:
5 4 7 4 8 6 6 9 5 2 9 1 3 5 8 9 5 3 1 8  all numbers from 1
to 9 are present  barely. There is only a single "2"
but "5" appears four times. (These were actually generated
by the Sudoku program.)
As soon as a number can be placed in a cell the program goes
on to the next cell, so why place a limit on the number of
random digits? Because if a number can't be placed, it will
keep trying the same nine digits forever. So in this case,
20 times is the limit.
Originally, the program wasted time trying numbers it
already attempted, such as trying the number "5" four times.
Starting in Version 7.2 the program "remembers" numbers it
has already used.
If a grid or the entire board starts over, the numbers that
the user has entered or that Board0 has found are put back in their cells by a
subroutine named ReloadData.
The program is not able to "see" the whole board at once,
like a human can. It only sees the 3X3 grid of the cell it is
currently working in, as well as the row and column. It
keeps plugging numbers in over and over till the puzzle is
complete.
Each cell has it's own programming. You can think of it as
81 subroutines.
I programmed the first cell for Board1, then copied, pasted and edited
it 80 more times. I did the same thing for Board0. It
was a bug factory. A single mistake would produce 80 more
bugs! Once the bugs were out the program worked very well,
though it can still take quite a while to solve a "hard"
puzzle. And I mean QUITE a while. It has "AI" or "artificial
ignorance."
The challenge was figuring out how to tell the computer to
solve the puzzle, since I'm actually not very good at
Sudoku. Even before I started, there were some basic
questions, such as, "How does the program know it's done?" I
thought that one way was to check and see if every row and
column added up to 45. In the end, it wasn't necessary. When
the bottomright cell is filled, there is nothing left for
it to do.
When I say that the programs "looks" at a cell and "sees" a
number I mean it almost literally. The program is displayed
on an 80 x 25 text screen. It queries the screen coordinates and returns the
number found there.
For example, it will look 40 columns across and 15 rows down and get the number in that spot on the screen.
So here's a question to keep you awake tonight: Will the
program work if the monitor is turned off?




DOWNLOAD 







Click on icon
above to view or download the source code 

Click on icon above to
download SUDOKU85.exe 



Note: Browsers don't like .EXE
files. Please rename "SUDOKU85.RenameToExe" to "SUDOKU85.exe"
after downloading.



According to a
Wikipedia article titled "The Mathematics of Sudoku," there
are 6,670,903,752,021,072,936,960 ways to fill in a blank
Sudoku board. This explains how the program can fill in a
blank board so quickly.
You would think that
the number is just a factorial of 81 (81 x 80 x 79 x 78 x
77....etc). However, the
factorial of 81 is 5,797,126,020,747,367,985,879,734,231,578,109,105,412,357,244,731,625,958,745,865,049,
716,390,179, 693,892,056,256,184,534,249,745,940,480,000,000,000,000,000,000.
The difference in the numbers is that the factorial of 81
doesn't follow any Sudoku rules.
An actual Sudoku puzzle will have just one solution. The
minimum number of clues to complete a puzzle is 17. 




Here is a very
interesting Sudoku puzzle. It's the number Pi in order,
which is 3.141592653589793238462. This puzzle was
created by Phillip Newman in March of 2021. The "Sudoku
Solver" program solved it in
221,385 attempts.
I ran it a second time
and it took 555,242 attempts, and a third time it only took
6349 attempts. The program
really struggles with this, but it will eventually solve it.
Since it's random, the only question is, will it solve it
sooner rather than later? It was interesting to see
that Board0 found three numbers before Board1 even started
working. I found the puzzle
here. 



Last updated July 2022 


