Courses/CS 460/Fall 2005/Homework/Jeff Bailey/Dec 3

From CSWiki

Contents 1 Sudoku

[edit] Sudoku

The puzzles all come from www.websudoku.com. The comments represent the puzzle numbers so that the solutions can be applied to the real puzzle to confirm success.

I choose to expand my code to enhance readability.

The most annoying aspect of using Finite Sets over Finite Domains is the output conversion.

declare
proc {Sudoku Puzzle Solution}
   % return the intersection of a set and row
   fun {IntersectRow Set RowNum}
      Row I
      FPs = [1 10 19 28 37 46 55 64 73]
   in
      I = {Nth FPs RowNum}
      Row = {FS.var.bounds [I#I+8] [I#I+8]}
      {FS.card Row 9}
      {FS.intersect Set Row} 
   end

   % return the intersection of a set and column
   fun {IntersectColumn Set ColumnNum}
      Column I
      FPs = [1 2 3 4 5 6 7 8 9]
   in
      I = {Nth FPs ColumnNum}
      Column = {FS.var.bounds [I I+9 I+18 I+27 I+36 I+45 I+54 I+63 I+72] [I I+9 I+18 I+27 I+36 I+45 I+54 I+63 I+72]}
      {FS.card Column 9}
      {FS.intersect Set Column}
   end
   
   %return the intersection of a set and box
   fun {IntersectBox Set BoxNum}
      Box I
      FPs = [1 4 7 28 31 34 55 58 61]
   in
      I = {Nth FPs BoxNum}
      Box = {FS.var.bounds [I#I+2 I+9#I+11 I+18#I+20] [I#I+2 I+9#I+11 I+18#I+20]}
      {FS.card Box 9}
      {FS.intersect Set Box}
   end
in
   Solution = {FS.var.list.upperBound 9 [1#81]}
   {ForAll Solution proc {$ N} {FS.card N 9} end}
   
   % givens
   {For 1 81 1
    proc {$ I}
       if {IsDet {Nth Puzzle I}} then
	  {FS.include I {Nth Solution {Nth Puzzle I}}}
       end
    end
   }
   
   % intersections
   {For 1 9 1
    proc {$ I}
       {For 1 9 1
	proc {$ J} Set in
	   Set = {Nth Solution I}
	   {FS.card {IntersectRow Set J} 1}
	   {FS.card {IntersectColumn Set J} 1}
	   {FS.card {IntersectBox Set J} 1}
	end
       }
    end
   }
   
   % disjoints
   {For 1 8 1
    proc {$ I}
       {For I+1 9 1 
	proc {$ J} Set1 Set2 in
	   Set1 = {Nth Solution I}
	   Set2 = {Nth Solution J}
	   {FS.disjoint Set1 Set2}
	end
       }
    end
   }
   
   % distribute
   {FS.distribute naive Solution}
end

% convert sets to row arrays
proc {DisplaySets Sets ?Out}
   Full = {MakeList 81}
   Rows = {MakeList 9}
in
   % convert sets to big array
   {For 1 9 1
    proc {$ I}
       {For 1 81 1
	proc {$ J}
	   if {FS.reified.isIn J {Nth Sets I}} == 1 then
	      {Nth Full J} = I
	   end
	end
       }
    end
   }
   
   % convert big array to rows
   {For 1 9 1
    proc {$ I} StartPos EndPos in
       StartPos = 9*(I-1)+1
       EndPos = StartPos + 8
       {Nth Rows I} = {List.filterInd Full fun {$ Ind E} Ind >= StartPos andthen Ind =< EndPos end}
    end
   }
   
   Out = Rows
end
   
local
   EasyPuzzle
   MediumPuzzle
   HardPuzzle
   EvilPuzzle
in
   % 5,929,267,531
   EasyPuzzle = [_ _ 7 1 6 _ 8 _ 3
		 _ _ _ _ _ 8 _ _ _
		 _ 8 _ 3 9 _ _ 6 _ 
		 5 9 _ 8 _ _ 4 _ 6
		 _ _ 6 9 3 2 1 _ _ 
		 7 _ 2 _ _ 6 _ 8 9
		 _ 3 _ _ 7 9 _ 5 _
		 _ _ _ 2 _ _ _ _ _
		 9 _ 4 _ 5 1 2 _ _]
   
   % 6,253,887,125
   MediumPuzzle = [_ _ _ 1 _ 6 _ _ _
		   _ _ _ _ _ 5 6 _ _
		   _ _ 1 7 2 _ 8 3 _
		   _ 4 _ 2 _ _ 9 _ 5
		   3 5 _ _ _ _ _ 2 7
		   2 _ 9 _ _ 1 _ 4 _
		   _ 9 7 _ 1 8 5 _ _
		   _ _ 2 6 _ _ _ _ _
		   _ _ _ 9 _ 2 _ _ _]
   
   % 9,686,815,620
   HardPuzzle = [_ _ _ 2 5 _ 7 _ _
		 8 _ _ _ _ _ _ _ 2
		 _ _ _ 7 _ _ 1 _ 9
		 _ 2 _ _ _ 4 _ _ 6
		 _ 9 5 _ 6 _ 8 2 _
		 6 _ _ 9 _ _ _ 5 _
		 9 _ 4 _ _ 2 _ _ _
		 3 _ _ _ _ _ _ _ 8
		 _ _ 8 _ 1 6 _ _ _]
   
   % 9,213,828,067
   EvilPuzzle = [_ _ _ _ _ _ 6 _ _
		 8 5 _ _ _ _ _ 1 _
		 6 _ _ 4 8 _ _ _ 2
		 _ 9 _ _ 6 _ 1 _ _
		 _ 7 _ _ _ _ _ 3 _
		 _ _ 6 _ 5 _ _ 7 _
		 9 _ _ _ 2 1 _ _ 5
		 _ 1 _ _ _ _ _ 4 3
		 _ _ 5 _ _ _ _ _ _]
   
   {Browse {SearchOne fun {$} {DisplaySets {Sudoku EasyPuzzle}} end}}
   {Browse {SearchOne fun {$} {DisplaySets {Sudoku MediumPuzzle}} end}}
   {Browse {SearchOne fun {$} {DisplaySets {Sudoku HardPuzzle}} end}}
   {Browse {SearchOne fun {$} {DisplaySets {Sudoku EvilPuzzle}} end}}

   {ExploreOne fun{$} {Sudoku EvilPuzzle} end}     
end