
QuickBASIC
programs 



SUDOKU Solver
Ver 5.3 

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 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 

The program has two subroutines where
the "puzzle solving" is done, named
Grid0 and Grid1.
Grid0 begins by going through all
the empty cells, 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. It scans the
puzzle ten times. Each number that it finds increases the
odds it will find another number.
If it's an "easy" puzzle, it will sometimes solve the puzzle during this phase.

Flaw in the Grid0 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.
That's OK, the Grid1 subroutine will find it. 

If the puzzle is not solved, Grid1 then starts in the topleft cell in the topleft
grid. It finds the first available empty cell. It generates
a random number, then 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, it calls the subroutine
FindNumbers, which makes a list of all the numbers in
the puzzle. Grid1 then looks at what FindNumbers
has found in the row and column. If a
matching number is not found, it puts the number in the
cell. If a matching number IS found, it generates a new
number. The process repeats till all 81 cells contain a
number.







This image shows how the "Grid1" subroutine works.






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 been processed 20 times and still can't be completed,
the whole board starts over.
Why 20 times? 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. (I
initially had it set to 40.)
For example,
If you generate 20 random digits 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".
If you edit the QuickBASIC and display the numbers that are
being generated, you'll see the program actually waste time
trying numbers it already attempted, such as trying the
number "5" three times. Oh well, they're supposed to be
random.
If a grid or the entire board starts over, the numbers that
the user has entered or that Grid0 has found are put back in their cells by a
subroutine named ReloadData.
Grid1 is not able to "see" the whole board at once,
like a human can. It sees the 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 Grid1, then copied, pasted and edited
it 80 more times. I did the same thing for Grid0. 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 of
the cells and returns the ASCII character code found there.
For example, it will look 15 rows down and 40 columns across
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?










Click on icon
above to view or download source code 

Click on icon above to
download SUDOKU53.exe 



Note: Browsers don't like .EXE
files. Rename "SUDOKU53.RenameToExe" to "SUDOKU53.exe"



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.
You would think that
it 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. 




Notes: (Read from the
bottom up)
Version 5.3
72 "IF...THEN" statements removed from Grid1 subroutine.
Number of attempts made before starting over reduced from 40
to 20
All variables are defined as integers. This supposedly
speeds up the program since we're dealing with small whole
numbers.
Version 5.0
Instead of a cell "looking" left and right, it will look
across the whole row and just ignore itself.
Was able to delete
126 IF...THEN statements using this method.
Version 4.9
While user is entering a number, row and column will be
checked for duplicates.
(A duplicate number in a row or column will result in a
puzzle with no solution.)
Slightly compacted QuickBASIC code  two subroutines merged
into one.
Version 4.6
If Grid0 doesn't find any numbers on the first pass, it's
pointless to keep looking, so it exits.
Version 4.5
Added a message saying how many passes the Grid0
subroutine makes so you can see something happening while in
QuickBASIC. (Happens so fast in the .EXE version you can't see it).
Minor fix to the text.
Version 4.4
Minor tweaks. I read that the way I was clearing the
keyboard buffer doesn't work in Windows, so I changed it. It
didn't seem to
affect
anything one way or the other. QB64 has "_KEYCLEAR" but this
is not compatible with QuickBASIC.
Version 4.3
Replaced 1050 lines of code with 126 lines by adding 9 subroutines. Will now
load into QuickBASIC. (YAY!)
Version 4.1
Major logic flaw fixed. (program didn't rescan 3 X 3 grids
after populating a cell, resulting in doubles.)
Several other bug fixes. No longer fits in QuickBASIC. (WAH!)
Version 3.1
Prescan of cells with addition of Grid0 subroutine.
Y axis changed to letters instead of
numbers. Some improvements to performance.
Version 2.0
Non working version. I attempted to fill the puzzle
using digits in numerical order. it never got past number 5.
Version 1.7
2 bugs fixed.
Version 1.62
You can make unlimited changes while filling in the puzzle.
Some improvements to performance.
Version 1.4
You no longer need to press <ENTER> when entering numbers.
Less tedious!
Version
1.3
Board is now white, other color fixes.
1 bug fix.
Version 1.2
Now runs in a resizable window.
Grid 1 runs more efficiently (Grid 1 gets hit every single
time the Sudoku screen restarts.)
Will open in QuickBASIC 4.5 and QB64.
Asks if you want another puzzle.
1 bug fix.
Screens cleaned up.
Version 1.0
The nine grids started out as nine subroutines (Grid1 to
Grid9). However, switching back and forth caused a Stack
Overflow and the program would crash. All the subroutines
were combined into one large sub. Unfortunately, it was too
large to load into QuickBASIC 4.5 and would only load in
QB64. March, 2020.
The board was supposed to be white, but it was gray. The
program uses the BASIC text mode screen. Text mode doesn't
support a white background.



December 2020 


