Thread: C++ chess-like task

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    12

    C++ chess-like task

    So I got a task from our countries programming team to do this but I have no idea how I could go at it (I'm not looking for a solution in code but just how I could be able to do this in C++)

    So you have a square chess field which is N x N fields big (get as input) and you have a rook placed on X1 and Y1 coords. You need to get it to X2 Y2 coords and calculate the cost of the cheapest way (if no way possible output is -1) with the costs of Cx (cost of moving 1 square in x-axis) and Cy (cost of moving 1 square in y-axis) then you get an input for M which is amount of obstacles. Followed by M lines of Xi Yi coords of the obstacles. You have to find the cheapest way from X1 Y1 to X2 Y2. The rook can only move left/right up/down and can't jump over obstacles.

    Any help would be appreciated. The only problem I am having is how to count the obstacles in the equation.

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    So you have a square chess field which is N x N fields big (get as input)
    why on earth would you be required to input the size of a chess board? Unless there are variations involved?

    The rook can only move left/right up/down and can't jump over obstacles.
    again, that is implicit in the game. Do you just need a move evaluation or is there a set problem like say knights tour to code? Are there any other pieces involved in this problem?

    Show your work - dont post the entire thing if it is not relevant, start with just the function / construct you are having difficulties with
    Last edited by rogster001; 05-12-2013 at 11:02 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  3. #3
    Registered User
    Join Date
    May 2013
    Posts
    12
    There are variations involved. I know how I would calculate without the obstacles but I don't know how to take the obstacles into the equation or try another path. I just need a general idea how to do it not in code.

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Hmm, just a quick thought, but what about an algorithm like this (whether or not this is efficient depends on exactly what you need to do with it - if you were going to do multiple trials with the same obstacles and end points it could actually be the most efficient):

    * Create an array equal to the board size to store the minimum distance from each point to the target point.
    * Initialize these all to a sentinel value (a very large number - greater than any possible calculated distance)
    * Initialize the locations of the obstacles to another sentinel value (e.g. -1)
    * Create a queue to store locations that you need to process.
    * Start the algorithm by processing the X2 Y2 location (cost here is 0), and enqueue the four adjacent squares (unless they are out of bounds or obstacles).

    * While the queue is not empty, do the following:
    1. Remove the location from the queue
    2. Check this location against its four adjacent squares (unless out of bounds/obstacles) to determine what the minimal distance is from this new square. Save this minimum calculated amount.
    3. If any adjacent locations have minimal distances that are greater than this location's minimum distance plus the cost of moving from that square to this one, queue that location for recalculation. (This should automatically catch any squares that haven't yet been calculated since those have very large distances). You can optimize this by making sure no location is currently in the queue more than once.

    * When the queue is empty, any remaining unprocessed squares have no path to the target location.

    Essentially, the third step of the loop recalculates distances if a shorter path was found later (because the original calculation was made before all adjacent squares were calculated, this will sometimes happen).
    Last edited by Cat; 05-12-2013 at 11:47 AM.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    That's rather advanced for a first look at the problem.
    Here is a list of suggestions:
    - At (x, y), for every possible move check:
    -- Can the piece move there from (x, y)?
    -- Is there an obstacle in the way?
    - If no to both questions, move the piece, document the cost and repeat recursively.
    - If yes to at least one question, fail and backtrack.

    How to implement this is up to you.
    Try tackling each problem in part, then piecing it together. For example, make a function that checks if a piece can move to (x2, y2) from (x1, y1).
    This is a well known backtracking way of handling it.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Some people may have over-thought this one. It's no different whether there is barely a single obstacle on the board, or the board is almost entirely filled.

    This is a simple optimal-pathfinding problem, to which the A* algorithm is perfectly suited. I would not consider any other approach.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    If you know graph theory, sure. If you don't have dijkstra at hand, though, it may be a little more difficult.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    iMalc identified that well, A* is not that hard and is a great programming project.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  9. #9
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Quote Originally Posted by iMalc View Post
    Some people may have over-thought this one. It's no different whether there is barely a single obstacle on the board, or the board is almost entirely filled.

    This is a simple optimal-pathfinding problem, to which the A* algorithm is perfectly suited. I would not consider any other approach.
    Hmm, I hadn't come across that algorithm before - thanks for sharing that! One more algorithm to file away for future reference
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help to do the big task
    By Steve Cao in forum Linux Programming
    Replies: 1
    Last Post: 07-16-2010, 02:01 PM
  2. Replies: 2
    Last Post: 12-31-2007, 11:40 AM
  3. chess
    By lilhawk2892 in forum C++ Programming
    Replies: 11
    Last Post: 12-11-2005, 11:17 AM
  4. Chess AI
    By thedumbmutt in forum Game Programming
    Replies: 1
    Last Post: 12-11-2002, 11:39 PM
  5. my grandfather's chess algorithm can beat your grandfather's chess algorithm...
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 22
    Last Post: 08-17-2001, 06:52 PM