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

Answer 1

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.

Answer 2

Oasis, 3 bytes

k>v

Try it online!

square - increment - integer halve

Answer 3

Prolog (SWI), 22 19 bytes

Saved 3 bytes thanks to Kevin Cruijssen

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

Try it online!

Answer 4

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)

Answer 5

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))

Answer 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!

Answer 7

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.

Answer 8

05AB1E, 3 bytes

Straight implementation of the formula given by A000982

n;î

Try it online!

Explanation

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

Answer 9

Python 2, 17 bytes

1 byte thanks to @ovs.

lambda x:x*x+1>>1

Try it online!

Answer 10

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

Answer 11

Brachylog, 6 bytes

^₂/₂⌉₁

Try it online!

Answer 12

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));
  }
}

Answer 13

J, 8 bytes

Anonymous tacit prefix function.

2>.@%~*:

Try it online!

*: square

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

Answer 14

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

Answer 15

Actually, 3 bytes

²½K

Try it online!

Answer 16

Pyth, 6 bytes

.E**.5

Try it online!

Answer 17

Pyke, 3 bytes

Xhe

Try it here!

How?

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

Answer 18

C# (.NET Core), 14 12 bytes

^{-2 bytes thanks to Emigna}

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

Try it online!

Answer 19

Perl 5, 16 bytes

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

Try it online!

Answer 20

MATL, 5 bytes

UH/Xk

Try it online!

Answer 21

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.

Answer 22

Mathematica, 12 bytes

⌈#^2/2⌉&

Answer 23

Pyke, 3 bytes

Xhe

Try it here!

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

Answer 24

Ohm v2, 3 bytes

²½ı

Try it online!

² squares, ½ halves, ı ceils.

Answer 25

Jelly, 3 bytes

-1 thanks to Mr. Xcoder.

Based on my APL solution.

²HĊ

Try it online!

² Square

H Halve

Ċ Ceiling (round up)

Answer 26

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.

Answer 27

Cubically, 12 bytes

$:*FDF'+8/0%

Try it online!

Personally I don't see any point with using language features newer than the challenge to get less bytes, because you mostly compete with yourself (almost always there are at most one answer/language/challenge), but I still updated, by MDXF's suggestion. : defaults to :7 is a good idea anyway.

---

Explanation:

$:*7FDF'+8/0%
$                  Read input as number.
 :                 Set notepad value (face 6) to input.
  *                Multiply notepad value with itself.
   FDF'            Scramble the cube so face 8 value will be 1 
                   (unsolved) and face 0 value will be 2.
       +8          Add 1 (face 8 value) to notepad value.
         /0        Divide notepad value by 2 (face 0 value),
                   get integer part.
           %       Output notepad value as number.

This program works because ceil(n^2 / 2) == floor((n^2 + 1) / 2).

Answer 28

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]

Answer 29

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.

Answer 30

TI-Basic, 7 bytes

round(Ans²/2,0

Alternatively (8 bytes):

int(Ans²/2+.5

Answer 31

///, 35 bytes

/I///,*/+,//+/I//**,/,A//*/A//,//,I

Try it online!

Takes input in unary using symbol *, and output in unary using symbol A. This is allowed for some specific languages, including /// (meta)

Because there is no way to take input in ///, input should be hardcoded:

/I/«put input here»//,*/+,//+/I//**,/,A//*/A//,//,I

for input = 4.

---

Explanation: (before reading, you need to know that the only syntax of /// are /pattern/replacement/, which replace every occurence of pattern by replacement; and \ for escaping; other characters is printed to output)

For n=4:

/I/****//,*/+,//+/I//**,/,A//*/A//,//,I    Start program.
/I/****/                                   Replace all `I` in the program by the input.

/,*/+,//+/****//**,/,A//*/A//,//,****      Remaining part of the program.
/,*/+,/                                    Use the `,` as a scanner, scan through `*` after it and convert to `+`.
       /+/****//**,/,A//*/A//,//++++,      Note that only `*` in the second group is affected.
       /+/****/                            Replace all `+` (which is just created) by `n` asterisks (from the first `I` group)

/**,/,A//*/A//,//****************,         Now at the last of the program before the `,` there are `n²` asterisks.
/**,/,A/                                   Scan the `,` to the left to perform division by 2:
                                           replace each `**` by a `A` as the scanner `,` pass through.
/*/A//,//,AAAAAAAA                         Remaining program.
/*/A/                                      If there is any `*` remaining (if `n²` is odd), replace it with `A`.
     /,//                                  Remove the scanner `,`.
          AAAAAAAA                         Output the result.

Answer 32

Husk, 3 bytes

⌈½□

Try it online!

The code is pretty much self-explanatory:

• □ Square.

• ½ Halve.

• ⌈ Ceil.

Answer 33

Java 8, 20 11 bytes

i->i*i+1>>1

Answer 34

Convex, 5 bytes

{²½¯}

Try it online!

This is the same as CJam's {2#2./m]}.

Answer 35

,,,, 7 bytes

2*1+1»

Try it online!

Yay, commata works for something!

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

Answer 36

Neim, 3 bytes

ᛦ>ᚺ

Try it online!

Answer 37

Gaia, 3 bytes

sḥ⌉

Try it online!

s squares, ḥ halves, ⌉ ceils.

Answer 38

RProgN 2, 6 bytes

2^1+2÷

Try it online!

Answer 39

PocoLithp, 21 bytes

(#(N)(/(+(* N N)1)2))

Anonymous lambda taking argument N. Can be used in either of the following ways:

• ((#(N)(/(+(* N N)1)2))7) - call with argument 7

• (begin (define camel (#(N)(/(+(* N N)1)2))) (camel 7))

Enter either of these lines into the REPL to test.

This language was created a few weeks ago, and the most recent changes a day ago are just bug fixes.

Answer 40

ARBLE, 11 bytes

ceil(n^2/2)

Try it online!

Answer 41

Bash, 18 bytes

echo $[$1*$1+1>>1]

Try it online

Answer 42

Add++, 13 bytes

+?
^2
+1
/2
O

Try it online!

Looks like I got here too late (again)

Answer 43

ASP, 13 bytes

a((x*x+1)/2).

Call with clingo -c x=7 or by putting #const x=7. in source.

Answer 44

Haskell, 18 bytes

w n=ceiling(n*n/2)

Run as:

main = print $ w n

Where n is the input number.

Answer 45

FALSE, 6 bytes

$*1+2/

Explanation:

• $ duplicate top of stack
• * multiply
• 1 push 1
• + add
• 2 push 2
• / divide

False only has 32-bit integers.

Answer 46

x86 machine code, 6 bytes

Takes its argument in eax register, returns also there.

f7 e0   mul eax
40      inc eax
d1 e8   shr eax,1
c3      ret

Answer 47

Excel, 15 bytes

=ROUND(A1^2/2,)

Because we are dividing by 2, we can safely replace CEILING with ROUND, saving 3 bytes.

=CEILING(A1^2/2,1)

Answer 48

JavaScript (ES8), 16 bytes

x=>(h=x*x/2)+h%1
x=>                  // arrow function
   (h=x*x/2)         // dictionarying
            +h%1     // Math.ceil function