How many Wazirs can be placed on an N×N Chessboard?

Question

Suppose a new fairy chess piece named the Wazir is introduced to chess. Wazirs can move from a position (x, y) to:
(x+1, y)
(x, y+1)
(x-1, y)
(x, y-1)

That is, they move orthogonally like the rook, but only one step at a time like the king. How many such wazirs can be placed on an N×N chessboard so that no two wazirs can attack each other?

On a 1×1 board, there can be only 1 such piece.
On a 2×2 board, there can be 2 such pieces.
On a 3×3 board, there can be 5 such pieces.

Given N, return the number of wazirs that can be placed on an N×N chessboard.

This is OEIS sequence A000982.

More test cases

7 → 25

8 → 32

100 → 5000

So the Camel is to the Rook what the King is to the Queen? I.e. can only move orthogonally, and only one step at a time. — Adám, Oct 2, 2017 at 8:32
@SashaR May I rewrite your question as a proper code golf challenge? — Adám, Oct 2, 2017 at 9:09
As a new user of this site, you've been very lucky this time. A lot of (off-topic) programming questions on this site has been permanently closed and downvoted, not edited as a challenge and upvoted like this one. As other people already explained, this site is for programming competitions only, not for asking homework. You can use the sandbox (at codegolf.meta.stackexchange.com/questions/2140/… ) before posting a challenge to avoid common mistakes next time; and note that most users on this site, as you have seen, use "unreadable" languages. — DELETE_ME, Oct 2, 2017 at 14:52
This question is pretty confusing in that the Camel is already the standard fairy chess name for a piece like a knight that makes longer jumps and the piece you describe already has a fairy chess name: Wazir. — Mark S., Oct 3, 2017 at 11:26
OTOH editing the question to the the standard name after answers have already been written using the name used in the question is also confusing. — Peter Green, Oct 4, 2017 at 8:40

Lynn · Accepted Answer · 2017-10-04 13:12:02Z

33

Whitespace, 45 bytes

Try it online!

By the way, here is a proof that the ⌈n²/2⌉ formula is correct.

We can always place at least ⌈n²/2⌉ wazirs: just lay them out in a checkerboard pattern! Assuming the top-left tile is white, there are ⌈n²/2⌉ white tiles and ⌊n²/2⌋ black tiles on the n × n board. And if we place wazirs on the white tiles, no two of them are attacking each other, as every wazir only “sees” black tiles.

Here’s how we place 13 wazirs on a 5 × 5 board (each W is a wazir).

　　　　　　　　　　
We can’t do any better: let’s arbitrarily tile the checkerboard with 2 × 1 domino pieces, optionally using a 1 × 1 piece for the final corner of an odd-length chessboard, like so:

　　　　　　　　　　

We need ⌈n²/2⌉ dominoes to cover the chessboard. Clearly, putting two wazirs on one domino makes it so that they can attack one another! So each domino can only contain at most one wazir, meaning we can’t possibly place more than ⌈n²/2⌉ wazirs on the board.

edited Oct 4, 2017 at 13:12

answered Oct 2, 2017 at 20:39

Lynn

68.1k11 gold badges130 silver badges279 bronze badges

\$\begingroup\$ You don't need the pigeonhole principle for the last part: you have exactly ⌈n²/2⌉ tiles, and at most camel per tile, so you have at most ⌈n²/2⌉ camels. \$\endgroup\$
– ShreevatsaR
Oct 3, 2017 at 7:29
8

\$\begingroup\$ @ShreevatsaR What ensures you that you can't put x > ⌈n²/2⌉ camels in ⌈n²/2⌉ tiles? It's the pigeonhole principle... \$\endgroup\$
– frarugi87
Oct 3, 2017 at 7:58
2

\$\begingroup\$ I thought at first the code didn't load, so I refreshed the page, and it still didn't. Then I realized what language name was written at the top. \$\endgroup\$
– Arthur
Oct 4, 2017 at 9:28
7

