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