Test for the Yakist - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

Site Related Forums

The Yak Corral

Test for the Yakist

Author

Topic

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-03 : 07:39:26

OK, Sam.... How about to run chess knight over all
chess board cells? Below, in bold, the 4 possible first moves:

56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
08 09 10 11 12 13 14 15
00 01 02 03 04 05 06 07

And this is a sample of failed chain of moves:

17 00 10 04 14 20 03 09 19 02 08 18 01 11 05 15
21 06 12 22 07 13 23 29 35 25 40 34 24 41 26 16
33 27 37 31 46 36 30 45 39 54 44 50 60 43 28 38
55 61 51 57 42 32 49 59 53 47 62 52 58 48 xx xx

SamC
White Water Yakist

3467 Posts

Posted - 2004-02-03 : 09:20:35

Did ya buy a book on SQL puzzles or did your manager bug you today? This reeks of a revolt against real work. Only a twisted mind would publish such a question.

I don't think it's solvable.

Nope.

Can't be solved.

Got to go now.

SamC
White Water Yakist

3467 Posts

Posted - 2004-02-03 : 09:22:09

I got a solution with a small change to the problem.

I used a rook.

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-03 : 14:50:07

LOL, Sam. I wish you knew how many "problems" I keep in
mind simultaneosly. OK, I just got (already at home) my 1st
Hamilton circuit for the knight on the standard chess board.
Not easy job I would say. True, this is old good VB..........

00 10 04 14 20 03 09 19 02 08 18 01 11 05 15 21
06 12 22 07 13 23 29 35 25 40 34 24 41 56 50 33
16 26 32 49 59 44 38 28 43 60 54 39 45 55 61 51
57 42 48 58 52 62 47 30 36 53 63 46 31 37 27 17

Sub hamC()
Const n = 63, w = 8
Dim s1(n), s2(n), i, j, k, c1, c2, f, ff
For j = 0 To n
s2(j) = j: s1(j) = -1
Next
s2(0) = -1: s1(0) = 0: c1 = 0: c2 = -1: i = 0
While i < n
f = 0
For k = 0 To n
If s2(k) > -1 And s2(k) > c2 Then
If ok(c1, s2(k), w) Then
If zorg(s2, s2(k), c2, w) Then
i = i + 1: s1(i) = s2(k): s2(k) = -1: c1 = s1(i): f = 1
If c2 <> -1 Then
s2(c2) = c2: c2 = -1
End If
Exit For
End If
End If
End If
Next k
If f = 0 Then
If c2 <> -1 Then
s2(c2) = c2
End If
c2 = s1(i): s1(i) = -1: i = i - 1: c1 = s1(i)
End If
Wend
For k = 0 To n
ff = ff & Right("0" & CStr(s1(k)), 2) & _
IIf((k + 1) Mod (2 * w) = 0, vbCrLf, " ")
Next
Debug.Print ff
End Sub

Function zorg(ByVal s, ByVal c, ByVal d, ByVal ww) As Boolean
zorg = False
s(0) = 0: s(c) = c
If d > -1 Then
s(d) = d
End If
Dim a, b, g
For Each a In s
If a > -1 And a <> 0 And a <> c Then
g = 0
For Each b In s
If b > -1 And ok(a, b, ww) Then
g = g + 1
If g > 1 Then
Exit For
End If
End If
Next
If g < 2 Then
Exit Function
End If
End If
Next
zorg = True
End Function

Function ok(ByVal p, ByVal q, ByVal r) As Boolean
ok = False
If ((Abs(p \ r - q \ r) = 1 And Abs(p Mod r - q Mod r) = 2) Or _
(Abs(p \ r - q \ r) = 2 And Abs(p Mod r - q Mod r) = 1)) Then
ok = True
End If
End Function

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-02-04 : 06:08:45

Setup:


CREATE TABLE MovesA (s1 tinyint NOT NULL, s2 tinyint NOT NULL, PRIMARY KEY (s1, s2))

INSERT INTO MovesA
SELECT A.n, B.n
FROM (
    SELECT n, n % 8 AS x, n / 8 AS y
    FROM Numbers
    WHERE n BETWEEN 0 AND 63
  ) AS A
INNER JOIN (
    SELECT n, n % 8 AS x, n / 8 AS y
    FROM Numbers
    WHERE n BETWEEN 0 AND 63
  ) AS B
