Author Topic: Backtracking in Oxygenbasic  (Read 241 times)

0 Members and 1 Guest are viewing this topic.

Arnold

  • Hero Member
  • *****
  • Posts: 861
Backtracking in Oxygenbasic
« on: August 07, 2019, 10:53:46 PM »
Hi Charles,

for a small project I will need backtracking and for experimenting I found the nQueens task in Rosetta Code. This is an interesting problem, because there is no formula to determine the exact number of solutions. I applied recursive backtracking. I also added an option to show only the first and last solution of the task. And here is my question:

I tried in function try() to assign the values of array col_in_row to array indexes (indexes[] = col_in_row[]). This did not work for me and I used the copy function instead (line 49). Is there a better alternative or is there a way to apply indexes[] = col_in_row[] also?

The app works quite nice. Perhaps there are some places in the code where the speed of the app could be increased by using assembler statements? I know that it is impossibe to beat the record of n=27, but it will already take some time for n=16 to find the 14.772.512 solutions.

Roland

Code: [Select]
$ filename "nQueens.exe"
'uses rtl32
'uses rtl64

uses console


! GetTickCount lib "kernel32.dll"


int doprint
int solution
int size_of_board
double t1, t2
string ans
sys *index

sub printBoard(int col_in_row[], int size_of_board, solution)
    int x, row, col

    printl "Solution: " + solution
    printl "   "
   
    for x = 1 to size_of_board : print chr(x+96) + " " : next x
    for row = 1 to size_of_board
        if row < 10 then printl row + "  " else printl row + " "
        for col = 1 to size_of_board
            if col_in_row[col] = row then print "Q " else print "- "
        next col
    next row
    printl
end sub

function is_free(int col_in_row[], test_row,  current_row) as int
=================================================================
  int i
  for i = 1 to current_row-1
    if col_in_row[i] = test_row
      return 0  'beat queen in the vertical
    endif
    if abs(col_in_row[i]-test_row) = abs(i-current_row)
      return 0  'beat queen in the diagonal
    endif
  next i
  return 1
end function

' place queen in current row
sub try(int col_in_row[], int current_row)
    int test_row
    if current_row > size_of_board then
        solution += 1 : if doprint = 0 then copy &index, &col_in_row[], size_of_board*sizeof(int)
        if solution = 1 then printBoard(col_in_row[], size_of_board, solution)
        if solution > 1 and doprint then printBoard(col_in_row[], size_of_board, solution)
    else
        for test_row = 1 to size_of_board
            if is_free(col_in_row[], test_row, current_row) then
                col_in_row[current_row] = test_row
                try(col_in_row[], current_row+1)
            end if
        next test_row
    end if
end sub


sub main()
loop1:
    redim int col_in_row(0)
    redim int indexes(0)
    solution = 0

    cls
    print "Size of Board (1-16)? " : size_of_board = val(input())

    if size_of_board < 1 then size_of_board = 1
    if size_of_board > 16 then size_of_board = 16
    print  "Your input = " size_of_board
    printl "Show all solutions - default is first and last? (Y/N): " : ans=ltrim rtrim(input)
    if lcase(ans) = "y" then doprint = 1 else doprint = 0

    redim int col_in_row(size_of_board)  'column of queen in row
    redim int indexes(size_of_board)
    @index = @indexes

    t1=GetTickCount
    try(col_in_row[], 1)
    t2=GetTickCount

    if doprint = 0 then printBoard(indexes[], size_of_board, solution)
    printl : printl "Found " + solution + " Solutions, " + "used time: " + (t2-t1)/1000 + " seconds"

    printl "Another Try? (Y/N) "
    ans = ltrim rtrim(input())
    if lcase(ans) = "y" then goto loop1
end sub

main()
« Last Edit: August 09, 2019, 06:48:02 AM by Arnold »

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4186
    • Oxygen Basic
Re: Backtracking in Oxygenbasic
« Reply #1 on: August 09, 2019, 01:11:14 AM »
Thanks Roland,

copy is an efficient way to transfer data. It is used internally for many tasks.

Minor correction needed in function is_free so that the indexing starts from 1

Code: [Select]
function is_free(byval int col_in_row[], int test_row, int current_row) as int
    int i
    for i = 1 to current_row-1
        if col_in_row[i-1] = test_row or                                 'beat queen in the vertical
            abs(col_in_row[i]-test_row) = abs(i-current_row) then    'beat queen in the diagonal
            return 0
        end if
    next i
    return 1
