C LANGUAGE TECHNOLOGY

【C言語】Nクイーン問題の解き方【総当たり法,バックトラック法】

悩んでいる人

C言語でNクイーン問題の解き方を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

Nクイーン問題の解き方

Nクイーン問題とは,チェスのエイトクイーン問題を一般化したものです.

エイトクイーンとは,チェスの盤とコマを使用したパズルの名称です,チェスの盤上に8個のクイーンを他のクイーンに取られるような場所に配置しない解法を見つけることです.

クイーンの動きは,上下左右斜めの8方向に遮る物がない限り進めます.

この性質を考慮してクイーンを配置します.

Nクイーン問題を総当たり法で解くコード

Nクイーン問題を総当たり法で解くコードは以下になります.

実行結果は以下になります.

エイトクイーン(クイーンが8個)の場合は,92の解法があることがわかります.

Nクイーン問題をバックトラック法で解くコード

Nクイーン問題をバックトラック法で解くコードは以下になります.

実行結果は以下になります.

結果は総当たり法と同様ですが,バックトラック法の方が処理時間は短いです.

まとめ

C言語でNクイーン問題の解き方を紹介しました.

具体的には,総当たり法とバックトラック法を解説しました.

Nクイーン問題の解き方の高速化を知りたいあなたは,以下の記事を読みましょう!

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , ,