Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Need help with generator

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
BigPapa

Joined: 12 Jan 2009
Posts: 14
:

Items
PostPosted: Mon Jan 12, 2009 9:22 pm    Post subject: Need help with generator Reply with quote

Hi,
I thought I would come up with building a Sudoku puzzle game, using Macromedia Director 11. I have pretty good background in programming with Lingo, but I have hardly any experience programming Sudoku. However, I did do some research here through the forums. What I understand so far is first I need a generator, then a solver and a level of difficulty. As for a generator I have spent pretty much the weekend reading many of the threads here, and from what I get is there are several ways of building a generator. However, I am a little lost considering that many of the threads that I have read either only discuss the steps people have tried doing, or they show one main function but not include what the functions who are being called inside the main function do. For example, for my first attempt, I tried doing a recursive function method, which came from this thread "Need Help with my first Sudoku generator."

When I first tried it, I realized that it created empty cells, which meant it did not do any backtracking. I tried building a backtracking method which would take away the previous cell and try another number. In addition, when it could not do an entire region, then it would delete region and try it again. However, I am having no luck with it, and all it is doing is making my code messier. Worse yet, I over-wrote my clean code, so I hope you can still understand it.


Code:

property pSpriteLink
property pSudoku
property pDeadLocks
property funcCall --dont forget to get rid of this when you know the generateSuduko function works

on beginSprite me
  pSpriteLink = [[1, 11, 21], [31, 41, 51], [61, 71, 81]]
  funcCall = 0
 
  initializeSprites()
  initializeSudoku()
 
  repeat with boardRow = 1 to 3
    repeat with boardCol = 1 to 3
      if boardRow = 3 and boardCol = 3 then
        nothing
      end if
     
      if not generateSudoku(boardRow, boardCol, 1, 1) then
        displayBoard()
        updateStage()
        if boardCol = 1 then
          boardCol = 3
          boardRow = boardRow - 1
        else
          boardCol = boardCol - 1
        end if
        undoRegion(boardRow, boardCol)
        if boardCol = 1 then
          boardCol = 3
          boardRow = boardRow - 1
        else
          boardCol = boardCol - 1
        end if
      end if
    end repeat
  end repeat
 
  displayBoard()
end beginSprite

on initializeSprites
 
  loopX = 0
  loopY = 0
 
  repeat with z = 1 to pSpriteLink.count
    repeat with spriteList in pSpriteLink[z]
      repeat with y = 0 to 2
        repeat with x = 0 to 2
          currSprite = spriteList + x + (y * 3)
          sprite(currSprite).locH = 118 + (24 * x) + loopX
          sprite(currSprite).locV = 83 + (24 * y) + loopY
          sprite(currSprite).member = member("block")
        end repeat
      end repeat
      loopX = loopX + (24 * 3) + 10
    end repeat
    loopX = 0
    loopY = loopY + (24 * 3) + 10
  end repeat
end initializeSprites

on initializeSudoku
  defaultBoard = [[0, 0, 0],[0, 0, 0], [0, 0, 0]]
  tempLocks = [[[],[],[]], [[], [], []], [[],[],[]]]
  pSudoku = []
  pDeadLocks = []
 
  repeat with boardRow = 1 to 3
    pSudoku.add([])
    pDeadLocks.add([])
    tempLocks = []
   
    repeat with boardCol = 1 to 3
      --pSudoku[boardRow].add([])
     
      pSudoku[boardRow].add(defaultBoard.duplicate())
      --pDeadLocks[boardRow].add(tempLocks.duplicate())
     
      repeat with row = 1 to 3
        tempLocks.add([])
       
        repeat with col = 1 to 3
          tempLocks[row].add([])
        end repeat
      end repeat
     
      pDeadLocks[boardRow].add(tempLocks)
      put pDeadLocks[boardRow][boardCol][1][1]
     
    end repeat
  end repeat
 
end initializeSudoku

on generateSudoku boardRow, boardCol, row, col
  ranValues = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  --funcCall = funcCall + 1
 
