sudoku


See On Github

Data

Contributor

Generic placeholder thumbnail

by JanBerktold

in go

Source Code

package main

import (
	"fmt"
	"math"
)

type Field struct {
	value    int
	pregiven bool
	options  []int
}

type Sudoku [][]Field

func newField() Sudoku {
	result := make(Sudoku, 9)
	for i := 0; i < len(result); i++ {
		result[i] = make([]Field, 9)
	}
	return result
}

// Generates an array of the numbers from 0 to 9
// Helper method for createOptions
func makeNumbers() []int {
	numbers := make([]int, 9)
	for i := 0; i < len(numbers); i++ {
		numbers[i] = i + 1
	}
	return numbers
}

// Checks whether a sudoku is fully solved
func isDone(sd Sudoku) bool {
	for y := 0; y < len(sd); y++ {
		for x := 0; x < len(sd[y]); x++ {
			if sd[y][x].value == 0 {
				return false
			}
		}
	}
	return true
}

// Takes a field in a sudoku and creates a list of all legit numbers for this field
func createOptions(sd Sudoku, x, y int) []int {
	result := make([]int, 10, 10)
	numbers := makeNumbers()

	// horizontal line
	for nX := 0; nX < 9; nX++ {
		if sd[y][nX].value != 0 {
			numbers[sd[y][nX].value-1] = 0
		}
	}

	// vertical line
	for nY := 0; nY < 9; nY++ {
		if sd[nY][x].value != 0 {
			numbers[sd[nY][x].value-1] = 0
		}
	}

	// quadrant
	qX, qY := int(math.Floor(float64(x/3.0))), int(math.Floor(float64(y/3.0)))
	for nX := qX * 3; nX < (qX+1)*3; nX++ {
		for nY := qY * 3; nY < (qY+1)*3; nY++ {
			if sd[nY][nX].value != 0 {
				numbers[sd[nY][nX].value-1] = 0
			}
		}
	}

	counter := 0
	for _, num := range numbers {
		if num != 0 {
			result[counter] = num
			counter++
		}
	}

	return result[0:counter]
}

// Searches the field with the lowest number of possible values
func fieldWithLowest(sd Sudoku) (x, y int) {
	lowest := 100
	lX, lY := 0, 0
	for y := 0; y < len(sd); y++ {
		for x := 0; x < len(sd[y]); x++ {
			if sd[y][x].value == 0 {
				if len(sd[y][x].options) < lowest {
					lX, lY = x, y
					lowest = len(sd[y][x].options)
				}
			}
		}
	}
	return lX, lY
}

func copyField(sd Sudoku, y, x int) Field {
	return Field{
		sd[y][x].value,
		sd[y][x].pregiven,
		sd[y][x].options,
	}
}

func copySudoku(sd Sudoku) Sudoku {
	field := newField()
	for y := 0; y < len(sd); y++ {
		for x := 0; x < len(sd[y]); x++ {
			field[y][x] = copyField(sd, y, x)
		}
	}

	return field
}

func SolveSudoku(sd Sudoku) Sudoku {

	for {
		// First step: For every non-full field, create all options
		mod := false

		for y := 0; y < len(sd); y++ {
			for x := 0; x < len(sd[y]); x++ {
				if sd[y][x].value == 0 {
					options := createOptions(sd, x, y)
					if len(options) == 0 {
						return nil
					} else if len(options) == 1 {
						sd[y][x].value = options[0]
						mod = true
					} else {
						sd[y][x].options = options
					}

				}
			}
		}

		if !mod {
			break
		}
	}

	if isDone(sd) {
		return sd
	}

	// For every possible option for the field: Try it!
	lX, lY := fieldWithLowest(sd)
	for _, option := range sd[lY][lX].options {
		newField := copySudoku(sd)
		newField[lY][lX].value = option
		if solField := SolveSudoku(newField); solField != nil {
			return solField
		}
	}

	return nil
}

func printField(sd Sudoku) {
	for i := 0; i < len(sd); i++ {
		for f := 0; f < len(sd[i]); f++ {
			fmt.Print(sd[i][f].value, " ")
		}
		fmt.Print("\n")
	}
	fmt.Print("-------------------------------------------\n")
}

// Takes a string containing all numbers of the sudoku puzzle concatenated together
func SodukuFromString(str string) Sudoku {
	result := newField()
	for i := 0; i < 9*9; i++ {
		num := int(str[i] - '0')
		result[int(math.Floor(float64(i)/9.0))][i%9] = Field{
			num,
			num != 0,
			nil,
		}
	}

	return result
}

func main() {
	field := SodukuFromString("003020600900305001001806400008102900700000008006708200002609500800203009005010300")
	printField(SolveSudoku(field))
}
package main

import (
	"fmt"
	"testing"
)