ON (ABS(A.x - B.x) = 2 AND ABS(A.y - B.y) = 1) OR
   (ABS(A.x - B.x) = 1 AND ABS(A.y - B.y) = 2)
WHERE (A.x + A.y) % 2 = 0

CREATE TABLE MovesB (s1 tinyint NOT NULL, s2 tinyint NOT NULL, PRIMARY KEY (s1, s2))

INSERT INTO MovesB
SELECT A.n, B.n
FROM (
    SELECT n, n % 8 AS x, n / 8 AS y
    FROM Numbers
    WHERE n BETWEEN 0 AND 63
  ) AS A
INNER JOIN (
    SELECT n, n % 8 AS x, n / 8 AS y
    FROM Numbers
    WHERE n BETWEEN 0 AND 63
  ) AS B
ON (ABS(A.x - B.x) = 2 AND ABS(A.y - B.y) = 1) OR
   (ABS(A.x - B.x) = 1 AND ABS(A.y - B.y) = 2)
WHERE (A.x + A.y) % 2 = 1

Find the first one:


SELECT TOP 1 *
FROM MovesA AS M01
INNER JOIN MovesB AS M02 ON M01.s2 = M02.s1
INNER JOIN MovesA AS M03 ON M02.s2 = M03.s1
INNER JOIN MovesB AS M04 ON M03.s2 = M04.s1
INNER JOIN MovesA AS M05 ON M04.s2 = M05.s1
INNER JOIN MovesB AS M06 ON M05.s2 = M06.s1
INNER JOIN MovesA AS M07 ON M06.s2 = M07.s1
INNER JOIN MovesB AS M08 ON M07.s2 = M08.s1
INNER JOIN MovesA AS M09 ON M08.s2 = M09.s1
INNER JOIN MovesB AS M10 ON M09.s2 = M10.s1
INNER JOIN MovesA AS M11 ON M10.s2 = M11.s1
INNER JOIN MovesB AS M12 ON M11.s2 = M12.s1
INNER JOIN MovesA AS M13 ON M12.s2 = M13.s1
INNER JOIN MovesB AS M14 ON M13.s2 = M14.s1
INNER JOIN MovesA AS M15 ON M14.s2 = M15.s1
INNER JOIN MovesB AS M16 ON M15.s2 = M16.s1
INNER JOIN MovesA AS M17 ON M16.s2 = M17.s1
INNER JOIN MovesB AS M18 ON M17.s2 = M18.s1
INNER JOIN MovesA AS M19 ON M18.s2 = M19.s1
INNER JOIN MovesB AS M20 ON M19.s2 = M20.s1
INNER JOIN MovesA AS M21 ON M20.s2 = M21.s1
INNER JOIN MovesB AS M22 ON M21.s2 = M22.s1
INNER JOIN MovesA AS M23 ON M22.s2 = M23.s1
INNER JOIN MovesB AS M24 ON M23.s2 = M24.s1
INNER JOIN MovesA AS M25 ON M24.s2 = M25.s1
INNER JOIN MovesB AS M26 ON M25.s2 = M26.s1
INNER JOIN MovesA AS M27 ON M26.s2 = M27.s1
INNER JOIN MovesB AS M28 ON M27.s2 = M28.s1
INNER JOIN MovesA AS M29 ON M28.s2 = M29.s1
INNER JOIN MovesB AS M30 ON M29.s2 = M30.s1
INNER JOIN MovesA AS M31 ON M30.s2 = M31.s1
INNER JOIN MovesB AS M32 ON M31.s2 = M32.s1
INNER JOIN MovesA AS M33 ON M32.s2 = M33.s1
INNER JOIN MovesB AS M34 ON M33.s2 = M34.s1
INNER JOIN MovesA AS M35 ON M34.s2 = M35.s1
INNER JOIN MovesB AS M36 ON M35.s2 = M36.s1
INNER JOIN MovesA AS M37 ON M36.s2 = M37.s1
INNER JOIN MovesB AS M38 ON M37.s2 = M38.s1
INNER JOIN MovesA AS M39 ON M38.s2 = M39.s1
INNER JOIN MovesB AS M40 ON M39.s2 = M40.s1
INNER JOIN MovesA AS M41 ON M40.s2 = M41.s1
INNER JOIN MovesB AS M42 ON M41.s2 = M42.s1
INNER JOIN MovesA AS M43 ON M42.s2 = M43.s1
INNER JOIN MovesB AS M44 ON M43.s2 = M44.s1
INNER JOIN MovesA AS M45 ON M44.s2 = M45.s1
INNER JOIN MovesB AS M46 ON M45.s2 = M46.s1
INNER JOIN MovesA AS M47 ON M46.s2 = M47.s1
INNER JOIN MovesB AS M48 ON M47.s2 = M48.s1
INNER JOIN MovesA AS M49 ON M48.s2 = M49.s1
INNER JOIN MovesB AS M50 ON M49.s2 = M50.s1
INNER JOIN MovesA AS M51 ON M50.s2 = M51.s1
INNER JOIN MovesB AS M52 ON M51.s2 = M52.s1
INNER JOIN MovesA AS M53 ON M52.s2 = M53.s1
INNER JOIN MovesB AS M54 ON M53.s2 = M54.s1
INNER JOIN MovesA AS M55 ON M54.s2 = M55.s1
INNER JOIN MovesB AS M56 ON M55.s2 = M56.s1
INNER JOIN MovesA AS M57 ON M56.s2 = M57.s1
INNER JOIN MovesB AS M58 ON M57.s2 = M58.s1
INNER JOIN MovesA AS M59 ON M58.s2 = M59.s1
INNER JOIN MovesB AS M60 ON M59.s2 = M60.s1
INNER JOIN MovesA AS M61 ON M60.s2 = M61.s1
INNER JOIN MovesB AS M62 ON M61.s2 = M62.s1
INNER JOIN MovesA AS M63 ON M62.s2 = M63.s1
INNER JOIN MovesB AS M64 ON M63.s2 = M64.s1
WHERE M01.s1 = 0 AND M64.s2 = 0
AND M03.s1 NOT IN (M01.s1)
AND M04.s1 NOT IN (M02.s1)
AND M05.s1 NOT IN (M01.s1,M03.s1)
AND M06.s1 NOT IN (M02.s1,M04.s1)
AND M07.s1 NOT IN (M01.s1,M03.s1,M05.s1)
AND M08.s1 NOT IN (M02.s1,M04.s1,M06.s1)
AND M09.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1)
AND M10.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1)
AND M11.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1)
AND M12.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1)
AND M13.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1)
AND M14.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1)
AND M15.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1)
AND M16.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1)
AND M17.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1)
AND M18.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1)
AND M19.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1)
AND M20.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1)
AND M21.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1)
AND M22.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1)
AND M23.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1)
AND M24.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1)
AND M25.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1)
AND M26.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1)
AND M27.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1)
AND M28.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1)
AND M29.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1)
AND M30.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1)
AND M31.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1)
AND M32.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1)
AND M33.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1)
AND M34.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1)
AND M35.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1)
AND M36.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1)
AND M37.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1)
AND M38.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1)
AND M39.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1)
AND M40.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1)
AND M41.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1)
AND M42.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1)
AND M43.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1)
AND M44.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1)
AND M45.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1)
AND M46.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1)
AND M47.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1)
AND M48.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1)
AND M49.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1)
AND M50.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1)
AND M51.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1,M49.s1)
AND M52.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1,M50.s1)
AND M53.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1,M49.s1,M51.s1)
AND M54.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1,M50.s1,M52.s1)
AND M55.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1,M49.s1,M51.s1,M53.s1)
AND M56.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1,M50.s1,M52.s1,M54.s1)
AND M57.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1,M49.s1,M51.s1,M53.s1,M55.s1)
AND M58.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1,M50.s1,M52.s1,M54.s1,M56.s1)
AND M59.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1,M49.s1,M51.s1,M53.s1,M55.s1,M57.s1)
AND M60.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1,M50.s1,M52.s1,M54.s1,M56.s1,M58.s1)
AND M61.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1,M49.s1,M51.s1,M53.s1,M55.s1,M57.s1,M59.s1)
AND M62.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1,M50.s1,M52.s1,M54.s1,M56.s1,M58.s1,M60.s1)
AND M63.s1 NOT IN (M01.s1,M03.s1,M05.s1,M07.s1,M09.s1,M11.s1,M13.s1,M15.s1,M17.s1,M19.s1,M21.s1,M23.s1,M25.s1,M27.s1,M29.s1,M31.s1,M33.s1,M35.s1,M37.s1,M39.s1,M41.s1,M43.s1,M45.s1,M47.s1,M49.s1,M51.s1,M53.s1,M55.s1,M57.s1,M59.s1,M61.s1)
AND M64.s1 NOT IN (M02.s1,M04.s1,M06.s1,M08.s1,M10.s1,M12.s1,M14.s1,M16.s1,M18.s1,M20.s1,M22.s1,M24.s1,M26.s1,M28.s1,M30.s1,M32.s1,M34.s1,M36.s1,M38.s1,M40.s1,M42.s1,M44.s1,M46.s1,M48.s1,M50.s1,M52.s1,M54.s1,M56.s1,M58.s1,M60.s1,M62.s1)