end function

This is a speed optimised version, with de-compunded logic, direct arrays, and bytewise table output:

Code: [Select]
$ filename "nQueens.exe"
'uses rtl32
'uses rtl64

uses console

! GetTickCount lib "kernel32.dll"

int doprint
int solution
int size_of_board
double t1, t2
string ans
int *index

sub printBoard(int col_in_row[], size_of_board, solution)
=========================================================
  int x, row, col

  printl "Solution: " + solution + cr
'/*
  int m,k
  string pr
  pr = space( (size_of_board+1) * (size_of_board*2+3+2) +2 )
  byte *b
  @b = strptr(pr)+3
  k = 97
  for x = 1 to size_of_board
    b=k : k+=1 : @b+=2 'a b c d e etc  ... 
  next
  for row = 1 to size_of_board
    b=13 : @b++ 'cr
    b=10 : @b++ 'lf
    m=32
    if row < 10
      b=row+48  : @b+=3 'units digit
    else
      m=row\10
      k=row-(m*10)
      b=m+48 : @b++  'tens digit
      b=k+48 : @b+=2 'units digit
    endif
    for col = 1 to size_of_board
      if col_in_row[col] = row
        b=0x51 'Q
      else
        b=45 '-
      endif
      @b += 2
    next col
  next row
  b=13 : @b++
  b=10 : @b++
  print pr
'*/
/*
  print "   "
  for x = 1 to size_of_board
    print chr(x+96) + " "
  next x
  for row = 1 to size_of_board
    if row < 10
      printl row + "  "
    else
      printl row + " "
    endif
    for col = 1 to size_of_board
      if col_in_row[col] = row
        print "Q "
      else
        print "- "
      endif
    next col
  next row
  printl
*/
end sub

function is_free(int col_in_row[], test_row,  current_row) as int
=================================================================
  int i
  for i = 1 to current_row-1
    if col_in_row[i] = test_row
      return 0  'beat queen in the vertical
    endif
    if abs(col_in_row[i]-test_row) = abs(i-current_row)
      return 0  'beat queen in the diagonal
    endif
  next i
  return 1
end function

' place queen in current row
sub try(int col_in_row[], current_row)
======================================
  int test_row
  if current_row > size_of_board
    solution += 1
    if doprint = 0
      copy &index, &col_in_row[], size_of_board*sizeof(int)
    endif
    if solution = 1
      printBoard(col_in_row[], size_of_board, solution)
    endif
    if solution > 1 and doprint
      printBoard(col_in_row[], size_of_board, solution)
    endif   
  else
    for test_row = 1 to size_of_board
      if is_free(col_in_row[], test_row, current_row)
        col_in_row[current_row] = test_row
        try(col_in_row[], current_row+1)
      endif
    next test_row
  endif
end sub


sub main()
==========
  '
  loop1:
  '
  'redim int col_in_row(0)
  'redim int indexes(0)
  dim int col_in_row(20)
  dim int indexes(20)
  solution = 0
  '
  cls
  print "Size of Board (1-16)? " : size_of_board = val(input())
  '
  if size_of_board < 1
    size_of_board = 1
  endif
  if size_of_board > 16
    size_of_board = 16
  endif
  '
  print  "Your input = " size_of_board
  printl "Show all solutions - default is first and last? (Y/N): " : ans=ltrim rtrim(input)
  '
  if lcase(ans) = "y"
    doprint = 1
  else
    doprint = 0
  endif
  'redim int col_in_row(size_of_board)  'column of queen in row
  'redim int indexes(size_of_board)
  @index = @indexes
  '
  t1=GetTickCount
  try(col_in_row[], 1)
  t2=GetTickCount
  '
  if doprint = 0
    printBoard(indexes[], size_of_board, solution)
  endif
  printl : printl "Found " + solution + " Solutions, " + "used time: " + (t2-t1)/1000 + " seconds"
  '
  printl "Another Try? (Y/N) "
  ans = ltrim rtrim(input())
  if lcase(ans) = "y"
    goto loop1
  endif
end sub

main()


Arnold

  • Hero Member
  • *****
  • Posts: 861
