# Sudoku.frink

``` // 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       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[] ```

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 18492 days, 22 hours, 18 minutes ago.