// 50 sudoku puzzles, 9x9 fields
// first 9 numbers belong to the first row, next 9 to the second row and so on
var input = []string{
	"003020600900305001001806400008102900700000008006708200002609500800203009005010300",
	"200080300060070084030500209000105408000000000402706000301007040720040060004010003",
	"000000907000420180000705026100904000050000040000507009920108000034059000507000000",
	"030050040008010500460000012070502080000603000040109030250000098001020600080060020",
	"020810740700003100090002805009040087400208003160030200302700060005600008076051090",
	"100920000524010000000000070050008102000000000402700090060000000000030945000071006",
	"043080250600000000000001094900004070000608000010200003820500000000000005034090710",
	"480006902002008001900370060840010200003704100001060049020085007700900600609200018",
	"000900002050123400030000160908000000070000090000000205091000050007439020400007000",
	"001900003900700160030005007050000009004302600200000070600100030042007006500006800",
	"000125400008400000420800000030000095060902010510000060000003049000007200001298000",
	"062340750100005600570000040000094800400000006005830000030000091006400007059083260",
	"300000000005009000200504000020000700160000058704310600000890100000067080000005437",
	"630000000000500008005674000000020000003401020000000345000007004080300902947100080",
	"000020040008035000000070602031046970200000000000501203049000730000000010800004000",
	"361025900080960010400000057008000471000603000259000800740000005020018060005470329",
	"050807020600010090702540006070020301504000908103080070900076205060090003080103040",
	"080005000000003457000070809060400903007010500408007020901020000842300000000100080",
	"003502900000040000106000305900251008070408030800763001308000104000020000005104800",
	"000000000009805100051907420290401065000000000140508093026709580005103600000000000",
	"020030090000907000900208005004806500607000208003102900800605007000309000030020050",
	"005000006070009020000500107804150000000803000000092805907006000030400010200000600",
	"040000050001943600009000300600050002103000506800020007005000200002436700030000040",
	"004000000000030002390700080400009001209801307600200008010008053900040000000000800",
	"360020089000361000000000000803000602400603007607000108000000000000418000970030014",
	"500400060009000800640020000000001008208000501700500000000090084003000600060003002",
	"007256400400000005010030060000508000008060200000107000030070090200000004006312700",
	"000000000079050180800000007007306800450708096003502700700000005016030420000000000",
	"030000080009000500007509200700105008020090030900402001004207100002000800070000090",
	"200170603050000100000006079000040700000801000009050000310400000005000060906037002",
	"000000080800701040040020030374000900000030000005000321010060050050802006080000000",
	"000000085000210009960080100500800016000000000890006007009070052300054000480000000",
	"608070502050608070002000300500090006040302050800050003005000200010704090409060701",
	"050010040107000602000905000208030501040070020901080406000401000304000709020060010",
	"053000790009753400100000002090080010000907000080030070500000003007641200061000940",
	"006080300049070250000405000600317004007000800100826009000702000075040190003090600",
	"005080700700204005320000084060105040008000500070803010450000091600508007003010600",
	"000900800128006400070800060800430007500000009600079008090004010003600284001007000",
	"000080000270000054095000810009806400020403060006905100017000620460000038000090000",
	"000602000400050001085010620038206710000000000019407350026040530900020007000809000",
	"000900002050123400030000160908000000070000090000000205091000050007439020400007000",
	"380000000000400785009020300060090000800302009000040070001070500495006000000000092",
	"000158000002060800030000040027030510000000000046080790050000080004070100000325000",
	"010500200900001000002008030500030007008000500600080004040100700000700006003004050",
	"080000040000469000400000007005904600070608030008502100900000005000781000060000010",
	"904200007010000000000706500000800090020904060040002000001607000000000030300005702",
	"000700800006000031040002000024070000010030080000060290000800070860000500002006000",
	"001007090590080001030000080000005800050060020004100000080000030100020079020700400",
	"000003017015009008060000000100007000009000200000500004000000020500600340340200000",
	"300200000000107000706030500070009080900020004010800050009040301000702000000008006",
}

func printFieldTest(t *testing.T, sd Sudoku) {
	for i := 0; i < len(sd); i++ {
		str := ""
		for f := 0; f < len(sd[i]); f++ {
			str += " " + fmt.Sprintf("%v", sd[i][f].value)
		}
		t.Log(str + "\n")
	}
	t.Log("-------------------------------------------\n")
}

func validateSudoku(sod Sudoku) bool {
	return true
}

func TestSolve(t *testing.T) {
	for _, str := range input {
		field := SodukuFromString(str)
		if sod := SolveSudoku(field); len(sod) != 9 {
			printFieldTest(t, field)
			t.Fatal("Failed to solve puzzle")
		}
	}
}