Microsoft Small Basic

Program Listing: CNV255-1

List Program

''' Knight's Domination
''' Version 0.6
''' Copyright © 2012-2016 Nonki Takahashi. The MIT License.
'
' History :
' 0.6 2016-05-29 . Added (CNV255-1)
' 0.51 2016-05-01 Rewrote for knight domination problem. (CNV255-0)
' 0.4 2016-04-16 Solving with depth-first search. (WPV159-0)
' 0.3 2016-04-01 Rewrote for knight's tour. (WPV159)
' 0.2 2013-03-22 Enabled to move chessmen with mouse. (CLP327-0)
' 0.1 2012-08-04 Code for chessmen written in hexadecimal.
' 0.0 2012-08-04 25-line version created. (CLP327)
'
' Reference:
' [1] https://en.wikipedia.org/wiki/Mathematical_chess_problem
'
t0 = Clock.ElapsedMilliseconds
title = "Knight's Domination 0.6"
GraphicsWindow.Title = title
Not = "False=True;True=False;"
CRLF = Text.GetCharacter(13) + Text.GetCharacter(10)
ALPHA = "abcdefghijklmnopqrstuvwxyz"
GraphicsWindow.BackgroundColor = "#003300"
dim = 8
Form()
InitQ()
min = 17
For p = 0 To 65535
num = 0
j = 1
Stack.PushValue("local", p)
While 0 < p
If Math.Remainder(p, 2) = 1 Then
n = q[1][j]
AddKnight()
n = q[2][j]
AddKnight()
n = q[3][j]
AddKnight()
n = q[4][j]
AddKnight()
num = num + 1
EndIf
p = Math.Floor(p / 2)
j = j + 1
EndWhile
p = Stack.PopValue("local")
CheckDomination()
If dominated Then
dom[p] = num
If num < min Then
min = num
buf = Text.Append(buf, p) + CRLF
Controls.SetTextBoxText(tbox, buf)
EndIf
EndIf
j = 1
Stack.PushValue("local", p)
While 0 < p
If Math.Remainder(p, 2) = 1 Then
n = q[1][j]
RemoveKnight()
n = q[2][j]
RemoveKnight()
n = q[3][j]
RemoveKnight()
n = q[4][j]
RemoveKnight()
EndIf
p = Math.Floor(p / 2)
j = j + 1
EndWhile
p = Stack.PopValue("local")
EndFor
Sub AddKnight
''' Add knight
''' param n - posision in the board
' draw knight
nRow = Math.Floor((n - 1) / dim) + 1
nCol = Math.Remainder((n - 1), dim) + 1
knight = Shapes.AddText(pieces["N"])
board[n] = knight
y = pos["y0"] + (dim - nRow) * size
x = pos["x0"] + (nCol - 1) * size
Shapes.Move(knight, x, y - size * 0.12)
If cross[n] <> "" Then
' remove cross
Shapes.Remove(cross[n])
EndIf
For d = 1 To 8
r = nRow + nDir[d]["row"] ' candidate
c = nCol + nDir[d]["col"]
i = (r - 1) * dim + c ' index for board array
If 1 <= r And r <= dim And 1 <= c And c <= dim Then
attacked[i] = attacked[i] + 1
If attacked[i] = 1 And board[i] = "" Then
' draw cross
y1 = pos["y0"] + (dim - r) * size
x1 = pos["x0"] + (c - 1) * size
cross[i] = Shapes.AddText(pieces["X"])
Shapes.Move(cross[i], x1 + size * 0.08, y1 - size * 0.16)
EndIf
EndIf
EndFor
EndSub
Sub CheckDomination
dominated = "True"
For i = 1 To dim * dim
If attacked[i] < 1 And board[i] = "" Then
dominated = "False"
i = dim * dim ' exit For
EndIf
EndFor
EndSub
Sub Form
''' Initialize GUI form
''' return gw - graphics window width
''' return gh - graphics window height
gw = 598
gh = 428
GraphicsWindow.Width = gw
GraphicsWindow.Height = gh
InitBoard()
GraphicsWindow.BrushColor = "Black"
GraphicsWindow.PenColor = "#99000000"
GraphicsWindow.FontSize = 12
tbox = Controls.AddMultiLineTextBox(pos["x0"] + size * dim + 20, pos["y0"])
Controls.SetSize(tbox, 140, gh - 60)
GraphicsWindow.FontSize = size
GraphicsWindow.MouseDown = OnMouseDown
EndSub
Sub OnMouseDown
''' Mouse down event handler
''' return mx - mouse x coordinate
''' return my - mouse y coordinate
''' return mouseDown - "True"
mx = GraphicsWindow.MouseX
my = GraphicsWindow.MouseY
mouseDown = "True"
EndSub
Sub InitBoard
pos = "x0=40;y0=10;" ' left, top position of the board
color = "W=White;B=Black;0=SaddleBrown;1=BurlyWood;"
pieces = "P=♟;N=♞;B=♝;R=♜;Q=♛;K=♚;X=✖;"
nDir[1] = "row=+2;col=+1;" ' directions for a knight
nDir[2] = "row=+2;col=-1;"
nDir[3] = "row=+1;col=+2;"
nDir[4] = "row=+1;col=-2;"
nDir[5] = "row=-1;col=+2;"
nDir[6] = "row=-1;col=-2;"
nDir[7] = "row=-2;col=+1;"
nDir[8] = "row=-2;col=-1;"
nMoves = 0
For i = 1 To dim
ntoa[i] = Text.GetSubText(ALPHA, i, 1)
aton[ntoa[i]] = i
If i < dim / 2 + 1 Then
For j = 1 To i
nMoves = nMoves + 1
next[nMoves] = ntoa[i] + j
EndFor
EndIf
EndFor
size = 48 ' font height and square size
GraphicsWindow.FontSize = size / 2
For i = 1 To dim
x = pos["x0"] + (i - 1) * size
GraphicsWindow.BrushColor = color["W"]
GraphicsWindow.DrawText(x + size * 0.3, pos["y0"] + size * dim, ntoa[i])
EndFor
For j = dim To 1 Step - 1
y = pos["y0"] + (dim - j) * size
GraphicsWindow.BrushColor = color["W"]
GraphicsWindow.DrawText(pos["x0"] - size / 2, y + size * 0.2, j)
For i = 1 To dim
x = pos["x0"] + (i - 1) * size
GraphicsWindow.BrushColor = color[Math.Remainder((i + j), 2)]
GraphicsWindow.FillRectangle(x, y, size, size)
EndFor
EndFor
EndSub
Sub InitQ
i = 0
For nRow = 1 To 4
For nCol = 1 To 4
i = i + 1
n = (nRow - 1) * dim + nCol
q[1][i] = n
rowSave = nRow
row = nCol
col = dim - rowSave + 1
n = (row - 1) * dim + col
q[2][i] = n
rowSave = row
row = col
col = dim - rowSave + 1
n = (row - 1) * dim + col
q[3][i] = n
rowSave = row
row = col
col = dim - rowSave + 1
n = (row - 1) * dim + col
q[4][i] = n
EndFor
EndFor
EndSub
Sub MouseToBoard
''' param mx - mouse x coordinate
''' param my - mouse y coordinate
''' param pos - array for board top left position
''' return nRow - row number
''' return nCol - column number
nRow = dim - Math.Floor((my - pos["y0"]) / size)
nCol = Math.Floor((mx - pos["x0"]) / size) + 1
EndSub
Sub RemoveKnight
''' param n - posision in the board
' remove knight
nRow = Math.Floor((n - 1) / dim) + 1
nCol = Math.Remainder((n - 1), dim) + 1
Shapes.Remove(board[n])
board[n] = ""
If attacked[n] <> "" Then
' draw cross
y = pos["y0"] + (dim - nRow) * size
x = pos["x0"] + (nCol - 1) * size
cross[n] = Shapes.AddText(pieces["X"])
Shapes.Move(cross[n], x + size * 0.08, y - size * 0.16)
EndIf
For d = 1 To 8
r = nRow + nDir[d]["row"] ' candidate
c = nCol + nDir[d]["col"]
i = (r - 1) * dim + c ' index for board array
If 1 <= r And r <= dim And 1 <= c And c <= dim And attacked[i] <> "" Then
attacked[i] = attacked[i] - 1
If attacked[i] = 0 Then
' remove cross
attacked[i] = ""
Shapes.Remove(cross[i])
EndIf
EndIf
EndFor
EndSub