Welcome, guest | Sign In | My Account | Store | Cart
NOTE: Recipes have moved! Please visit GitHub.com/activestate/code for the current versions.

An enigma for the chess fans is the problem of the Eight Queens, that demands the following one: it is possible to place eight queens in an empty chessboard in way that none is ' attacking ' some another one (that is, without that two queens are in the same line, the same column or the same diagonal line)?

Um enigma para os fãs de xadrez é o problema das Oito Rainhas, que exige o seguinte: é possível colocar oito rainhas em um tabuleiro de xadrez vazio de modo que nenhuma esteja 'atacando' alguma outra (isto é, sem que duas rainhas estejam na mesma linha, na mesma coluna ou na mesma diagonal)?

PS.: Texto retirado do livro: Java Como Programar, Sexta Edição, Capítulo: 15, Pagina: 580, Exercicio: 15.15, H. M. Deitel(Ditel & Associates, Inc.), P. J. Deitel(Deitel & Associates, Inc.).

Python, 226 lines
  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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
#!/usr/bin/env python
# -*- coding: utf-8 -*-

#
#   Problem Of The Eight Queens <Problema das Oito Rainhas>.
#   Copyright (C) 2006 by Nycholas de Oliveira e Oliveira <nycholas@gmail.com>
#
#   This program is free software; you can redistribute it and/or
#   modify it under the terms of the GNU General Public License
#   as published by the Free Software Foundation; either version 2
#   of the License, or (at your option) any later version.
#
#   <Este programa é software livre; você pode redistribuí-lo e/ou modificá-lo sob os
#   termos da Licença Pública Geral GNU conforme publicada pela Free Software Foundation;
#   tanto a versão 2 da Licença, como (a seu critério) qualquer versão posterior.>
#
#   This program is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU General Public License for more details.
#
#   <Este programa é distribuído na expectativa de que seja útil, porém, SEM NENHUMA
#   GARANTIA; nem mesmo a garantia implícita de COMERCIABILIDADE OU ADEQUAÇÃO A UMA 
#   FINALIDADE ESPECÍFICA. Consulte a Licença Pública Geral do GNU para mais detalhes.>
#
#   You should have received a copy of the GNU General Public License
#   along with this program; if not, write to the Free Software
#   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
#
#   <Você deve ter recebido uma cópia da Licença Pública Geral do GNU junto com este 
#   programa; se não, escreva para a Free Software Foundation, Inc., no endereço 59
#   Temple Street, Suite 330, Boston, MA 02111-1307 USA.>
#

#########################################################
# NOME        : Nycholas de Oliveira e Oliveira         #
# E-MAIL      : nycholas@gmail.com                      #
# ICQ         : 114965471                               #
# MSN         : o_lalertom@hotmail.com                  #
# JABBER      : nycholas@jabber.org                     #
# TALK        : nycholas@gmail.com                      #
# DESCRICAO   : Problema das Oito Rainhas               #
# LOCALIZACAO : Uberlândia - MG                         #
# LOCALIZACAO : Brasil                                  #
#########################################################

import random