\$\begingroup\$ I appreciate that you went and changed your C's to W's in your proof illustration. \$\endgroup\$
– Giuseppe
Oct 4, 2017 at 13:39
4

\$\begingroup\$ I also appreciate that the W's are all on the WHITE SPACES with an answer in WHITESPACE. \$\endgroup\$
– corsiKa
Oct 4, 2017 at 16:13

| Show 4 more comments

Leaky Nun · Accepted Answer · 2017-10-02 12:55:43Z

16

Oasis, 3 bytes

k>v

Try it online!

square - increment - integer halve

answered Oct 2, 2017 at 12:55

Leaky Nun

49.6k6 gold badges107 silver badges281 bronze badges

Add a comment |

Emigna · Accepted Answer · 2017-10-02 14:05:25Z

11

Prolog (SWI), 22 19 bytes

Saved 3 bytes thanks to Kevin Cruijssen

X*Y:-Y is(X*X+1)/2.

Try it online!

edited Oct 2, 2017 at 14:05

answered Oct 2, 2017 at 12:39

Emigna

52.9k5 gold badges42 silver badges162 bronze badges

\$\begingroup\$ X*Y:-Y is(X*X+1)/2. (19 bytes) \$\endgroup\$
– Kevin Cruijssen
Oct 2, 2017 at 13:43
2

\$\begingroup\$ @KevinCruijssen: Doh! I suggested the same change to another user, but somehow I didn't take my own advice. Thank you :) \$\endgroup\$
– Emigna
Oct 2, 2017 at 14:06

Add a comment |

Adám · Accepted Answer · 2017-10-02 12:19:55Z

10

APL (Dyalog), 9 7 6 bytes

Now uses Mr. Xcoder's formula.

This is an anonymous prefix tacit function which takes N as argument.

⌈2÷⍨×⍨

Try it online!

×⍨ square N (lit. multiplication selfie, i.e. multiply by self)

2÷⍨ divide by 2

⌈ ceiling (round up)

edited Oct 2, 2017 at 12:19

answered Oct 2, 2017 at 8:38

Adám

29.9k2 gold badges119 silver badges286 bronze badges

\$\begingroup\$ Wow!I have no idea how you did this !!Didn't get the logic thoughsigh \$\endgroup\$
– Sasha R
Oct 2, 2017 at 8:49
\$\begingroup\$ Darn, someone already found out the pattern. \$\endgroup\$
– Feathercrown
Oct 2, 2017 at 18:26
1

\$\begingroup\$ Huh, just realized the formula is on the OEIS page. Probably shouldn't have linked that. \$\endgroup\$
– Feathercrown
Oct 2, 2017 at 18:27

Add a comment |

Arnauld · Accepted Answer · 2017-10-02 16:48:04Z

7

JS (ES6) / C# polyglot, 11 bytes

n=>n*n+1>>1

Test cases

let f =

n=>n*n+1>>1

console.log(f(7))
console.log(f(8))
console.log(f(100))

edited Oct 2, 2017 at 16:48

answered Oct 2, 2017 at 12:55

Arnauld

189k20 gold badges171 silver badges631 bronze badges

3

\$\begingroup\$ C# polyglot \$\endgroup\$
– Shaggy
Oct 2, 2017 at 16:41
\$\begingroup\$ @Shaggy Thanks for noticing! \$\endgroup\$
– Arnauld
Oct 2, 2017 at 16:49
1

\$\begingroup\$ JS and C# polyglot seems extremely rare, given the differences between them. +1 \$\endgroup\$
– caird coinheringaahin g ♦
Oct 4, 2017 at 11:36

Add a comment |

Emigna · Accepted Answer · 2017-10-02 12:29:53Z

6

05AB1E, 3 bytes

Straight implementation of the formula given by A000982

n;î

Try it online!

Explanation

n      # square
 ;     # divide by 2
  î    # round up

answered Oct 2, 2017 at 12:29

Emigna

52.9k5 gold badges42 silver badges162 bronze badges