--  if boardRow = 3 and boardCol = 3 then
--    across = []
--    downward = []
--   
--    repeat with tempBoardCol = 1 to 3
--      repeat with x = 1 to 3
--        across.add(pSudoku[boardRow][tempBoardCol][row][x])
--      end repeat
--    end repeat
--   
--    repeat with tempBoardRow = 1 to 3
--      repeat with y = 1 to 3
--        downward.add(pSudoku[tempBoardRow][boardCol][y][col])
--      end repeat
--    end repeat
--   
--  end if
 
  if funcCall = 5 then
    return true
  end if
 
  if row = 4 then --3 and col = 3 then
    return true
  end if
 
  shuffleRanValues(ranValues)
  deadLocks = []
 
  repeat with index = 1 to 9
    --    if pDeadLocks[boardRow][boardCol][row][col].count then
    --      if pDeadLocks[boardRow][boardCol][row][col].getPos(ranValues[index]) then
    --        next repeat
    --      end if
    --    end if
   
    if deadLocks.count then
      if deadLocks.getPos(ranValues[index]) then
        next repeat
      end if
    end if
   
    if validateBoard(boardRow, boardCol, row, col, ranValues[index]) then
      pSudoku[boardRow][boardCol][row][col] = ranValues[index]
      tempCol = col
      tempRow = row
     
      if (tempCol + 1) = 4 then
        tempCol = 1
        tempRow = tempRow + 1
      else
        tempCol = tempCol + 1
      end if
     
      if generateSudoku(boardRow, boardCol, tempRow, tempCol) then
        return true
      else
        --pDeadLocks[boardRow][boardCol][row][col].add(ranValues[index])
        deadLocks.add(ranValues[index])
      end if
    end if
  end repeat
 
  if col = 1 then
    if row > 1 then
      pSudoku[boardRow][boardCol][row - 1][3] = 0
    else
      if boardCol > 1 then
        pSudoku[boardRow][boardCol - 1][3][3] = 0
      else if boardRow > 1 then
        pSudoku[boardRow - 1][3][3][3] = 0
      else
        alert("error in solving puzzle. The program cannot continue")
        abort()
      end if
    end if
  else
    pSudoku[boardRow][boardCol][row][col - 1] = 0
  end if
 
  return false
end generateSudoku

on shuffleRanValues ranValues
  repeat with x = 1 to 9
    r = x + random(9) mod (9 - x)
    tCard = ranValues[x]
    ranValues[x] = ranValues[r]
    ranValues[r] = tCard
  end repeat
end shuffleRanValues

on validateBoard boardRow, boardCol, row, col, value
  --checkValue = pSudoku[boardRow][boardCol][row][col]
 
  --check 3x3 block
  repeat with index = 1 to 3
    checkList = pSudoku[boardRow][boardCol][index]
    if getPos(checkList, value) then --checkValue) then
      return false
    end if
  end repeat
 
  --check current row across
  repeat with index = 1 to 3
    checkList = pSudoku[boardRow][index][row]
    if getPos(checkList, value) then
      return false
    end if
  end repeat
 
  -- check current column down
  repeat with y = 1 to 3
    repeat with x = 1 to 3
      checkValue = pSudoku[y][boardCol][x][col]
      if checkValue = value then
        return false
      end if
    end repeat
  end repeat
 
  return true
end validateBoard

on undoRegion boardRow, boardCol
  repeat with row = 1 to 3
    repeat with col = 1 to 3
      pSudoku[boardRow][boardCol][row][col] = 0
    end repeat
  end repeat
end undoRegion

on displayBoard
  repeat with boardRow = 1 to 3
    repeat with boardCol = 1 to 3
      repeat with row = 0 to 2
        repeat with col = 0 to 2
          spriteNum = pSpriteLink[boardRow][boardCol] + col  + (row * 3)
          if pSudoku[boardRow][boardCol][row + 1][col + 1] = 0 then
            sprite(spriteNum).member = member(24)
          else
            sprite(spriteNum).member = member(pSudoku[boardRow][boardCol][row + 1][col + 1])
          end if
        end repeat
      end repeat
    end repeat
  end repeat
end displayBoard

on exitFrame me
  go to the frame
end


so my question is, I wanted to know if someone could help me out with how I could do the backtracking.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron