use pubs
set nocount on
SET ANSI_WARNINGS off
if exists (select 1 from sysobjects where name = 'sudoku_table' and xtype = 'U') drop table sudoku_table
if exists (select 1 from sysobjects where name = 'onetonine' and xtype = 'U') drop table onetonine
if exists (select 1 from sysobjects where name = 'temptable' and xtype = 'U') drop table temptable
if exists (select * from sysobjects where name = 'printSudokuGrid' and xtype = 'P') drop procedure printSudokuGrid
if exists (select 1 from sysobjects where name = 'updateSudokuGrid' and xtype = 'P') drop procedure updateSudokuGrid
if exists (select 1 from sysobjects where name = 'loadSudokuGrid' and xtype = 'P') drop procedure loadSudokuGrid
if exists (select 1 from sysobjects where name = 'isFilled' and xtype = 'FN') drop function isFilled
if exists (select 1 from sysobjects where name = 'hasError' and xtype = 'FN') drop function hasError
/*****************/
/* create tables */
/*****************/
create table sudoku_table (
	ix int primary key,
	row int,
	col int,
	squ int,
	value int
)

create table temptable (
	ix int,
	row int,
	col int,
	squ int,
	value int
)

select 1 value into onetonine
insert into onetonine values (2)
insert into onetonine values (3)
insert into onetonine values (4)
insert into onetonine values (5)
insert into onetonine values (6)
insert into onetonine values (7)
insert into onetonine values (8)
insert into onetonine values (9)

-- put 81 squares into the table
-- each 3x3 square is computed and labeled based on the values of the row and column
insert into sudoku_table 
select (a.value - 1) * 9 + b.value, 
       a.value,
       b.value,
       ((a.value - 1)/3)*3+((b.value - 1)/3)+1,
       null
from onetonine a
cross join onetonine b
GO


/*************************/
/* Create the procedures */
/*************************/

-- loadSudokuGrid takes a string containing 81 numbers and 
-- populates sudoku_grid accordingly
create procedure loadSudokuGrid (@tableString nvarchar(1000))
AS
BEGIN
    declare @i int
    set @i = 1
    while @i <= 81
    begin
        update sudoku_table
        set value = cast (substring(@tableString, @i, 1) as int)
        where ix = @i
        set @i = @i + 1
    end

    update sudoku_table
    set value = null
    where value = 0

    delete temptable

    insert into temptable
    select st.ix, st.row, st.col, st.squ, zte.value
    from sudoku_table st
    cross join onetonine zte
    where st.value is null

END
GO

-- updateSudokuGrid fills numbers into the grid only 
-- when it can determine the value uniquely. 
-- I always use these rules of thumb when solving Sudoku: 
-- 1. If two squares in a group (col, row or 3x3 square) have only two choices
--    Then no other square in that group can take on those choices
-- 2. For a given number within a row remove choices from a block where that number is 
--    already guaranteed for another block (do same for columns)
-- 3. In a given row, and a given number find the only square left
--    to place that number. Do the same for columns and 3x3 squares.
-- 4. For a given square, find the single valid number that doesn't 
--    conflict with existing numbers in the same row, column or 3x3 square. 
-- The rules of thumb might overlap, but it doesn't matter
create procedure updateSudokuGrid
AS
BEGIN

-- clear the temptable of extra digits
delete temptable
from temptable tt
join sudoku_table st on st.ix = tt.ix
where st.value is not null

-- remove choices that conflict with existing numbers on the same row
delete temptable
from temptable tt
join sudoku_table st on tt.row = st.row and tt.value = st.value

-- remove choices that conflict with existing numbers in the same column
delete temptable
from temptable tt
join sudoku_table st on tt.col = st.col and tt.value = st.value

-- remove choices that conflict with existing numbers in the same 3x3 square
delete temptable
from temptable tt
join sudoku_table st on tt.squ = st.squ and tt.value = st.value

-- First Step: If there are only two choices for two squares in a given group. 
-- The other squares do not have that choice. First create list of 
-- two choices:

declare @twoChoices table (
	row int,
	col int, 
	squ int,
	ix int,
	max int,
	min int)

