Weekly Challenge

Solve the challenge, share your solution and summit the ranks of our Community!
New content is available in Academy! You may need to clear your browser cache for an optimal viewing experience

Challenge #200: Sudoku Solver

Highlighted
Atom
 
Highlighted
Meteor

Solved Beginner level. 

 

Highlighted
Asteroid

Can anyone's flow solve this one?

 

 

000000190230000600000240000000000960000160070048070000001003405009008000006005800

 

 

(Mine can't! Fails with max iterations for the macro, even if set to 1000)

Highlighted
ACE Emeritus
ACE Emeritus
Highlighted
Comet

Two ways of solving the basic challenge.  Intermediate to be tackled when I have more time!

 

Spoiler
tonyp_0-1580744463704.png
Highlighted
Asteroid

@JohnJPS I guess you can't link to an individual reply on this forum. Your link just points to the first page of the topic.

 

EDIT: Ah! its the one you posted on the first page:

#
# This ianswer is taken from: https://www.kaggle.com/dmartin0409/sudoku-solver-in-r
#

library(stringr)
library(dplyr,warn.conflicts = FALSE)

sudoku <- read.Alteryx("#1", mode="data.frame")

# Define functions
# Convert the input data into a matrix
sudoku.matrix<-function(l) {
  matrix(unlist(str_extract_all(l,'.')),nrow=9,ncol=9,byrow=TRUE)
}

# Perform the search for a value of an empty square
sudoku.square<-function(m,r,c) {
  nums<-c(1:9)
  
  # Quick search row and column and 3x3 square
  rs <- 3 * ((r-1) %/% 3)
  cs <- 3 * ((c-1) %/% 3) + 1:3
  list <- sort(unique(c(m[r,],m[,c],m[rs+1,cs],m[rs+2,cs],m[rs+3,cs])))
  miss <- ! (nums %in% list)
  if (sum(miss) == 1) {   # Return the value
    return(nums[miss])
  }

  # Search square and eliminate cross values
  for (k in nums[miss]) {   # Step through each possible value
    hit<-0
    for (i in rs+1:3) {
      for (j in cs) {   # For each spot in the 3x3 square
        if (! (i == r & j == c)) {   # ...except for my spot
          if (m[i,j] == 0 & hit >= 0) {   # Find all open spots
            if (k %in% m[i,] || k %in% m[,j]) {   # This value is eliminated by criss-cross
              hit<-k   # So we found a possibile match
            }
            else {
              hit<-0-1   # Force the loop to end because this value could be in the criss-cross
            }
          }
        }
      }
    }
    if (hit > 0 ) {  # Return the value
      return(hit)
    }
  }

  # Search row and eliminate cross values
  list <- sort(unique(c(m[r,])))
  miss <- ! (nums %in% list)
  for (k in nums[miss]) {
    hit<-0
    for (j in 1:9) {   # For each column in my row
      if (! j == c) {   # ..except for my column
        if (m[r,j] == 0 & hit >=0) {   # Find all open spots
          if (k %in% m[,j]) {   # This value is eliminated
            hit<-k   # Found a possible match, keep going
          }
          else {
            hit<-0-1   # Force the loop to end
          }
        }
      } 
    }
    if (hit > 0 ) {   # Return the value
       return(hit)
    }
  }

  # Search column and eliminate cross values
  list <- sort(unique(c(m[,c])))
  miss <- ! (nums %in% list)
  for (k in nums[miss]) {
    hit<-0
    for (i in 1:9) {   # For each row in my column
      if (! i == r) {   # ..except for my row
        if (m[i,c] == 0 & hit >=0) {   # Find all open spots
          if (k %in% m[i,]) {   # This value is eliminated
            hit<-k   # Found a possible match, keep going
          }
          else {
            hit<-0-1   # Force the loop to end
          }
        }
      } 
    }
    if (hit > 0 ) {   # Return the value
      return(hit)
    }
  }
  
  # No value found
  return(NULL)
}

sudoku.solve<-function(m,detail=FALSE,format.matrix=FALSE) {
  scan<-1
  while (scan == 1) {
    scan<-0
    for (i in sample(1:9)) {
      for (j in 1:9) {
        if (m[i,j] == 0) {   # If the value is unknown "0"
          a<-sudoku.square(m,i,j)   # Search for possible values
            if (! is.null(a)) {
            scan<-1   # Force another scan
            m[i,j]=as.character(a)   # Set the value in the matrix
            if (detail) {   # Print the positio and number, and display the matrix
              print(str_c("Position ",i,"x",j," == ",a))
              print(m)
            }
          }
        }
      }
    }
  }
  if (format.matrix) {   # Return the matrix for easy display
    return(m)
  }
  else {   # Return the sting version for comparison to the data set
    r<-NULL
    for (i in 1:9) {
      for (j in 1:9) {
        r<-str_c(r,m[i,j])
      }
    }
    return(r)
  }
}

# Bulk quizes

# Convert the quizzes to a liset of matrices
q.matrix<-lapply(sudoku$quizzes,sudoku.matrix)

# Solve the quizzes and display the running time
system.time(SOL<-lapply(q.matrix,sudoku.solve))

# Sum up the matching solutions
SOL.matches<-sum(sudoku$solutions == SOL)
SOL.matches

SOL <- as.data.frame(SOL)
names(SOL) <- c("solutions")

write.Alteryx(SOL, 1)

I've coded in many languages in my career, but not R-code and I find quite cryptic! I've read through it a couple of times. but can't yet see what cleverness it is doing that my flow does not do...

Highlighted
Asteroid

@JohnJPS I found the R code in your posted solution on page 1. I replied asking a question and re-posted your R-code in my post using the 

code sample markup

but my message must have got deleted. Perhaps I broke a rule and a moderator deleted it, do you think?

Anyway, reading your R-code, I can't spot what it is doing to solve the puzzle that my iterative macro is not doing, and wanted to discuss it with you.

My iterative macro loops infinitely if it can't solve at least one more cell in the puzzle on each iteration. How does your R-code avoid that problem?

Highlighted
Asteroid

Well I got the Beginner one done, going to have to think more about the others.

 

Spoiler
Capture.PNG
Highlighted
Alteryx Certified Partner

Beginner solution.

 

Spoiler
Preview.png
Highlighted
ACE Emeritus
ACE Emeritus

@PaulRB, I can't be sure. If within the macro, making this example the first row of your macro input template, we put a sort between the final Join and the Summary tool, and sort on all columns, then look at the data at that stage: there are several rows for each row of quizzes/position/row/col/region/cell...so it's almost like at that stage, there are simply too many possibilities, such that grabbing "First" in the Summary tool is not reliable. I don't have a handy fix top of mind, but I wager some other solution thus far can do it.