Re: Backtracking in Oxygenbasic
« Reply #2 on: August 09, 2019, 06:55:32 AM »
Hi Charles,

thank you for the fix. I had to change also this line to:

Code: [Select]
           if col_in_row[i] = test_row or

Your code runs about 33% faster than mine. I noticed that you separated the statements for the conditions in function is_free and applied your solution in my code. To my surprise I get similar results now for n=16 (475 seconds instead of 700 seconds). I simply did not expect such a gain of time saving by only adjusting some statements. That was an educational experience for me again.

I replaced the code of my first message in case somebody would like to try the puzzle. And I found much information here:

https://en.wikipedia.org/wiki/Eight_queens_puzzle

Roland



Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4186
    • Oxygen Basic
Re: Backtracking in Oxygenbasic
« Reply #3 on: August 09, 2019, 10:36:34 AM »
You can squeeze a little more performance by in-lining the is_free procedure, within try.

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4186
    • Oxygen Basic
Re: Backtracking in Oxygenbasic
« Reply #4 on: August 10, 2019, 12:40:48 AM »
After inlining is_free, it can be converted into Assembler. This further improves the speed, so a 14*14 originally taking 24 seconds, now takes about 9 seconds.

Code: [Select]
    for test_row = 1 to size_of_board
      '
      'is_free
      'int i,k
      'for i = 1 to current_row-1
        'k=col_in_row[i]
        'if k = test_row
        '  jmp fwd nxt_test_row  'beat queen in the vertical
        'endif
        'if abs(k-test_row) = abs(i-current_row)
        '  jmp fwd nxt_test_row  'beat queen in the diagonal
        'endif
      'next i
      int i
      mov ecx,current_row
      addr rdi,col_in_row
      mov dword i,1
      (
        dec ecx
        jle fwd exit
        mov eax,[rdi] 'k col_in_row
        cmp eax,test_row
        jz fwd nxt_test_row
        sub eax,test_row
        (
         jge exit
         neg eax
        )
        mov edx,i
        sub edx,current_row
        (
         jge exit
         neg edx
        )
        cmp eax,edx
        jz fwd nxt_test_row
        add rdi,4
        inc dword i
        repeat
      )
      '
      col_in_row[current_row] = test_row
      try(col_in_row[], current_row+1)
      '
      nxt_test_row:     
      '
    next test_row

complete code
Code: [Select]
$ filename "nQueens.exe"
'uses rtl32
'uses rtl64

uses console

! GetTickCount lib "kernel32.dll"

int doprint
int solution
int size_of_board
double t1, t2
string ans
int *index

sub printBoard(int col_in_row[], size_of_board, solution)
=========================================================
  int x, row, col

  printl "Solution: " + solution + cr
'/*
  int m,k
  string pr
  pr = space( (size_of_board+1) * (size_of_board*2+3+2) +2 )
  byte *b
  @b = strptr(pr)+3
  k = 97
  for x = 1 to size_of_board
    b=k : k+=1 : @b+=2 'a b c d e etc  ... 
  next
  for row = 1 to size_of_board
    b=13 : @b++ 'cr
    b=10 : @b++ 'lf
    m=32
    if row < 10
      b=row+48  : @b+=3 'units digit
    else
      m=row\10
      k=row-(m*10)
      b=m+48 : @b++  'tens digit
      b=k+48 : @b+=2 'units digit
    endif
    for col = 1 to size_of_board
      if col_in_row[col] = row
        b=0x51 'Q
      else
        b=45 '-
      endif
      @b += 2
    next col
  next row
  b=13 : @b++
  b=10 : @b++
  print pr
'*/
/*
  print "   "
  for x = 1 to size_of_board
    print chr(x+96) + " "
  next x
  for row = 1 to size_of_board
    if row < 10
      printl row + "  "
    else
      printl row + " "
    endif
    for col = 1 to size_of_board
      if col_in_row[col] = row
        print "Q "
      else
        print "- "
      endif
    next col
  next row
  printl
*/
end sub


