. QuickBASIC
QuickBASIC programs

    Analog Dial          ROCKET       GALCON    SUDOKU PROGRAMS    

SUDOKU Solver
Ver 6.6

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 Grid0 and Grid1. There are two subroutines that are needed by both: FindNumbers which finds numbers by row and column, and Viewgrid (actually Viewgrid1, Viewgrid2, etc.) which finds numbers in the 3X3 grid each cell is in.

Grid0 looks for cells that only have one solution, based on numbers populated in other cells. It goes through each empty cell, starting at the top-left, 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.
 
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.
It only "looks" in the direction of the arrows, blind to the other 2s. That's OK, the Grid1 subroutine will find it.

Grid1 then starts in the top-left 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. 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 "Grid1" 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 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, 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.

If you edit the QuickBASIC and display the numbers that are being generated, you'll see the program waste time trying numbers it already attempted, such as trying the number "5" four 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 and returns the ASCII character code 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?

 
 
     
  Click on icon above to view or download source code   Click on icon above to download SUDOKU68.exe  

Note: Browsers don't like .EXE files.  Rename "SUDOKU68.RenameToExe" to "SUDOKU68.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. 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.
 
 
 
Sudoku Pi Puzzle
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 GRID0 found three numbers before GRID1 even started working. I found the puzzle here.

 
Notes: (Read from the bottom up)

Version 6.8
Numbers are no longer converted to strings when they are placed on the puzzle grid. This speeds up the processing in GRID1 by eliminating two functions in every cell. (Converting to a string and removing the blank space on the left.)

Version 6.5
Each number list in GRID0 could have up to 9 digits (9 x 81 or 729 digits total in a blank puzzle), but only a list with a single digit is valid. It will now stop and move on to the next cell if it finds more than one digit.

Version 6.3
The last number in any grid can only be whatever digit hasn't already been used. Instead of generating random numbers, the program puts in the only option, then it checks to see if it will work. No checking is done at all on the very last number (number 81).

Version 6.1
Compacted code in Grid0. Compacted sub FindNumbers.
Duplicate entries will blink to show what digit is the duplicate.

Version 5.8
Grid0 subroutine made more efficient. It was putting numbers in the cells while checking them, then erasing the numbers if they didn't work, which was unnecessary.

Version 5.7
Streamlined duplicate checking (see Ver 4.9). If Grid0 subroutine finds a number on the first pass, it will continue to look till it can't find any more, then exit. Slight changes to text and sounds.

Version 5.3
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.

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

 
Last updated December 2021
 
  NEXT