\$\begingroup\$ *;î works too \$\endgroup\$
– Makonede
May 10, 2021 at 21:45

Add a comment |

brhfl · Accepted Answer · 2017-10-02 18:46:25Z

6

dc, 6 bytes

2^2~+p

2^: square; 2~: divide by 2, pushing the quotient then the remainder; +p: add the remainder to the quotient & print.

Try it online!

answered Oct 2, 2017 at 18:46

brhfl

1,47111 silver badges13 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-10-02 16:35:09Z

5

Python 2, 17 bytes

1 byte thanks to @ovs.

lambda x:x*x+1>>1

Try it online!

edited Oct 2, 2017 at 16:35

answered Oct 2, 2017 at 13:03

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

\$\begingroup\$ Alternatively: lambda x:-~x**2/2 \$\endgroup\$
– RoryT
Oct 2, 2017 at 23:46

Add a comment |

Jonathan Frech · Accepted Answer · 2017-10-03 22:23:28Z

5

C (gcc), 23 18 17 bytes

Saved a byte thanks to Tahg; golfing n/2+n%2 to n+1>>1.

f(n){n=n*n+1>>1;}

Try it online!

C (gcc), 22 bytes (not using undefined behavior)

f(n){return n*n+1>>1;}

Try it online!

Some people really do not like exploiting a certain compiler's undefined bahavior when using specific compiler flags. Doing so does save bytes, though.

edited Oct 3, 2017 at 22:23

answered Oct 2, 2017 at 8:41

Jonathan Frech

7,3411 gold badge21 silver badges43 bronze badges

3

\$\begingroup\$ Odd way of providing an answer IMO, but: f(n){n=n*n+1>>1;} to save a byte. \$\endgroup\$
– Tahg
Oct 2, 2017 at 9:56
1

\$\begingroup\$ @Tahg Thanks; though in what way do you find my way of providing an answer odd? \$\endgroup\$
– Jonathan Frech
Oct 2, 2017 at 10:51
2

\$\begingroup\$ I didn't think changing the input argument was a normal way of returning a value in C. \$\endgroup\$
– Tahg
Oct 2, 2017 at 13:41
2

\$\begingroup\$ @YSC Yet in the compiler's opinion it is understandable and creates an executable which works. \$\endgroup\$
– Jonathan Frech
Oct 3, 2017 at 15:10
5

\$\begingroup\$ @YSC We believe here on PPCG that, if the program works on one interpreter, it is a valid submission. It works on an online interpreter, it is therefore valid without any further remarks. \$\endgroup\$
– Conor O'Brien
Oct 3, 2017 at 22:37

| Show 5 more comments

Erik the Outgolfer · Accepted Answer · 2017-10-02 13:41:58Z

4

Brachylog, 6 bytes

^₂/₂⌉₁

Try it online!

answered Oct 2, 2017 at 13:41

Erik the Outgolfer

40.5k5 gold badges41 silver badges121 bronze badges

Add a comment |

totallyhuman · Accepted Answer · 2017-10-02 15:01:56Z

4

Python 3, 19 bytes