' place queen in current row
sub try(int col_in_row[], current_row)
======================================
  int test_row
  if current_row > size_of_board
    solution += 1
    if doprint = 0
      copy &index, &col_in_row[], size_of_board*sizeof(int)
    endif
    if solution = 1
      printBoard(col_in_row[], size_of_board, solution)
    endif
    if solution > 1 and doprint
      printBoard(col_in_row[], size_of_board, solution)
    endif   
  else
    for test_row = 1 to size_of_board
      '
      'is_free
      'int i,k
      'for i = 1 to current_row-1
        'k=col_in_row[i]
        'if k = test_row
        '  jmp fwd nxt_test_row  'beat queen in the vertical
        'endif
        'if abs(k-test_row) = abs(i-current_row)
        '  jmp fwd nxt_test_row  'beat queen in the diagonal
        'endif
      'next i
      int i
      mov ecx,current_row
      addr rdi,col_in_row
      mov dword i,1
      (
        dec ecx
        jle fwd exit
        mov eax,[rdi] 'k col_in_row
        cmp eax,test_row
        jz fwd nxt_test_row
        sub eax,test_row
        (
         jge exit
         neg eax
        )
        mov edx,i
        sub edx,current_row
        (
         jge exit
         neg edx
        )
        cmp eax,edx
        jz fwd nxt_test_row
        add rdi,4
        inc dword i
        repeat
      )
      '
      col_in_row[current_row] = test_row
      try(col_in_row[], current_row+1)
      '
      nxt_test_row:     
      '
    next test_row
  endif
end sub


sub main()
==========
  '
  loop1:
  '
  'redim int col_in_row(0)
  'redim int indexes(0)
  dim int col_in_row(20)
  dim int indexes(20)
  solution = 0
  '
  cls
  print "Size of Board (1-16)? " : size_of_board = val(input())
  '
  if size_of_board < 1
    size_of_board = 1
  endif
  if size_of_board > 16
    size_of_board = 16
  endif
  '
  print  "Your input = " size_of_board
  printl "Show all solutions - default is first and last? (Y/N): " : ans=ltrim rtrim(input)
  '
  if lcase(ans) = "y"
    doprint = 1
  else
    doprint = 0
  endif
  'redim int col_in_row(size_of_board)  'column of queen in row
  'redim int indexes(size_of_board)
  @index = @indexes
  '
  t1=GetTickCount
  try(col_in_row[], 1)
  t2=GetTickCount
  '
  if doprint = 0
    printBoard(indexes[], size_of_board, solution)
  endif
  printl : printl "Found " + solution + " Solutions, " + "used time: " + (t2-t1)/1000 + " seconds"
  '
  printl "Another Try? (Y/N) "
  ans = ltrim rtrim(input())
  if lcase(ans) = "y"
    goto loop1
  endif
end sub

main()
« Last Edit: August 10, 2019, 02:09:43 AM by Charles Pegge »

Arnold

  • Hero Member
  • *****
  • Posts: 861
Re: Backtracking in Oxygenbasic
« Reply #5 on: August 10, 2019, 10:48:35 PM »
Hi Charles,

I get a similar time saving. With me n=14 now takes about 6 seconds. n=16 will take about 285 seconds instead of 700 seconds. And I could not resist and tried n=17. This takes about 2250 seconds, which is about 38 minutes. Your assembly routines in function try() to integrate is_free() function are very instructive and maybe can be used in similar situations.

For me it is amazing what can be done with the (simple?) computers nowadays: play a game of chess or drMario and calculate a problem additionally. In 1969 using punch cards and Fortran, they were happy to find out the solution for n=12. Nevertheless, they flew to the moon. If things continue this way, maybe someday some people will indeed land on Mars.

Roland
« Last Edit: August 10, 2019, 11:05:26 PM by Arnold »

Aurel

  • Sr. Member
  • ****
  • Posts: 394
Re: Backtracking in Oxygenbasic
« Reply #6 on: August 11, 2019, 05:54:55 AM »
input 8
95 solutions
take 0.25 sec

