Howard,
Take a look at this code that I wrote awhile back when I first stumbled on Sudoku. This is absolutely not pretty code!! It was just a quickie one Sunday afternoon to have some fun. After solving the puzzle, I decided not to waste anymore time cleaning up this code (maybe one day, though). Let me emphasize once again - it works, but it ain't pretty and I did not spend time refactoring. :~)
Here's the program and after that some explanatory text:
clear
dimension GBArray(9, 9)
GBArray = "123456789"
GBArray(1, 3) = "1"
GBArray(2, 2) = "5"
GBArray(3, 1) = "2"
GBArray(4, 3) = "7"
GBArray(5, 2) = "4"
GBArray(6, 3) = "2"
GBArray(7, 1) = "1"
GBArray(8, 2) = "2"
GBArray(9, 3) = "8"
GBArray(2, 5) = "6"
GBArray(3, 4) = "8"
GBArray(3, 6) = "5"
GBArray(4, 5) = "8"
GBArray(5, 4) = "6"
GBArray(5, 6) = "1"
GBArray(6, 5) = "7"
GBArray(7, 4) = "7"
GBArray(7, 6) = "2"
GBArray(8, 5) = "9"
GBArray(1, 7) = "9"
GBArray(2, 8) = "2"
GBArray(3, 9) = "3"
GBArray(4, 7) = "4"
GBArray(5, 8) = "7"
GBArray(6, 7) = "8"
GBArray(7, 9) = "5"
GBArray(8, 8) = "6"
GBArray(9, 7) = "2"
for rb = 1 to 7 step 3
for cb = 1 to 7 step 3
DisallowedStr = ""
for i = 0 to 2
for j = 0 to 2
r = rb + i
c = cb + j
if len(GBArray(r, c)) = 1
DisallowedStr = DisallowedStr + GBArray(r, c)
endif
endfor
endfor
for i = 0 to 2
for j = 0 to 2
r = rb + i
c = cb + j
if len(GBArray(r, c)) > 1
GBArray(r, c) = chrtran(GBArray(r, c), DisallowedStr, replicate("x", len(DisallowedStr)))
endif
endfor
endfor
endfor
endfor
for r = 1 to 9
DisallowedStr = ""
for c = 1 to 9
if len(GBArray(r, c)) = 1
DisallowedStr = DisallowedStr + GBArray(r, c)
endif
endfor
for c = 1 to 9
if len(GBArray(r, c)) > 1
GBArray(r, c) = chrtran(GBArray(r, c), DisallowedStr, replicate("x", len(DisallowedStr)))
endif
endfor
endfor
for c = 1 to 9
DisallowedStr = ""
for r = 1 to 9
if len(GBArray(r, c)) = 1
DisallowedStr = DisallowedStr + GBArray(r, c)
endif
endfor
for r = 1 to 9
if len(GBArray(r, c)) > 1
GBArray(r, c) = chrtran(GBArray(r, c), DisallowedStr, replicate("x", len(DisallowedStr)))
endif
endfor
endfor
for r = 1 to 9
for c = 1 to 9
if len(GBArray(r, c)) = 1
GBArray(r, c) = "Z" + GBArray(r, c)
endif
endfor
endfor
Done = .f.
do while not Done
ChgdCount = 0
for r = 1 to 9
for c = 1 to 9
if occurs("x", GBArray(r, c)) = 8
Num = chrtran(GBArray(r, c), "x", "")
GBArray(r, c) = "Z" + Num
for x = 1 to 9
if between(occurs("x", GBArray(r, x)), 1, 7)
GBArray(r, x) = chrtran(GBArray(r, x), Num, "x")
ChgdCount = ChgdCount + 1
endif
endfor
for x = 1 to 9
if between(occurs("x", GBArray(x, c)), 1, 7)
GBArray(x, c) = chrtran(GBArray(x, c), Num, "x")
ChgdCount = ChgdCount + 1
endif
endfor
endif
endfor
endfor
for r = 1 to 9
TempStr = replicate("0", 9)
for c = 1 to 9
if "x" $ GBArray(r, c)
for x = 1 to 9
if substr(GBArray(r, c), x, 1) <> "x"
TempStr = stuff(TempStr, x, 1, transform(val(substr(TempStr, x, 1)) + 1))
endif
endfor
endif
endfor
Num = at("1", TempStr)
if Num > 0
Num = transform(Num)
for x = 1 to 9
if Num $ GBArray(r, x)
c = x
GBArray(r, x) = "Z" + Num
for x = 1 to 9
if between(occurs("x", GBArray(x, c)), 1, 7)
GBArray(x, c) = chrtran(GBArray(x, c), Num, "x")
ChgdCount = ChgdCount + 1
endif
endfor
exit
endif
endfor
endif
endfor
for c = 1 to 9
TempStr = replicate("0", 9)
for r = 1 to 9
if "x" $ GBArray(r, c)
for x = 1 to 9
if substr(GBArray(r, c), x, 1) <> "x"
TempStr = stuff(TempStr, x, 1, transform(val(substr(TempStr, x, 1)) + 1))
endif
endfor
endif
endfor
Num = at("1", TempStr)
if Num > 0
Num = transform(Num)
for x = 1 to 9
if Num $ GBArray(x, c)
r = x
GBArray(x, c) = "Z" + Num
for x = 1 to 9
if between(occurs("x", GBArray(r, x)), 1, 7)
GBArray(r, x) = chrtran(GBArray(r, x), Num, "x")
ChgdCount = ChgdCount + 1
endif
endfor
exit
endif
endfor
endif
endfor
set step on
for rb = 1 to 7 step 3
for cb = 1 to 7 step 3
TempStr = replicate("0", 9)
UsedNums = ""
for i = 0 to 2
for j = 0 to 2
r = rb + i
c = cb + j
if "Z" $ GBArray(r, c)
UsedNums = UsedNums + right(GBArray(r, c), 1)
endif
endfor
endfor
LenUsedNums = len(UsedNums)
if LenUsedNums > 0
for i = 0 to 2
for j = 0 to 2
r = rb + i
c = cb + j
if "x" $ GBArray(r, c)
OrigVal = GBArray(r, c)
GBArray(r, c) = chrtran(GBArray(r, c), UsedNums, replicate("x", LenUsedNums))
if GBArray(r, c) <> OrigVal
ChgdCount = ChgdCount + 1
endif
endif
endfor
endfor
endif
endfor
endfor
Done = ChgdCount = 0
enddo
CompletedCount = 0
for r = 1 to 9
for c = 1 to 9
?? padr(substr(GBArray(r, c), 2), 10)
if "Z" $ GBArray(r, c)
CompletedCount = CompletedCount + 1
endif
endfor
?
endfor
?
? "CompletedCount = " + transform(CompletedCount)
Now some explanatory text (note that some of the "diagrams" are not displaying properly here on the UT, even with the user of the PRE tag):
Rules of Sudoku:
Sudoku is a Japanese number game played on a 9x9 grid. Some numbers are filled in for you at the start of the game. The object is to fill in the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9.
The game I showed started with the grid below. I've broken it into 3x3 cells for clarity.
Figure 1: The game board at the start of the game
1 2 3 4 5 6 7 8 9
-------------------------------------
1 | 1 | | 9 |
2 | 5 | 6 | 2 |
3 | 2 | 8 5 | 3 |
-------------------------------------
4 | 7 | 8 | 4 |
5 | 4 | 6 1 | 7 |
6 | 2 | 7 | 8 |
-------------------------------------
7 | 1 | 7 2 | 5 |
8 | 2 | 9 | 6 |
9 | 8 | | 2 |
-------------------------------------
I represented this via an array called GBArray (Game Board Array). To start out with, each element of the array contains string like this: "123456789"
So after the initial creation of the array, the first 3x3 section of the array would look like this:
Figure 2: The GBArray after initial creation and population
1 2 3
1 123456789 123456789 123456789
2 123456789 123456789 123456789
3 123456789 123456789 123456789
I'm only showing one 3x3 section, but the array is filled out to 9x9, of course. After this initial creation and population of the array, I immediately place the known values (the numbers that are filled in for us at the start of the game) in their proper locations, so the first 3x3 section now looks like this:
Figure 3: The GBArray after placement of the starting numbers
1 2 3
1 123456789 123456789 1
2 123456789 5 123456789
3 2 123456789 123456789
This represents the possible numbers at each grid location. At row 1, column 3 (1,3) we know that 1 is the only value we can have and at 2,2 we know 5 is the only value we can have and at 3,1 we know 2 is the only value we can have. At the other locations our possible values are (at this point in the explanation at least) 1 through 9.
However, the rules say 1 through 9 can only be used once in each 3x3 grid, so we know that at each of the other locations in this 3x3 grid we can't use 1, 2, or 5. So for each 3x3 grid, we must change the value in the other (non-prefilled) locations so that the possible choices are 1 through 9, minus any number that has already been used in that 3x3 grid. Looking at our 3x3 example, we have to remove 1, 2, and 5 from the choice of possibilities in each of the locations where we haven't been given a starting number. I replaced number that were removed with an "X". After doing this, our 3x3 grid would look like this:
Figure 4: The GBArray after the choices in the other cells have been narrowed to remove 1, 2, and 5
1 2 3
1 xx34x6789 xx34x6789 1
2 xx34x6789 5 xx34x6789
3 2 xx34x6789 xx34x6789
This tells us that at the positions where we don't have a prefilled number, our choices of numbers to use are 3, 4, 6, 7, 8, or 9. As you can probably tell, I'm using a process of elimination to whittle our choices down until we have a solution. (Remember, the cells with "xx34x6789" in them are actually empty on the game board - "xx34x6789" represents that numbers that could go there.)
I accomplished the above "whittling" via a loop that processed the array like this: I would pick the "base point" of a 3x3 grid (the upper left corner), then process each of the elements in that 3x3 section. I would look at each location and determine if it had a prefilled number and, if it did, I would add that number to a string called DisallowedStr. When I had looked at each element of a 3x3 grid, I would then remove anything in the rest of the cells of the 3x3 grid that I found in the DisallowedStr variable. That's how I got the array to the state represented in figure 4.
Look at the section of code that has these two loops:
for rb = 1 to 7 step 3
for cb = 1 to 7 step 3
...code...
endfor
endfor
These outer loops (using rb = row base and cb = column base) let me find the upper left corner (the "base") of each 3x3 array. Inside of these FOR loops, I have a more FOR loops that process the elements of the 3x3 section of the array, so they use FOR i = 0 to 2. The first set of 0 to 2 loops lets me figure out what numbers can't be played in the cells that are empty and the second set of 0 to 2 loops lets me remove those numbers from the set of possible numbers that can go in the empty cells. Study the code, it looks confusing, but really isn't (at least to my warped mind!).
After handling the 3x3 cells as discrete units, we can start looking at the rows and columns. We know that the numbers 1 through 9 need to appear once in each row and once in each column. Looking back at our 3x3 example in figure 4, we know that 3, 4, 6, 7, 8, or 9 are the only values that can currently go in the empty cells of that 3x3 grid. However, look back at figure 1 and note that in column 2 the number 4 has been prefilled at row 5. This means that in column two of our 3x3 grid, the number 4 can't be placed, because it's already been placed in the "overall" column at row 5. So we have to remove 5 as a possibility and make our grid look like this:
Figure 5: The number 4 has been removed as a possible number for column 2
1 2 3
1 xx34x6789 xx3xx6789 1
2 xx34x6789 5 xx34x6789
3 2 xx3xx6789 xx34x6789
Column three can be processed in the same manner, removing 7 and 8 as possibilities, and our grid would then look like this:
1 2 3
1 xx34x6789 xx3xx6789 1
2 xx34x6789 5 xx34x6xx9
3 2 xx3xx6789 xx34x6xx9
You can find the code that processes the rows and columns (I actually did rows first, not columns) and continues to whittle down our choices for each of the empty cells). Hopefully, the comments in the code will help you figure out that code.
MAKE IMPROVEMENTS! This was a quick and dirty program just as an exercise. If you do make some improvements, send them to me with comments.
