Sudoku.frink

View or download Sudoku.frink in plain text format


// Sudoku solver class.
// The board is a 9x9 array, each element of which is a set which contains
// the possible values for that cell.  The values in each cell are expected
// to be the integers 1 through 9.
//
class Sudoku
{
   var board;

   // Constructor;  creates a board with no items yet set.
   new[] :=
   {
      board = new array[8]
      for row = 0 to 8
      {
         thisrow = board@row = new array[]
         for col = 0 to 8
         {
            thisset = thisrow@col = new set
            for n = 1 to 9
               thisset.put[n]
         }
      }
   }

   // Create a new board from a 2-dimensional array of values, like the
   // following:
   //
   // c=["----19-4-",
   //    "--48--6--",
   //    "75------2",
   //    "-9-1-2--4",
   //    "-----3---",
   //    "5--4-6-3-",
   //    "8------73",
   //    "--6--84--",
   //    "-1-29----"]
   // b = Sudoku.createFromArray[c]
   // b.solve[]
   // b.dump[]
   //
   // Any character other than [1-9] can be used for the "placeholder"
   // character.
   // Note that this will automatically begin to simplify the 
   class createFromArray[array] :=
   {
      b = new Sudoku
      for row=0 to 8
      {
         r = array@row
         for col=0 to 8
         {
            c = substrLen[r, col, 1]
            if c >= "1" and c <= "9"
               b.setNoCheck[row, col, parseInt[c]]
         }
      }
      return b
   }

   // Prints a representation of the current state of the solution.
   dump[] :=
   {
      for row = 0 to 8
      {
         for col = 0 to 8
         {
            dumpCell[board@row@col]
            if col != 8
               print["|"]
         }
         println[]
      }
      println[]
   }

   dumpCell[cell] :=
   {
      for n = 1 to 9
         if cell.contains[n]
            print[n]
         else
            print[" "]
   }

   // Internal set method
   setNoCheck[row, col, value] :=
   {
      x = new set
      x.put[value]
      board@row@col = x

      // Remove all instances of that value from all columns in that row.
      for c = 0 to 8
         if c != col
         {
            len = length[board@row@c]
            if len > 1
            {
               board@row@c.remove[value]
               // If it's the last remaining value, eliminate it.
               if length[board@row@c] == 1
               {
                  for val = board@row@c
                     setNoCheck[row, c, val]
               }
            }
         }

      // Remove all instances of that value from all rows in that column.
      for r = 0 to 8
         if r != row
         {
            len = length[board@r@col]
            if len > 1
            {
               board@r@col.remove[value]
               // If it's the last remaining value, eliminate it.
               if length[board@r@col] == 1
                  for val = board@r@col
                     setNoCheck[r, col, val]
            }
         }

      // Remove all instances of that value from all boxes in that square.
      rowstart = (row div 3) * 3
      colstart = (col div 3) * 3
      for r = rowstart to rowstart + 2
         for c = colstart to colstart + 2
            if !(r==row and c==col)
            {
               len = length[board@r@c]
               if len > 1
               {
                  board@r@c.remove[value]
                  // If it's the last remaining value, eliminate it.
                  if length[board@r@c] == 1
                  {
                     for val = board@r@c
                        setNoCheck[r, c, val]
                  }
               }
            }
            
    }


