I've always wanted to implement sudoku. Solving a sudoku is an issue on its on, but this is a step beyond. We want our own program to check whether the user has finished the sudoku. I'm going to be honest, the challenge this time started off very easy, but near the end increased in difficulty.
Now, of course, we have to make this in a single day. I'll give you the strict design, then we can get to work. If you want, you can stop reading after the design and make it yourself.
From the User's Perspective
We're only going to have one phase for this game, just like space invaders. If you haven't played sudoku before, the game is centered on a 9x9 grid. It needs to be obvious that the grid is chopped up into 9 3x3 grids. We're going to have a few set sudokus to solve. Clicking reset will clear the board and pick one of the set sudokus. There should be some sort of indication when we solve a sudoku. I think we should also try to add an auto-solver. Our auto-solver won't be a good algorithm, but it'll be good enough for a make in day!
Shortlist
- There is a 9x9 grid made up of 9 3x3 grids
- There will be multiple pre-made sudokus to play
- There is a reset button
- The user can add numbers to the grid, but only if valid
- The user can remove numbers from the grid, but only those they placed
- The game will show when the sudoku is solved
- There will be an auto-solve button
Product of a Day
A 9x9 grid, for me, that's a 2D array, so let's put that in and get it drawing.
We need to draw the grid lines, then the text on top.
// Draw grid lines
g.vis.DrawLine(0, 0, 0, TILE_SIZE*9, 1, color.White)
g.vis.DrawLine(TILE_SIZE, 0, TILE_SIZE, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*2, 0, TILE_SIZE*2, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*3, 0, TILE_SIZE*3, TILE_SIZE*9, 1, color.White)
g.vis.DrawLine(TILE_SIZE*4, 0, TILE_SIZE*4, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*5, 0, TILE_SIZE*5, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*6, 0, TILE_SIZE*6, TILE_SIZE*9, 1, color.White)
g.vis.DrawLine(TILE_SIZE*7, 0, TILE_SIZE*7, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*8, 0, TILE_SIZE*8, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*9, 0, TILE_SIZE*9, TILE_SIZE*9, 1, color.White)
g.vis.DrawLine(0, 0, TILE_SIZE*9, 0, 1, color.White)
g.vis.DrawLine(0, TILE_SIZE, TILE_SIZE*9, TILE_SIZE, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*2, TILE_SIZE*9, TILE_SIZE*2, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*3, TILE_SIZE*9, TILE_SIZE*3, 1, color.White)
g.vis.DrawLine(0, TILE_SIZE*4, TILE_SIZE*9, TILE_SIZE*4, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*5, TILE_SIZE*9, TILE_SIZE*5, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*6, TILE_SIZE*9, TILE_SIZE*6, 1, color.White)
g.vis.DrawLine(0, TILE_SIZE*7, TILE_SIZE*9, TILE_SIZE*7, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*8, TILE_SIZE*9, TILE_SIZE*8, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*9, TILE_SIZE*9, TILE_SIZE*9, 1, color.White)
for r := range GRID_SIZE {
for c := range GRID_SIZE {
if g.grid[r][c] == 0 {
continue
}
op := text.DrawOptions{}
op.PrimaryAlign = text.AlignCenter
op.SecondaryAlign = text.AlignCenter
g.vis.DrawText(strconv.Itoa(g.grid[r][c]),TILE_SIZE, float64(c)*TILE_SIZE+TILE_SIZE/2, float64(r)*TILE_SIZE+TILE_SIZE/2, g.vis.GetFont("default"), &op)
}
}
You can see we have no numbers drawn, because we don't draw zeroes. I did check that the numbers were drawn correctly. But we're not drawing the zeroes because we're going to have them denote an empty tile. And of course, the numbers in the grid can't be over 9. We've also drawn thicker lines to show the sub-grids. Now, I really don't want the player to be able to write any character. Because of this, I'm going to have 9 buttons, and the current selected number. In this case, choosing a button then pressing in the grid places that number.
And now we need to be able to place these numbers in the grid.
func (g *Game) leftClick() {
x := int(g.mousePos[0] / TILE_SIZE)
y := int(g.mousePos[1] / TILE_SIZE)
if x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE {
return
}
g.grid[y][x] = g.curNumber
}
Now that we have the placing of our own numbers, we want a sudoku to solve for ourselves. Let's just grab a few from online, and save them to use. We also want to randomly choose a grid whenever we open the game or reset.
var premadeGrids = [][GRID_SIZE][GRID_SIZE]int{
{
{5, 3, 0, 7, 0, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9},
},
}
func (g *Game) reset() {
i := rand.Intn(len(premadeGrids))
g.grid = premadeGrids[i]
}
Looks like it's working to me. We do have an issue, however. Currently, we can override numbers that are pre-placed, which we don't want. We could do a check on the original grid, to check whether it's valid to place. However, what I think is more correct is to create a tile structure. This way, we can have a Boolean that locks it. This also means that later on we can extend the tile. For example, if we want to give the player the ability to type all the possible numbers a tile could be, we could store that in the tile.
type Tile struct {
num int
locked bool
}
func (g *Game) reset() {
i := rand.Intn(len(premadeGrids))
for r := range GRID_SIZE {
for c := range GRID_SIZE {
n := premadeGrids[i][r][c]
g.grid[r][c] = Tile{num:n, locked:n != 0}
}
}
}
Looks pretty good so far, so let's check our list.
- [x] There is a 9x9 grid made up of 9 3x3 grids
- [x] There will be multiple pre-made sudokus to play
- [x] There is a reset button
- [x] The user can add numbers to the grid, but only if valid
- [x] The user can remove numbers from the grid, but only those they placed
- [ ] The game will show when the sudoku is solved
- [ ] There will be an auto-solve button
Nice, only 2 problems left! Checking we've solved the sudoku, and auto-solving.
Solving is quite simple, the first check is to check for zeroes. If there are any of them, that means we haven't finished yet. We then check each column, row, and sub-grids for duplicates. If we find none, then we have to inform the user they won.
I've made a method getWinState, and if this returns true, then the sudoku lines will turn green. For placeholder, it will just return true.
Looks like it's working.
// 0 Check
for r := range GRID_SIZE {
for c := range GRID_SIZE {
if g.grid[r][c].num == 0 {
return false
}
}
}
The zero check is quite simple, as soon as we find a zero, the problem can't be solved. Now before we start with the other checks, we need a way to make sure there's no duplicates. First, we could use a map.
If the size of the map is not 9, then we haven't solved the puzzle. We could compress this down to an array of Booleans with 9 spaces. We use the number in the tile to index the array to true. If there is a false in this array, the puzzle isn't solved. To compress this even more, we could use a 9-bit integer. Each bit will be a true or false for whether a given number is shown. If the number equals 0b111111111, which is 511, then we've got a valid section. We can't have 9 bits, so we have to take the next biggest integer size, 16 bits. Let's take this approach.
func (g *Game) checkWinState() bool {
// 0 Check
for r := range GRID_SIZE {
for c := range GRID_SIZE {
if g.grid[r][c].num == 0 {
return false
}
}
}
// Row Check
for r := range GRID_SIZE {
var check uint16 = 0
for c := range GRID_SIZE {
check |= uint16(1 << (g.grid[r][c].num-1))
}
if check != 511 {
return false
}
}
// Col Check
for c := range GRID_SIZE {
var check uint16 = 0
for r := range GRID_SIZE {
check |= uint16(1 << (g.grid[r][c].num-1))
}
if check != 511 {
return false
}
}
// Sub-Grid Check
for or := range SUB_GRID_SIZE {
for oc := range SUB_GRID_SIZE {
var check uint16 = 0
for ir := range SUB_GRID_SIZE {
for ic := range SUB_GRID_SIZE {
check |= uint16(1 << (g.grid[or*SUB_GRID_SIZE+ir][oc*SUB_GRID_SIZE+ic].num-1))
}
}
if check != 511 {
return false
}
}
}
return true
}
Using this code, the puzzle only goes green when I complete it correctly. Now we only have one more thing on our list, auto solve. We're going to be using a backtracking algorithm, which brute-forces its way through. It attempts to try every possibility until it finds the correct one. It would be smart to clear the board before we start, just in case the user messes stuff up.
func (g *Game) auto() {
for r := range GRID_SIZE {
for c := range GRID_SIZE {
if g.grid[r][c].locked {
continue
}
g.grid[r][c].num = 0
}
}
g.solve(0, 0)
}
g.solve is a recursive method that we will use. It takes in a position on the grid. It will iterate over 1 through 9 on this tile. Each iteration, it will call itself on the next tile. If a valid iteration is achieved, it will return and end the process.
This isn't actually what I want to do, however. This will cause the game to hang, as the solver is checking all possibilities. I think it would be cooler if we could watch it try to find the answer in real time. The rules we've written don't forbid this, so let's see if we can do this. A note is that we don't want to allow the player to press tiles while this is happening.
We want to start the solver at 0, 0, and increment it at each step. Once it has hit 9, it will set it back to 0, and increment the next tile. Then it will go back to the first tile and go through the process again. Once it has hit the bottom right, if it is solved, it should stop. From this, we need to know the position of the tile we're working on. This approach also requires all number to be at least one, so let's do that.
func (g *Game) auto() {
// Done!
if g.checkWinState() {
g.autoSolving = false
return
}
// Invalid move
if g.autoRow < 0 || g.autoRow >= GRID_SIZE {
g.autoSolving = false
return
}
if g.grid[g.autoRow][g.autoCol].locked {
g.autoMove(g.autoRow, g.autoCol+1)
return
}
// This tile is done
if g.grid[g.autoRow][g.autoCol].num == 9 {
g.grid[g.autoRow][g.autoCol].num = 1
// Move to the next tile
g.autoMove(g.autoRow, g.autoCol+1)
return
}
g.grid[g.autoRow][g.autoCol].num++
g.autoMove(0, 0)
return
}
func (g *Game) autoMove(r, c int) {
// Out of bounds
if r < 0 || r >= GRID_SIZE {
g.autoRow = 0
g.autoCol = 0
return
}
// Wrap
if c < 0 {
g.autoRow = r-1
g.autoCol = GRID_SIZE-1
return
}
if c >= GRID_SIZE {
g.autoRow = r+1
g.autoCol = 0
return
}
// Correct (no change needed
g.autoRow = r
g.autoCol = c
}
This code goes through each and every possibility, so it is extremely slow. What we want is a way to speed this thing up a bit.
Optimization
First step is the fact that this method is only being called once per frame. We could get away with calling it multiple times per frame.
So let's do that first.
func (g *Game) auto() {
t1 := time.Now()
var diff time.Duration = 0
for diff.Milliseconds() < MS_PER_FRAME {
g.solve()
t2 := time.Now()
diff = t2.Sub(t1)
}
}
This works very well. In each frame, we have so much dead time, and this takes advantage of that fact. Without the optimization, the first tile would change very rapidly. Now, the entire first row is constantly changing. I added a counter that would print how many times g.solve is called per frame. It is called around 100,000 times every frame, so 6,000,000 a second. This is an incredible time save, but we're still a long way off. To create a reasonable solver, we still need to cut down the solve time by multiple orders of magnitude.
Now, our spec does not specifically say how fast something like this should take. However, I don't think it's reasonable to say we solved it, and then it takes a full day to compute. This challenge is make in a day, not make in a day then run for two. So what is our next point to attack? Well we've tried calling the method more, now let's trying needing to call it less.
We're going to make it so that when incrementing, we don't pick a number that is in a further column. We can do the exact same thing for further rows. The code below helps us determine this.
func (g *Game) countRowMatches(r, c, n int) int {
count := 0
for c = c+1; c < GRID_SIZE; c++ {
if g.grid[r][c].num == n {
count++
}
}
return count
}
"Human" Solving
This does well, but is still too slow. It takes quite a while to affect the 3rd row. Now, we admit defeat. Well, not exactly. Let's try a completely different approach. What if we go through each tile, and mark off all the numbers that tile can't be. If that tile can only be one number, we set it to that number. We then repeat this process until all tiles are done. If we get stuck, we're going to fall back on the brute force approach given above.
func (g *Game) humanSolve() bool {
if !g.checkedAllPoss {
if g.checkAllValidPoss() {
g.checkedAllPoss = true
g.autoRow = 0
g.autoCol = 0
}
return true
}
// Now find singles and place them
if g.placeEnsuredTile() {
g.checkedAllPoss = false
g.autoRow = 0
g.autoCol = 0
return true
}
return false
}
// Returns true if a wrap occurs
func (g *Game) nextTile() bool {
// Move to next tile
g.autoMove(g.autoRow, g.autoCol+1)
// Wrapped?
return g.autoRow == 0 && g.autoCol == 0
}
func (g *Game) placeEnsuredTile() bool {
// Number already given
if g.grid[g.autoRow][g.autoCol].num != 0 {
return g.nextTile()
}
if g.grid[g.autoRow][g.autoCol].locked {
return g.nextTile()
}
numValids := 0
lastIndex := 0
for i := range 9 {
if g.grid[g.autoRow][g.autoCol].canBe[i] {
numValids++
lastIndex = i
}
}
if numValids == 1 {
g.grid[g.autoRow][g.autoCol].num = lastIndex+1
}
return g.nextTile()
}
func (g *Game) checkAllValidPoss() bool {
// Number already given
if g.grid[g.autoRow][g.autoCol].num != 0 {
return g.nextTile()
}
if g.grid[g.autoRow][g.autoCol].locked {
return g.nextTile()
}
g.grid[g.autoRow][g.autoCol].canBe = [9]bool{true, true, true, true, true, true, true, true, true}
for r := range GRID_SIZE {
if r == g.autoRow {
continue
}
if g.grid[r][g.autoCol].num == 0 {
continue
}
g.grid[g.autoRow][g.autoCol].canBe[g.grid[r][g.autoCol].num-1] = false
}
for c := range GRID_SIZE {
if c == g.autoCol {
continue
}
if g.grid[g.autoRow][c].num == 0 {
continue
}
g.grid[g.autoRow][g.autoCol].canBe[g.grid[g.autoRow][c].num-1] = false
}
startRow := g.autoRow-g.autoRow%3
startCol := g.autoCol-g.autoCol%3
for subRow := range 3 {
for subCol := range 3 {
r := startRow+subRow
c := startCol+subCol
if c == g.autoCol {
continue
}
if r == g.autoRow {
continue
}
if g.grid[r][c].num == 0 {
continue
}
g.grid[g.autoRow][g.autoCol].canBe[g.grid[r][c].num-1] = false
}
}
return g.nextTile()
}
From my testing, if it can figure out a solution, it's pretty much instant.
But that's a lot of code, so let's walk through. The algorithm first goes through each tile to calculate all the possible numbers that tile could be. Once it has finished that, it goes back to the start, and checks for tiles that can only be one thing. If it finds a tile that can only be one thing, it will set it to that thing. If this whole thing doesn't work, we fall back to brute force.
Done
I'm kind of sick of sudokus at this point. It was fun though, and we did some important optimization work. Honestly, I might work on this in my spare time to speed up the solver. Otherwise, the code is here as always. Maybe I'll use hidden twins to allow the solver to solve the sudoku quicker. Or, I could play around with other methods. Regardless, I'll keep this version on the GitHub, and create a second folder so that we can get a before and after sort of idea.
Your Next Steps
With this sudoku solver looks pretty good now, but you can add more, here are some ideas.
- Use a faster sudoku solving algorithm
- Automatically generate sudokus
- Allow for sudokus of differing sizes
If you have any more ideas for this series, put it in the comments!
One last thing, my minesweeper post reach one of the top 7 of the week! I'm glad people are enjoying these, and I hope people are learning a lot from them (:
Top comments (2)
This is really interesting! Are you planning to implement the hidden twins or other advanced solving techniques in a future update? Would love to hear more about any progress or new ideas you try out!
I think I will, I've already uploaded new sudoku solving code to GitHub, but it's by no means optimal yet. This should be a fun problem I'll come back to every once in a while to see if I can get it faster (: