Thread: Sliding Numbers Puzzle

  1. #1
    Senor Member nomi's Avatar
    Join Date
    Jan 2004
    Posts
    129

    Sliding Numbers Puzzle

    Hey,

    I hope everyone is familiar with the number sliding puzzles. The numbers 1-N*N are scrabbled where N(dimension of grid) ranges from 4-10. The user needs to place the numbers in order after they have been scrambled. The number of empty spaces can range from 1 to N/2.

    This project has certain requirements:

    - Display the scrambled numbers.
    - Allow the user to solve.
    and
    - Show the solution.

    I have been working on this for sometime now but I can't seem to come up with a working algorithm that would solve the grid in a reasonable amount of time. Two empty spaces may be assumed since the grid may become unsolvable with only one empty space.

    A push in the right direction would be greatly appreciated.

    Thx,
    Nomi

  2. #2
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,164
    I'd have the user input either the tile-position or the tile-value that is to move, your choice. Tile-position would be the easiest. Then look for adjacent empty spots and if only 1, move the tile. If 2 or more, ask the user for the new tile-position.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  3. #3
    Senor Member nomi's Avatar
    Join Date
    Jan 2004
    Posts
    129
    Quote Originally Posted by WaltP
    I'd have the user input either the tile-position or the tile-value that is to move, your choice. Tile-position would be the easiest. Then look for adjacent empty spots and if only 1, move the tile. If 2 or more, ask the user for the new tile-position.
    Well allowing the user to play the game isnt that hard. What I am really having trouble with is showing the solution. It needs to be step by step instructions to solve the board in a minimal amount of time.

  4. #4
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,164
    Calculate every move from the current board layout. Store them in an array with a pointer the the parent (current) layout. Move to the next layout in the array.

    Check for final layout as you calculate each new board.

    This will take time and memory. The more empty spaces, the more memory.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Well, do you want ONE solution, or the BEST solution? The algorithm and complexity is inherently different.

    In any case: Wikipedia, which also links to a page containing a pretty good algorithm and a Java implementation. Hope you can figure it out from there.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  6. #6
    Senor Member nomi's Avatar
    Join Date
    Jan 2004
    Posts
    129
    Quote Originally Posted by jafet
    Well, do you want ONE solution, or the BEST solution? The algorithm and complexity is inherently different.

    In any case: Wikipedia, which also links to a page containing a pretty good algorithm and a Java implementation. Hope you can figure it out from there.
    Im actually looking for the most efficient solution, but any solution would work right now. Thanks for the links. Im reading through them now.

  7. #7
    Senor Member nomi's Avatar
    Join Date
    Jan 2004
    Posts
    129
    I have finalized and cleaned up my code so everything but AI solve works. I cant seem to pen down the algorithm to solve it though. I sort of understand what needs to be done, but the complexity of the coding is scaring the crap out of me and I am making no significant progress.

  8. #8
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Oh, that Java one was comparatively EASY -- simple recursion algorithm

    The BEST (shortest) solution is NP-Hard (read: will take a long long time to calculate), and I don't think the user will actually notice the difference between a "good" solution and the best one.

    If you don't think you're up to the task, I think it's best to put all that code aside for now and go for something simpler first, just to get the hang of solving stuff.

    Like this
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  9. #9
    Senor Member nomi's Avatar
    Join Date
    Jan 2004
    Posts
    129
    Hey thanks a lot, I think I finally understand whats happening. I have a rough algorithm written down, I just need to code it now and see how it turns out.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 06-06-2008, 05:26 PM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Crossword Puzzle Program
    By Loctan in forum C++ Programming
    Replies: 2
    Last Post: 07-31-2006, 11:08 PM
  4. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 11:15 AM
  5. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 06:38 PM