Knight's tour: Difference between revisions

Line 5,797:

=={{header|Phix}}==

This is pretty fast (<<1s) up to size 48, before some sizes start to take quite some time to complete. It will even solve a 200x200 in 0.67s

<lang Phix>~~constant size = 8~~

with javascript_semantics

constant nchars = length(sprintf(" %d",size*size))

constant size = 8,

constant fmt = sprintf(" %%%dd",nchars-1)

nchars = length(sprintf(" %d",size*size)),

constant blank = repeat(' ',nchars)

fmt = sprintf(" %%%dd",nchars-1),

blank = repeat(' ',nchars)

-- to simplify output, each square is nchars

sequence board = repeat(repeat(' ',size*nchars),size)

-- to simplify output, each square is nchars

-- keep current counts, immediately backtrack if any hit 0

sequence board = repeat(repeat(' ',size*nchars),size)

-- (in line with the above, we only use every nth entry)

-- keep current counts, immediately backtrack if any hit 0

sequence warnsdorffs = repeat(repeat(0,size*nchars),size)

-- (in line with the above, we only use every nth entry)

sequence warnsdorffs = repeat(repeat(0,size*nchars),size)

constant ROW = 1, COL = 2

constant moves = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}}

constant ROW = 1, COL = 2,

moves = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}}

function onboard(integer row, integer col)

return row>=1 and row<=size and col>=nchars and col<=nchars*size

function onboard(integer row, integer col)

end function

return row>=1 and row<=size and col>=nchars and col<=nchars*size

end function

procedure init_warnsdorffs()

integer nrow,ncol

procedure init_warnsdorffs()

for row=1 to size do

for row=1 to size do

for col=nchars to nchars*size by nchars do

for col=nchars to nchars*size by nchars do

for move=1 to length(moves) do

for move=1 to length(moves) do

nrow = row+moves[move][ROW]

integer nrow = row+moves[move][ROW],

ncol = col+moves[move][COL]*nchars

ncol = col+moves[move][COL]*nchars

if onboard(nrow,ncol) then

if onboard(nrow,ncol) then

warnsdorffs[row][col] += 1

warnsdorffs[nrow][ncol] += 1

end if

end if

end for

end for

end for

end for

end for

end for

end procedure

end procedure

atom t0 = time()

atom t0 = time(),

integer tries = 0

t1 = time()+1

atom t1 = time()+1

integer tries = 0

function solve(integer row, integer col, integer n)

function solve(integer row, integer col, integer n)

integer nrow, ncol

if time()>t1 and platform()!=JS then

if time()>t1 then

?{row,floor(col/nchars),n,tries}

?{row,floor(col/nchars),n,tries}

puts(1,join(board,"\n"))

puts(1,join(board,"\n"))

t1 = time()+1

t1 = time()+1

end if

-- if wait_key()='!' then ?9/0 end if

tries+= 1

end if

if n>size*size then return 1 end if

tries+= 1

sequence wmoves = {}

if n>size*size then return 1 end if

integer nrow, ncol

sequence wmoves = {}

for move=1 to length(moves) do

for move=1 to length(moves) do

nrow = row+moves[move][ROW]

nrow = row+moves[move][ROW]

ncol = col+moves[move][COL]*nchars

ncol = col+moves[move][COL]*nchars

if onboard(nrow,ncol)

if onboard(nrow,ncol)

and board[nrow][ncol]=' ' then

and board[nrow][ncol]=' ' then

wmoves = append(wmoves,{warnsdorffs[nrow][ncol],nrow,ncol})

wmoves = append(wmoves,{warnsdorffs[nrow][ncol],nrow,ncol})

end if

end if

end for

end for

wmoves = sort(wmoves)

wmoves = sort(wmoves)

-- avoid creating orphans

-- avoid creating orphans

if length(wmoves)<2 or wmoves[2][1]>1 then

if length(wmoves)<2 or wmoves[2][1]>1 then

for m=1 to length(wmoves) do

for m=1 to length(wmoves) do

{?,nrow,ncol} = wmoves[m]

{?,nrow,ncol} = wmoves[m]

warnsdorffs[nrow][ncol] -= 1

warnsdorffs[nrow][ncol] -= 1

end for

end for

for m=1 to length(wmoves) do

for m=1 to length(wmoves) do

{?,nrow,ncol} = wmoves[m]

{?,nrow,ncol} = wmoves[m]

integer scol = ncol-nchars+1

board[nrow][ncol-nchars+1..ncol] = sprintf(fmt,n)

board[nrow][scol..ncol] = sprintf(fmt,n)

if solve(nrow,ncol,n+1) then return 1 end if

if solve(nrow,ncol,n+1) then return 1 end if

board[nrow][ncol-nchars+1..ncol] = blank

board[nrow][scol..ncol] = blank

end for

end for

for m=1 to length(wmoves) do

for m=1 to length(wmoves) do

{?,nrow,ncol} = wmoves[m]

{?,nrow,ncol} = wmoves[m]

warnsdorffs[nrow][ncol] += 1

warnsdorffs[nrow][ncol] += 1

end for

end for

end if

end if

return 0

return 0

end function

end function

init_warnsdorffs()

init_warnsdorffs()

board[1][nchars] = '1'

board[1][nchars] = '1'

if solve(1,nchars,2) then

if solve(1,nchars,2) then

puts(1,join(board,"\n"))

puts(1,join(board,"\n"))

printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0})

printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0})

else

else

puts(1,"no solutions found\n")

puts(1,"no solutions found\n")

end if

end if

~~{} = wait_key()~~</lang>

<pre>