Sudoku Board Generator
A few weeks lately I caught Sudoku Flu on my Microsoft Surface Pro and it spread to my iPhone and my Mac. Not my first time playing but I'm enjoying a renaissance right now. I became interested in the algorithms for generating and solving Sudoku boards and ended up writing a nice Sudoku board generator from scratch!
My first stab at the algorithm was a dismal failure. I thought I'd recursively fill each 3x3 region with all permutations of the numbers 1-9 in a random order and backtrack when necessary. This is what I needed the permutation algorithm for that I wrote about last time. Anyways, the algorithm would get stuck on the next-to-last region, trying all combinations, and didn't complete after several minutes.
After reading some good tips on Stack Overflow I gave it another try and it was a great success!
My working algorithm is as follows:
-
Seed 3 regions in a diagonal (top-left, middle, bottom-right) with the numbers 1-9 in a random order. By doing so, none of those regions can violate the 1-9 rule of any row, column, or region.
7 4 1 0 0 0 0 0 0 2 8 9 0 0 0 0 0 0 6 5 3 0 0 0 0 0 0 0 0 0 6 7 3 0 0 0 0 0 0 8 1 5 0 0 0 0 0 0 2 9 4 0 0 0 0 0 0 0 0 0 2 1 7 0 0 0 0 0 0 3 4 5 0 0 0 0 0 0 9 8 6 - Use a "Sudoku solver" approach to filling in the remaining numbers. Each number that was originally assigned should "knock out" any possibility of that number occurring in the same row, the same column, or the same region.
- Loop through all empty cells and find one that's tied for having the fewest possible numbers that can be assigned while still having at least one possibility. Randomly assign one of the possible numbers while knocking out any repeats of that number as before.
- When no cell can be assigned to the algorithm is finished. If any cells are still unassigned then the current solution is invalid. While it would be possible to backtrack and whatnot, 9 times out of 10 the generator results in a valid solution so I chose to keep it simple and just discard any invalid solutions and try again. The algorithm runs "instantly" and the most I've ever seen it take is three tries. Here's an example solution: ``` 7 4 1 9 3 8 6 5 2 2 8 9 4 5 6 7 3 1 6 5 3 1 2 7 8 9 4 9 1 4 6 7 3 5 2 8 3 7 2 8 1 5 4 6 9 8 6 5 2 9 4 1 7 3 4 3 8 5 6 9 2 1 7 1 9 6 7 8 2 3 4 5 5 2 7 3 4 1 9 8 6 ```
- The big challenge that I haven't tackled yet is then to randomly remove numbers to fit an easy/medium/hard/etc. difficulty rating. I believe it would be necessary to combine some "# of values removed" setting with a Sudoku solver that employs some level of inferencing to guarantee solvability - for example, "only fill in spots with one possible value" or "look for two spots that each contain only two numbers and remove those numbers from other candidate spots".
Here's the Rogue source code for my generator:
#====================================================================
# SudokuGenerator.rogue
#
# 2016.01.19 by Abe Pralle
#====================================================================
Board().display
class Board
PROPERTIES
cells = Cell[]( 9*9 )
regions = Region[]
candidates = Int32[] # a work list
METHODS
method init
forEach (index in 0..9*9-1) cells.add( Cell(index%9,index/9) )
forEach (j in 0..2)
forEach (i in 0..2)
regions.add( Region(this,i,j) )
endForEach
endForEach
local tries = 1
while (not generate_board)
++tries
# Clear the cell values and invalid number flags
# for the next try
forEach (cell in cells)
cell.value = 0
cell.invalid_numbers = 0
endForEach
endWhile
#println "Generated valid board in $."...
# ("# try/# tries".pluralize(tries))
method cell_at( i:Int32, j:Int32 )->Cell
return cells[ j*9 + i ]
method display
forEach (j in 0..8)
forEach (i in 0..8)
if (i > 0) print ' '
print cell_at(i,j).value
endForEach
println
endForEach
println
method display_debug
# Displays the number assigned to each cell or all possible
# numbers that can still be placed in the cell.
println "-------------------------------------"
forEach (j in 0..8)
print_row_fragment( j, 0 )
print_row_fragment( j, 1 )
print_row_fragment( j, 2 )
println "-------------------------------------"
endForEach
println
method generate_board->Logical
# Seed the board by filling 3 independent regions in a
# diagonal with numbers 1-9 in a random order
region_at(0,0).randomize
region_at(1,1).randomize
region_at(2,2).randomize
#println "SEED"
#display
while (place_another_number)
#display_debug
#println
endWhile
# Make sure every cell has a number
forEach (cell in cells)
if (cell.value == 0) return false # failed board generation
endForEach
# Valid board
return true
method invalidate_column( i:Int32, value:Int32 )
forEach (j in 0..8)
cell_at(i,j).invalidate_number(value)
endForEach
method invalidate_row( j:Int32, value:Int32 )
forEach (i in 0..8)
cell_at(i,j).invalidate_number(value)
endForEach
method place_another_number->Logical
# Find a cell with the fewest possible assignable values >= 1
local min = 10
local min_cell : Cell
forEach (cell in cells)
if (cell.value == 0)
local count = cell.possible_numbers
if (count > 0 and count < min)
min = count
min_cell = cell
if (min == 1) escapeForEach
endIf
endIf
endForEach
if (not min_cell) return false
candidates.clear
forEach (n in 1..9)
if (min_cell.can_assign(n)) candidates.add( n )
endForEach
min_cell.assign( candidates.random )
return true
method print_row_fragment( j:Int32, fragment:Int32 )
print "|"
forEach (i in 0..8)
local cell = cell_at(i,j)
if (cell.value)
which (fragment)
case 0: print "..."
case 1: print ".$." (cell.value)
case 2: print "..."
endWhich
else
forEach (n in fragment*3+1..fragment*3+3)
if (cell.can_assign(n)) print n
else print " "
endForEach
endIf
print "|"
endForEach
println
method region_at( i:Int32, j:Int32 )->Region
return regions[ j*3 + i ]
endClass
class Cell
PROPERTIES
region : Region
index_i, index_j : Int32
value : Int32
invalid_numbers : Int32
METHODS
method init( index_i, index_j )
method assign( n:Int32 )->Logical
if (value or (invalid_numbers & (1:<<:n))) return false
value = n
region.board.invalidate_column( index_i, n )
region.board.invalidate_row( index_j, n )
region.invalidate_number( n )
return true
method can_assign( n:Int32 )->Logical
return not (value or (invalid_numbers & (1:<<:n)))
method invalidate_number( n:Int32 )
invalid_numbers |= (1:<<:n)
method possible_numbers->Int32
local flags = (!invalid_numbers) :>>: 1
local count = 0
forEach (1..9)
if (flags & 1) ++count
flags = flags :>>: 1
endForEach
return count
method to->String
return "($,$)" (index_i,index_j)
endClass
class Region
PROPERTIES
board : Board
cells = Cell[]
next_region : Region
region_index : Int32
METHODS
method init( board, index_i:Int32, index_j:Int32 )
region_index = index_j * 3 + index_i
index_i *= 3
index_j *= 3
forEach (j in index_j..index_j+2)
forEach (i in index_i..index_i+2)
cells.add( board.cell_at(i,j) )
cells.last.region = this
endForEach
endForEach
method invalidate_number( n:Int32 )
forEach (cell in cells) cell.invalidate_number( n )
method randomize
# Assign 1-9 in a random order
forEach (cell at i in cells.clone.shuffle)
cell.assign( i+1 )
endForEach
endClass