/* By Peter Klein and Bryan Watts"
/*
    Implements a concurrent Sudoku solver.

    A full Sudoku grid is called a board.  Each small square that may
    contain a single number is called a cell.  We refer to the number of
    cells along one side of the board as its size.  For a board of size
    n, it's divided into n n matrices of size sqrt(n).

    A board is valid if none of its rows, columns, or matrices contain
    duplicate values.  Cells in a valid board may, however, be blank.

    A board is solved if it is valid and has no blanks.

    by Curtis Clifton
    Oct 29, 2010
*/
package sudoku

import "fmt"

// Size is the number of cells across the full Sudoku board.
const (
    // implementation of parsing and display don't handle Size > 3
    RootOfSize = 3
    Size = RootOfSize * RootOfSize
)

// repeat constructs a string by concatenating count instances of the string s.
func repeat(s string, count int) string {
    r := ""
    for i:=0; i<count ; i++ {
        r += s
    }
    return r
}

// Punctuation is used to divide a board into matrices for printing.
var (
    verticalLine = "|"
    horizontalLine = repeat("-", Size + RootOfSize - 1)  + "\n"
)

// -----------------------------------------------------------------------------

// BitSet is an efficient set representation.  Valid set elements are integers
// between 1 and 16 inclusively.
type BitSet uint16

// Add adds the given value to the set, returning true if the value was not
// already in the set.
func (s *BitSet) Add(v int) (wasNew bool) {
    var mask uint16 = 1 << uint16(v-1)
    var ptr *uint16 = (*uint16)(s)
    if *ptr & mask != 0 {
    return false
    }
    *ptr |= mask
    return true
}

// Clear empties the given set.
func (s *BitSet) Clear() {
    *s = 0
}

// Remove removes the given value from the set.
func (s *BitSet) Remove(v int) {
    var mask uint16 = 1 << uint16(v-1)
    var ptr *uint16 = (*uint16)(s)
    *ptr &^= mask
}

// Contain checks whether the given value is in the set.
func (s *BitSet) Contains(v int) bool {
    var mask uint16 = 1 << uint16(v-1)
    var ptr *uint16 = (*uint16)(s)
    return *ptr & mask != 0
}

func (s *BitSet) String() string {
    r := "{ "
    v := uint16(*s)
    for i:= 1; i <= Size; i, v = i + 1, v >> 1 {
        if uint16(1) & v != 0 {
            r += fmt.Sprint(i, " ")
        }
    }
    r += "}"
    return r
}

// -----------------------------------------------------------------------------

// Board represents a Sudoku board.
type Board struct {
    backingSlice []int
}

// index converts row and column values--zero-based--into an index into a
// board's backingSlice.
func index(r, c int) int {
    return r * Size + c
}

// coord converts an index into a board's backingSlice into row and
// column values--zero-based.
func coord(index int) (r, c int) {
    c = index % Size
    r = index / Size
    return
}

// Parse takes a string representing a Sudoku board and returns a Board.
// The representation should use digits between 1 and Size, inclusive, to
// indicate filled cells.  Blank cells are indicate by an underscore.  Rows
// in the representation should be separated by newlines.
func Parse(bs string) (b *Board, ok bool)  {
    ok = true
    rep := make([]int, Size*Size)
    next := 0
    for _, v := range bs {
        switch {
            case '0' < v && v <= '0' + Size:
                rep[next] = v - '0'
                next++
            case v == '_':
                rep[next] = 0
                next++
            case v == '\n':
                // ignore
            default:
                ok = false
        }
    }
    return &Board{rep}, ok
}

// EmptyBoard returns a new, empty board where every cell is blank.
func EmptyBoard() *Board {
    return &Board{make([]int, Size*Size)}
}

// Copy makes a deep copy of the board so that the original board and the new
// board have no shared memory.
func (b *Board) Copy() *Board {
    newBack := make([]int, Size*Size)
    copy(newBack, b.backingSlice)
    return &Board{newBack}
}

// at returns the value in the cell at the given row and column.  Zero
// indicates a blank cell.
func (b *Board) at(r, c int) int {
    return b.backingSlice[index(r,c)]
}

// set sets the value for the cell at the given row and column.  Zero
// indicates a blank cell.
func (b *Board) set(r, c, val int) {
    b.backingSlice[index(r,c)] = val
}

