N-Bishops Puzzle - Revision history

Michael Leuschel at 14:52, 18 February 2016

2016-02-18T14:52:06Z

← Older revision		Revision as of 14:52, 18 February 2016
Line 53:		Line 53:

	For the chess pieces we have used the images available at [https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces wikimedia.org].		For the chess pieces we have used the images available at [https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces wikimedia.org].
	These images are available under the [https://en.wikipedia.org/wiki/Creative_Commons Creative Commons] [https://creativecommons.org/licenses/by-sa/3.0/deed.en Attribution-Share Alike 3.0 Unported license]. The same applies to the screenshots shown ~~below~~.		These images are available under the [https://en.wikipedia.org/wiki/Creative_Commons Creative Commons] [https://creativecommons.org/licenses/by-sa/3.0/deed.en Attribution-Share Alike 3.0 Unported license]. The same applies to the screenshots shown here.

Michael Leuschel at 14:51, 18 February 2016

2016-02-18T14:51:52Z

← Older revision		Revision as of 14:51, 18 February 2016
Line 47:		Line 47:
	</pre>		</pre>

	~~For the chess pieces we have used the images available at [https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces wikimedia.org].~~
	This will lead to ProB to show the solution graphically, as follows:		This will lead to ProB to show the solution graphically, as follows:

	[[File:ProB_Bishops_8_14_Screenshot.png\|300px\|center]]		[[File:ProB_Bishops_8_14_Screenshot.png\|300px\|center]]

			For the chess pieces we have used the images available at [https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces wikimedia.org].
			These images are available under the [https://en.wikipedia.org/wiki/Creative_Commons Creative Commons] [https://creativecommons.org/licenses/by-sa/3.0/deed.en Attribution-Share Alike 3.0 Unported license]. The same applies to the screenshots shown below.

Michael Leuschel at 14:46, 18 February 2016

2016-02-18T14:46:01Z

← Older revision		Revision as of 14:46, 18 February 2016
Line 47:		Line 47:
	</pre>		</pre>

			For the chess pieces we have used the images available at [https://commons.wikimedia.org/wiki/Category:SVG_chess_pieces wikimedia.org].
	This will lead to ProB to show the solution graphically, as follows:		This will lead to ProB to show the solution graphically, as follows:

	[[File:ProB_Bishops_8_14_Screenshot.png\|~~600px~~\|center]]		[[File:ProB_Bishops_8_14_Screenshot.png\|300px\|center]]

Michael Leuschel at 14:43, 18 February 2016

2016-02-18T14:43:33Z

← Older revision		Revision as of 14:43, 18 February 2016
Line 26:		Line 26:
	</pre>		</pre>

	The maximum number of bishops ~~tath~~ can be placed is 2*n - 2; see http://mathworld.wolfram.com/BishopsProblem.html		One can try and find the maximum number of bishops by gradually increasing the lower limit for nbishops in the last line of the model before the final END.
			The maximum number of bishops that can be placed is 2*n - 2; see http://mathworld.wolfram.com/BishopsProblem.html.


			ProB 1.5.1 can solve this puzzle with <tt>nbishops >13</tt> in about half a second.

			One can use [[Graphical_Visualization\|graphical visualisation]] features to display the solution, by declaring the ANIMATION FUNCTION inside the DEFINITIONS section as follows:

			<pre>
			DEFINITIONS
			BWOFFSET(x,y) == (x+y) mod 2;
			ANIMATION_FUNCTION_DEFAULT == ( {r,c,i\|r:1..n & c:1..n & i=(r+c) mod 2 } );
			ANIMATION_FUNCTION == {r,c,i\|(r,c):hasbishop & i= 2+BWOFFSET(r,c)} ;
			ANIMATION_IMG0 == "ChessPieces/Chess_emptyl45.gif";
			ANIMATION_IMG1 == "ChessPieces/Chess_emptyd45.gif";
			ANIMATION_IMG2 == "ChessPieces/Chess_bll45.gif";
			ANIMATION_IMG3 == "ChessPieces/Chess_bld45.gif";
			SET_PREF_TK_CUSTOM_STATE_VIEW_PADDING == 1;
			END
			</pre>

			This will lead to ProB to show the solution graphically, as follows:

			[[File:ProB_Bishops_8_14_Screenshot.png\|600px\|center]]

Michael Leuschel: Created page with "This puzzle is a variation of the N-Queens puzzle: we try to place as many bishops as possible on a n by n chess board. In contrast to the N-Queens puzzle, one can place m..."

2016-02-18T14:37:12Z

Created page with "This puzzle is a variation of the N-Queens puzzle: we try to place as many bishops as possible on a n by n chess board. In contrast to the N-Queens puzzle, one can place m..."

New page

This puzzle is a variation of the [[N-Queens]] puzzle: we try to place as many bishops as possible on a n by n chess board.
In contrast to the N-Queens puzzle, one can place more than one bishop per row.
As such, we can now longer represent the positions of the bishops as an total function <tt>1..n >-> 1..n</tt>.
There are two encodings we show below.
The first represents the bishops as a subset of the Cartesian product <tt>(1..n)*(1..n)</tt>, i.e., a set of positions (aka a binary relation on <tt>1..n</tt>).

<pre>
MACHINE NBishopsSets
CONSTANTS n, nbishops, hasbishop
PROPERTIES
n=8 &
hasbishop <: (1..n)*(1..n) &
!(i,j).(i:1..n & j:1..n
=>
( (i,j): hasbishop
=>
(!k.(k:(i+1)..n =>
(k,j+k-i) /: hasbishop &
(k,j-k+i) /: hasbishop
))
))
& nbishops = card(hasbishop)
& nbishops >13
END
</pre>

The maximum number of bishops tath can be placed is 2*n - 2; see http://mathworld.wolfram.com/BishopsProblem.html