Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Sudoku Solver
Build a simple backtracking Sudoku solver.

Pull request description:
Sudoku
Resolves #47.

Patch:
diff --git a/README.md b/README.md
index c296b22..61edbc3 100644
--- a/README.md
+++ b/README.md
@@ -32,3 +32,4 @@ problems from
 * [Day 19](https://github.com/vaskoz/dailycodingproblem-go/issues/41)
 * [Day 19 N-Queens](https://github.com/vaskoz/dailycodingproblem-go/issues/43)
 * [Day 19 Flight Itinerary](https://github.com/vaskoz/dailycodingproblem-go/issues/45)
+* [Day 19 Sudoku Solver](https://github.com/vaskoz/dailycodingproblem-go/issues/47)
diff --git a/sudoku/problem.go b/sudoku/problem.go
new file mode 100644
index 0000000..c8b13c2
--- /dev/null
+++ b/sudoku/problem.go
@@ -0,0 +1,48 @@
+package sudoku
+
+// Board is a 1-D array of size n^2 x n^2. You need 'n' to know how to read it properly.
+type Board []int
+
+// Solver returns a solved Sudoku puzzle of size n^2 x n^2.
+func Solver(board Board, n int) (Board, bool) {
+	row, col, complete := findEmpty(board, n)
+	if complete {
+		return board, complete
+	}
+	for choice := 1; choice <= n*n; choice++ {
+		isValid := true
+		gridrow, gridcol := row/n, col/n
+		for r := n * gridrow; r < n*gridrow+n; r++ {
+			for c := n * gridcol; c < n*gridcol+n; c++ {
+				if board[r*n*n+c] == choice {
+					isValid = false
+				}
+			}
+		}
+		for j := 0; j < n*n; j++ {
+			if board[n*n*j+col] == choice || board[row*n*n+j] == choice {
+				isValid = false
+				break
+			}
+		}
+		if isValid {
+			board[row*n*n+col] = choice
+			var solved bool
+			board, solved = Solver(board, n)
+			if solved {
+				return board, solved
+			}
+			board[row*n*n+col] = 0
+		}
+	}
+	return board, false
+}
+
+func findEmpty(board Board, n int) (int, int, bool) {
+	for i, box := range board {
+		if box == 0 {
+			return i / (n * n), i % (n * n), false
+		}
+	}
+	return 0, 0, true
+}


Test patch:
diff --git a/sudoku/problem_test.go b/sudoku/problem_test.go
new file mode 100644
index 0000000..01ddc9b
--- /dev/null
+++ b/sudoku/problem_test.go
@@ -0,0 +1,48 @@
+package sudoku
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	board    Board
+	n        int
+	expected Board
+}{
+	{Board{4, 0, 0, 0, 0, 0, 0, 0, 5,
+		0, 0, 9, 4, 0, 2, 8, 0, 0,
+		0, 6, 0, 0, 5, 0, 0, 9, 0,
+		0, 3, 0, 0, 8, 0, 0, 2, 0,
+		0, 0, 2, 5, 0, 1, 3, 0, 0,
+		0, 9, 0, 0, 4, 0, 0, 7, 0,
+		0, 1, 0, 0, 6, 0, 0, 5, 0,
+		0, 0, 8, 1, 0, 5, 9, 0, 0,
+		5, 0, 0, 0, 0, 0, 0, 0, 7},
+		3,
+		Board{4, 8, 7, 6, 1, 9, 2, 3, 5,
+			3, 5, 9, 4, 7, 2, 8, 1, 6,
+			2, 6, 1, 3, 5, 8, 7, 9, 4,
+			1, 3, 4, 7, 8, 6, 5, 2, 9,
+			6, 7, 2, 5, 9, 1, 3, 4, 8,
+			8, 9, 5, 2, 4, 3, 6, 7, 1,
+			9, 1, 3, 8, 6, 7, 4, 5, 2,
+			7, 4, 8, 1, 2, 5, 9, 6, 3,
+			5, 2, 6, 9, 3, 4, 1, 8, 7}},
+}
+
+func TestSolver(t *testing.T) {
+	for _, tc := range testcases {
+		if result, _ := Solver(tc.board, tc.n); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v but got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSolver(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			Solver(tc.board, tc.n)
+		}
+	}
+}