/* Even now, I can think of no rational explanation for writing this Sudoku puzzle generator other than a bout of insomnia whilst programming too hard on a difficult website. Basically, it just popped out.
Sudoku is a poular number puzzle. The aim of the puzzle is to place numbers from 1 through 9 in each cell of a 9×9 grid made up of 3×3 "regions".
When the puzzle is presented, some of the numbers are shown and others aren't. The shown ones are the "givens");
The person doing the puzzle has to fill in the blanks. Computers are much better at doing this sort of laborious work.
Each row, column, and region must contain only one instance of each number from 1 to 9.
The puzzle was first published in a U.S. puzzle magazine in 1979.
The name Sudoku is a trademark in Japan
This stored procedure makes repeated attempts at a solution. It generally finds a solution 50% of the time, but keeps at it until it finds one. Each one is, hopefully, different.
I get no pleasure from solving Sudoku puzzles but if you do, you can modify the source to blank out some of the numbers once a solution has been reached.
You will notice that you can turn it into a very good Sudoku solving system just my modding the program with the 'Givens' for the puzzle instead of allowing the program to choose them all.
The stored procedure uses a function that produces a random number. This is not allowed, but I do it to makes sure a random number is different in each row of the result.*/
ALTER VIEW vRandomNumber
/*
*/
AS
SELECT RAND() AS RandomNumber
GO
/* here is a little function, passing back an integer
random number which is used to sort the result of a
select statement randomly */
ALTER function ufiRandom
(
@lower INT,
@upper INT
)
RETURNS INT AS
BEGIN
RETURN FLOOR(
(SELECT RandomNumber FROM vRandomNumber)
*(@Upper-@lower+1)+@Lower)
END
GO
/* and here is the Sudoku table generator */
ALTER PROCEDURE spMakeSudokuTable
AS
--generate a table to hold the valid numbers
DECLARE @AcceptableValues TABLE (number INT)
INSERT INTO @acceptableValues SELECT 1
INSERT INTO @acceptableValues SELECT 2
INSERT INTO @acceptableValues SELECT 3
INSERT INTO @acceptableValues SELECT 4
INSERT INTO @acceptableValues SELECT 5
INSERT INTO @acceptableValues SELECT 6
INSERT INTO @acceptableValues SELECT 7
INSERT INTO @acceptableValues SELECT 8
INSERT INTO @acceptableValues SELECT 9
--and a table that represents the board. We have to do
--a pivot table to represent the board in a human way
--later on in the SP
DECLARE @SudokuTable TABLE
(MyID INT IDENTITY(1,1),
Value INT,
[column] INT,
[row] INT,
Region INT)
---and stock it with all the rows, columns and region values
INSERT INTO @SudokuTable (Value, [Column], Row, Region)
SELECT NULL, [column].number,row.number,
(((row.number-1)/3)*3) + (([column].number-1)/3)+1
FROM @AcceptableValues [column] CROSS JOIN @AcceptableValues row
--put in all the possible values for each cell. These get whittled down
--as the board is constructed merely by flagging that they are already used
--in the region
DECLARE @PossibleValues TABLE
(MyID INT IDENTITY(1,1), Value INT, [row] INT,[column] INT,Region INT, used INT
)
INSERT INTO @PossibleValues (value, [row],[column],Region, used)
SELECT number,[column],row,Region,0
FROM @SudokuTable CROSS JOIN @AcceptableValues
DECLARE @RowToSet INT
DECLARE @ColumnToSet INT
DECLARE @RegiontoSet INT
DECLARE @Value INT
--until we get a valid board----
WHILE EXISTS (SELECT 1 FROM @SudokuTable WHERE value IS NULL)
BEGIN
UPDATE @SudokuTable SET value=NULL--clean out any previous work
UPDATE @possibleValues SET used=0
--loop round constructing the board
WHILE EXISTS (SELECT 1 FROM @PossibleValues WHERE used=0)
BEGIN
--are there any squares which have only
--one possible value?
SELECT TOP 1 @ColumnToSet=[column],
@RowToSet=row ,
@RegionToSet=
MAX(Region)
FROM @PossibleValues
WHERE used=0
GROUP BY [column],row
HAVING COUNT(*)=1
IF @@rowcount=0
--find one of the squares with
--the most possibilities
SELECT TOP 1 @ColumnToSet=[column],
@RowToSet=row ,
@RegiontoSet=MAX(Region)
FROM @PossibleValues
WHERE used=0
GROUP BY [column],row
ORDER BY COUNT(*),dbo.ufiRandom(1,20) DESC
--choose one at random
SELECT TOP 1 @value=value FROM @PossibleValues
WHERE [column]=
@ColumnToSet
AND row=@RowToSet AND used=0
ORDER BY dbo.ufiRandom(2,6)
--show that this square has no possibilities left
UPDATE @PossibleValues SET
used=1 WHERE [column]=@ColumnToSet AND row=@RowToSet
--flag its usage in that row
UPDATE @PossibleValues SET
used=
1 WHERE value=@Value AND row=@RowToSet
--flag its usage in that column
UPDATE @PossibleValues SET
used=1 WHERE value=@Value AND [column]=@ColumnToSet
--flag its usage in that Region
UPDATE @PossibleValues SET
used=1 WHERE value=@Value AND Region=@RegionToSet
--and enter it into the table
UPDATE @SudokuTable SET value=@Value
WHERE [column]=@ColumnToSet AND row=@RowToSet
END
END
SELECT
[a]=CONVERT(INT,MAX(CASE WHEN [Column]=1 THEN value ELSE 0 END)),
[b]=CONVERT(INT,MAX(CASE WHEN [Column]=2 THEN value ELSE 0 END)
),
[c]=CONVERT(INT,MAX(CASE WHEN [Column]=3 THEN value ELSE 0 END)),
[d]=CONVERT(INT,MAX(CASE WHEN [Column]=4 THEN value ELSE 0 END)),
[e]=CONVERT(INT,MAX(CASE WHEN [Column]=5 THEN value ELSE 0 END)),
[f]=CONVERT(INT,MAX(CASE WHEN [Column]=6 THEN value ELSE 0 END)),
[g]=CONVERT(INT,MAX(CASE WHEN [Column]=7 THEN value ELSE 0 END)),
[h]=CONVERT(INT,MAX(CASE WHEN [Column]=8 THEN value ELSE 0 END)),
[i]=
CONVERT(INT,MAX(CASE WHEN [Column]=9 THEN value ELSE 0 END))
FROM @SudokuTable GROUP BY row