2votos

Despliegue de tropas en SQL

por josejuan usando isqlw hace 6 años

El famosísimo problema de las ocho reinas... ¡en SQL!

Imagina un campo de batalla de 8 filas por 8 columnas, tienes que desplegar tu ejercito de 8 tanques pero has de tener cuidado, no pueden coincidir más de uno en la misma fila, en la misma columna y tampoco en la misma diagonal. Escribe un algoritmo en tu lenguaje preferido que despliegue los tanque en el menor tiempo posible y devuelva la posición de cada uno de ellos. El ejercito que se coloque más rápido gana la batalla.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
DECLARE @t TABLE (x int, y int, primary key(x, y)) 
 
INSERT INTO @t(x, y) VALUES (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0) 
INSERT INTO @t(x, y) SELECT a.x, b.x FROM @t a, @t b 
DELETE FROM @t WHERE y = 0 
 
SELECT    TOP 1 
FROM    @t a 
JOIN    @t b ON a.x - a.y - b.x + b.y <> 0 AND a.x + a.y - b.x - b.y <> 0 AND a.x < b.x AND a.y <> b.y 
JOIN    @t c ON a.x - a.y - c.x + c.y <> 0 AND a.x + a.y - c.x - c.y <> 0 AND a.y <> c.y AND b.x - b.y - c.x + c.y <> 0 AND b.x + b.y - c.x - c.y <> 0 AND b.x < c.x AND b.y <> c.y 
JOIN    @t d ON a.x - a.y - d.x + d.y <> 0 AND a.x + a.y - d.x - d.y <> 0 AND a.y <> d.y AND b.x - b.y - d.x + d.y <> 0 AND b.x + b.y - d.x - d.y <> 0 AND b.y <> d.y AND c.x - c.y - d.x + d.y <> 0 AND c.x + c.y - d.x - d.y <> 0 AND c.x < d.x AND c.y <> d.y 
JOIN    @t e ON a.x - a.y - e.x + e.y <> 0 AND a.x + a.y - e.x - e.y <> 0 AND a.y <> e.y AND b.x - b.y - e.x + e.y <> 0 AND b.x + b.y - e.x - e.y <> 0 AND b.y <> e.y AND c.x - c.y - e.x + e.y <> 0 AND c.x + c.y - e.x - e.y <> 0 AND c.y <> e.y AND d.x - d.y - e.x + e.y <> 0 AND d.x + d.y - e.x - e.y <> 0 AND d.x < e.x AND d.y <> e.y 
JOIN    @t f ON a.x - a.y - f.x + f.y <> 0 AND a.x + a.y - f.x - f.y <> 0 AND a.y <> f.y AND b.x - b.y - f.x + f.y <> 0 AND b.x + b.y - f.x - f.y <> 0 AND b.y <> f.y AND c.x - c.y - f.x + f.y <> 0 AND c.x + c.y - f.x - f.y <> 0 AND c.y <> f.y AND d.x - d.y - f.x + f.y <> 0 AND d.x + d.y - f.x - f.y <> 0 AND d.y <> f.y AND e.x - e.y - f.x + f.y <> 0 AND e.x + e.y - f.x - f.y <> 0 AND e.x < f.x AND e.y <> f.y 
JOIN    @t g ON a.x - a.y - g.x + g.y <> 0 AND a.x + a.y - g.x - g.y <> 0 AND a.y <> g.y AND b.x - b.y - g.x + g.y <> 0 AND b.x + b.y - g.x - g.y <> 0 AND b.y <> g.y AND c.x - c.y - g.x + g.y <> 0 AND c.x + c.y - g.x - g.y <> 0 AND c.y <> g.y AND d.x - d.y - g.x + g.y <> 0 AND d.x + d.y - g.x - g.y <> 0 AND d.y <> g.y AND e.x - e.y - g.x + g.y <> 0 AND e.x + e.y - g.x - g.y <> 0 AND e.y <> g.y AND f.x - f.y - g.x + g.y <> 0 AND f.x + f.y - g.x - g.y <> 0 AND f.x < g.x AND f.y <> g.y 
JOIN    @t h ON a.x - a.y - h.x + h.y <> 0 AND a.x + a.y - h.x - h.y <> 0 AND a.y <> h.y AND b.x - b.y - h.x + h.y <> 0 AND b.x + b.y - h.x - h.y <> 0 AND b.y <> h.y AND c.x - c.y - h.x + h.y <> 0 AND c.x + c.y - h.x - h.y <> 0 AND c.y <> h.y AND d.x - d.y - h.x + h.y <> 0 AND d.x + d.y - h.x - h.y <> 0 AND d.y <> h.y AND e.x - e.y - h.x + h.y <> 0 AND e.x + e.y - h.x - h.y <> 0 AND e.y <> h.y AND f.x - f.y - h.x + h.y <> 0 AND f.x + f.y - h.x - h.y <> 0 AND f.y <> h.y AND g.x - g.y - h.x + h.y <> 0 AND g.x + g.y - h.x - h.y <> 0 AND g.x < h.x AND g.y <> h.y 
 