// String returns a human-readable representation of the board, with
// punctuation to divide the board into matrices.
func (b *Board) String() string {
    s := ""
    for r := 0; r < Size; r++ {
        if r != 0 && r % RootOfSize == 0 {
            s += horizontalLine
        }
        for c := 0; c < Size; c++ {
            if c != 0 && c % RootOfSize == 0 {
                s += verticalLine
            }
            switch v := b.at(r,c); v {
                case 0:
                    s += " "
                default:
                    s += fmt.Sprint(b.at(r,c))
            }
        }
        if r != Size -1 {
            s += "\n"
        }
    }
    return s
}

// IsFull returns true iff every cell of the board has a value; otherwise,
// it returns the coordinates of the first blank cell in scan-line order.
func (b *Board) IsFull() (full bool, r, c int) {
    for r:= 0; r < Size; r++ {
        for c:= 0; c < Size; c++ {
            if b.at(r,c) == 0{
                return false, r, c
            }
        }
    }
    return true, 0, 0
}

// IsValid returns true iff every row, column, and matrix is free of
// duplicates.  A valid board may contain blanks.
func (b *Board) IsValid() bool {
    for x := 0; x < Size; x++{
        var bsr BitSet// := make([]int,10)
        var bsc BitSet//checkc := make([]int,10)
        var bss BitSet//checks := make([]int,10)
        for y:= 0; y < Size; y++ {
            //Rows
            rv := b.at(x,y)
            if rv > 0{
                if bsr.Contains(rv){//checkr[cr] != 0{
                    return false
                } else {
                    bsr.Add(rv)//checkr[cr] = 1
                }
            }
            //Cols
            cv := b.at(y,x)
            if cv > 0{
                if bsc.Contains(cv) {
                    return false
                } else {
                    bsc.Add(cv)
                }
            }
            //Squares
            sv := b.at(3*(x/3)+(y/3),3*(x%3)+(y%3))
            if sv > 0{
                if bss.Contains(sv) {
                    return false
                } else {
                    bss.Add(sv)
                }
            }
        }

    }
    return true
}

// ValidGuesses calculates what values could be legally placed in the cell at
// the given row and column, based on the rest of that cell's row, column, and
// matrix.
func (b *Board) ValidGuesses(r, c int) BitSet {
    var s BitSet
    for i := 1; i <= Size; i++ {
        s.Add(i)
    }
    for i := 0; i < Size; i++ {
        s.Remove(b.at(r,i))
        s.Remove(b.at(i,c))
        s.Remove(b.at(3*(r/3)+i/3,3*(c/3)+i%3))
    }
    return s
}

// Solve takes a Sudoku board and either solves it or reports that it cannot
// be solved.  This version solves the puzzle with recursion, but not
// using concurrency.
func (b *Board) Solve() (result *Board, success bool) {
    full,r,c := b.IsFull()
    if full {
        return b.Copy(), b.IsValid();
    }
    s := b.ValidGuesses(r,c)
    for i := 1; i <= Size; i++ {
        if s.Contains(i) {
            b.set(r,c,i)
            bs,solved := b.Solve()
            if solved { return bs, solved }
            b.set(r,c,0)
        }
    }
    return EmptyBoard(), false
}

const (
    SOLVED = -1
)


// ConcSolve takes a Sudoku board and either solves it or reports that it cannot
// be solved.  This version solves the puzzle using concurrency.
func (b *Board) ConcSolve() (result *Board, success bool) {
    solution := make(chan *Board,1)
    status := make(chan int)
    b.ConcHelper(solution, status)
    grcount := 1
    for {
        s := <-status
        switch {
            case s > 0:
                grcount += s // Number in channel will be number of processes spawned
                grcount -= 1 // Subtract one since it sends this number when it's done
            case s == SOLVED:
                return <-solution, true
        }
        if grcount == 0 {
            return EmptyBoard(), false
        }
    }
    return EmptyBoard(), false
}

func (b *Board) ConcHelper(solution chan *Board, status chan int) {
    go func() {
        full,r,c := b.IsFull()
        if full {
            if b.IsValid() {
                status <- SOLVED
                solution <- b.Copy()
            } else {
                status <- 0
            }
        } else {
            calls := 0
            s := b.ValidGuesses(r,c)
            for i := 1; i <= Size; i++ {
                if s.Contains(i) {
                    calls += 1
                    b.set(r,c,i)
                    b.Copy().ConcHelper(solution, status)
                    b.set(r,c,0)
                }
            }
            status <- calls
        }
    } ()
}