Sudoku checker

Sudoku checker

March 20, 2023

Moch Lutfi
Name
Moch Lutfi
Twitter
@kaptenupi

Problem

Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with numbers in such a way that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid all contain all of the numbers from 1 to 9 one time.

Implement an algorithm that will check whether the given grid of numbers represents a valid Sudoku puzzle according to the layout rules described above. Note that the puzzle represented by grid does not have to be solvable.

Example

  • For


    grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'],
    ['.', '.', '6', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '1', '.', '.', '.', '.', '.', '.'],
    ['.', '6', '7', '.', '.', '.', '.', '.', '9'],
    ['.', '.', '.', '.', '.', '.', '8', '1', '.'],
    ['.', '3', '.', '.', '.', '.', '.', '.', '6'],
    ['.', '.', '.', '.', '.', '7', '.', '.', '.'],
    ['.', '.', '.', '5', '.', '.', '.', '7', '.']]

    the output should be solution(grid) = true;

  • For


    grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'],
    ['.', '.', '.', '.', '6', '.', '.', '.', '.'],
    ['7', '1', '.', '.', '7', '5', '.', '.', '.'],
    ['.', '7', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '8', '3', '.', '.', '.'],
    ['.', '.', '8', '.', '.', '7', '.', '6', '.'],
    ['.', '.', '.', '.', '.', '2', '.', '.', '.'],
    ['.', '1', '.', '2', '.', '.', '.', '.', '.'],
    ['.', '2', '.', '.', '3', '.', '.', '.', '.']]

    the output should be solution(grid) = false.

    The given grid is not correct because there are two 1s in the second column. Each column, each row, and each 3 × 3 subgrid can only contain the numbers 1 through 9 one time.

Solution

Before solving the problem we must find out how to check the valid condition of sudoku board.

  • No duplicate number in same row and column
  • No duplicate number in 3x3 subgrid

Which data structure to check the duplicate number? Yes we can use map ( Don't forget with Dora The explorer vibes lol).

Here the step by step solution:

  • Create map map[string]bool to store checker and prepare template string
  • Iterate through all grid, continue if the grid contains dot if not empty add current value to map in row, column, and subgrid.
  • If same number occurred in one of row, column and subgrid return false, otherwise continue until finish then return true.

package main
import (
"fmt"
"testing"
)
func solution(grid [][]string) bool {
n := len(grid)
set := make(map[string]bool)
const (
templateRow = "%s in row %d"
templateCol = "%s in col %d"
templateSubgrid = "%s in square %d %d"
)
for row := 0; row < n; row++ {
for col := 0; col < n; col++ {
if grid[row][col] == "." {
continue
}
if !set[fmt.Sprintf(templateRow, grid[row][col], row)] {
set[fmt.Sprintf(templateRow, grid[row][col], row)] = true
} else {
return false
}
if !set[fmt.Sprintf(templateCol, grid[row][col], col)] {
set[fmt.Sprintf(templateCol, grid[row][col], col)] = true
} else {
return false
}
if !set[fmt.Sprintf(templateSubgrid, grid[row][col], row/3, col/3)] {
set[fmt.Sprintf(templateSubgrid, grid[row][col], row/3, col/3)] = true
} else {
return false
}
}
}
return true
}
func TestSudoku(t *testing.T) {
tests := []struct {
grid [][]string
want bool
}{
{
grid: [][]string{
{".", ".", ".", ".", "2", ".", ".", "9", "."},
{".", ".", ".", ".", "6", ".", ".", ".", "."},
{"7", "1", ".", ".", "7", "5", ".", ".", "."},
{".", "7", ".", ".", ".", ".", ".", ".", "."},
{".", ".", ".", ".", "8", "3", ".", ".", "."},
{".", ".", "8", ".", ".", "7", ".", "6", "."},
{".", ".", ".", ".", ".", "2", ".", ".", "."},
{".", "1", ".", "2", ".", ".", ".", ".", "."},
{".", "2", ".", ".", "3", ".", ".", ".", "."},
},
want: false,
},
{
grid: [][]string{
{".", ".", ".", ".", ".", ".", ".", ".", "."},
{".", ".", "2", ".", ".", ".", ".", ".", "."},
{".", ".", ".", ".", ".", "2", "7", "1", "."},
{".", ".", ".", ".", ".", ".", ".", ".", "."},
{".", "2", ".", ".", ".", ".", ".", ".", "."},
{".", "5", ".", ".", ".", ".", ".", ".", "."},
{".", ".", ".", ".", "9", ".", ".", ".", "8"},
{".", ".", ".", ".", ".", "1", "6", ".", "."},
{".", ".", ".", ".", "6", ".", ".", ".", "."}},
want: true,
},
}
for _, tt := range tests {
if got := solution(tt.grid); got != tt.want {
t.Errorf("Sudoku(%v) = %v, want %v", tt.grid, got, tt.want)
}
}
}

Try it yourself https://go.dev/play/p/5fwka6bk1vv?v=gotip (opens in a new tab)