    // Solve the board.
    solve[verbose=false] :=
    {
       do
       {
          dump[]
          changed = findSingletons[verbose]
       } while (changed)
    }

    
    // Find and remove the singletons.
    // See http://www.eddaardvark.co.uk/sudokusolver.html#Singletons
    findSingletons[verbose] :=
    {
       if (verbose)
          println["Starting findSingletons"]
       changed = false
       count = new array

       // Remove in rows
       for r = 0 to 8
       {
          for c = 0 to 8
             count@c = 0

          row = board@r
          
          // Remove all instances of that value from all columns in that row.
          for c = 0 to 8
          {
             cell = row@c
             if length[cell] > 1 // Exclude already-found values
                for v = cell
                   count@(v-1) = count@(v-1) + 1
          }

          for n = 0 to 8
             if count@n == 1
             {
                println["Singleton found, row=$r, value=" + (n+1)]
                // Find that value
                COL1:
                for c = 0 to 8
                   if (board@r@c).contains[n+1] and length[board@r@c] > 1
                   {
                      if verbose
                         println["Found singleton at [$r, $c], changed to " + n+1]
                      setNoCheck[r,c,n+1]
                      dump[]
                      changed = true
                      break COL1 
                   }
             }
       }

       // Remove in cols
       for c = 0 to 8
       {
          for r = 0 to 8
             count@r = 0
       
          // Remove all instances of that value from all columns in that row.
          for r = 0 to 8
          {
             cell = board@r@c
             if length[cell] > 1 // Exclude already-found values
                for v = cell
                   count@(v-1) = count@(v-1) + 1
          }

          for n = 0 to 8
             if count@n == 1
             {
                println["Singleton found, col=$c, value=" + (n+1)]
                // Find that value
                ROW1:
                for r = 0 to 8
                   if (board@r@c).contains[n+1] and length[board@r@c] > 1
                   {
                      if verbose
                         println["Found singleton at [$r, $c], changed to " + n+1]
                      setNoCheck[r,c,n+1]
                      dump[]
                      changed = true
                      break ROW1
                   }
             }
       }

       // Remove in block
       for rowblock = 0 to 2
          for colblock = 0 to 2
          {
             rowstart = rowblock * 3
             colstart = colblock * 3
             for r = 0 to 8
                count@r = 0

             // Remove all instances of that value from all cells in that
             // block
             for c = colstart to colstart+2
             {
                for r = rowstart to rowstart+2
                {
                   cell = board@r@c
                   if length[cell] > 1 // Exclude already-found values
                      for v = cell
                         count@(v-1) = count@(v-1) + 1
                }
             }

             for n = 0 to 8
                if count@n == 1
             {
                println["Singleton found, block=[$rowblock, $colblock] value=" + (n+1)]
                // Find that value
                BLOCK1:
                for c = colstart to colstart+2
                {
                   for r = rowstart to rowstart+2
                   if (board@r@c).contains[n+1] and length[board@r@c] > 1
                   {
                      if verbose
                         println["Found singleton at [$r, $c], changed to " + n+1]
                      setNoCheck[r,c,n+1]
                      dump[]
                      changed = true
                      break BLOCK1
                   }
                }
             }
          }
       
       return changed
    }
}

a=["1-8--7462",
   "---1--8--",
   "9---2---1",
   "-----4---",
   "6-2-8-3-9",
   "---3-----",
   "8---5---6",
   "--6--2---",
   "5136--7-8"]

b = Sudoku.createFromArray[a]
b.dump[]
b.solve[verbose=true]
b.dump[]

c=["----19-4-",
   "--48--6--",
   "75------2",
   "-9-1-2--4",
   "-----3---",
   "5--4-6-3-",
   "8------73",
   "--6--84--",
   "-1-29----"]
b = Sudoku.createFromArray[c]
b.dump[]
b.solve[false]
b.dump[]


c=["8--91----",
   "3-76--9-1",
   "-9-------",
   "5---3-7-9",
   "-34-8-26-",
   "9-2-7---4",
   "-------5-",
   "1-3--24-7",
   "----91--3"]
b = Sudoku.createFromArray[c]
b.dump[]
b.solve[false]
b.dump[]

c=["-1-4-63-9",
   "----3-85-",
   "-------6-",
   "-6-5--7-2",
   "25-6-7-13",
   "4-7--2-9-",
   "-7-------",
   "-94-5----",
   "6-39-4-7-"]
b = Sudoku.createFromArray[c]
b.dump[]
b.solve[false]
b.dump[]


View or download Sudoku.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17592 days, 15 hours, 40 minutes ago.