lambda x:-(-x*x//2)

Try it online!

lambda x:-(-x*x//2)  # Unnamed function
lambda x:            # Given input x:
            x*x      # Square
           -         # Negate
               //2   # Halve and Floor (equivalent of Ceil)
         -(       )  # Negate again (floor -> ceil)

-1 byte thanks to Mr. Xcoder

edited Oct 2, 2017 at 15:01

totallyhuman

16.3k3 gold badges31 silver badges86 bronze badges

answered Oct 2, 2017 at 12:56

hyper-neutrino♦

41.3k5 gold badges65 silver badges221 bronze badges

\$\begingroup\$ x**2 -> x*x \$\endgroup\$
– Mr. Xcoder
Oct 2, 2017 at 13:00
\$\begingroup\$ @Mr.Xcoder Facepalm thanks \$\endgroup\$
– hyper-neutrino ♦
Oct 2, 2017 at 13:06
\$\begingroup\$ What about lambda x:x*x+1>>1 ? \$\endgroup\$
– Alix Eisenhardt
Oct 2, 2017 at 15:47
\$\begingroup\$ Or lambda x:x*x+1//2 Disclaimer: I don't know this language's syntax or order of operations, so I guessed; I'm saying add 1 before you //2 instead of negating twice. \$\endgroup\$
– Dan Henderson
Oct 2, 2017 at 15:57
\$\begingroup\$ @DanHenderson You still need parentheses otherwise it's parsed as (x*x) + (1//2), so that isn't actually shorter. \$\endgroup\$
– Skyler
Oct 2, 2017 at 17:09

Add a comment |

ceilingcat · Accepted Answer · 2021-05-09 20:36:31Z

4

x86_64 machine language (Linux), 9 8 bytes

0:       97                      xchg   %eax,%edi
1:       f7 e8                   imul   %eax
3:       ff c0                   inc    %eax
5:       d1 f8                   sar    %eax
7:       c3                      retq

To Try it online!, compile and run the following C program.

#include<stdio.h>
const char *f="\x97\xf7\xe8\xff\xc0\xd1\xf8\xc3";
int main() {
  for(int i=1; i<10; i++) {
    printf("%d\n", ((int(*)())f)(i));
  }
}

edited May 9, 2021 at 20:36

answered Oct 2, 2017 at 21:13

ceilingcat

7,4672 gold badges28 silver badges30 bronze badges

\$\begingroup\$ Segmentation fault on TIO \$\endgroup\$
– l4m2
Apr 30, 2021 at 20:20
\$\begingroup\$ @l4m2 Fixed, thanks! \$\endgroup\$
– ceilingcat
May 9, 2021 at 20:36

Add a comment |

Adám · Accepted Answer · 2017-10-02 12:34:12Z

3

J, 8 bytes

Anonymous tacit prefix function.

2>.@%~*:

Try it online!

*: square

>. ceiling (round up)
@ after
2…%~ dividing by two

answered Oct 2, 2017 at 12:34

Adám

29.9k2 gold badges119 silver badges286 bronze badges

\$\begingroup\$ Alternate solutions: <.@-:@*: and *:<.@%2: \$\endgroup\$
– Conor O'Brien
Oct 3, 2017 at 22:39
2

\$\begingroup\$ @ConorO'Brien 2>.@%~*:‽ Where did I get that from? I can't read that – looks like line noise to me… \$\endgroup\$
– Adám
Oct 3, 2017 at 22:47
\$\begingroup\$ >.@-:@*: gets my vote. \$\endgroup\$
– Jonah
Oct 4, 2017 at 2:56
1

\$\begingroup\$ @Jonah If you squint, you can see a camel. \$\endgroup\$
– Adám
Oct 4, 2017 at 8:30

Add a comment |

Sherlock9 · Accepted Answer · 2017-10-02 14:16:45Z

3

Actually, 3 bytes

²½K

Try it online!

answered Oct 2, 2017 at 14:16

Sherlock9

12.2k1 gold badge29 silver badges68 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

Mathematica, 12 bytes

⌈#^2/2⌉&

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 2, 2017 at 20:50

ZaMoC

24.4k2 gold badges29 silver badges79 bronze badges

2

\$\begingroup\$ 11 bytes: ⌈#.5#⌉& \$\endgroup\$
– DELETE_ME
Oct 5, 2017 at 0:48

Add a comment |

Giuseppe · Accepted Answer · 2017-12-11 20:48:30Z

3

R, 22 21 bytes

cat((scan()^2+1)%/%2)

Try it online!

Square, increment, integer divide. Easy peasy.

Input from stdin; it can take space or newline separated input and it will compute the max wazirs for each input boardsize. Output to stdout.

-1 byte thanks to plannapus

edited Dec 11, 2017 at 20:48

answered Oct 2, 2017 at 13:09

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

\$\begingroup\$ @plannapus fixed, thank you. \$\endgroup\$
– Giuseppe
Dec 11, 2017 at 20:48
\$\begingroup\$ Is the cat necessary? if you run it as an Rscript, it will auto output to stdout. \$\endgroup\$
– qwr
Apr 30, 2021 at 21:34
\$\begingroup\$ @qwr there was an older consensus that you had to explicitly write output out; we've mostly gone away from that at this point, but this answer was following that particular rule. \$\endgroup\$
– Giuseppe
Apr 30, 2021 at 21:44

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-10-02 12:32:17Z

2

Pyth, 6 bytes

.E**.5

Try it online!

answered Oct 2, 2017 at 12:32

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Pyke, 3 bytes

Xhe

Try it here!

How?

X   - Square.
 h  - Increment.
  e - Floor halve.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 2, 2017 at 12:32

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

Add a comment |

the default. · Accepted Answer · 2017-10-02 12:48:27Z

2

C# (.NET Core), 14 12 bytes

^{-2 bytes thanks to Emigna}

n=>(n*n+1)/2

Try it online!

edited Oct 2, 2017 at 12:48

answered Oct 2, 2017 at 12:43

the default.

8,4151 gold badge34 silver badges61 bronze badges

\$\begingroup\$ Save 2 bytes \$\endgroup\$
– Emigna
Oct 2, 2017 at 12:46
2

\$\begingroup\$ n=>n*n+1>>1 (11 bytes) \$\endgroup\$
– Kevin Cruijssen
Oct 2, 2017 at 13:40
\$\begingroup\$ I have noticed the javascript answer to do the same, and this change would make our answers byte to byte equivalent. \$\endgroup\$
– the default.
Oct 2, 2017 at 13:41

Add a comment |

Xcali · Accepted Answer · 2017-10-02 12:57:10Z

2

Perl 5, 16 bytes

$_=0|$_*$_/2+.5

Try it online!

answered Oct 2, 2017 at 12:57

Xcali

13.4k2 gold badges14 silver badges37 bronze badges

\$\begingroup\$ $_=$_*$_+1>>1 14 bytes \$\endgroup\$
– Nahuel Fouilleul
Oct 4, 2017 at 8:11

Add a comment |

Cinaski · Accepted Answer · 2017-10-02 13:23:17Z

2

MATL, 5 bytes

UH/Xk

Try it online!

answered Oct 2, 2017 at 13:23

Cinaski

2,2481 gold badge7 silver badges17 bronze badges

1

\$\begingroup\$ or UQ2/k at the same byte count. \$\endgroup\$
– Giuseppe
Oct 2, 2017 at 13:31

Add a comment |

Giuseppe · Accepted Answer · 2017-10-02 14:37:15Z

2

Cubix, 11 bytes

Iu*:^\)2,O@

Heheh, :^\)