is that ok for my old dual core pentium  ;D
( i must say that i don't like those console progs.. )  ::)

yes i finally download and try this version 0.2.6 from github
also i am able to compile old AsciEdit with this new version.
So i must try my latest AurelEdit with awinh037..i hope that should work.

Charles
Is this new version selfcompiled version of o2?
or is still compiled with FreeBasic?

all best
Aurel
my site:BLOG and FORUM
https://aurelsoft.ucoz.com/

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4186
    • Oxygen Basic
Re: Backtracking in Oxygenbasic
« Reply #7 on: August 13, 2019, 03:06:33 AM »
Hi Aurel,

The o2 releases are self-compiled. FB-based o2 is no longer maintained.

Aurel

  • Sr. Member
  • ****
  • Posts: 394
Re: Backtracking in Oxygenbasic
« Reply #8 on: August 13, 2019, 11:58:01 AM »
Thank you Charles !
good to know
currently i don't have time to testing some things but i will  :D
my site:BLOG and FORUM
https://aurelsoft.ucoz.com/

Arnold

  • Hero Member
  • *****
  • Posts: 861
Re: Backtracking example (Sudoku)
« Reply #9 on: August 15, 2019, 02:52:13 AM »
Hello,

here is a solver for Sudoku puzzles (9x9 grid). The app uses simple brute force recursive backtracking (many for/next loops) without any special optimization methods. The only action I took was to check if rotating the grid could be approprate. The app will load a puzzle as text file. It checks the puzzle for correct entries. If more solutions should be possible, only the first solution will be shown.

Brute force is not the best method to solve Sudoku puzzles, nevertheless the app will solve a lot of puzzles very fast. In the attached zip file I included the code of the program and 20 puzzles, which I find interesting. s4.txt and s5.txt are very difficult, they take about 20 seconds on my system. s15.txt is almost impossible to solve manually, it takes about 3 minutes on my system to solve it. The puzzles s9.txt, s17.txt and s19.txt cannot be solved, although there are no duplicate numbers horicontally, vertically or in a box. So the app can also be used to check if a Sudoku puzzle is valid.

Roland

Code: OxygenBasic
  1.   $ filename "sudoku.exe"
  2.   'uses rtl32
  3.  'uses rtl64
  4.  
  5.   uses corewin
  6.   uses console
  7.  
  8.   type CONSOLE_CURSOR_INFO ' cci
  9.    dword dwSize
  10.     bool  bVisible
  11.   end type
  12.  
  13.   sub setcolor(int fg, bg)
  14.     SetConsoleTextAttribute (ConsOut, fg+bg*16)
  15.   end sub
  16.  
  17.   sub locate(int row,int col, optional int cursor_visible=0,int shape=12)
  18.     CONSOLE_CURSOR_INFO cci
  19.     SetPos(col-1,row-1)
  20.     cci.bVisible = cursor_visible
  21.     cci.dwSize   = shape
  22.     SetConsoleCursorInfo(ConsOut, cci)
  23.   end sub
  24.  
  25.   sub display(int col, row, string txt, optional int cursor_visible=0,int shape=12)
  26.     locate(row, col, cursor_visible, shape)
  27.     print txt
  28.   end sub
  29.  
  30.   function replace(string t,w,r) as string    'parseutil.inc
  31.  ========================================
  32.     '
  33.    sys a,b,lw,lr
  34.     string s=t
  35.     '
  36.    lw=len(w)
  37.     lr=len(r)
  38.     a=1
  39.     do
  40.       a=instr(a,s,w)
  41.       if a=0 then exit do
  42.       s=left(s,a-1)+r+mid(s,a+lw)
  43.       a+=lr
  44.     end do
  45.     return s
  46.   end function
  47.  
  48.   redim int sudoku(9*9)
  49.   ' use sudoku as 2d array with index 1
  50.  macro array2d_sudoku(x,y) sudoku(((y)-1)*9+(x))
  51.  
  52.   redim int tmpArray(9*9)
  53.  
  54.   double t1, t2
  55.   int maxval
  56.   int CheckNotify
  57.   int count
  58.  
  59.   function loadSudoku()
  60.     string fname, s
  61.     string lf=chr(10)
  62.     int x
  63.     cls
  64.     print "Solving Sudoku (9x9) using Recursive Backtracking"
  65.     printl "Filename to load? " : fname = input()
  66.     fname = rtrim ltrim fname
  67.     getfile(fname, s)
  68.     if len(s)=0 then print "Error: does not exist or cannot read file: " + fname : return 0
  69.     'simple check for /* comment at the beginning
  70.    int pos=instr(s,"*/")
  71.     if pos then s=mid(s,pos+2)
  72.     s=replace(s,cr, "") : s=replace(s,lf,"") : s=replace(s,tab,"")
  73.     s=replace(s,chr(32), "") : s=replace(s,",","") : s=replace(s,".","")
  74.     for x=1 to 81 : sudoku[x]=mid(s,x,1) : next x
  75.     print "Sudoku loaded"
  76.     return 1
  77.   end sub
  78.  
  79.   sub checkForRotate()
  80.     string z1,z2,z3,z4
  81.     int ix,n
  82.     ' No change?
  83.    for ix = 1 to 9 : z1 += sudoku[ix]: next ix : maxval = 1
  84.     ' Rotate Grid 180?
  85.    for ix = 81 to 73 step -1 : z2 += sudoku[ix]: next ix : if val(z2) > val(z1) then maxval = 2
  86.   end sub
  87.  
  88.   sub rotate()
  89.     int ix, n, r,c
  90.     if maxval > 1 then
  91.       printl : printl "Rotate grid 180 degrees"
  92.       n = 81
  93.       for ix = 1 to 81 : tmpArray[ix] = sudoku[n] : n -= 1 : next ix
  94.       for ix = 1 to 81 : sudoku[ix] = tmpArray[ix] : next ix
  95.     end if
  96.   end sub
  97.  
  98.   sub printSudoku(int sudoku[], int x, y)
  99.     int row, col, x1
  100.     string index = "    1 2 3  4 5 6  7 8 9"
  101.     string underline = "  ----------------------"
  102.     string vertLine = "|"
  103.  
  104.     display(x,y, index)
  105.     y += 1
  106.     display(x,y, underline)
  107.  
  108.     for row = 1 to 9
  109.       display(x, y+row, row ) : display(x+2, y+row, vertline)
  110.       x1 = x + 2
  111.       for col = 1 to 9
  112.         if sudoku[(row-1 )*9 + col] = 0 then
  113.           display(x1+col, y+row, "  ")
  114.         else
  115.           display(x1+col, y+row, " " + sudoku[(row-1)*9 + col])
  116.         end if
  117.         if col = 3 or col = 6 or col = 9 then x1 = x1 + 2 : display(x1+col, y+row, "!" ) : x1 -= 1
  118.         x1 = x1 + 1
  119.       next col
  120.       if row = 3 or row = 6 or row = 9 then y += 1 : display(x, y+row, underline)
  121.     next row
  122.   end sub
  123.  
  124.   function testSudoku() as int
  125.     ' test columns vertically
  126.    int col, row, testrow
  127.     for col = 1 to 9
  128.       for row = 1 to 9
  129.         'if array2d_sudoku(col, row) != 0 then
  130.        if sudoku((row-1)*9 + col) != 0 then
  131.           for testrow = row+1 to 9
  132.             'if array2d_sudoku(col, row) = array2d_sudoku(col, testrow) then
  133.            if sudoku((row-1)*9 + col) = sudoku((testrow-1)*9 + col)
  134.               if CheckNotify = true then
  135.                 printl "Error: Col " + col + ", Row "+ row" = " + array2d_sudoku(col, row) +
  136.                        " and Col " + col  + ", Row " + testrow" = " + array2d_sudoku(col, testrow) + cr
  137.                 CheckNotify = false
  138.               end if
  139.               return 0
  140.             end if
  141.           next testrow
  142.         end if
  143.       next row
  144.     next next col
  145.  
  146.     ' test columns in row
  147.    int testcol
  148.     for row = 1 to 9
  149.       for col = 1 to 9
  150.         'if array2d_sudoku(col, row) != 0 then
  151.        if sudoku((row-1)*9 + col) != 0 then
  152.           for testcol = col+1 to 9
  153.             'if array2d_sudoku(col, row) = array2d_sudoku(testcol, row) then
  154.            if sudoku((row-1)*9 + col) = sudoku((row-1)*9 + testcol)
  155.               if CheckNotify = true then
  156.                 printl "Error: Row " + row + ", Col " + col + " = " + array2d_sudoku(col, row) +
  157.                        " and Row " + row + ", Col " + testcol + " = " + array2d_sudoku(testcol, row) + cr
  158.                 CheckNotify = false
  159.               end if
  160.               return 0
  161.             end if
  162.           next testcol
  163.         end if
  164.       next col
  165.     next row
  166.  
  167.     ' test boxes
  168.    int BoxX, BoxY, Col_inBox, Row_inBox, TestCol_inBox, TestRow_inBox
  169.     int expr1, expr2
  170.  
  171.     for BoxX = 1 to 3
  172.       for BoxY = 1 to 3
  173.         for Col_inBox = 1 to 3
  174.           for Row_inBox = 1 to 3
  175.             'expr1 = array2d_sudoku(3*(BoxX-1) + Col_inBox, 3*(BoxY-1) + Row_inBox)
  176.            expr1 = sudoku(((3*(BoxY-1) + Row_inBox)-1)*9 + 3*(BoxX-1) + Col_inBox)
  177.             if expr1 != 0 then
  178.               for TestCol_inBox = 1 to 3
  179.                 for TestRow_inBox = 1 to 3
  180.                   'expr2 = array2d_sudoku(3*(BoxX-1) + TestCol_inBox, 3*(BoxY-1) + TestRow_inBox)
  181.                  expr2 = sudoku(((3*(BoxY-1) + TestRow_inBox)-1)*9 + 3*(BoxX-1) + TestCol_inBox)
  182.                   if expr1 = expr2 and (Col_inBox != TestCol_inBox or Row_inBox != TestRow_inBox) then
  183.                     if CheckNotify = true then
  184.                       printl "Error: Box h,v: " + BoxX + ", " + BoxY + " -- Col:Row " + Col_inBox + ":" + Row_inBox +
  185.                              " = Col:Row " + TestCol_inBox + ":" + TestRow_inBox + " (" + expr1 + ")" + cr
  186.                       CheckNotify = false
  187.                     end if
  188.                     return 0
  189.                   end if
  190.                 next TestRow_inBox
  191.               next TestCol_inBox
  192.             end if
  193.           next Row_inBox
  194.         next Col_inBox
  195.       next BoxY
  196.     next BoxX
  197.     return 1
  198.   end function
  199.  
  200.   function solve() as int
  201.     ' recursive brute-force method
  202.    ' check if Sudoku is correct
  203.    count += 1
  204.     if testSudoku() = 0 then return 0
  205.  
  206.     'test next free position
  207.    int col, row, testnum
  208.     for col = 1 to 9
  209.       for row = 1 to 9
  210.         'if array2d_sudoku(col, row) = 0 then
  211.        if sudoku((row-1)*9 + col) = 0 then
  212.           for testnum = 1 to 9
  213.             'array2d_sudoku(col, row) = testnum
  214.            sudoku((row-1)*9 + col) = testnum
  215.             if solve() = true then return true
  216.           next testnum
  217.           'does not fit
  218.          'array2d_sudoku(col,row) = 0
  219.          sudoku((row-1)*9 + col) = 0
  220.           return false
  221.         end if
  222.       next row
  223.     next col
  224.     return true
  225.   end function
  226.  
  227.  
  228.   sub main()
  229.     string ans
  230. loop1:
  231.     setcolor(7, 0)
  232.     if not loadSudoku() then goto loop2
  233.     printSudoku(sudoku[], 5,5)
  234.  
  235.     CheckNotify = true
  236.     if testSudoku() then
  237.       printl : printl "Solving ..."
  238.       count = 0
  239.       if CheckNotify = true then CheckNotify = false
  240.  
  241.       t1 = GetTickCount
  242.       checkForRotate()
  243.       rotate()
  244.       setcolor(11, 0)
  245.       if maxval > 1 then printSudoku(sudoku[], 40,5)
  246.  
  247.       if solve() = false then printl : printl "Solution not possible" : goto loop2
  248.  
  249.       setcolor(7, 0)
  250.       rotate()
  251.  
  252.       t2 = GetTickCount
  253.       printSudoku(sudoku[], 40,5)
  254.       printl : printl  "Elapsed time: " + (t2-t1)/1000 + " seconds"
  255.       printl "Recursive calls: " + count + "   "
  256.     end if
  257.  
  258. loop2:
  259.     printl "Load another file? (Y/N) " : ans = ltrim rtrim(input())
  260.     if lcase(ans) = "y" then goto loop1
  261.   end sub
  262.  
  263.   main()
  264.  

« Last Edit: August 15, 2019, 03:43:12 AM by Arnold »

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4186
    • Oxygen Basic
Re: Backtracking in Oxygenbasic
« Reply #10 on: August 15, 2019, 06:09:18 AM »
Many thanks, Roland,

I'll include this in version 0.2.7 in projectsB\Console\