Without a doubt: 〜に違いない

〜に違いない expresses a strong conviction drawn from clues: “without a doubt, it must be…”. The speaker has no proof but is deeply convinced. It's a rather written phrasing, common in stories and detective novels.

• 部屋の電気がついている。彼はもう帰っているに違いない。へやのでんきがついている。かれはもうかえっているにちがいない。His light is on. He must be home already.
• あんなに練習したのだから、きっと合格するに違いない。あんなにれんしゅうしたのだから、きっとごうかくするにちがいない。After practising that much, he's sure to pass.
• この足跡は、犯人のものに違いない。このあしあとは、はんにんのものにちがいない。These footprints must be the culprit's.

違う means “to differ, to be wrong”. So 〜に違いない reads “there's no mistake that…”: the speaker has observed clues and draws a conclusion they're convinced of — English “must”, “without a doubt”, “I'm sure”.

It isn't a proven fact: it's an inner certainty. It often comes with きっと (surely).

• かばんがない。電車の中に忘れたに違いない。かばんがない。でんしゃのなかにわすれたにちがいない。My bag's gone. I must have left it on the train.

Verbs and い-adjectives: plain form (present or past) + に違いない. Nouns and な-adjectives: directly, without だ. Politely: に違いありません. You also find 〜に違いなかった (in a past narrative).

• あんなに大きな家だから、家賃は高いに違いない。あんなにおおきないえだから、やちんはたかいにちがいない。A house that big — the rent must be high.
• これは本物の茶わんに違いありません。これはほんもののちゃわんにちがいありません。This tea bowl is undoubtedly genuine.

かもしれない: maybe (50%). だろう / でしょう: probably. はずだ: logically, from known facts (“it should be”). に違いない: a strong, personal conviction drawn from clues. に決まっている: subjective certainty, spoken and peremptory (“obviously!”).

はずだ rests on reasoning (“he took the 9 o'clock train, so he should have arrived”). に違いない rests rather on an intuition fed by clues (“the light's on, so he must be in”).

• 九時の電車に乗ったから、もう着いているはずだ。くじのでんしゃにのったから、もうついているはずだ。He took the 9 o'clock train, so he should be there by now.
• 顔が真っ赤だ。お酒を飲んだに違いない。かおがまっかだ。おさけをのんだにちがいない。His face is bright red. He must have been drinking.