Try it online!

Expands to the following cube:

    I u
    * :
^ \ ) 2 , O @ .
. . . . . . . .
    . .
    . .

Which is the same algorithm that many use.

^Iu : read in input as int and change directions
:* : dup top of stack, multiply
\) : change direction, increment
2, : push 2, integer divide
O@ : print output as int, end program.

answered Oct 2, 2017 at 14:37

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Pyke, 3 bytes

Xhe

Try it here!

X   -   input ** 2
 h  -  ^ + 1
  e - floor_half(^)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 2, 2017 at 23:09

Blue

28.5k8 gold badges50 silver badges99 bronze badges

\$\begingroup\$ I ninja'd you by about 12 hours :-/ \$\endgroup\$
– Mr. Xcoder
Oct 3, 2017 at 11:56

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-10-03 12:00:11Z

2

Ohm v2, 3 bytes

²½ı

Try it online!

² squares, ½ halves, ı ceils.

answered Oct 3, 2017 at 12:00

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

Add a comment |

Adám · Accepted Answer · 2017-10-02 12:33:03Z

1

Jelly, 3 bytes

-1 thanks to Mr. Xcoder.

Based on my APL solution.

²HĊ

Try it online!

² Square

H Halve

Ċ Ceiling (round up)

answered Oct 2, 2017 at 12:33

Adám

29.9k2 gold badges119 silver badges286 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Japt, 4 bytes

Been sitting on these since the challenge was closed.

²Ä z

Try it

Explanation: Square, add 1, floor divide by 2

Alternative

²ÄÁ1

Try it

Explanation: Square, add 1, bit-shift right by 1.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 2, 2017 at 12:59

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

totallyhuman · Accepted Answer · 2017-10-02 15:13:01Z

1

,,,, 7 bytes

2*1+1»

Try it online!

Yay, commata works for something!

_{Fudge, I didn't implement ceiling...}

edited Oct 2, 2017 at 15:13

answered Oct 2, 2017 at 15:05

totallyhuman

16.3k3 gold badges31 silver badges86 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-10-03 12:05:31Z

1

Gaia, 3 bytes

sḥ⌉

Try it online!

s squares, ḥ halves, ⌉ ceils.

answered Oct 3, 2017 at 12:05

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

Add a comment |

caird coinheringaahin g · Accepted Answer · 2017-10-04 12:35:01Z

Commentator, 19 bytes

//{-//-}! {-#  -}<!

Try it online!

Who needs golfing languages? I've got confusing languages!

Ungolfed version:

5//{-8}//{5-}
print(10!= 5)
x={-1,3,4} # Smiley :-}
print(5<!=10)*/ # Weird comparision.

Try it online!

How does it work? I'll explain, with input 5

//                         - Take input.                           Tape: [5 0 0]
  {-//-}!                  - Square the input.                     Tape: [25 0 0]
  {-                         - Move one along the tape
    //                       - Copy the input to the tape.         Tape: [5 5 0]
      -}                     - Move one back along the tape
        !                    - Take the product of the tape.       Tape: [25 5 0]
         <space>           - Increment the tape head.              Tape: [26 5 0]
                 {-#  -}<! - Halve the tape head (floor division). Tape: [13 2 0]
                 {-          - Move one along the tape
                   #         - Set the tape head to 2.             Tape: [26 2 0]
                      -}     - Move one back along the tape
                        <!   - Reduce the tape by floor division.  Tape: [13 2 0]

Giuseppe · Accepted Answer · 2017-10-04 13:35:22Z

1

OCaml, 19 bytes

let f n=(n*n+1)/2;;

Try it online!

I'm a bit bummed the name got changed from "camels" to "wazirs" before I managed to write this, but I figured I'd post it anyway.

answered Oct 4, 2017 at 13:35

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

Add a comment |

How many Wazirs can be placed on an N×N Chessboard?

More test cases

51 Answers 51

Whitespace, 45 bytes

Oasis, 3 bytes

Prolog (SWI), 22 19 bytes

APL (Dyalog), 9 7 6 bytes

JS (ES6) / C# polyglot, 11 bytes

Test cases

05AB1E, 3 bytes

dc, 6 bytes

Python 2, 17 bytes

C (gcc), 23 18 17 bytes

C (gcc), 22 bytes (not using undefined behavior)

Brachylog, 6 bytes

Python 3, 19 bytes

x86_64 machine language (Linux), 9 8 bytes

J, 8 bytes

Actually, 3 bytes

Mathematica, 12 bytes

R, 22 21 bytes

Pyth, 6 bytes

Pyke, 3 bytes

How?

C# (.NET Core), 14 12 bytes

Perl 5, 16 bytes

MATL, 5 bytes

Cubix, 11 bytes

Pyke, 3 bytes

Ohm v2, 3 bytes

Jelly, 3 bytes

Japt, 4 bytes

Alternative

,,,, 7 bytes

Gaia, 3 bytes

Commentator, 19 bytes

OCaml, 19 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfnumberchess or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
number
chess
or ask your own question.