class OitoRainhas:
	def __init__(self):
		print self.printBegin()
		self.run()
	
	def printBegin(self):
		p = \
		" + Problema das Oito Rainhas\n" \
		"  * Copyright (C) 2006 by Nycholas de Oliveira e Oliveira <nycholas@gmail.com>\n\n" \
		">> Para melhor visualizar o conteúdo impresso em tela, o terminal deve esta setado com a coluna em 42.\n"
		return p
		
	def printRainha(self):
		p = \
		"\n==========================================\n" \
		" + " + str(len(self.posRainha)) + " Rainha\n\n" \
		+ str(self.t)
		return p
		
	def printEnd(self):
		p = \
		"\n\n >> Nycholas de Oliveira e Oliveira - o_lalertom - nycholas@gmail.com"
		return p
		
	def setVars(self):
		self.TABULEIRO = \
		"########\n" \
		"########\n" \
		"########\n" \
		"########\n" \
		"########\n" \
		"########\n" \
		"########\n" \
		"########\n"
		self.VAZIO, self.ATAQUE, self.RAINHA = "#", "+", "*"
		self.posRainha, self.posValida = [], []
		self.t = [list(line) for line in self.TABULEIRO.splitlines()]
		self.posValida = self.setPosValida()
		
	def setPosValida(self):
		l = []
		for y in range(len(self.t)):
			for x in range(len(self.t)):
				l.append([x,y])
		return l
		
	def setRainha(self, x=0, y=0):
		if 0 <= x <= 7 and 0 <= y <= 7:
			if self.t[x][y] == self.VAZIO:
				self.t[x][y] = self.RAINHA
				self.posRainha.append([x, y])
				self.posValida.remove([x, y])
				self.moveX(x, y)
				self.moveY(x, y)
				self.moveXYDir(x, y)
				self.moveXYEsq(x, y)
				print self.printRainha()

	def moveX(self, x=0, y=0):
		if 0 <= x <= 7:
			if self.t[x][y] == self.RAINHA:
				i = (map(lambda x: x == self.RAINHA, self.t[x])).index(True)
				self.t[x][:i] = list(len(self.t[x][:i])*self.ATAQUE)
				self.t[x][i+1:] = list(len(self.t[x][i+1:])*self.ATAQUE)
				for i in range(len(self.t[x])):
					if self.t[x][i] == self.ATAQUE:
						try:
							self.posValida.remove([x, i])
						except ValueError:
							pass
				return True
			else:
				if self.moveX(x+1, y) or self.moveX(x-1, y): pass
				return False
				
	def moveY(self, x=0, y=0):
		if 0 <= y <= 7:
			if self.t[x][y] == self.RAINHA:
				for i in range(len(self.t)):
					if self.t[i][y] <> self.RAINHA:
						self.t[i][y] = self.ATAQUE
						try:
							self.posValida.remove([i, y])
						except ValueError:
							pass
				return True
			else:
				if self.moveY(x, y+1) or self.moveX(x, y-1): pass
				return False
				
	def moveXYDir(self, x=0, y=0):
		if 0 <= x <= 7 and 0 <= y <= 7:
			if self.t[x][y] == self.RAINHA:
				try:
					for i in range(len(self.t[x])):
						if 0 <= (x+i) < len(self.t[x]) and 0 <= (y+i) < len(self.t[x]):
							if self.t[x+i][y+i] <> self.RAINHA:
								self.t[x+i][y+i] = self.ATAQUE
								try:
									self.posValida.remove([x+i, y+i])
								except ValueError:
									pass
				finally:
					for i in range(len(self.t[x])):
						#print (x-i), (y-i), len(self.t[x])
						if 0 <= (x-i) < len(self.t[x]) and 0 <= (y-i) < len(self.t[x]):
							if self.t[x-i][y-i] <> self.RAINHA:
								self.t[x-i][y-i] = self.ATAQUE
								try:
									self.posValida.remove([x-i, y-i])
								except ValueError:
									pass
				return True
			else:
				if self.moveXYDir(x+1, y+1) or self.moveXYDir(x-1, y-1): pass
				return False
	
	def moveXYEsq(self, x=0, y=0):
		if 0 <= x <= 7 and 0 <= y <= 7:
			if self.t[x][y] == self.RAINHA:
				try:
					for i in range(len(self.t[x])):
						if 0 <= (x-i) < len(self.t[x]) and 0 <= (y+i) < len(self.t[x]):
							if self.t[x-i][y+i] <> self.RAINHA:
								self.t[x-i][y+i] = self.ATAQUE
								try:
									self.posValida.remove([x-i, y+i])
								except ValueError:
									pass
				finally:
					for i in range(len(self.t[x])):
						if 0 <= (x+i) < len(self.t[x]) and 0 <= (y-i) < len(self.t[x]):
							if self.t[x+i][y-i] <> self.RAINHA:
								self.t[x+i][y-i] = self.ATAQUE
								try:
									self.posValida.remove([x+i, y-i])
								except ValueError:
									pass
				return True
			else:
				if self.moveXYEsq(x+1, y-1) or self.moveXYEsq(x+1, y-1): pass
				return False
		
	def testVazio(self):
		r = False
		for i in range(8):
			if len(filter(lambda x: x == self.VAZIO, self.t[i])) > 0:
				r = True
			else:
				r = False
		return r
	
	def loop(self):
		try:
			for i in range(8):
				x = self.posValida[random.randrange(0, 7, 1)][0]
				y = self.posValida[random.randrange(0, 7, 1)][1]
				if [x, y] in self.posValida:
					self.setRainha(x, y)
				else:
					continue
		except IndexError:
			pass
		if len(self.posRainha) < 8 and self.testVazio() == True:
			self.loop()
			
	def run(self):
		self.setVars()
		self.setRainha()
		self.loop()
		if 0 <= len(self.posRainha) < 8 and self.testVazio() == False:
			self.run()
		else:
			print self.printEnd()

if __name__ == "__main__":
	oitoRainhas = OitoRainhas()

1 comment

Shalabh Chaturvedi 11 years, 11 months ago  # | flag

Using Generators. I'm not sure how the above solution works. Here is a solution I wrote a while back:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/473832

Created by Nycholas Oliveira e Oliveira on Thu, 2 Feb 2006 (PSF)
Python recipes (4591)
Nycholas Oliveira e Oliveira's recipes (2)

Required Modules

  • (none specified)

Other Information and Tasks