Only joking!
[Edit: Oops! Had the join conditions the wrong way round]

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-02-04 : 06:39:47

quote:
Originally posted by Stoad
OK, I just got (already at home) my 1st
Hamilton circuit for the knight on the standard chess board.

1 down, 13267364410531 to go!

nr
SQLTeam MVY

12543 Posts

Posted - 2004-02-04 : 07:27:32

Don't know if this will work but should be something like it.
It doesn't avoid things it has already done just tries random moves each time.

set nocount on
create table #a (i int, j int)
declare @i int, @j int
select @i = 0, @j = 1

while @i < 8
begin
select @i = @i + 1
insert #a select @i, @j
end
while @j < 8
begin
select @j = @j + 1
insert #a select i, @j from #a where j = 1
end
select * into #b from #a

select @i = 1, @j = 1
create table #moves (i int, j int, id int identity)
insert #moves select 2,-1
insert #moves select 2,1
insert #moves select 1,2
insert #moves select -1,2
insert #moves select -2,1
insert #moves select -2,-1
insert #moves select -1,-2
insert #moves select 1,-2

create table #MoveDone (i int, j int, id int identity)

-- now lets try 1000 times - selecting random moves each time
set nocount on
declare @runs int, @Best int
select @runs = 1000, @Best = 0
while @runs > 0 and 64 > (select max(id) from #MoveDone)
begin
select @runs = @runs - 1
truncate table #MoveDone
delete #b
insert #b select * from #a
declare @i int, @j int
select @i = 1, @j = 1
declare @MoveID int, @MoveAttempt int
select @MoveAttempt = 0
while @MoveAttempt < 9 and 64 > (select count(*) from #MoveDone)
begin
select @MoveAttempt = 0
select @MoveID = convert(int,rand() * 8 + 1)
while @MoveAttempt < 9 and not exists (select * from #b, #moves where #b.i = @i + #moves.i and #b.j = @j + #moves.j and #moves.id = @MoveID)
begin
select @MoveAttempt = @MoveAttempt + 1 ,
@MoveID = case when @MoveID = 8 then 1 else @MoveID + 1 end
end
if @MoveAttempt < 9
begin
select @i = @i + i, @j = @j + j from #Moves where id = @MoveID
delete #b where i = @i and j = @j
insert #MoveDone select @i, @j
end
end
if @Best < (select max(id) from #MoveDone)
select @Best = max(id) from #MoveDone
end
select bestattempt = @Best

second run got 63 moves

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-04 : 07:56:25

lol >>

SQL XTreme....

quote:
1 down, 13267364410531 to go!

No problem:

00 10 04 14 20 03 09 19 02 08 18 01 11 05 15 21
06 12 22 07 13 23 29 35 25 40 34 24 41 56 50 33
16 26 32 49 59 44 38 28 43 60 54 39 45 55 61 51
57 42 48 58 52 62 47 30 36 53 63 46 31 37 27 17

00 10 04 14 20 03 09 19 02 08 18 01 11 05 15 21
06 12 22 07 13 23 29 35 25 40 34 24 41 56 50 33
16 26 32 49 59 44 54 39 45 60 43 28 38 55 61 51
57 42 48 58 52 62 47 30 36 53 63 46 31 37 27 17

00 10 04 14 20 03 09 19 02 08 18 01 11 05 15 21
06 12 22 07 13 23 29 35 25 40 34 24 41 56 50 33
16 26 32 49 59 44 61 55 38 28 43 60 54 39 45 30
36 51 57 42 48 58 52 62 47 53 63 46 31 37 27 17

00 10 04 14 20 03 09 19 02 08 18 01 11 05 15 21
06 12 22 07 13 23 29 35 25 40 34 24 41 56 50 33
16 26 32 49 59 44 61 55 38 28 43 60 54 39 45 30
47 62 52 58 48 42 57 51 36 53 63 46 31 37 27 17

00 10 04 14 20 03 09 19 02 08 18 01 11 05 15 21
06 12 22 07 13 23 29 35 25 40 34 24 41 56 50 33
16 26 32 49 59 44 61 55 38 28 43 60 54 39 45 51
57 42 48 58 52 62 47 30 36 53 63 46 31 37 27 17

nr
SQLTeam MVY

12543 Posts

Posted - 2004-02-04 : 08:17:53

Does the square you start at count or do you have to return to it?
From the example I thought you had to return but from this you don't.

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

nr
SQLTeam MVY

12543 Posts

Posted - 2004-02-04 : 08:23:46

Counting the start position as taken quickly gives (hope it's right)
(
just add
delete #b where i = @i and j = @j
insert #MoveDone select @i, @j
after
select @i = 1, @j = 1
)

i j id
----------- ----------- -----------
1 1 1
3 2 2
5 1 3
7 2 4
8 4 5
7 6 6
8 8 7
6 7 8
4 8 9
2 7 10
1 5 11
2 3 12
3 1 13
5 2 14
7 1 15
8 3 16
7 5 17
8 7 18
6 8 19
4 7 20
2 8 21
3 6 22
1 7 23
3 8 24
2 6 25
1 8 26
3 7 27
1 6 28
2 4 29
1 2 30
3 3 31
2 1 32
1 3 33
3 4 34
4 6 35
2 5 36
4 4 37
6 3 38
5 5 39
4 3 40
6 2 41
8 1 42
7 3 43
6 5 44
7 7 45
5 8 46
6 6 47
8 5 48
6 4 49
5 6 50
3 5 51
1 4 52
2 2 53
4 1 54
5 3 55
4 5 56
5 7 57
7 8 58
8 6 59
7 4 60
8 2 61
6 1 62
4 2 63
5 4 64

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-04 : 09:48:21

Not sure what exactly you mean, Nigel. My enumeration of
the board squares is as follows:

56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
08 09 10 11 12 13 14 15
00 01 02 03 04 05 06 07

So, the result
00 10 04 14 20 03 09 19 02 08 18 01 11 05 15 21
06 12 22 07 .. .. .. .. and so on .. .. .. .. .. .. .. 17
meaning is pretty obvious. Plus, the condition to find
circuit is embedded into my code. That is why
all my chains of moves end up with square 17.

Edit: see nr's sample of NON-circuit path in the previous post.

nr
SQLTeam MVY

12543 Posts

Posted - 2004-02-04 : 10:08:30

It was the first four possible moves you gave in the question that confused me.
Guess it was 3 moves and you started from 17.
Mine starts from a corner but that could be randomised too.

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-04 : 14:24:16

Nice (and working) idea - "to randomize it".

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2004-02-04 : 15:45:11

To be honest, I'm finding Nigel's code a bit difficult to understand -- too many random numbers! Is it (deliberately or accidentally) using Warnsdorff's algorithm?

http://mathworld.wolfram.com/KnightsTour.html

Here's my attempt at Warnsdorff: it seems generate a path about 98% of the time, but a circuit only about 2%.


CREATE TABLE Moves(
  s1 tinyint NOT NULL,
  s2 tinyint NOT NULL,
  PRIMARY KEY (s1,s2)
)

CREATE TABLE Squares(i int IDENTITY(1,1) PRIMARY KEY,
  s tinyint NOT NULL UNIQUE, ct int NOT NULL)

INSERT INTO Moves
SELECT N1.n, N2.n
FROM Numbers AS N1
INNER JOIN Numbers AS N2
ON (ABS(N1.n %8 - N2.n%8) = 2 AND ABS(N1.n /8 - N2.n/8) = 1)
OR (ABS(N1.n %8 - N2.n%8) = 1 AND ABS(N1.n /8 - N2.n/8) = 2)
WHERE N1.n BETWEEN 0 AND 63
  AND N2.n BETWEEN 0 AND 63

DECLARE @i int
SET @i = 0
WHILE @i < 100 BEGIN
  SET @i = @i + 1

  SET NOCOUNT ON

  TRUNCATE TABLE Squares
  
  INSERT INTO Squares (s, ct)
  SELECT TOP 1 s1, 2
  FROM Moves
  GROUP BY s1
  ORDER BY COUNT(*)
  
  WHILE 1=1 BEGIN
    INSERT INTO Squares (s, ct)
    SELECT TOP 1 s, ct
    FROM (
        SELECT TOP 1 WITH TIES s2 AS s, (
            SELECT COUNT(*)
            FROM Moves AS B
            WHERE A.s2 = B.s1
              AND s2 NOT IN (SELECT s FROM Squares)
          ) AS ct
        FROM Moves AS A
        WHERE s1 = (SELECT TOP 1 s FROM Squares ORDER BY i DESC)
          AND s2 NOT IN (SELECT s FROM Squares)
        ORDER BY ct
      ) AS A
    ORDER BY NEWID()
    
    IF @@ROWCOUNT = 0 BREAK
  END

  SET NOCOUNT OFF

  IF (SELECT COUNT(*) FROM Squares) = 64 AND EXISTS(
    SELECT * FROM Moves
    WHERE s1 = (SELECT TOP 1 s FROM Squares ORDER BY i ASC)
      AND s2 = (SELECT TOP 1 s FROM Squares ORDER BY i DESC))
  BEGIN
    SELECT i, s%8, s/8, ct
    FROM Squares
    ORDER BY i
  END
END

nr
SQLTeam MVY

12543 Posts

Posted - 2004-02-04 : 16:32:06

I don't know anything about the theory of this.
It just picks a random move - if that square isn't available it tries the other 7 in turn and takes the first that is and keeps going until it can't move.

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

SamC
White Water Yakist

3467 Posts

Posted - 2004-02-05 : 12:27:13

I looked for the solution to the Knights problem on the web, and found that the problem requires that a knight doesn't land on the same place twice.

It may be that there are some starting points that cannot succeed.

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-05 : 15:00:18

>> A. F.
Great (but I can test it only tomorrow - how fast it produces circuits).
Plus, I don't see so far where in the code a backtracking part. I suppose
there is no any. Think the ORDER BY NEWID() took its place (with
"intermittent" success while in the outer "while" loop). Not sure but I believe
that Warnsdorff meant "backtracking" + "playing with the successors". I will
try to use his idea in my code - which is extremely plain: "backtracking" +
"checking (zorg() function) before each move will (or not) some not-visited
"remote" square be left deadlocked (i.e., left with less than 2 "exits" from it)".

>>nr

quote:
I don't know anything about the theory of this.

In fact there is no any theory of this. Only some fuzzy euristics.

>>SamC

quote:
It may be that there are some starting points that cannot succeed.

Do you mean succeed with circuits? (lol, it's just a stoad crack)

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-06 : 04:06:30

>> Arnold Fribble <<

Works fine and pretty fast, however in vb it is about 10 times faster.

PS Here I mean only hamilton circuits.

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2004-02-06 : 08:35:22

The WITH TIES + ORDER BY NEWID() .... it's very clever I think.

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2004-02-08 : 18:16:10

Ahh Chess... My pet SQL project at the moment.....

I won't bore you with the details but the query below shows every possible Knight move on the board..


Select A.Square, B.Square
from RealBoard A CROSS JOIN RealBoard B
WHERE dbo.KnightValidMove(A.Square, B.Square) = 1

It returns 336 possible moves.. Can anyone confirm that?

DavidM

"SQL-3 is an abomination.."

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2004-02-08 : 20:22:27

Yep. that's what I got.


select x as StartX, y as StartY,
    x + (H.Squares * Horiz.Mult) as EndX,
    y + ((3- H.Squares) * Vert.Mult) as EndY
from
(select 1 as Mult union select -1 as Mult) Horiz
cross join
(select 1 as Mult union select -1 as Mult) Vert
cross join
(select 1 as Squares union select 2)  H
cross join
(select 1 as X union all select 2 union all select 3 union all select 4 union all
 select 5 union all select 6 union all select 7 union all select 8) A
cross join
(select 1 as Y union all select 2 union all select 3 union all select 4 union all
 select 5 union all select 6 union all select 7 union all select 8) B
where
   x + (H.Squares * Horiz.Mult) between 1 and 8 AND
   y + ((3-H.Squares) * Vert.Mult) between 1 and 8

- Jeff

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources