. QuickBASIC
QuickBASIC programs

    Analog Dial          ROCKET       GALCON    SUDOKU 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 left-center 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 top-left cell in the top-left 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 top-left 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 sub-routines.

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 bottom-right 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
Pre-scan 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
 
  NEXT