/* 
--  1 solución en 11 segundos 
1    2    2    6    3    1    4    7    5    4    6    8    7    3    8    5 
 
-- 92 soluciones en 36 segundos 
1    2    2    6    3    1    4    7    5    4    6    8    7    3    8    5 
1    4    2    7    3    1    4    8    5    5    6    2    7    6    8    3 
1    4    2    8    3    1    4    5    5    7    6    2    7    6    8    3 
1    4    2    8    3    1    4    3    5    6    6    2    7    7    8    5 
1    4    2    6    3    1    4    5    5    2    6    8    7    3    8    7 
1    5    2    7    3    1    4    3    5    8    6    6    7    4    8    2 
1    5    2    7    3    1    4    4    5    2    6    8    7    6    8    3 
1    5    2    3    3    1    4    7    5    2    6    8    7    6    8    4 
1    5    2    3    3    1    4    6    5    8    6    2    7    4    8    7 
1    6    2    4    3    1    4    5    5    8    6    2    7    7    8    3 
1    6    2    3    3    1    4    7    5    5    6    8    7    2    8    4 
1    6    2    3    3    1    4    8    5    4    6    2    7    7    8    5 
1    6    2    3    3    1    4    8    5    5    6    2    7    4    8    7 
1    7    2    3    3    1    4    6    5    8    6    5    7    2    8    4 
1    8    2    3    3    1    4    6    5    2    6    5    7    7    8    4 
1    8    2    4    3    1    4    3    5    6    6    2    7    7    8    5 
1    3    2    5    3    2    4    8    5    6    6    4    7    7    8    1 
1    3    2    6    3    2    4    5    5    8    6    1    7    7    8    4 
1    3    2    6    3    2    4    7    5    5    6    1    7    8    8    4 
1    3    2    7    3    2    4    8    5    6    6    4    7    1    8    5 
1    3    2    6    3    2    4    7    5    1    6    4    7    8    8    5 
1    3    2    7    3    2    4    8    5    5    6    1    7    4    8    6 
1    3    2    5    3    2    4    8    5    1    6    7    7    4    8    6 
1    5    2    7    3    2    4    6    5    3    6    1    7    8    8    4 
1    5    2    7    3    2    4    4    5    8    6    1    7    3    8    6 
1    5    2    7    3    2    4    6    5    3    6    1    7    4    8    8 
1    6    2    4    3    2    4    8    5    5    6    7    7    1    8    3 
1    6    2    8    3    2    4    4    5    1    6    7    7    5    8    3 
1    7    2    4    3    2    4    8    5    6    6    1    7    3    8    5 
1    7    2    4    3    2    4    5    5    8    6    1    7    3    8    6 
1    2    2    7    3    3    4    6    5    8    6    5    7    1    8    4 
1    4    2    7    3    3    4    8    5    2    6    5    7    1    8    6 
1    7    2    5    3    3    4    1    5    6    6    8    7    2    8    4 
1    7    2    1    3    3    4    8    5    6    6    4    7    2    8    5 
1    1    2    7    3    4    4    6    5    8    6    2    7    5    8    3 
1    3    2    6    3    4    4    2    5    8    6    5    7    7    8    1 
1    3    2    6    3    4    4    1    5    8    6    5    7    7    8    2 
1    3    2    8    3    4    4    7    5    1    6    6    7    2    8    5 
1    5    2    2    3    4    4    7    5    3    6    8    7    6    8    1 
1    5    2    7    3    4    4    1    5    3    6    8    7    6    8    2 
1    5    2    8    3    4    4    1    5    7    6    2    7    6    8    3 
1    5    2    1    3    4    4    6    5    8    6    2    7    7    8    3 
1    5    2    2    3    4    4    6    5    8    6    3    7    1    8    7 
1    5    2    8    3    4    4    1    5    3    6    6    7    2    8    7 
1    7    2    2    3    4    4    1    5    8    6    5    7    3    8    6 
1    8    2    2    3    4    4    1    5    7    6    5    7    3    8    6 
1    1    2    7    3    5    4    8    5    2    6    4    7    6    8    3 
1    2    2    7    3    5    4    8    5    1    6    4    7    6    8    3 
1    4    2    1    3    5    4    8    5    6    6    3    7    7    8    2 
1    4    2    7    3    5    4    3    5    1    6    6    7    8    8    2 
1    4    2    8    3    5    4    3    5    1    6    7    7    2    8    6 
1    4    2    1    3    5    4    8    5    2    6    7    7    3    8    6 
1    4    2    2    3    5    4    8    5    6    6    1    7    3    8    7 
1    4    2    7    3    5    4    2    5    6    6    1    7    3    8    8 
1    6    2    1    3    5    4    2    5    8    6    3    7    7    8    4 
1    6    2    3    3    5    4    8    5    1    6    4    7    2    8    7 
1    6    2    3    3    5    4    7    5    1    6    4    7    2    8    8 
1    8    2    2    3    5    4    3    5    1    6    7    7    4    8    6 
1    2    2    8    3    6    4    1    5    3    6    5    7    7    8    4 
1    2    2    4    3    6    4    8    5    3    6    1    7    7    8    5 
1    5    2    2    3    6    4    1    5    7    6    4    7    8    8    3 
1    7    2    2    3    6    4    3    5    1    6    4    7    8    8    5 
1    2    2    5    3    7    4    4    5    1    6    8    7    6    8    3 
1    2    2    5    3    7    4    1    5    3    6    8    7    6    8    4 
1    3    2    1    3    7    4    5    5    8    6    2    7    4    8    6 
1    3    2    5    3    7    4    1    5    4    6    2    7    8    8    6 
1    4    2    2    3    7    4    3    5    6    6    8    7    5    8    1 
1    4    2    2    3    7    4    5    5    1    6    8    7    6    8    3 
1    4    2    2    3    7    4    3    5    6    6    8    7    1    8    5 
1    6    2    4    3    7    4    1    5    8    6    2    7    5    8    3 
1    6    2    2    3    7    4    1    5    4    6    8    7    5    8    3 
1    6    2    3    3    7    4    2    5    8    6    5    7    1    8    4 
1    6    2    2    3    7    4    1    5    3    6    5    7    8    8    4 
1    6    2    3    3    7    4    2    5    4    6    8    7    1    8    5 
1    6    2    3    3    7    4    4    5    1    6    8    7    2    8    5 
1    6    2    4    3    7    4    1    5    3    6    5    7    2    8    8 
1    1    2    5    3    8    4    6    5    3    6    7    7    2    8    4 
1    1    2    6    3    8    4    3    5    7    6    4    7    2    8    5 
1    2    2    6    3    8    4    3    5    1    6    4    7    7    8    5 
1    3    2    6    3    8    4    1    5    4    6    7    7    5    8    2 
1    3    2    6    3    8    4    1    5    5    6    7    7    2    8    4 
1    3    2    6    3    8    4    2    5    4    6    1    7    7    8    5 
1    3    2    5    3    8    4    4    5    1    6    7    7    2    8    6 
1    4    2    6    3    8    4    3    5    1    6    7    7    5    8    2 
1    4    2    6    3    8    4    2    5    7    6    1    7    3    8    5 
1    4    2    2    3    8    4    5    5    7    6    1    7    3    8    6 
1    4    2    2    3    8    4    6    5    1    6    3    7    5    8    7 
1    5    2    3    3    8    4    4    5    7    6    1    7    6    8    2 
1    5    2    1    3    8    4    6    5    3    6    7    7    2    8    4 
1    5    2    1    3    8    4    4    5    2    6    7    7    3    8    6 
1    5    2    2    3    8    4    1    5    4    6    7    7    3    8    6 
1    7    2    3    3    8    4    2    5    5    6    1    7    6    8    4 
*/ 
2 comentarios
0votos

Escrito por Marcos Diaz hace 6 años

No me esperaba ver una solución en SQL, te votaré cuando llegue al mínimo de reputación para hacerlo :P
0votos

Escrito por jneira hace 6 años

Este desafio es un duplicado de http://www.solveet.com/exercises/Problema-de-las-ocho-reinas/50

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.