insert into @twoChoices
select row, col, squ, ix, max(value) as max, min(value) as min
from temptable
group by row, col, squ, ix
having count(1) = 2
order by max(value), min(value)

-- remove from same rows:
delete temptable
from temptable tt
join (select row, max(ix) maxix, min(ix) minix, max, min 
      from @twoChoices 
      group by row, max, min
      having count(1) = 2) tc on tt.row = tc.row
where tt.value in (tc.max, tc.min)
and   not tt.ix in (maxix, minix)

--remove from same cols:
delete temptable
from temptable tt
join (select col, max(ix) maxix, min(ix) minix, max, min 
      from @twoChoices 
      group by col, max, min
      having count(1) = 2) tc on tt.col = tc.col
where tt.value in (tc.max, tc.min)
and   not tt.ix in (minix, maxix)

--remove from same 3x3 square:
delete temptable
from temptable tt
join (select squ, max(ix) maxix, min(ix) minix, max, min 
      from @twoChoices 
      group by squ, max, min
      having count(1) = 2) tc on tt.squ = tc.squ
where tt.value in (tc.max, tc.min)
and   not tt.ix in (minix, maxix)

-- Second Step:
-- For a given number within a row, delete choices where that number 
-- is guaranteed for another block. (same with columns)
delete temptable
from temptable tt
join 
    (select max(row) as row, squ, value
     from (select row, squ, value, count(1) as count
           from temptable
           group by row, squ, value) innerA
     group by squ, value
     having count(1) = 1)innerB 
on tt.row = innerB.row
and tt.value = innerB.value
and tt.squ <> innerB.squ

delete temptable
from temptable tt
join 
    (select max(col) as col, squ, value
     from (select col, squ, value, count(1) as count
           from temptable
           group by col, squ, value) innerA
     group by squ, value
     having count(1) = 1)innerB 
on tt.col = innerB.col
and tt.value = innerB.value
and tt.squ <> innerB.squ

-- Third Step: In a given row, and a given number, find the only square left
--             to place that number. Do the same for columns and 3x3 squares.

-- If there is only one square left for a given 3x3 square and number, fill it.
update sudoku_table 
set    value = tt.value
from   (select max(row) row, max(col) col, value from temptable tt group by squ, value having count(1) = 1) tt
where  sudoku_table.row = tt.row and sudoku_table.col = tt.col

-- If there is only one square left for a given row and number, fill it.
update sudoku_table 
set    value = tt.value
from   (select row, max(col) col, value from temptable tt group by row, value having count(1) = 1) tt
where  sudoku_table.row = tt.row and sudoku_table.col = tt.col

-- If there is only one square left for a given column and number, fill it.
update sudoku_table 
set    value = tt.value
from   (select max(row) row, col, value from temptable tt group by col, value having count(1) = 1) tt
where  sudoku_table.row = tt.row and sudoku_table.col = tt.col

-- Fourth Step: For a given square, find the single valid number that doesn't 
--    conflict with existing numbers in the same row, column or 3x3 square.

-- find the squares where there only is one choice left 
update sudoku_table 
set    value = tt.value
from   (select row, col, max(value) value
        from temptable
        group by row, col
        having count(1) = 1) tt
where  sudoku_table.row = tt.row and sudoku_table.col = tt.col

-- clear the temptable (again) of extra digits
delete temptable
from temptable tt
join sudoku_table st on st.ix = tt.ix
where st.value is not null

END
GO

-- printSudokuGrid prints out the known values for 
create procedure printSudokuGrid
AS
BEGIN
select 
isnull(max(case when col = 1 then cast(value as char(1)) else null end), '.') as [1],
isnull(max(case when col = 2 then cast(value as char(1)) else null end), '.') as [2],
isnull(max(case when col = 3 then cast(value as char(1)) else null end), '.') as [3],
isnull(max(case when col = 4 then cast(value as char(1)) else null end), '.') as [4],
isnull(max(case when col = 5 then cast(value as char(1)) else null end), '.') as [5],
isnull(max(case when col = 6 then cast(value as char(1)) else null end), '.') as [6],
isnull(max(case when col = 7 then cast(value as char(1)) else null end), '.') as [7],
isnull(max(case when col = 8 then cast(value as char(1)) else null end), '.') as [8],
isnull(max(case when col = 9 then cast(value as char(1)) else null end), '.') as [9]
from sudoku_table
group by row
order by row asc
END
GO

-- is it filled
create function isFilled() returns bit as
begin
    if exists(select 1 from sudoku_table where value is null)
        return 0

    return 1
end
go

-- is there an error?
create function hasError() returns bit as
begin
    if exists(select 1 from sudoku_table where value is not null group by row, value having count(1) > 1)
        return 1

    if exists(select 1 from sudoku_table where value is not null group by col, value having count(1) > 1)
        return 1

    if exists(select 1 from sudoku_table where value is not null group by squ, value having count(1) > 1)
        return 1

    if exists(select * from sudoku_table st where value is null and ix not in (select ix from temptable))
	return 1

    return 0
end
go

/**********************************************/
/* Populate the grid,                         */
/* which sudoku puzzle are we going to solve? */
/**********************************************/

-- Tough puzzles:
--exec loadSudokuGrid N'000946010910000200084200000803000000490000053000000601000007820007000045040562000'
--exec loadSudokuGrid N'001500000006000007000090040005000100900040008003000600020070000800000700000003500'
--exec loadSudokuGrid N'000000040080030900005601000076000020000090000040000850000705300002080001090000000'
--exec loadSudokuGrid N'070010090900800007003000006040001500030000010002700060500000600600005002080020070'
--exec loadSudokuGrid N'902507000000000009003006705308002000500103002000600308701200600600000000000908107'
--exec loadSudokuGrid N'017000000000000008800060020901007000200000005000300406050090004600000000000000310'
--exec loadSudokuGrid N'000009001003000000046050000000205008005040600700601000000060390000000400200800000'
exec loadSudokuGrid N'049503000000000600010002030020030400700208006003070080070300020005000000000401870'
--seventeen hints:
--exec loadSudokuGrid N'000000010400000000020000000000050407008000300001090000300400200050100000000806000'
exec printSudokuGrid

/**********/
/* Solve: */
/**********/
begin tran
declare @savecount int
set @savecount = 0

Solve:
print 'Solve'
declare @gridSum int,@newGridSum int
declare @hasError bit,@isFilled bit
declare @save varchar(10)
select @gridSum = -1, @newGridSum = sum(value) from temptable
select @hasError = dbo.hasError(), @isFilled = dbo.isFilled()

while @hasError = 0 and @isFilled = 0 and @newGridSum <> @gridSum
begin
    print 'Update'
    exec updateSudokuGrid
    exec printSudokuGrid

    select @gridSum = @newGridSum
    select @newGridSum = sum(value), @hasError = dbo.hasError(), 
        @isFilled = dbo.isFilled()
    from temptable
end

if dbo.hasError() = 1 goto Error
else if dbo.isFilled() = 1 goto Finally
else goto Stuck

/***********/
/* Stuck?: */
/***********/
Stuck:
-- can't solve? time to play what if.
set @save = 'save' + cast(@savecount + 1 as varchar(5))
print 'Stuck, nesting level ' + cast(@savecount as varchar(5))
print 'save point ' + @save
save tran @save
set @savecount = @savecount + 1

delete temptable
from temptable tt
join (select top 1 ix, max(value) as value from temptable group by ix having count(1) = 2 order by ix) innertt
on innertt.ix = tt.ix and innertt.value = tt.value

goto Solve

/***********/
/* Error?: */
/***********/
Error:
-- else if error
set @save = + 'save' + cast(@savecount as varchar(5))
print 'Error, nesting level ' + cast(@savecount as varchar(5)) 
print 'rolling back to savepoint ' + @save
rollback tran @save
set @savecount = @savecount - 1

delete temptable
from temptable tt
join (select top 1 ix, min(value) as value from temptable group by ix having count(1) = 2 order by ix) innertt
on innertt.ix = tt.ix and innertt.value = tt.value

goto Solve

/************/
/* Finally: */
/************/
Finally:
print 'Solved!'
while @@trancount > 0
    commit tran

exec printSudokuGrid