### Author Topic: Backtracking in Oxygenbasic  (Read 1574 times)

0 Members and 1 Guest are viewing this topic.

#### Arnold

• Hero Member
• Posts: 973
##### 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 rtl64uses console! GetTickCount lib "kernel32.dll"int doprintint solutionint size_of_boarddouble t1, t2string anssys *indexsub 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    printlend subfunction 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 1end function' place queen in current rowsub 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 ifend subsub 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 loop1end submain()`
« Last Edit: August 09, 2019, 06:48:02 AM by Arnold »

#### Charles Pegge

• Posts: 4409
##### 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 1end 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 rtl64uses console! GetTickCount lib "kernel32.dll"int doprintint solutionint size_of_boarddouble t1, t2string ansint *indexsub 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 subfunction 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 1end function' place queen in current rowsub 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  endifend subsub 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  endifend submain()`

#### Arnold

• Hero Member
• Posts: 973
##### 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

• Posts: 4409
##### 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

• Posts: 4409
##### 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 rtl64uses console! GetTickCount lib "kernel32.dll"int doprintint solutionint size_of_boarddouble t1, t2string ansint *indexsub 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 rowsub 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  endifend subsub 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  endifend submain()`
« Last Edit: August 10, 2019, 02:09:43 AM by Charles Pegge »

#### Arnold

• Hero Member
• Posts: 973
##### 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

• Guest
##### 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
( i must say that i don't like those console progs.. )

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

#### Charles Pegge

• Posts: 4409
##### 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

• Guest
##### 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

#### Arnold

• Hero Member
• Posts: 973
##### 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.
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
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 »