  $ filename "sudoku.exe"
  'uses rtl32
  'uses rtl64

  uses corewin
  uses console

  type CONSOLE_CURSOR_INFO ' cci
    dword dwSize
    bool  bVisible
  end type

  sub setcolor(int fg, bg)
    SetConsoleTextAttribute (ConsOut, fg+bg*16)
  end sub

  sub locate(int row,int col, optional int cursor_visible=0,int shape=12)
    CONSOLE_CURSOR_INFO cci
    SetPos(col-1,row-1)
    cci.bVisible = cursor_visible
    cci.dwSize   = shape
    SetConsoleCursorInfo(ConsOut, cci)
  end sub

  sub display(int col, row, string txt, optional int cursor_visible=0,int shape=12)
    locate(row, col, cursor_visible, shape)
    print txt
  end sub

  function replace(string t,w,r) as string    'parseutil.inc
  ========================================
    '
    sys a,b,lw,lr
    string s=t
    '
    lw=len(w)
    lr=len(r)
    a=1
    do
      a=instr(a,s,w)
      if a=0 then exit do
      s=left(s,a-1)+r+mid(s,a+lw)
      a+=lr
    end do
    return s
  end function

  redim int sudoku(9*9)
  ' use sudoku as 2d array with index 1
  macro array2d_sudoku(x,y) sudoku(((y)-1)*9+(x))

  redim int tmpArray(9*9)

  double t1, t2
  int maxval
  int CheckNotify
  int count

  function loadSudoku()
    string fname, s
    string lf=chr(10)
    int x
    cls
    printl "Solving Sudoku (9x9) using Recursive Backtracking"
    print  "Filename to load? " : fname = input()
    fname = rtrim ltrim fname
    getfile(fname, s)
    if len(s)=0 then printl "Error: does not exist or cannot read file: " + fname : return 0
    'simple check for /* comment at the beginning
    int pos=instr(s,"*/")
    if pos then s=mid(s,pos+2)
    s=replace(s,cr, "") : s=replace(s,lf,"") : s=replace(s,tab,"")
    s=replace(s,chr(32), "") : s=replace(s,",","") : s=replace(s,".","")
    for x=1 to 81 : sudoku[x]=mid(s,x,1) : next x
    print "Sudoku loaded"
    return 1
  end sub

  sub checkForRotate()
    string z1,z2,z3,z4
    int ix,n
    ' No change?
    for ix = 1 to 9 : z1 += sudoku[ix]: next ix : maxval = 1
    ' Rotate Grid 180?
    for ix = 81 to 73 step -1 : z2 += sudoku[ix]: next ix : if val(z2) > val(z1) then maxval = 2
  end sub

  sub rotate()
    int ix, n, r,c
    if maxval > 1 then
      printl "" : printl "Rotate grid 180 degrees     "
      n = 81
      for ix = 1 to 81 : tmpArray[ix] = sudoku[n] : n -= 1 : next ix
      for ix = 1 to 81 : sudoku[ix] = tmpArray[ix] : next ix
    end if
  end sub

  sub printSudoku(int sudoku[], int x, y)
    int row, col, x1
    string index = "    1 2 3  4 5 6  7 8 9"
    string underline = "  ----------------------"
    string vertLine = "|"

    display(x,y, index)
    y += 1
    display(x,y, underline)

    for row = 1 to 9
      display(x, y+row, row ) : display(x+2, y+row, vertline)
      x1 = x + 2
      for col = 1 to 9
        if sudoku[(row-1 )*9 + col] = 0 then
          display(x1+col, y+row, "  ")
        else
          display(x1+col, y+row, " " + sudoku[(row-1)*9 + col])
        end if
        if col = 3 or col = 6 or col = 9 then x1 = x1 + 2 : display(x1+col, y+row, "!" ) : x1 -= 1
        x1 = x1 + 1
      next col
      if row = 3 or row = 6 or row = 9 then y += 1 : display(x, y+row, underline)
    next row
  end sub

  function testSudoku() as int
    ' test columns vertically
    int col, row, testrow
    for col = 1 to 9
      for row = 1 to 9
        'if array2d_sudoku(col, row) != 0 then
        if sudoku((row-1)*9 + col) != 0 then
          for testrow = row+1 to 9
            'if array2d_sudoku(col, row) = array2d_sudoku(col, testrow) then
            if sudoku((row-1)*9 + col) = sudoku((testrow-1)*9 + col)
              if CheckNotify = true then
                printl "Error: Col " + col + ", Row "+ row" = " + array2d_sudoku(col, row) +
                       " and Col " + col  + ", Row " + testrow" = " + array2d_sudoku(col, testrow) + cr
                CheckNotify = false
              end if
              return 0
            end if
          next testrow
        end if
      next row
    next next col

    ' test columns in row
    int testcol
    for row = 1 to 9
      for col = 1 to 9
        'if array2d_sudoku(col, row) != 0 then
        if sudoku((row-1)*9 + col) != 0 then
          for testcol = col+1 to 9
            'if array2d_sudoku(col, row) = array2d_sudoku(testcol, row) then
            if sudoku((row-1)*9 + col) = sudoku((row-1)*9 + testcol)
              if CheckNotify = true then
                printl "Error: Row " + row + ", Col " + col + " = " + array2d_sudoku(col, row) +
                       " and Row " + row + ", Col " + testcol + " = " + array2d_sudoku(testcol, row) + cr
                CheckNotify = false
              end if
              return 0
            end if
          next testcol
        end if
      next col
    next row

    ' test boxes
    int BoxX, BoxY, Col_inBox, Row_inBox, TestCol_inBox, TestRow_inBox
    int expr1, expr2

    for BoxX = 1 to 3
      for BoxY = 1 to 3
        for Col_inBox = 1 to 3
          for Row_inBox = 1 to 3
            'expr1 = array2d_sudoku(3*(BoxX-1) + Col_inBox, 3*(BoxY-1) + Row_inBox)
            expr1 = sudoku(((3*(BoxY-1) + Row_inBox)-1)*9 + 3*(BoxX-1) + Col_inBox)
            if expr1 != 0 then
              for TestCol_inBox = 1 to 3
                for TestRow_inBox = 1 to 3
                  'expr2 = array2d_sudoku(3*(BoxX-1) + TestCol_inBox, 3*(BoxY-1) + TestRow_inBox)
                  expr2 = sudoku(((3*(BoxY-1) + TestRow_inBox)-1)*9 + 3*(BoxX-1) + TestCol_inBox)
                  if expr1 = expr2 and (Col_inBox != TestCol_inBox or Row_inBox != TestRow_inBox) then
                    if CheckNotify = true then
                      printl "Error: Box h,v: " + BoxX + ", " + BoxY + " -- Col:Row " + Col_inBox + ":" + Row_inBox +
                             " = Col:Row " + TestCol_inBox + ":" + TestRow_inBox + " (" + expr1 + ")" + cr
                      CheckNotify = false
                    end if
                    return 0
                  end if
                next TestRow_inBox
              next TestCol_inBox
            end if
          next Row_inBox
        next Col_inBox
      next BoxY
    next BoxX
    return 1
  end function

  function solve() as int
    ' recursive brute-force method
    ' check if Sudoku is correct
    count += 1
    if testSudoku() = 0 then return 0

    'test next free position
    int col, row, testnum
    for col = 1 to 9
      for row = 1 to 9
        'if array2d_sudoku(col, row) = 0 then
        if sudoku((row-1)*9 + col) = 0 then
          for testnum = 1 to 9
            'array2d_sudoku(col, row) = testnum
            sudoku((row-1)*9 + col) = testnum
            if solve() = true then return true
          next testnum
          'does not fit
          'array2d_sudoku(col,row) = 0
          sudoku((row-1)*9 + col) = 0
          return false
        end if
      next row
    next col
    return true
  end function


  sub main()
    string ans
loop1:
    setcolor(7, 0)
    if not loadSudoku() then goto loop2
    printSudoku(sudoku[], 5,5)

    CheckNotify = true
    if testSudoku() then
      printl "" : printl "Solving ..."
      count = 0
      if CheckNotify = true then CheckNotify = false

      t1 = GetTickCount
      checkForRotate()
      rotate()
      setcolor(11, 0)
      if maxval > 1 then printSudoku(sudoku[], 40,5)

      if solve() = false then printl "" : printl "Solution not possible" : goto loop2

      setcolor(7, 0)
      rotate()

      t2 = GetTickCount
      printSudoku(sudoku[], 40,5)
      printl "" : printl  "Elapsed time: " + (t2-t1)/1000 + " seconds "
      printl "Recursive calls: " + count + "           "
    end if

loop2:
    print "Load another file? (Y/N) " : ans = ltrim rtrim(input())
    if lcase(ans) = "y" then goto loop1
  end sub

  main()
