Repository: Kaamkiya/gg (language: go)

Issue:
feat: Sudoku
**Is your feature request related to a problem? Please describe.**
No.

**Describe the solution you'd like**
A Sudoku game.

**Describe alternatives you've considered**
None.

**Additional context**
See [Geeks for Geeks](https://www.geeksforgeeks.org/program-sudoku-generator/) for an algorithm, if needed.


Discussion / hints:

Fix patch:
diff --git a/cmd/gg/main.go b/cmd/gg/main.go
index 5ac09f5..c1ff63a 100644
--- a/cmd/gg/main.go
+++ b/cmd/gg/main.go
@@ -9,6 +9,7 @@ import (
 	"github.com/Kaamkiya/gg/internal/app/maze"
 	"github.com/Kaamkiya/gg/internal/app/pong"
 	"github.com/Kaamkiya/gg/internal/app/snake"
+	"github.com/Kaamkiya/gg/internal/app/sudoku"
 	"github.com/Kaamkiya/gg/internal/app/tictactoe"
 	"github.com/Kaamkiya/gg/internal/app/twenty48"
 
@@ -24,6 +25,7 @@ func main() {
 		Title("choose a game:").
 		Options(
 			huh.NewOption("2048", "twenty48"),
+			huh.NewOption("sudoku", "sudoku"),
 			huh.NewOption("dodger", "dodger"),
 			huh.NewOption("maze", "maze"),
 			huh.NewOption("hangman", "hangman"),
@@ -59,6 +61,8 @@ func main() {
 		connect4.Run()
 	case "snake":
 		snake.Run()
+	case "sudoku":
+		sudoku.Run()
 	default:
 		panic("This game either doesn't exist or hasn't been implemented.")
 	}
diff --git a/internal/app/sudoku/sudoku.go b/internal/app/sudoku/sudoku.go
new file mode 100644
index 0000000..8ac4c8d
--- /dev/null
+++ b/internal/app/sudoku/sudoku.go
@@ -0,0 +1,127 @@
+package sudoku
+
+import (
+	"fmt"
+	"strconv"
+
+	"github.com/Kaamkiya/gg/internal/app/sudoku/sudokugenerator"
+
+	tea "github.com/charmbracelet/bubbletea"
+	"github.com/charmbracelet/lipgloss"
+)
+
+type model struct {
+	origGrid [][]int
+	grid     [][]int
+
+	cursorx int
+	cursory int
+}
+
+func (m model) Init() tea.Cmd {
+	return nil
+}
+
+func (m model) Update(msg tea.Msg) (tea.Model, tea.Cmd) {
+	switch msg := msg.(type) {
+	case tea.KeyMsg:
+		switch msg.String() {
+		case "q", "ctrl+c":
+			return m, tea.Quit
+		case "up", "k":
+			if m.cursory > 0 {
+				m.cursory--
+			}
+		case "down", "j":
+			if m.cursory < 8 {
+				m.cursory++
+			}
+		case "left", "h":
+			if m.cursorx > 0 {
+				m.cursorx--
+			}
+		case "right", "l":
+			if m.cursorx < 8 {
+				m.cursorx++
+			}
+		case "1", "2", "3", "4", "5", "6", "7", "8", "9", "0":
+			m.setSquare(msg.String())
+		}
+	}
+
+	return m, nil
+}
+
+func (m model) View() string {
+	s := ""
+
+	for i, r := range m.grid {
+		for j, c := range r {
+			if j%3 == 0 && j != 0 {
+				s += " | "
+			}
+
+			if j == m.cursorx && i == m.cursory {
+				col := lipgloss.NewStyle().Background(lipgloss.Color("#0000ff")).Render
+				if c == 0 {
+					s += col(" . ")
+				} else {
+					s += col(fmt.Sprintf(" %d ", c))
+				}
+			} else {
+				if c == 0 {
+					s += " . "
+				} else {
+					s += fmt.Sprintf(" %d ", c)
+				}
+			}
+		}
+
+		s += "\n"
+
+		if i == 2 || i == 5 {
+			s += "--------------------------------\n"
+		}
+	}
+
+	s += fmt.Sprintf("\n\norig: %v\n\ncurr: %v", m.origGrid, m.grid)
+
+	return s
+}
+
+func (m *model) setSquare(button string) {
+	if m.origGrid[m.cursory][m.cursorx] == 0 {
+		m.grid[m.cursory][m.cursorx], _ = strconv.Atoi(button)
+	}
+}
+
+func initialModel() tea.Model {
+	g := sudokugenerator.Model{}
+	g.Init()
+
+	grid := make([][]int, 9)
+	orig := make([][]int, 9)
+
+	for i := range 9 {
+		grid[i] = make([]int, 9)
+		orig[i] = make([]int, 9)
+
+		for j := range 9 {
+			grid[i][j] = g.Grid[j][i]
+			orig[i][j] = g.Grid[j][i]
+		}
+	}
+
+	return model{
+		grid:     grid,
+		origGrid: orig,
+	}
+}
+
+func Run() {
+	p := tea.NewProgram(initialModel())
+
+	if _, err := p.Run(); err != nil {
+		panic(err)
+	}
+}
diff --git a/internal/app/sudoku/sudokugenerator/generator.go b/internal/app/sudoku/sudokugenerator/generator.go
new file mode 100644
index 0000000..72b1618
--- /dev/null
+++ b/internal/app/sudoku/sudokugenerator/generator.go
@@ -0,0 +1,109 @@
+package sudokugenerator
+
+import (
+	"math/rand/v2"
+	"slices"
+)
+
+type Model struct {
+	Grid [][]int
+}
+
+func (m *Model) unusedInBox(row, col, n int) bool {
+	for i := range 3 {
+		for j := range 3 {
+			if m.Grid[row+i][col+j] == n {
+				return false
+			}
+		}
+	}
+
+	return true
+}
+
+func (m *Model) fillBox(row, col int) {
+	var n int
+	for i := range 3 {
+		for j := range 3 {
+			for !m.unusedInBox(row, col, n) {
+				n = rand.IntN(9) + 1
+			}
+			m.Grid[row+i][col+j] = n
+		}
+	}
+}
+
+func (m *Model) unusedInCol(col, n int) bool {
+	for j := range 9 {
+		if m.Grid[j][col] == n {
+			return false
+		}
+	}
+
+	return true
+}
+
+func (m *Model) unusedInRow(row, n int) bool {
+	return !slices.Contains(m.Grid[row], n)
+}
+
+func (m *Model) isSafe(row, col, n int) bool {
+	return m.unusedInBox(row-row%3, col-col%3, n) && m.unusedInCol(col, n) && m.unusedInRow(row, n)
+}
+
+func (m *Model) fillRemaining(row, col int) bool {
+	if row == 9 {
+		return true
+	}
+
+	if col == 9 {
+		return m.fillRemaining(row+1, 0)
+	}
+
+	if m.Grid[row][col] != 0 {
+		return m.fillRemaining(row, col+1)
+	}
+
+	for n := 1; n < 10; n++ {
+		if m.isSafe(row, col, n) {
+			m.Grid[row][col] = n
+			if m.fillRemaining(row, col+1) {
+				return true
+			}
+			m.Grid[row][col] = 0
+		}
+	}
+
+	return false
+}
+
+func (m *Model) emptyCells(amount int) {
+	for amount > 0 {
+		id := rand.IntN(81)
+		i := id / 9
+		j := id % 9
+
+		if m.Grid[i][j] != 0 {
+			m.Grid[i][j] = 0
+			amount--
+		}
+	}
+}
+
+func (m *Model) generate() {
+	for i := 0; i < 9; i += 3 {
+		m.fillBox(i, i)
+	}
+
+	m.fillRemaining(0, 0)
+}
+
+func (m *Model) Init() {
+	m.Grid = make([][]int, 9)
+	for i := range m.Grid {
+		m.Grid[i] = make([]int, 9)
+	}
+
+	m.generate()
+	m.emptyCells(54)
+}


Test patch:
diff --git a/internal/app/sudoku/sudokugenerator/generator_test.go b/internal/app/sudoku/sudokugenerator/generator_test.go
new file mode 100644
index 0000000..42fb642
--- /dev/null
+++ b/internal/app/sudoku/sudokugenerator/generator_test.go
@@ -0,0 +1,36 @@
+package sudokugenerator
+
+import "testing"
+
+func TestGen(t *testing.T) {
+	m := Model{}
+	m.Init()
+
+	m.grid = make([][]int, 9)
+	for i := range m.grid {
+		m.grid[i] = make([]int, 9)
+	}
+	m.generate()
+
+	for r, row := range m.grid {
+		for c, cell := range row {
+			if !m.unusedInBox(r-r%3, c-c%3, cell) || !m.unusedInCol(c, cell) || !m.unusedInRow(r, cell) {
+				t.Fatalf("Invalid Sudoku generated: %d overlaps", cell)
+			}
+		}
+	}
+
+	m.emptyCells(20)
+	c := 0
+	for _, r := range m.grid {
+		for _, n := range r {
+			if n == 0 {
+				c++
+			}
+		}
+	}
+
+	if c != 20 {
+		t.Fatalf("Not enough empty cells: wanted=20 got=%d", c)
+	}
+}