Advertisement
vencinachev

TKT

Sep 6th, 2019
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.10 KB | None | 0 0
  1. using System;
  2.  
  3. namespace TheKnightTour
  4. {
  5.     class Program
  6.     {
  7.         static int N;
  8.  
  9.         static bool IsSafe(int[,] board, int row, int col)
  10.         {
  11.             if (row < 0 || col < 0 || row >= N || col >= N)
  12.             {
  13.                 return false;
  14.             }
  15.             if (board[row, col] != 0)
  16.             {
  17.                 return false;
  18.             }
  19.             return true;
  20.         }
  21.  
  22.         static void PrintSolution(int[,] board)
  23.         {
  24.             for (int i = 0; i < N; i++)
  25.             {
  26.                 for (int j = 0; j < N; j++)
  27.                 {
  28.                     Console.Write("{0} ", board[i, j]);
  29.                 }
  30.                 Console.WriteLine();
  31.             }
  32.         }
  33.  
  34.         static bool SolveKnightTour(int[,] board, int x, int y, int movei, int[] xMove, int[] yMove)
  35.         {
  36.             if ((movei - 1) == N*N)
  37.             {
  38.                 return true;
  39.             }
  40.             for (int k = 0; k < 8; k++)
  41.             {
  42.                 int nextX = x + xMove[k];
  43.                 int nextY = y + yMove[k];
  44.                 if (IsSafe(board, nextX, nextY))
  45.                 {
  46.                     board[nextX, nextY] = movei;
  47.                     //PrintSolution(board);
  48.                     //Console.WriteLine();
  49.                     if (SolveKnightTour(board, nextX, nextY, movei + 1, xMove, yMove))
  50.                     {
  51.                         return true;
  52.                     }
  53.                     else
  54.                     {
  55.                         board[nextX, nextY] = 0;
  56.                     }
  57.                 }
  58.             }
  59.             return false;
  60.         }
  61.         static void Main(string[] args)
  62.         {
  63.             N = 6;
  64.             int[,] matrix = new int[N, N];
  65.             int[] xm = { -1, -1, 1, 1, -2, -2, 2, 2};
  66.             int[] ym = { -2, 2, 2, -2, 1, -1, 1, -1};
  67.             if (!SolveKnightTour(matrix, 0, 0, 1, xm, ym))
  68.             {
  69.                 Console.WriteLine("No solution!");
  70.             }
  71.             else
  72.             {
  73.                 PrintSolution(matrix);
  74.             }
  75.         }
  76.     }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement