Task

Solve a partially filled-in normal   9x9   Sudoku grid   and display the result in a human-readable format.

references

 Algorithmics of Sudoku   may help implement this.
 Python Sudoku Solver Computerphile video.


 
#!/usr/local/bin/shale
 
time library
 
// This solves a sudoku with:
//  row/column/3x3box constraints (standard sudoku)
//  row/column/irregular, or jigsaw, region constraints
// optionally with a Chess Knight's move constraint.
// It is based on the python code from the Computerphile video
//  https://www.youtube.com/watch?v=G_UYXzGuqvM
// The sudoku example from this video is used below, along with
// a couple of Cracking The Cryptic examples and one from Andrew Stuart.
 
// The sudoku grid is stored in a multi-dimensional array under the grid:: namespace.
// The row and column of each cell is represented by:
//
//  row column:: grid::
//
// A 0 value represents an empty cell, and a 1 to 9 value represents a cell value.
 
// You can specify which of the sudokus to solve by specifying s={n} on the command line.
// If it is not specified then you get a text explaining how to specify an option
// and what the options are and the default (s=1) option is solved.
 
startTime dup var now time::() =
 
whichSudoku var
 
s initialised {
  whichSudoku s =
} {
  "You can choose to solve one of several sudokus by adding s=n to the command line," println
  "where n is" println
  "  1: standard sudoku from Computerphile (the default)" println
  "  2: standard sudoku from Cracking The Cryptic" println
  "  3: standard sudoku from Cracking The Cryptic, with Knight's move constraint" println
  "  4: standard sudoku from Cracking The Cryptic" println
  "  5: irregular sudoku from Cracking The Cryptic" println
  "  6: irregular sudoku from Andrew Stuart" println
  "" println
  "You can also enable colour output by adding colour=true or color=true to the command line." println
  "" println
  "For example," println
  file arg:: shale:: "  %s s=3 colour=true\n" printf
  "will solve the CTC sudoku with the Knight's move constraint" println
  "" println
  whichSudoku 1 =
} if
 
// Prints the sudoku grid.
printGrid dup var {
  r var
  c var
  doColour var
  irregular var
  region var
 
  colour initialised {
    doColour colour =
  } {
    color initialised {
      doColour color =
    } {
      doColour false =
    } if
  } if
  irregular 0 0:: regions:: initialised =
 
  r 0 =
  { r 9 < } {
    c 0 =
    { c 9 < } {
      doColour {
        irregular {
          region r.value c.value:: regions:: =
          region.value colour:: 0x1b "%c[1;%dm" printf
        } {
          r 3 / c 3 / + 1 + 2 % 3 * 31 + 0x1b "%c[1;%dm" printf
        } if
      } ifthen
      r.value c.value:: grid:: dup 0 == { pop " ." } { " %d" } if printf
      doColour {
        0x1b "%c[0m" printf
      } ifthen
      c++
    } while
    "" println
    r++
  } while
} =
 
// This sets up the colour map for irregular sudokus.
1 colour:: dup var 30 =
2 colour:: dup var 31 =
3 colour:: dup var 32 =
4 colour:: dup var 33 =
5 colour:: dup var 34 =
6 colour:: dup var 35 =
7 colour:: dup var 36 =
8 colour:: dup var 30 =   // skip 37 (too light) and reuse 30 and 31 (with luck they won't be close to regions 1 and 2).
9 colour:: dup var 31 =
 
// Assign the cell values to one row of the grid.
setRow dup var {
  8$ dup var swap =   // cell 9 of the row
  7$ dup var swap =   // cell 8 of the row
  6$ dup var swap =   // ...
  5$ dup var swap =
  4$ dup var swap =
  3$ dup var swap =
  2$ dup var swap =
  1$ dup var swap =   // ...
  0$ dup var swap =   // cell 1 of the row
  r dup var swap =    // the row number
  ns dup var swap &=  // the namespace to use
  i var               // loop counter
 
  r 0 < r 8 > or {
    r "Illegal row %d\n" printf
    1 exit
  } ifthen
 
  i 0 =
  { i 9 < } {
    i.value$ 0 < i.value$ 9 > or {
      i r i.value$ "Illegal value %d specified for r%dc%d\n" printf
      1 exit
    } ifthen
    r.value i.value:: ns->:: defined not {    // define this grid cell if not already defined
      r.value i.value:: ns->:: var
    } ifthen
    r.value i.value:: ns->:: i.value$ =       // assign the value to the grid cell
    i++
  } while
} =
 
// Standard 3x3 box region checker.
// This only works when called from within possible().
standardRegions dup var {
  r0 var
  c0 var
 
  r0 r 3 / 3 * =
  c0 c 3 / 3 * =
  i 0 =
  { i 3 < } {
    j 0 =
    { j 3 < } {
      r0 i + c0 j +:: grid:: n == {
        false return
      } ifthen
      j++
    } while
    i++
  } while
} =
 
// Irregular region checker.
// This only works when called from within possible().
irregularRegions dup var {
  region var
  i var
 
  region r.value c.value:: regions:: =   // The region we are in.
 
  i 0 =
  { i 9 < } {
    i.value r:: region.value:: region:: value i.value c:: region.value:: region:: value:: grid:: n == {
      false return
    } ifthen
    i++
  } while
} =
 
// Convert the regions:: namespace into something a little more cpu-time friendly.
// Only optimise if there are irregular regions defined.
optimiseRegions dup var {
  0 0:: regions:: initialised {
    region var
    r var
    c var
    i var
 
    region 1 =
    { region 10 < } {
      i 0 =
      r 0 =
      { r 9 < } {
        c 0 =
        { c 9 < } {
          r.value c.value:: regions:: region == {
            i.value r:: region.value:: region:: dup var r =
            i.value c:: region.value:: region:: dup var c =
            i++
          } ifthen
          c++
        } while
        r++
      } while
      i 9 != {
        i region "Region %d contains the wrong number of cells (%d)\n" printf
        1 exit
      } ifthen
      region++
    } while
  } ifthen
} =
 
// Is it possible to place a digit in a given cell?
possible dup var { function
  n dup var swap =
  c dup var swap =
  r dup var swap =
  i var
  j var
 
  // Check the column doesn't already contain this value.
  i 0 =
  { i 9 < } {
    r.value i.value:: grid:: n == {
      false return
    } ifthen
    i++
  } while
 
  // Check the row doesn't already contain this value.
  i 0 =
  { i 9 < } {
    i.value c.value:: grid:: n == {
      false return
    } ifthen
    i++
  } while
 
  // Check that the region doesn't already contain this value.
  regionChecker()
 
  // Check for any other constraint.
  constraint initialised { r c n constraint() not } and {
    false return
  } ifthen
 
  true
} =
 
// This is a Knight's move constraint.
knightsMoveConstraint dup var { function
  0$ dup var swap =  // n
  1$ dup var swap =  // column
  2$ dup var swap =  // row
  nr var
  nc var
 
  // Check Knight's move 2 left and 1 up and down.
  nc 1$ 2 - =
  nc 0 >= {
    nr 2$ 1 - =
    nr 0 >= {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
    nr 2$ 1 + =
    nr 9 < {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
  } ifthen
 
  // Check Knight's move 1 left and 2 up and down.
  nc 1$ 1 - =
  nc 0 >= {
    nr 2$ 2 - =
    nr 0 >= {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
    nr 2$ 2 + =
    nr 9 < {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
  } ifthen
 
  // Check Knight's move 1 right and 2 up and down.
  nc 1$ 1 + =
  nc 9 < {
    nr 2$ 2 - =
    nr 0 >= {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
    nr 2$ 2 + =
    nr 9 < {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
  } ifthen
 
  // Check Knight's move 2 right and 1 up and down.
  nc 1$ 2 + =
  nc 9 < {
    nr 2$ 1 - =
    nr 0 >= {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
    nr 2$ 1 + =
    nr 9 < {
      nr.value nc.value:: grid:: 0$ == {
        false return
      } ifthen
    } ifthen
  } ifthen
 
  true
} =
 
// Set this to standardRegions for the usual 3x3 boxes,
// or irregularRegions to handle irregular, or jigsaw, regions.
regionChecker var
 
// Leave this undefined to get the standard sudoku rules, or set this
// to constraint code such as knightsMoveConstraint defined above.
constraint var
 
solve dup var { function
  r var
  c var
  n var
 
  r 0 =
  { r 9 < } {
    c 0 =
    { c 9 < } {
      r.value c.value:: grid:: dup 0 == {   // dup r.value c.value:: grid:: so we don't have to recalculate it in the inner loop.
        n 1 =
        { n 10 < } {
          r.value c.value n.value possible() {
            dup n =   // picking up r.value c.value:: grid:: again.
            solve()
            dup 0 =   // picking up r.value c.value:: grid:: again.
          } ifthen
          n++
        } while
        pop   // get rid of r.value c.value:: grid::
        return
      } ifthen
      pop   // get rid of r.value c.value:: grid::
      c++
    } while
    r++
  } while
 
  "" println
  printGrid()
  now time::() startTime - 1000.0 / "Solution in %0.3f seconds\n" printf
} =
 
found var
found false =
 
// As mentioned above, this is the example taken from the Computerphile video.
// Raspberry Pi3 Model A time: 17s to the solution, 19s to finish.
// The time spent between the solution and the finish is the script searching
// of other, non-existant, soultion.
whichSudoku 1 == {
  found true =
  "From Computerphile: https://www.youtube.com/watch?v=G_UYXzGuqvM" println
  regionChecker standardRegions =
  grid 0 5 3 0 0 7 0 0 0 0 setRow()
  grid 1 6 0 0 1 9 5 0 0 0 setRow()
  grid 2 0 9 8 0 0 0 0 6 0 setRow()
  grid 3 8 0 0 0 6 0 0 0 3 setRow()
  grid 4 4 0 0 8 0 3 0 0 1 setRow()
  grid 5 7 0 0 0 2 0 0 0 6 setRow()
  grid 6 0 6 0 0 0 0 2 8 0 setRow()
  grid 7 0 0 0 4 1 9 0 0 5 setRow()
  grid 8 0 0 0 0 8 0 0 7 9 setRow()
} ifthen
 
// From https://www.youtube.com/watch?v=MXUgYxHmKq4&t=0s
// This sudoku was featured on Cracking The Cryptic, and takes considerably longer than the one above.
// Pi3 Model A time: 3m 23s to the solution, 15m 11s to finish.
whichSudoku 2 == {
  found true =
  "From Cracking The Cryptic: https://www.youtube.com/watch?v=MXUgYxHmKq4&t=0s" println
  regionChecker standardRegions =
  grid 0 0 6 8 0 0 0 0 1 3 setRow()
  grid 1 0 0 0 9 0 1 0 0 0 setRow()
  grid 2 0 0 0 0 0 8 0 0 4 setRow()
  grid 3 0 1 0 0 4 0 5 0 0 setRow()
  grid 4 0 3 0 0 0 9 0 0 0 setRow()
  grid 5 0 8 5 0 0 0 0 7 0 setRow()
  grid 6 0 2 0 0 0 7 3 0 0 setRow()
  grid 7 0 0 0 0 9 4 0 0 6 setRow()
  grid 8 4 0 0 0 6 0 0 0 0 setRow()
} ifthen
 
// From https://www.youtube.com/watch?v=rQHV-gIAG_0
// Another Cracking The Cryptic video, this one with a Knight's move constraint.
// Pi3 Model A time: 48s to the solution, 6m 10s to finish.
whichSudoku 3 == {
  found true =
  "From Cracking The Cryptic: https://www.youtube.com/watch?v=rQHV-gIAG_0" println
  "This includes a Chess Knight's move constraint." println
  regionChecker standardRegions =
  constraint knightsMoveConstraint =
  grid 0 0 0 0 0 0 6 0 0 0 setRow()
  grid 1 0 0 3 0 0 0 0 0 7 setRow()
  grid 2 2 0 0 3 0 0 4 9 0 setRow()
  grid 3 6 0 0 0 0 0 0 4 5 setRow()
  grid 4 0 0 2 0 0 0 8 0 0 setRow()
  grid 5 0 0 0 1 0 0 0 0 0 setRow()
  grid 6 3 0 0 0 0 0 0 0 0 setRow()
  grid 7 7 0 0 0 0 1 0 0 9 setRow()
  grid 8 0 0 0 0 0 0 5 0 0 setRow()
} ifthen
 
// Another CTC sudoku: https://www.youtube.com/watch?v=vH-JooV8RA4&t=0s
// Pi3 Model A time: 1m 6s to the solution, 48m 35s to finish.
whichSudoku 4 == {
  found true =
  "From Cracking The Cryptic: https://www.youtube.com/watch?v=vH-JooV8RA4&t=0s" println
  regionChecker standardRegions =
  grid 0 0 0 0 0 0 0 0 0 0 setRow()
  grid 1 0 0 9 8 0 0 0 0 7 setRow()
  grid 2 0 8 0 0 6 0 0 5 0 setRow()
  grid 3 0 5 0 0 4 0 0 3 0 setRow()
  grid 4 0 0 7 9 0 0 0 0 2 setRow()
  grid 5 0 0 0 0 0 0 0 0 0 setRow()
  grid 6 0 0 2 7 0 0 0 0 9 setRow()
  grid 7 0 4 0 0 5 0 0 6 0 setRow()
  grid 8 3 0 0 0 0 6 2 0 0 setRow()
} ifthen
 
// Another Cracking The Cryptic sudoku: https://www.youtube.com/watch?v=eJIu8w3ZXo8
// This is an irregular (jigsaw) sudoku.
// Pi3 Model A time: 2m 5s to the solution, 7m 5s to finish.
whichSudoku 5 == {
  found true =
  "From Cracking The Cryptic: https://www.youtube.com/watch?v=eJIu8w3ZXo8" println
  "An irregular sudoku." println
  regionChecker irregularRegions =
  regions 0 1 1 1 1 1 2 2 2 2 setRow()
  regions 1 1 3 3 3 6 6 2 2 2 setRow()
  regions 2 1 3 3 3 6 7 7 7 2 setRow()
  regions 3 1 3 3 3 6 7 7 7 2 setRow()
  regions 4 1 6 6 6 6 7 7 7 8 setRow()
  regions 5 9 6 4 4 4 8 8 8 8 setRow()
  regions 6 9 9 4 4 4 8 5 5 5 setRow()
  regions 7 9 9 4 4 4 8 5 5 5 setRow()
  regions 8 9 9 9 9 8 8 5 5 5 setRow()
  grid 0 3 0 0 0 0 0 0 0 1 setRow()
  grid 1 0 9 0 1 7 2 0 0 0 setRow()
  grid 2 0 0 3 0 0 0 9 0 0 setRow()
  grid 3 0 7 0 0 0 0 0 4 0 setRow()
  grid 4 0 4 0 0 3 0 0 6 0 setRow()
  grid 5 0 5 0 0 0 0 0 9 0 setRow()
  grid 6 0 0 6 0 0 0 5 0 0 setRow()
  grid 7 0 0 0 8 5 6 0 2 0 setRow()
  grid 8 7 0 0 0 0 0 0 0 8 setRow()
} ifthen
 
// This is taken from Andrew Stuart's web site https://www.sudokuwiki.org/Daily_Jigsaw_Sudoku
// No. 4294, dated 13 Nov 2020. It is rated 5-star out of 6: Diabolical.
// The archived version is here: https://www.sudokuwiki.org/Print_Daily_Jigsaw.asp?day=13/11/2020
// At the time of writing, Andrew only archives sudoku's for 31 days, then they are deleted.
// The region layout is called "Andrew Stuart 24" and the numbering is taken directly
// from Andrew's solver page. A big thanks goes to Andrew for giving me permission to include this sudoku.
// The region numbers must be between 1 and 9 inclusive.
// Pi3 Model A time: 26m 23s to the solution, 1h 15m 20s to finish.
whichSudoku 6 == {
  found true =
  "From Andrew Stuart's web page: https://www.sudokuwiki.org/Daily_Jigsaw_Sudoku" println
  "No. 4294, dated 13 Nov 2020" println
  regionChecker irregularRegions =
  regions 0 1 1 2 2 2 2 3 3 4 setRow()
  regions 1 1 1 2 2 2 3 3 3 4 setRow()
  regions 2 1 1 1 2 3 3 3 4 4 setRow()
  regions 3 1 1 5 2 3 7 4 4 4 setRow()
  regions 4 5 5 5 6 6 7 7 4 4 setRow()
  regions 5 5 5 5 6 6 7 7 7 9 setRow()
  regions 6 8 5 5 6 6 7 7 7 9 setRow()
  regions 7 8 8 6 6 6 9 9 9 9 setRow()
  regions 8 8 8 8 8 8 8 9 9 9 setRow()
  grid 0 0 0 0 0 0 0 0 9 0 setRow()
  grid 1 5 0 0 0 8 1 0 0 0 setRow()
  grid 2 0 0 0 9 0 4 5 0 0 setRow()
  grid 3 0 0 0 0 0 0 0 0 5 setRow()
  grid 4 0 1 0 0 0 8 0 0 0 setRow()
  grid 5 7 0 6 0 0 0 0 0 0 setRow()
  grid 6 0 0 0 1 0 0 6 0 0 setRow()
  grid 7 1 0 0 7 2 0 0 0 0 setRow()
  grid 8 0 9 0 0 0 0 0 0 0 setRow()
} ifthen
 
// If you want to add your own sudoku, add it here.
whichSudoku 7 == {
  found true =
  // add it here
  // regionChecker standardRegions =          // Include a region checker
  // regionChecker irregularRegions =
  // constraint knightsMoveConstraint =       // Include any extra contraints, as appropriate
} ifthen
 
// Don't change anything from here to the end.
 
found {
  optimiseRegions()
 
  "" println
  "Initial grid" println
  printGrid()
 
  solve()
 
  now time::() startTime - 1000.0 / "Total runtime was %0.3f seconds\n" printf
} {
  whichSudoku "Sudoku %d not found\n" printf
} if
 
// I'd like to see an irregular sudoku with a knight's move constraint. Any takers...
 